字典树

• 需求： 判断文本中是否包含某个词， 以及词频
• 问题：中文分词实际使用的词典往往在几十万个词以上，逐个匹配成本太大。
• 方案：

• Hash散列表 + 链表解决冲突：查找高效， 但是不适合分词的最长匹配查找方式
• 字典树： 分词器初始化时加载已有词典， 有标准Trie树(二叉树) 和 三叉Trie树

标准Trie树

三叉Trie数

/**
 * Created by fkissx on 18/7/30.
 */

public class TSTTree{
    public final class TSTNode {
        public String data = null;
        protected TSTNode loNode;
        protected TSTNode hiNode;
        protected TSTNode eqNode;
        protected char splitchar;
        protected Boolean endFlag;
        protected TSTNode(){

        }
        protected TSTNode(char splitchar) {
            this.splitchar = splitchar;
            this.endFlag = false;
        }

        public String toString() {
            return "splitchar:" + splitchar;
        }
    }

    private TSTNode root;
    TSTTree() {this.root = new TSTNode();}

    public TSTNode getNode(String key, TSTNode startNode) {
        if (key == null) {
            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(currentNode == null)
                return null;
            charComp = cmpChar - currentNode.splitchar;
            if(charComp == 0) {
                charIndex++;
                if (charIndex == len) {
                    return currentNode;
                } else {
                    cmpChar = key.charAt(charIndex);
                }
                currentNode = currentNode.eqNode;
            } else if(charComp < 0)
                currentNode = currentNode.loNode;
            else if(charComp > 0)
                currentNode = currentNode.hiNode;
        }
    }

    public TSTNode addWord(String key){
        TSTNode currentNode = root;
        int charIndex = 0;
        while(true){
            int charComp = key.charAt(charIndex) - currentNode.splitchar;
            if(charComp == 0){  // 相等
                charIndex ++;
                if(charIndex == key.length()){
                    currentNode.endFlag = true; // 设置标志位
                    return currentNode;  // 存在
                }
                if(currentNode.eqNode == null){  // 不存在
                    currentNode.eqNode = new TSTNode(key.charAt(charIndex));
                }

                currentNode = currentNode.eqNode;
            }

            else if(charComp < 0){
                if(currentNode.loNode == null){  // 左节点为空, 将左边节点初始化
                    currentNode.loNode = new TSTNode(key.charAt(charIndex));
                }
                currentNode = currentNode.loNode;
            }
            else if(charComp > 0) {
                if(currentNode.hiNode == null){
                    currentNode.hiNode = new TSTNode(key.charAt(charIndex));
                }
                currentNode = currentNode.hiNode;
            }
        }
    }

    public TSTNode getRoot(){
        return this.root;
    }


    public static void main(String[] args) {
        TSTTree tree = new TSTTree();
        String[] strs = {
                "中国人",
                "中国",
                "外国",
                "中国功夫",
                "外国月亮",
        };

        for (String str : strs) {
            tree.addWord(str);
        }

        System.out.println(tree.getNode("中国功夫", tree.root).endFlag);
    }
}

参考： 自然语言处理原理与技术实现