在使用基于词典的分词方法的时候，如果我们解决了下面4个问题：
1、如何把一句话中所有的词找出来呢？只要词典中有就一定要找出来。
2、如何利用1中找出来的词组合成完整的句子？组合成的句子要和原句一样。
3、如何保证2中组合而成的句子包含了所有可能的词序？
4、如何从所有可能的词序中选择最完美的一种作为最终的分词结果？
�字符串全切分，就是计算每种候选分词方式的概率，并从中取概率最大的那种。如”wheninthecourse”可能的分词方式有2的n-1次方中组合。
[‘w’, ‘henin’, ‘the’, ‘course’]
[‘wh’, ‘en’, ‘in’, ‘the’, ‘course’]
[‘whe’, ‘n’, ‘in’, ‘the’, ‘course’]
...
[‘wheninthecour’, ‘se’]
[‘wheninthecours’, ‘e’]
[‘wheninthecourse’]。
详细可见Beautiful Data第十四章。
Chapter 14, Natural Language Corpus Data, by Peter Norvig, takes the reader through some evocative exercises with a trillion-word corpus of natural language data pulled down from across the Web.
本文是对该书中python实现的所有可能的词序的一个移植。
def segment(text):
"""Return a list of words that is the best segmentation of text."""
if not text :return[]
candidates=([first]+ segment(rem) for first,rem in splits(text))
returnmax(candidates,key=Pwords)
算法基本思想根据字符串前i个及剩余的len-i个进行递归，每次取递归中的第一个元素后进行重新递归，直至剩余的字符串为空。
首先定义一个二元组
first存储字符串String.substring(0,i+1),
second存储String.substring(i+1,len)。
private class WordTuple<A,B> {
final String first;
final String second;
WordTuple(String a, String b) {
this.first = a;
this.second = b;
}
}
字符串切分函数，进行字符串遍历所有可能的WordTuple。
private ArrayList<TwoTuple<A,B>> spilts(String text){
ArrayList<TwoTuple<String,String>> arrayList = new ArrayList<>();
for (int i = 0; i < text.length(); i++){
TwoTuple<String,String> tuple = new WordTuple<>(text.substring(0,i+1),text.substring(i+1,text.length()));
arrayList.add(i,tuple);
}
return arrayList;
}
private ArrayList<ArrayList<String>> _segment(String text){
if (text == null){
return new ArrayList<>();
}
ArrayList<ArrayList<String>> arrayListAll = new ArrayList<>();
for (WordTuple<String,String> tuple : spilts(text)) {
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add(tuple.first);
ArrayList<ArrayList<String>> tmpArray = _segment(tuple.second);
if (tmpArray.size() == 0){
arrayListAll.add(arrayList);
}else{
for (ArrayList<String> tmp : tmpArray){
ArrayList<String> tmpArrayList = new ArrayList<>();
tmpArrayList.addAll(arrayList);
tmpArrayList.addAll(tmp);
arrayListAll.add(tmpArrayList);
}
}
}
return arrayListAll;
}
private ArrayList<ArrayList<String>> segment(String text){
ArrayList<ArrayList<String>> arrayLists = new ArrayList<>();
for (WordTuple<String,String> tuple : spilts(text)) {
ArrayList<ArrayList<String>> tmpArray = _segment(tuple.second);
if (tmpArray.size()==0){
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add(tuple.first);
arrayList.add(tuple.second);
arrayLists.add(arrayList);
}
for (ArrayList<String> tmp : tmpArray){
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add(tuple.first);
arrayList.addAll(tmp);
arrayLists.add(arrayList);
}
}
return arrayLists;
}
基本就是以上了，表达有限，java也是最近初学。
如果有什么问题请指出，表示感谢。
