多模式字符串匹配之 Trie 树

什么是 Trie 树

Trie 树，也叫“字典树”，是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

图示就表示 5 个字符串，radd、ram、rthe、rtfink、rgood，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到最后节点的一条路径表示一个字符串。Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

如何实现一个 Trie 树

如何存储

Trie 树是一棵多叉树，一个节点有多个子节点，这时可以借助散列表的思想，通过一个下标与字符一一映射的数组来存储子节点的指针。

假设我们的字符串中只有从 a 到 z 这 26 个小写字母，我们在数组中下标为 0 的位置，存储指向子节点 a 的指针，下标为 1 的位置存储指向子节点 b 的指针，以此类推，下标为 25 的位置，存储的是指向的子节点 z 的指针。如果某个字符的子节点不存在，对应的下标的位置存储 null。
数组是一个 Node 数组，根据索引就可以获取到子节点

代码实现

public class TrieNode {
    public char data;
    public TrieNode[] children = new TrieNode[26];
   // 标记字符是不是最后一个字符
    public boolean isEndingChar = false;
    public TrieNode(char data){
        this.data = data;
    }
}

public class Trie {
    private TrieNode root = new TrieNode('/');

    public void insert(char[] text) {
        TrieNode p = root;
        for (char c : text) {
            // 确定字符该存的位置
            int index = c - 'a';
            if (p.children[index] == null) {
                TrieNode node = new TrieNode(c);
                p.children[index] = node;
            }
            // 如果已经存在节点了，就指向下一个节点
            p = p.children[index];
        }
        p.isEndingChar = true;
    }
    
    public boolean find(char[] pattern){
        TrieNode p = root;
        for (char c : pattern) {
            int index = c - 'a';
            // 如果一条路径都到达叶子节点了，还没有匹配到，就说明不存在这个pattern
            if (p.children[index] == null) {
                return false;
            }
            p = p.children[index];
        }
        // 如果是尾部字符，就说明匹配到了，如果不是说明pattern只是一个前缀
        return p.isEndingChar;
    }
    
}

复杂度分析

时间复杂度

构建 Trie 树的过程需要扫描所有的字符，需要 O(n)的时间复杂度，n 表示所有的字符数，如果要查询的字符串的长度是 m，那么只需要 m 次比较就能确定是否存在这个字符串，需要 O(m)的时间复杂度。

空间复杂度

Trie 树用数组来存储一个节点的子节点的指针，在上面的例子中，假设的字符范围知识小写字符，如果还包含大写字母、数字、符号等等，那数组的空间就需要更大了，而且在存储节点的时候，每个数组并不能充分利用，只是存储了不多几个，有很大一部分的浪费。所以 Trie 树是比较耗内存的，用的是一种空间换时间的思路。
这个问题的解决思路是可以用其他数据结构代替数组，但是会降低查找的效率，后面再说用什么数据结构替换。

Trie 树与其他动态数据结构比较

Trie 树在处理字符串匹配的时候，是对字符集有要求的，不然是无法发挥它的高效查找的优势：

• 字符串中包含的字符集不能太大。我们前面讲到，如果字符集太大，那存储空间可能就会浪费很多。即便可以优化，但也要付出牺牲查询、插入效率的代价。
• 要求字符串的前缀重合比较多，不然空间消耗会变大很多。
• 如果要用 Trie 树解决问题，那我们就要自己从零开始实现一个 Trie 树，还要保证没有 bug，这个在工程上是将简单问题复杂化，除非必须，一般不建议这样做。
• 我们知道，通过指针串起来的数据块是不连续的，而 Trie 树中用到了指针，所以，对缓存并不友好，性能上会打个折扣

针对在一组字符串中查找字符串的问题，我们在工程中，更倾向于用散列表或者红黑树。因为这两种数据结构，我们都不需要自己去实现，直接利用编程语言中提供的现成类库就行了。Trie 树比较适合的是查找前缀匹配的字符串，类似于搜索引擎的关键词提示功能、自动输入补全，都可以根据 trie 树来找到公共前缀。