数据结构与算法之美学习笔记：35 | Trie树：如何实现搜索引擎的搜索关键词提示功能？

前言

本节课程思维导图

搜索引擎的搜索关键词提示功能我想你应该不陌生吧为了方便快速输入当你在搜索引擎的搜索框中输入要搜索的文字的某一部分的时候搜索引擎就会自动弹出下拉框里面是各种关键词提示。你是否思考过它是怎么实现的呢它底层使用的是哪种数据结构和算法呢其底层最基本的原理就是今天要讲的这种数据结构Trie 树。

什么是“Trie 树”

Trie 树也叫“字典树”。顾名思义它是一个树形结构。它是一种专门处理字符串匹配的数据结构用来解决在一组字符串集合中快速查找某个字符串的问题。
Trie 树到底长什么样子
我举个简单的例子来说明一下。我们有 6 个字符串它们分别是howhiherhellososee。我们希望在里面多次查找某个字符串是否存在。我们就可以先对这 6 个字符串做一下预处理组织成 Trie 树的结构之后每次查找都是在 Trie 树中进行匹配查找。Trie 树的本质就是利用字符串之间的公共前缀将重复的前缀合并在一起。

其中根节点不包含任何信息。每个节点表示一个字符串中的字符从根节点到红色节点的一条路径表示一个字符串注意红色节点并不都是叶子节点。
我画了一个 Trie 树构造的分解过程。构造过程的每一步都相当于往 Trie 树中插入一个字符串。当所有字符串都插入完成之后Trie 树就构造好了。

当我们在 Trie 树中查找一个字符串的时候比如查找字符串“her”那我们将要查找的字符串分割成单个的字符 her然后从 Trie 树的根节点开始匹配。如图所示绿色的路径就是在 Trie 树中匹配的路径。

如何实现一棵 Trie 树

Trie 树主要有两个操作一个是将字符串集合构造成 Trie 树。这个过程分解开来的话就是一个将字符串插入到 Trie 树的过程。另一个是在 Trie 树中查询一个字符串。
如何存储一个 Trie 树
我先介绍其中一种存储方式也是经典的存储方式我们通过一个下标与字符一一映射的数组来存储子节点的指针。

假设我们的字符串中只有从 a 到 z 这 26 个小写字母我们在数组中下标为 0 的位置存储指向子节点 a 的指针下标为 1 的位置存储指向子节点 b 的指针以此类推下标为 25 的位置存储的是指向的子节点 z 的指针。如果某个字符的子节点不存在我们就在对应的下标的位置存储 null。
当我们在 Trie 树中查找字符串的时候我们就可以通过字符的 ASCII 码减去“a”的 ASCII 码迅速找到匹配的子节点的指针。比如d 的 ASCII 码减去 a 的 ASCII 码就是 3那子节点 d 的指针就存储在数组中下标为 3 的位置中。

public class Trie {
  private TrieNode root = new TrieNode('/'); // 存储无意义字符

  // 往Trie树中插入一个字符串
  public void insert(char[] text) {
    TrieNode p = root;
    for (int i = 0; i < text.length; ++i) {
      int index = text[i] - 'a';
      if (p.children[index] == null) {
        TrieNode newNode = new TrieNode(text[i]);
        p.children[index] = newNode;
      }
      p = p.children[index];
    }
    p.isEndingChar = true;
  }

  // 在Trie树中查找一个字符串
  public boolean find(char[] pattern) {
    TrieNode p = root;
    for (int i = 0; i < pattern.length; ++i) {
      int index = pattern[i] - 'a';
      if (p.children[index] == null) {
        return false; // 不存在pattern
      }
      p = p.children[index];
    }
    if (p.isEndingChar == false) return false; // 不能完全匹配只是前缀
    else return true; // 找到pattern
  }

  public class TrieNode {
    public char data;
    public TrieNode[] children = new TrieNode[26];
    public boolean isEndingChar = false;
    public TrieNode(char data) {
      this.data = data;
    }
  }
}

