基于java的字符串所有可能的分词遍历

在使用基于词典的分词方法的时候，如果我们解决了下面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也是最近初学。
如果有什么问题请指出，表示感谢。