中文分词引擎 java 实现 — 正向最大、逆向最大、双向最大匹配法

正向最大匹配法

</article>

分词目标：

在词典中进行扫描，尽可能地选择与词典中最长单词匹配的词作为目标分词，然后进行下一次匹配。

算法流程：

假设词典中最长的单词为 5 个（MAX_LENGTH），那么最大匹配的起始子串字数也为 5 个

（1）扫描字典，测试读入的子串是否在字典中

（2）如果存在，则从输入中删除掉该子串，重新按照规则取子串，重复（1）

（3）如果不存在于字典中，则从右向左减少子串长度，重复（1）

分词实例：

比如说输入 “北京大学生前来应聘”，

第一轮：取子串 “北京大学生”，正向取词，如果匹配失败，每次去掉匹配字段最后面的一个字
- “北京大学生”，扫描 5 字词典，没有匹配，子串长度减 1 变为“北京大学”
- “北京大学”，扫描 4 字词典，有匹配，输出“北京大学”，输入变为“生前来应聘”
第二轮：取子串“生前来应聘”
- “生前来应聘”，扫描 5 字词典，没有匹配，子串长度减 1 变为“生前来应”
- “生前来应”，扫描 4 字词典，没有匹配，子串长度减 1 变为“生前来”
- “生前来”，扫描 3 字词典，没有匹配，子串长度减 1 变为“生前”
- “生前”，扫描 2 字词典，有匹配，输出“生前”，输入变为“来应聘””
第三轮：取子串“来应聘”
- “来应聘”，扫描 3 字词典，没有匹配，子串长度减 1 变为“来应”
- “来应”，扫描 2 字词典，没有匹配，子串长度减 1 变为“来”
- 颗粒度最小为 1，直接输出“来”，输入变为“应聘”
第四轮：取子串“应聘”
- “应聘”，扫描 2 字词典，有匹配，输出“应聘”，输入变为“”
输入长度为0，扫描终止

正向匹配法最终的切分结果为：”北京大学 / 生前 / 来 / 应聘”

正向匹配法实现代码如下：

public List<String> leftMax(String str) {

        List<String> results = new ArrayList<String>();
        String input = str;

        while( input.length() > 0 ) {

            String subSeq;
            // 每次取小于或者等于最大字典长度的子串进行匹配
            if( input.length() < MAX_LENGTH) 
                subSeq = input;
            else
                subSeq = input.substring(0, MAX_LENGTH);

            while( subSeq.length() > 0 ) {
                // 如果字典中含有该子串或者子串颗粒度为1，子串匹配成功
                if( dictionary.contains(subSeq) || subSeq.length() == 1) {
                    results.add(subSeq);
                    // 输入中从前向后去掉已经匹配的子串
                    input = input.substring(subSeq.length());
                    break;      // 退出循环，进行下一次匹配
                } else {
                    // 去掉匹配字段最后面的一个字
                    subSeq = subSeq.substring(0, subSeq.length() - 1);
                }   
            }

        }
        return results;
    }
 
  1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30

逆向最大匹配法

分词目标：

在词典中进行扫描，尽可能地选择与词典中最长单词匹配的词作为目标分词，然后进行下一次匹配。

在实践中，逆向最大匹配算法性能优于正向最大匹配算法。

算法流程：

假设词典中最长的单词为 5 个（MAX_LENGTH），那么最大匹配的起始子串字数也为 5 个

（1）扫描字典，测试读入的子串是否在字典中

（2）如果存在，则从输入中删除掉该子串，重新按照规则取子串，重复（1）

（3）如果不存在于字典中，则从左向右减少子串长度，重复（1）

分词实例：

比如说输入 “北京大学生前来应聘”，

第一轮：取子串 “生前来应聘”，逆向取词，如果匹配失败，每次去掉匹配字段最前面的一个字
- “生前来应聘”，扫描 5 字词典，没有匹配，字串长度减 1 变为“前来应聘”
- “前来应聘”，扫描 4 字词典，没有匹配，字串长度减 1 变为“来应聘”
- “来应聘”，扫描 3 字词典，没有匹配，字串长度减 1 变为“应聘”
- “应聘”，扫描 2 字词典，有匹配，输出“应聘”，输入变为“大学生前来”
第二轮：取子串“大学生前来”
- “大学生前来”，扫描 5 字词典，没有匹配，字串长度减 1 变为“学生前来”
- “学生前来”，扫描 4 字词典，没有匹配，字串长度减 1 变为“生前来”
- “生前来”，扫描 3 字词典，没有匹配，字串长度减 1 变为“前来”
- “前来”，扫描 2 字词典，有匹配，输出“前来”，输入变为“北京大学生”
第三轮：取子串“北京大学生”
- “北京大学生”，扫描 5 字词典，没有匹配，字串长度减 1 变为“京大学生”
- “京大学生”，扫描 4 字词典，没有匹配，字串长度减 1 变为“大学生”
- “大学生”，扫描 3 字词典，有匹配，输出“大学生”，输入变为“北京”
第四轮：取子串“北京”
- “北京”，扫描 2 字词典，有匹配，输出“北京”，输入变为“”
输入长度为0，扫描终止

