目录
前言
什么是Trie树?
如何实现一棵Trie树?
Trie 树与散列表、红黑树的比较?
问题
总结:
参考资料:
前言
搜索引擎的搜索关键词提示功能,我想你应该不陌生吧?为了方便快速输入,当你在搜索引擎的搜索框中,输入要搜索的文字的某一部分的时候,搜索引擎就会自动弹出下拉框,里面是各种关键词提示。你可以直接从下拉框中选择你要搜索的东西,而不用把所有内容都输入进去,一定程度上节省了我们的搜索时间。
像 Google、百度这样的搜索引擎,它们的关键词提示功能非常全面和精准,肯定做了很多优化,但万变不离其宗,底层最基本的原理就是今天要讲的这种数据结构:Trie 树。
什么是Trie树?
Trie 树,也叫“字典树”。顾名思义,它是一个树形结构。它是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串的问题。
现在,我们先来看下,Trie 树到底长什么样子。
我举个简单的例子来说明一下。我们有 6 个字符串,它们分别是:how,hi,her,hello,so,see。我们希望在里面多次查找某个字符串是否存在。如果每次查找,都是拿要查找的字符串跟这 6 个字符串依次进行字符串匹配,那效率就比较低,有没有更高效的方法呢?
这个时候,我们就可以先对这 6 个字符串做一下预处理,组织成 Trie 树的结构,之后每次查找,都是在 Trie 树中进行匹配查找。Trie 树的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起。最后构造出来的就是下面这个图中的样子。
如何实现一棵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 的位置中。
Trie 树的实现,你现在应该搞懂了。现在,我们来看下,在Trie树中,查找某个字符串的时间复杂度是多少?如果要在一组字符串中,频繁地查询某些字符串,用Trie树会非常高效。构建Trie树的过程,需要扫描所有的字符串,时间复杂度是 O(n)(n 表示所有字符串的长度和)。但是一旦构建成功之后,后续的查询操作会非常高效。
每次查询时,如果要查询的字符串长度是 k,那我们只需要比对大约 k 个节点,就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说,构建好Trie树后,在其中查找字符串的时间复杂度是 O(k),k 表示要查找的字符串的长度。
Trie 树与散列表、红黑树的比较?
实际上,字符串的匹配问题,笼统上讲,其实就是数据的查找问题。对于支持动态数据高效操作的数据结构,我们前面已经讲过好多了,比如散列表、红黑树、跳表等等。
实际上,这些数据结构也可以实现在一组字符串中查找字符串的功能。我们选了两种数据结构,散列表和红黑树,跟Trie树比较一下,看看它们各自的优缺点和应用场景。在刚刚讲的这个场景,在一组字符串中查找字符串,Trie 树实际上表现得并不好。
它对要处理的字符串有极其严苛的要求。
- 第一,字符串中包含的字符集不能太大。我们前面讲到,如果字符集太大,那存储空间可能就会浪费很多。即便可以优化,但也要付出牺牲查询、插入效率的代价。
- 第二,要求字符串的前缀重合比较多,不然空间消耗会变大很多。
-
第三,如果要用Trie树解决问题,那我们就要自己从零开始实现一个Trie树,还要保证没有 bug,这个在工程上是将简单问题复杂化,除非必须,一般不建议这样做。
-
第四,我们知道,通过指针串起来的数据块是不连续的,而Trie树中用到了指针,所以,对缓存并不友好,性能上会打个折扣。
综合这几点,针对在一组字符串中查找字符串的问题,我们在工程中,更倾向于用散列表或者红黑树。因为这两种数据结构,我们都不需要自己去实现,直接利用编程语言中提供的现成类库就行了。
问题
如何利用Trie树,实现搜索关键词的提示功能?
我们假设关键词库由用户的热门搜索关键词组成。我们将这个词库构建成一个Trie树。当用户输入其中某个单词的时候,把这个词作为一个前缀子串在Trie树中匹配。为了讲解方便,我们假设词库里只有 hello、her、hi、how、so、see 这 6 个关键词。当用户输入了字母 h 的时候,我们就把以 h 为前缀的 hello、her、hi、how 展示在搜索提示框内。当用户继续键入字母 e 的时候,我们就把以 he 为前缀的 hello、her 展示在搜索提示框内。这就是搜索关键词提示的最基本的算法原理。
实际上,Trie 树的这个应用可以扩展到更加广泛的一个应用上,就是自动输入补全,比如输入法自动补全功能、IDE 代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等。
总结:
Trie 树是一种解决字符串快速匹配问题的数据结构。如果用来构建Trie树的这一组字符串中,前缀重复的情况不是很多,那Trie树这种数据结构总体上来讲是比较费内存的,是一种空间换时间的解决问题思路。
尽管比较耗费内存,但是对内存不敏感或者内存消耗在接受范围内的情况下,在Trie树中做字符串匹配还是非常高效的,时间复杂度是 O(k),k 表示要匹配的字符串的长度。
但是,Trie 树的优势并不在于,用它来做动态集合数据的查找,因为,这个工作完全可以用更加合适的散列表或者红黑树来替代。Trie 树最有优势的是查找前缀匹配的字符串,比如搜索引擎中的关键词提示功能这个场景,就比较适合用它来解决,也是Trie树比较经典的应用场景。
参考资料:
本章内容来源于对王争大佬的《数据结构与算法之美》的专栏。
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?-极客时间