Trie树

字符串匹配系列文章链接：

后缀数组 (Jul 18, 2021)
朴素 (Jul 18, 2021)
AC自动机 (Jul 18, 2021)
KMP (Jul 18, 2021)
Trie树 (Jul 18, 2021)

什么是Trie树

Trie树，也叫“字典树”。它是一种专门处理字符串匹配的数据结构，Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

how, hi, her, hello, so, see这6个字符串的Trie树如下所示：

                  (/)
                /     \
               /       \
              /         \
             /           \
           (h)           (s)
          / | \         /   \
        (e)[i](o)     (e)   [o]
       / |      \     /
     (l)[r]      [w][e]
    /
   (l)
  /         其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到[]节点的一条路径表示一个字符串
[o]         (注意：[]节点并不都是叶子节点)

如何用代码实现一个Trie树

Trie树主要有两个操作：

将字符串集合构造成 Trie 树。
在 Trie 树中查询一个字符串。

如何存储一个 Trie 树？

Trie 树是一个多叉树
- 多叉树的存储：借助散列表的思想，通过一个下标与字符一一映射的数组，来存储子节点的指针。
- 假设我们的字符串中只有从 a 到 z 这 26 个小写字母，对应的数组下标为 0 到 25。
```
type TrieNode struct {
    data      byte
    children  [26]*TrieNode
}
```

type TrieNode struct {
    data      byte
    children  [26]*TrieNode
    isEndingChar bool
}
type Trie struct {
    root    *TrieNode
}

func NewTrie() *Trie {
    return &Trie{ root: &TrieNode{ data: '/' } }
}

func (t *Trie) insert(text []byte) {
    p := t.root
    for i:=0; i<len(text); i++ {
        index := text[i] - 'a'
        if p.children[index] == nil {
            newNode := &TrieNode{data: text[i]}
            p.children[index] = newNode
        }
        p = p.children[index]
    }
    p.isEndingChar = true
}

func (t *Trie) find(pattern []byte) bool {
    p := t.root
    for i:=0; i<len(pattern); i++ {
        index := pattern[i] - 'a'
        if p.children[index] == nil {
            return false // 不存在pattern
        }
        p = p.children[index]
    }
    if !p.isEndingChar {  // 不能完全匹配，只是前缀
        return false
    } else {  // 找到pattern
        return true
    }
}

时间复杂度：

构建trie树的时间复杂度：O(n)，n表示所有字符串的长度和
查询字符串的时间复杂度：O(n)，n表示要查找的字符串的长度

如何解决Trie树耗内存的问题？

稍微牺牲一点查询的效率，将每个节点中的数组换成其他数据结构，来存储一个节点的子节点指针。

有序数组:
- 数组中的指针按照所指向的子节点中的字符的大小顺序排列。查询的时候，我们可以通过二分查找的方法，快速查找到某个字符应该匹配的子节点的指针
- 但是，在往 Trie 树中插入一个字符串的时候，我们为了维护数组中数据的有序性，就会稍微慢了点。
跳表
散列表
红黑树

缩点优化就是对只有一个子节点的节点，而且此节点不是一个串的结束节点(结束节点并不都是叶子节点)，可以将此节点与子节点合并

Trie树对要处理的字符串有极其严苛的要求。

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

所以，在工程上，针对在一组字符串中查找字符串的问题，我们在工程中，更倾向于用散列表或者红黑树。

Trie 树不适合精确匹配查找
Trie 树比较适合的是查找前缀匹配的字符串

如何实现搜索引擎的搜索关键词提示功能？

我们假设关键词库由用户的热门搜索关键词组成。我们将这个词库构建成一个 Trie 树。当用户输入其中某个单词的时候，把这个词作为一个前缀子串在 Trie 树中匹配。为了讲解方便，我们假设词库里只有 hello、her、hi、how、so、see 这 6 个关键词。当用户输入了字母 h 的时候，我们就把以 h 为前缀的 hello、her、hi、how 展示在搜索提示框内。当用户继续键入字母 e 的时候，我们就把以 he 为前缀的 hello、her 展示在搜索提示框内。这就是搜索关键词提示的最基本的算法原理。

上面的解决办法遇到下面几个问题：

对于更加复杂的中文来说，词库中的数据又该如何构建成 Trie 树呢？
如果词库中有很多关键词，在搜索提示的时候，用户输入关键词，作为前缀在 Trie 树中可以匹配的关键词也有很多，如何选择展示哪些内容呢？
像 Google 这样的搜索引擎，用户单词拼写错误的情况下，Google 还是可以使用正确的拼写来做关键词提示，这个又是怎么做到的呢？

专题: 字符串匹配

本文发表于 2021-07-18，最后修改于 2021-07-18。

本站永久域名「 jiavvc.top 」，也可搜索「后浪笔记一零二四」找到我。