上一篇文章中介绍了正向最大匹配。能够看到有时候效果不是非常好。这里在介绍一种逆向最大匹配的算法。
词典和匹配的字符串都和上一篇文章同样
仅仅是本算法是从后到前搜索字符串。然后找到最长的匹配结果输出。
上代码
package com;
import java.util.ArrayList;
import java.util.List;
public class Segmentation1 {
private List<String> dictionary = new ArrayList<String>();
private String request = "北京大学生前来应聘";
public void setDictionary() {
dictionary.add("北京");
dictionary.add("北京大学");
dictionary.add("大学");
dictionary.add("大学生");
dictionary.add("生前");
dictionary.add("前来");
dictionary.add("应聘");
}
private boolean isIn(String s, List<String> list) {
for(int i=0; i<list.size(); i++) {
if(s.equals(list.get(i))) return true;
}
return false;
}
public String rightMax() {
String response = "";
String s = "";
for(int i=request.length()-1; i>=0; i--) {
s = request.charAt(i) + s;
if(isIn(s, dictionary) && tailCount(s, dictionary)==1) {
response = (s + "/") + response;
s = "";
} else if(tailCount(s, dictionary) > 0) {
} else {
response = (s + "/") + response;
s = "";
}
}
return response;
}
private int tailCount(String s, List<String> list) {
int count = 0;
for(int i=0; i<list.size(); i++) {
if((s.length()<=list.get(i).length()) && (s.equals(list.get(i).substring(list.get(i).length()-s.length(), list.get(i).length())))) count ++;
}
return count;
}
public static void main(String[] args) {
Segmentation1 seg = new Segmentation1();
seg.setDictionary();
String response2 = seg.rightMax();
System.out.println(response2);
}
}
能够看到执行结果是:北京/大学生/前来/应聘/
分词效果非常好