现在我们来看下在 Trie 树中查找某个字符串的时间复杂度是多少
如果要在一组字符串中频繁地查询某些字符串用 Trie 树会非常高效。构建 Trie 树的过程需要扫描所有的字符串时间复杂度是 O(n)n 表示所有字符串的长度和。每次查询时如果要查询的字符串长度是 k那我们只需要比对大约 k 个节点就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说构建好 Trie 树后在其中查找字符串的时间复杂度是 O(k)k 表示要查找的字符串的长度。

Trie 树真的很耗内存吗

关于 Trie 树你有没有听过这样一种说法“Trie 树是非常耗内存的用的是一种空间换时间的思路”。这是什么原因呢
刚刚我们在讲 Trie 树的实现的时候讲到用数组来存储一个节点的子节点的指针。如果字符串中包含从 a 到 z 这 26 个字符那每个节点都要存储一个长度为 26 的数组并且每个数组元素要存储一个 8 字节指针或者是 4 字节这个大小跟 CPU、操作系统、编译器等有关。而且即便一个节点只有很少的子节点远小于 26 个比如 3、4 个我们也要维护一个长度为 26 的数组。
如果字符串中不仅包含小写字母还包含大写字母、数字、甚至是中文那需要的存储空间就更多了。
那为了解决这个内存问题我们是否有其他办法呢
我们可以稍微牺牲一点查询的效率将每个节点中的数组换成其他数据结构来存储一个节点的子节点指针。用哪种数据结构呢我们的选择其实有很多比如有序数组、跳表、散列表、红黑树等。
假设我们用有序数组数组中的指针按照所指向的子节点中的字符的大小顺序排列。查询的时候我们可以通过二分查找的方法快速查找到某个字符应该匹配的子节点的指针。但是在往 Trie 树中插入一个字符串的时候我们为了维护数组中数据的有序性就会稍微慢了点。
实际上Trie 树的变体有很多都可以在一定程度上解决内存消耗的问题。比如缩点优化就是对只有一个子节点的节点而且此节点不是一个串的结束节点可以将此节点与子节点合并。这样可以节省空间但却增加了编码难度。

Trie 树与散列表、红黑树的比较

我们选了两种数据结构散列表和红黑树跟 Trie 树比较一下看看它们各自的优缺点和应用场景。
在刚刚讲的这个场景在一组字符串中查找字符串Trie 树实际上表现得并不好。它对要处理的字符串有极其严苛的要求。
第一字符串中包含的字符集不能太大。我们前面讲到如果字符集太大那存储空间可能就会浪费很多。即便可以优化但也要付出牺牲查询、插入效率的代价。
第二要求字符串的前缀重合比较多不然空间消耗会变大很多。
第三如果要用 Trie 树解决问题那我们就要自己从零开始实现一个 Trie 树还要保证没有 bug这个在工程上是将简单问题复杂化除非必须一般不建议这样做。
第四我们知道通过指针串起来的数据块是不连续的而 Trie 树中用到了指针所以对缓存并不友好性能上会打个折扣。

综合这几点针对在一组字符串中查找字符串的问题我们在工程中更倾向于用散列表或者红黑树。实际上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 还是可以使用正确的拼写来做关键词提示这个又是怎么做到的呢
实际上Trie 树的这个应用可以扩展到更加广泛的一个应用上就是自动输入补全比如输入法自动补全功能、IDE 代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等。

内容小结

今天我们讲了一种特殊的树Trie 树。Trie 树是一种解决字符串快速匹配问题的数据结构。如果用来构建 Trie 树的这一组字符串中前缀重复的情况不是很多那 Trie 树这种数据结构总体上来讲是比较费内存的是一种空间换时间的解决问题思路。
尽管比较耗费内存但是对内存不敏感或者内存消耗在接受范围内的情况下在 Trie 树中做字符串匹配还是非常高效的时间复杂度是 O(k)k 表示要匹配的字符串的长度。
但是Trie 树的优势并不在于用它来做动态集合数据的查找因为这个工作完全可以用更加合适的散列表或者红黑树来替代。Trie 树最有优势的是查找前缀匹配的字符串比如搜索引擎中的关键词提示功能这个场景就比较适合用它来解决也是 Trie 树比较经典的应用场景。