逆向匹配法最终的切分结果为：”北京/ 大学生/ 前来 / 应聘”

逆向匹配法实现如下：

public List<String> rightMax(String str) {
        // 采用堆栈处理结果，后进先出
        Stack<String> store=new Stack<String>();
        List<String> results = new ArrayList<String>();
        String input = str;

        while( input.length() > 0 ) {

            String subSeq;
            // 每次取小于或者等于最大字典长度的子串进行匹配
            if( input.length() < MAX_LENGTH)
                subSeq = input;
            else 
                subSeq = input.substring(input.length() - MAX_LENGTH);

            while( subSeq.length() > 0 ) {
                // 如果字典中含有该子串或者子串颗粒度为1，子串匹配成功
                if( dictionary.contains(subSeq) || subSeq.length() == 1) {
                    store.add(subSeq);
                    // 输入中从后向前去掉已经匹配的子串
                    input = input.substring(0, input.length() - subSeq.length());
                    break;
                } else {
                    // 去掉匹配字段最前面的一个字
                    subSeq = subSeq.substring(1);
                }
            }
        }
        // 输出结果
        int size = store.size();
        for( int i = 0; i < size; i ++) {
            results.add(store.pop());
        }

        return results;
    }
 
  1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36

双向最大匹配法

分词目标：

将正向最大匹配算法和逆向最大匹配算法进行比较，从而确定正确的分词方法。

算法流程：

比较正向最大匹配和逆向最大匹配结果
如果分词数量结果不同，那么取分词数量较少的那个
如果分词数量结果相同
- 分词结果相同，可以返回任何一个
- 分词结果不同，返回单字数比较少的那个

分词实例：

就上例来看，

正向匹配最终切分结果为：北京大学 / 生前 / 来 / 应聘，分词数量为 4，单字数为 1

逆向匹配最终切分结果为：”北京/ 大学生/ 前来 / 应聘，分词数量为 4，单字数为 0

逆向匹配单字数少，因此返回逆向匹配的结果。

双向最大匹配法实现如下：

public List<String> segment() {
        List<String> fmm = this.leftMax();
        List<String> bmm = this.rightMax();

        // 如果分词的结果不同，返回长度较小的
        if( fmm.size() != bmm.size()) {
            if ( fmm.size() > bmm.size())
                return bmm;
            else 
                return bmm;
        }
        // 如果分词的词数相同
        else {
            int fmmSingle = 0, bmmSingle = 0;
            boolean isEqual = true;
            for( int i = 0; i < bmm.size(); i ++) {
                if( !fmm.get(i).equals(bmm.get(i))) {
                    isEqual = false;
                }
                if( fmm.get(i).length() == 1)
                    fmmSingle ++;
                if( bmm.get(i).length() == 1)
                    bmmSingle ++;
            }
            // 如果正向、逆向匹配结果完全相等，返回任意结果
            if ( isEqual ) {
                return fmm;
            // 否则，返回单字数少的匹配方式
            } else if ( fmmSingle > bmmSingle)      
                return bmm;
            else 
                return fmm;     
        }

    }
 
  1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35

载入字典和自定义添加词

这里的字典文件采用的是

http://download.csdn.net/download/yuanlulu/2380141

载入字典和自定义添加词实现如下：

