三叉Trie树实现正向最大长度匹配分词

在一个三叉搜索树（Ternary Search Trie）中，每一个节点包括一个字符，但和数字搜索树不同，三叉搜索树只有三个指针：一个指向左边的树，一个指向右边的树，还有一个向下，指向单词的下一个数据单元。三叉搜索树是二叉搜索树和数字搜索树的混合体。它有和数字搜索树差不多的速度，但是和二叉搜索树一样只需要相对较少的内存空间。
　　树的平衡取决于单词的读入顺序。如果按排序后的顺序插入，则生成方式最不平衡。通过选择一个排序后数据单元集合的中间值，并把它作为开始节点，就可以创建一个平衡的三叉树。
　　下面用三叉搜索树来构建字典树以及进行最大正向长度匹配分词：

• TSTNode.java

public final class TSTNode {
    /**节点的值data可以存储词原文和词性、词频等相关的信息*/
    public String data=null;
    //左中右节点
    protected TSTNode lNode;
    protected TSTNode mNode;
    protected TSTNode rNode;
    
    protected char splitchar;//本节点表示的字符
    
    protected TSTNode(char splitchar){
        this.splitchar=splitchar;
    }
    public String toString(){
        return "splitchar:"+splitchar;
    }
    /**
     * 查找的过程是：输入一个词，返回这个词对应的TSTNode对象，如果该词不在词典中，则返回空。
     * 查找词典的过程中，从树的根节点匹配Key，从前往后匹配Key*/
    protected TSTNode getNode(String key,TSTNode startNode){
        if(null==key){
            return null;
        }
        int len=key.length();
        if(len==0)
            return null;
        TSTNode currentNode=startNode;//匹配过程中当前节点的位置
        int charIndex=0;
        char cmpChar=key.charAt(charIndex);
        int charComp;
        while(true){
            if(null==currentNode){
                return null;
            }
            charComp=cmpChar-currentNode.splitchar;
            if(charComp==0){//equal
                charIndex++;
                if(charIndex==len){//找到                 
                    return currentNode;
                }
                else
                    cmpChar=key.charAt(charIndex);

                currentNode=currentNode.mNode;
            }else if(charComp<0){//小于
                currentNode=currentNode.lNode;
            }else {
                currentNode=currentNode.rNode;
            }
        }
    }
    
    /**三叉树的创建过程，就是在Trie树上创建和单词对应的节点
     * 下面方法实现的是向词典树中加入一个单词的过程*/
     TSTNode addWord(String key,TSTNode root){
        TSTNode currentNode=root;//从树的根节点开始查找
        int charIndex=0;//从词的开头匹配
        while(true){
            //比较词的当前字符与节点的当前字符
            int charComp=key.charAt(charIndex)-currentNode.splitchar;
            if(charComp==0){
                charIndex++;
                if(charIndex==key.length()){
                  currentNode.data=key;//将当前的词存到最后一个节点的data中
                    return currentNode;
                }
                //如果不存在直接后继节点
                if(currentNode.mNode==null){
                    currentNode.mNode=new TSTNode(key.charAt(charIndex));
                }
                currentNode=currentNode.mNode;
            }else if (charComp<0) {
                if(currentNode.lNode==null){
                    currentNode.lNode=new TSTNode(key.charAt(charIndex));
                }
                currentNode=currentNode.lNode;
            }else {
                if(currentNode.rNode==null){
                    currentNode.rNode=new TSTNode(key.charAt(charIndex));
                }
                currentNode=currentNode.rNode;
            }
        }
    }
    
     /**Trie树搜索最长匹配单词的方法
      * @param key 待匹配字符串
      * @param offset 匹配开始位置*/
     public String matchLong(String key,int offset,TSTNode root){
         String ret=null;
         if(key==null||root==null||"".equals(key)){
             return ret;
         }
         TSTNode currentNode=root;
         int charIndex=offset;
         while(true){
             if(currentNode==null){
                 return ret;
             }
             int charComp=key.charAt(charIndex)-currentNode.splitchar;
             if(charComp==0){
                 charIndex++;
                 if(currentNode.data!=null){
                     ret=currentNode.data;//候选最长匹配词
                 }
                 if(charIndex==key.length()){
                     return ret;
                 }
                 currentNode=currentNode.mNode;
             }else if (charComp<0) {
                currentNode=currentNode.lNode;
            }else {
                currentNode=currentNode.rNode;
            }
         }
     }
     /**正向最大长度分词*/
     public void wordSegment(String sentence,TSTNode root){
         int senLen=sentence.length();
         int i=0;
         while(i<senLen){
             String word=root.matchLong(sentence, i, root);
             if(word!=null){
                 //下次匹配点在这个词之后
                 i+=word.length();
                 //如果词在词典中，则就直接打印出来
                 System.out.print(word+" ");
             }
             else{
                 //如果在词典中没找到，则按单字切分
                 word=sentence.substring(i, i+1);
                 //打印一个字
                 System.out.print(word);
                 i++;//下次匹配点在这个字符之后
             }
         }
     }
     
}

• TSNTreeTest.java
  例如，Trie树的字典中包含如下词语：

大 大学 大学生 活动 生活 中 中心 心

（下面直接按照上面字典的顺序添加，所以得到的可能不是平衡Trie树）

public class TSNTreeTest {

    public static void main(String[] args) {
        TSTNode root=new TSTNode(' ');
        root.addWord("大", root);
        root.addWord("大学", root);
        root.addWord("大学生", root);
        root.addWord("活动", root);
        root.addWord("生活", root);
        root.addWord("中", root);
        root.addWord("中心", root);
        root.addWord("心", root);
        
        String sentence="大学生活动中心";
        String ret=root.matchLong(sentence, 0, root);
        System.out.println(sentence+" match:"+ret);
        root.wordSegment(sentence, root);
    }
}

得到的结果是：

第一行是输入“大学生活动中心”时，返回的最长匹配词
第二行是根据正向最长匹配分词的结果

参考资料：
[1] Trie树和Ternary Search树的学习总结:
　　http://www.cnblogs.com/rush/archive/2012/12/30/2839996.html