[图片] 什么是 Trie 树 Trie 树,也叫“字典树”,是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。 [图片] 图示就表示 5 个字符串,radd、ram、rthe、rtfink、rgood,根节点不包含任何信息。每个节点表示一个字符串中的字符,从根节 ..

多模式字符串匹配之 Trie 树

什么是 Trie 树

Trie 树,也叫“字典树”,是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。
trie 树图示.jpg
图示就表示 5 个字符串,radd、ram、rthe、rtfink、rgood,根节点不包含任何信息。每个节点表示一个字符串中的字符,从根节点到最后节点的一条路径表示一个字符串。Trie 树的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起。

如何实现一个 Trie 树

如何存储

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

假设我们的字符串中只有从 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 树来找到公共前缀。

  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    2558 引用 • 7953 回帖 • 828 关注
  • 字符串
    28 引用 • 57 回帖
  • 数据结构
    62 引用 • 105 回帖 • 3 关注
回帖
请输入回帖内容...