在使用基于詞典的分詞方法的時(shí)候粘室，如果我們解決了下面4個(gè)問題：
1榄檬、如何把一句話中所有的詞找出來呢？只要詞典中有就一定要找出來衔统。
2鹿榜、如何利用1中找出來的詞組合成完整的句子？組合成的句子要和原句一樣锦爵。
3舱殿、如何保證2中組合而成的句子包含了所有可能的詞序？
4险掀、如何從所有可能的詞序中選擇最完美的一種作為最終的分詞結(jié)果沪袭？
?字符串全切分，就是計(jì)算每種候選分詞方式的概率樟氢，并從中取概率最大的那種冈绊。如”wheninthecourse”可能的分詞方式有2的n-1次方中組合。
[‘w’, ‘henin’, ‘the’, ‘course’]
[‘wh’, ‘en’, ‘in’, ‘the’, ‘course’]
[‘whe’, ‘n’, ‘in’, ‘the’, ‘course’]
...
[‘wheninthecour’, ‘se’]
[‘wheninthecours’, ‘e’]
[‘wheninthecourse’]埠啃。
詳細(xì)可見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.
本文是對(duì)該書中python實(shí)現(xiàn)的所有可能的詞序的一個(gè)移植。
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)
算法基本思想根據(jù)字符串前i個(gè)及剩余的len-i個(gè)進(jìn)行遞歸碴开，每次取遞歸中的第一個(gè)元素后進(jìn)行重新遞歸毅该，直至剩余的字符串為空。
首先定義一個(gè)二元組
first存儲(chǔ)字符串String.substring(0,i+1),
second存儲(chǔ)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;
}
}
字符串切分函數(shù)眶掌，進(jìn)行字符串遍歷所有可能的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;
}
基本就是以上了巴碗，表達(dá)有限畏线，java也是最近初學(xué)。
如果有什么問題請(qǐng)指出良价，表示感謝寝殴。