private static Set<String> dictionary;  
    // 初始化字典，采用 hashset 存储
    public void getDictionary() {
        dictionary = new HashSet<String>();  
        String dicpath = "data/worddict2.txt";  
        String line = null;  

            BufferedReader br;
            try {
                // 按照 gbk 编码读入文件
                br = new BufferedReader(new InputStreamReader(new FileInputStream(dicpath),"gbk"));
                try {
                    while(((line = br.readLine())!=null)) {
                        // 按照空格切分，只读取第二部分
                        String[] str = line.split("\\s+");
                        line = str[1];
                        dictionary.add(line);   
                    }
                    br.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            } catch (UnsupportedEncodingException | FileNotFoundException e) {
                e.printStackTrace();
            }       
    }
    // 自定义添加词汇
    public void addWord(String str) {
        dictionary.add(str);    
    }
 
  1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30

歧义句测试

可以看到效果还不错，最大匹配法的效果还是取决于字典的质量。

整体代码如下：

package mm;
import java.io.BufferedReader;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.io.UnsupportedEncodingException; 
public class MMSegment {

    private String request;
    private int MAX_LENGTH = 5;
    private static Set<String> dictionary;  

    public void getDictionary() {
        dictionary = new HashSet<String>();  
        String dicpath = "data/worddict2.txt";  
        String line = null;  

            BufferedReader br;
            try {
                br = new BufferedReader(new InputStreamReader(new FileInputStream(dicpath),"gbk"));
                try {
                    while(((line = br.readLine())!=null)) {
                        String[] str = line.split("\\s+");
                        line = str[1];
                        dictionary.add(line);   
                    }
                    br.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            } catch (UnsupportedEncodingException | FileNotFoundException e) {
                e.printStackTrace();
            }       
    }

    public void addWord(String str) {
        dictionary.add(str);    
    }

    public List<String> leftMax() {

        List<String> results = new ArrayList<String>();
        String input = request;

        while( input.length() > 0 ) {

            String subSeq;
            if( input.length() < MAX_LENGTH) 
                subSeq = input;
            else
                subSeq = input.substring(0, MAX_LENGTH);

            while( subSeq.length() > 0 ) {
                if( dictionary.contains(subSeq) || subSeq.length() == 1) {
                    results.add(subSeq);
                    input = input.substring(subSeq.length());
                    break;  
                } else {
                    subSeq = subSeq.substring(0, subSeq.length() - 1);
                }   
            }

        }
        return results;
    }
    public List<String> rightMax() {

        Stack<String> store=new Stack<String>();
        List<String> results = new ArrayList<String>();
        String input = request;

        while( input.length() > 0 ) {

            String subSeq;
            if( input.length() < MAX_LENGTH)
                subSeq = input;
            else 
                subSeq = input.substring(input.length() - MAX_LENGTH);

            while( subSeq.length() > 0 ) {
                if( dictionary.contains(subSeq) || subSeq.length() == 1) {
                    store.add(subSeq);
                    input = input.substring(0, input.length() - subSeq.length());
                    break;
                } else {
                    subSeq = subSeq.substring(1);
                }
            }
        }
        int size = store.size();
        for( int i = 0; i < size; i ++) {
            results.add(store.pop());
        }

        return results;
    }

    public List<String> segment() {
        List<String> fmm = this.leftMax();
        List<String> bmm = this.rightMax();

        if( fmm.size() != bmm.size()) {
            if ( fmm.size() > bmm.size())
                return bmm;
            else 
                return fmm;
        }

        else {
            int fmmSingle = 0, bmmSingle = 0;
            boolean isEqual = true;
            for( int i = 0; i < bmm.size(); i ++) {
                if( !fmm.get(i).equals(bmm.get(i))) {
                    isEqual = false;
                }
                if( fmm.get(i).length() == 1)
                    fmmSingle ++;
                if( bmm.get(i).length() == 1)
                    bmmSingle ++;
            }

            if ( isEqual ) {
                return fmm;
            } else if ( fmmSingle > bmmSingle)      
                return bmm;
            else 
                return fmm; 
        }
    }

    public void test(String str) {
        request = str;
        System.out.println(this.segment());
    }

    public static void main(String[] args) {
        MMSegment f = new MMSegment();
        f.getDictionary();
        f.test("研究生命科学");
        f.test("研究生命令本科生");
        f.test("我从马上下来");
        f.test("北京大学生喝进口红酒");
        f.test("美军中将竟公然说");
        f.test("阿美首脑会议将讨论巴以和平等问题");
        f.addWord("巴以和平");
        System.out.println("---------------------------");
        System.out.println("向字典中添加'巴以和平'后");
        f.test("阿美首脑会议将讨论巴以和平等问题");
        f.test("我不想吃东西");
    }

}

 
  1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
  
118
  
119
  
120
  
121
  
122
  
123
  
124
  
125
  
126
  
127
  
128
  
129
  
130
  
131
  
132
  
133
  
134
  
135
  
136
  
137
  
138
  
139
  
140
  
141
  
142
  
143
  
144
  
145
  
146
  
147
  
148
  
149
  
150
  
151
  
152
  
153
  
154
  
155
  
156
  
157
  
158
  
159
  
160

参考资料

[1] http://blog.csdn.net/worldwindjp/article/details/18085725

[2] http://blog.csdn.net/hu948162999/article/details/43608107

[3] http://blog.csdn.net/xiaoyeyopulei/article/details/25194021

[4] http://blog.csdn.net/chenlei0630/article/details/40710441