Trie树

Trie树，即字典树，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。

Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质：

  1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

Trie树的应用：

  1. 字符串检索：精确查找或者前缀查找
  2. 最长公共前缀
  3. 排序 等等。一个例子是检索文本中的违规词汇。

Trie树Java的简单代码，实现了简单的词汇过滤功能，内部是基于HashMap的。

import java.util.HashMap;
import java.util.Map;

/**
 * Created by zmc on 2017/6/27.
 */
public class NewTrieNode {

    private char key;

    private Map<Character, NewTrieNode> nextNodes;

    private boolean end;

    private int count;

    public NewTrieNode(char key) {
        this.key = key;
        nextNodes = new HashMap();
        end = false;
        count = 0;
    }



    public void insertWord(String s) {

        NewTrieNode node = this;

        for ( char ch : s.toCharArray() ) {
            if (node.nextNodes.get(ch) == null) {
                NewTrieNode newNode = new NewTrieNode(ch);
                node.nextNodes.put(ch, newNode);
            }

            node = node.nextNodes.get(ch);
            node.count++;

        }

        node.end = true;
    }



    public String guolv(String s) {

        int start = 0;
        int end = start + 1;

        char[] charArray = s.toCharArray();


        for (; start < charArray.length; start++) {

            NewTrieNode node = this;
            if ( this.nextNodes.get( charArray[start] ) != null ) {
                node = node.nextNodes.get(charArray[start]);

                for (end = start + 1; end < charArray.length; end++) {
                    if (node.nextNodes.containsKey(charArray[end])) {
                        node = node.nextNodes.get(charArray[end]);
                    }

                    if ( node.end ) {
                        for (int i = start; i <= end; i++)
                            charArray[i] = '*';
                        start = end + 1;
                        break;
                    }
                }
            }
        }


        return new String( charArray );

    }

    
}

从这个例子中还知道了Java中char类型是可以存中文字符的。Java中char的长度是2字节，可以支持UTF16的字符，包括中文。

Written on June 27, 2017