<正向/反向>最大匹配算法（Java）

算法描述（正向）：

　　给定最大词长n，待分词文本str，指针f=0，词典dic文档

　　1 取子串sub=str(f,f+n)

　　2 如果(遍历dic，有匹配sub)　　f++;

　　3 否则　　n--;

　　4 注意：边界判定、没有找到词的情况

算法举例分析（正向）：

　　你有个要分词的文本“你毁了我容忍傻逼的能力”，你给出能最大接受的词长为6

（注意，6为6字节(byte)，而一个汉字为2字节，你可能注意到下面的程序里我把6除以2了，因为在java里，char也是两字节的，所以它能装一个汉字，也可以装一个字母或符号。）

　　现在指针指向第一个字，第一次取到的子串是“你毁了”，在词典中找有没有这个词，没有，那我们把词长变成4，即两个字，第二次取到的子串是“你毁”，再找，也没有，第三次取到的子串是“你”，在词典中能找到了，这时指针加一，指向“毁”字，词长恢复6，这就是一轮查找了。

　　。。。

　　跳过几步，假如现在指针指向了“容”字，第一次取到“容忍傻”，第二次取到“容忍”，“容忍”在词典能找到，这个时候，指针需要移动两位指向“傻”字，同理，若你取到三个字的词而且这个词能在词典中找到时，指针也要移三位，即 f+n

反向最大匹配跟正向原理一样，只是指针从最后一位开始向前移动。

 1 package Algorithm;
 2 
 3 import common.InitializeCorpus;
 4 import java.io.IOException;
 5 import java.util.Stack;
 6 
 7 /**
 8  *
 9  * @author 小振xzh 20140317
10  * 正向/反向最大匹配分词算法
11  */
12 public final class MaximumMatching {
13     public String result;        //结果
14     private int posIndex;        //指针
15     private int len;             //长度
16     private int maxLen;          //最大长度
17     private boolean re;          //false正向，true反向
18     
19     //---正向---
20     public String forwardMaximumMatching(int maxLength, String str) throws IOException{
21         result = "";
22         posIndex = 0;
23         len = maxLength;
24         maxLen = len;
25         re = false;
26         MM(str, maxLen, 0);
27         return result;
28     }
29     
30     //---反向---
31     public String reversedMaximumMatching(int maxLength, String str) throws IOException{
32         result = "";
33         posIndex = 0;
34         len = maxLength;
35         maxLen = len;
36         re = true;
37         MM((new StringBuilder(str)).reverse().toString(), maxLen, 0);  //源串反转
38         return result;
39     }
40 
41     public void MM(String source,int len,int frompos) throws IOException{
42         if(posIndex>source.length()-1){
43             return;
44         }
45         if(source.length()-frompos<len){
46             len = source.length()-frompos;
47         }
48         String tmp = source.substring(frompos, frompos+len);  //获得子串
49         
50         if(!re){
51             if(InitializeCorpus.ChineseDicList.contains(tmp)){  //这是另一个类里定义的静态ArrayList，里面存的是词
52                 result += tmp+"/ ";
53                 posIndex += len;
54                 len = maxLen;  //重置长度
55                 MM(source, len, posIndex);
56             }else if(len>1){
57                 len -= 1;
58                 MM(source, len, posIndex);
59             }else{
60                 result += "字典中没有‘"+tmp+"’字/ ";
61                 posIndex += 1;
62                 len = maxLen;
63                 MM(source, len, posIndex);
64             }
65         }else{
66             tmp = (new StringBuilder(tmp)).reverse().toString();
67             Stack<String> sk = new Stack<String>();  //反向使用stack存储词语
68             if(InitializeCorpus.ChineseDicList.contains(tmp)){
69                 sk.push(tmp+"/ ");
70                 posIndex += len;
71                 len = maxLen;
72                 MM(source, len, posIndex);
73             }else if(len>1){
74                 len -= 1;
75                 MM(source, len, posIndex);
76             }else{
77                 sk.push("字典中没有’"+tmp+"'字/ ");
78                 posIndex += 1;
79                 len = maxLen;
80                 MM(source, len, posIndex);
81             }
82             while(!sk.isEmpty()){
83                 result += sk.pop();
84             }
85         }
86     }
87 }

------------------2014年03月22日

关于算法的效率改进的一个地方，就是在构造函数中，把词典读到一个数组里，空间换时间，这样速度可以提高大约10倍？

-------------------2014年04月15日

修改了算法的代码 | 代码整洁之道