35 | Trie树：如何实现搜索引擎的搜索关键词提示功能？
王争
该思维导图由 AI 生成，仅供参考
搜索引擎的搜索关键词提示功能，我想你应该不陌生吧？为了方便快速输入，当你在搜索引擎的搜索框中，输入要搜索的文字的某一部分的时候，搜索引擎就会自动弹出下拉框，里面是各种关键词提示。你可以直接从下拉框中选择你要搜索的东西，而不用把所有内容都输入进去，一定程度上节省了我们的搜索时间。
尽管这个功能我们几乎天天在用，作为一名工程师，你是否思考过，它是怎么实现的呢？它底层使用的是哪种数据结构和算法呢？
像 Google、百度这样的搜索引擎，它们的关键词提示功能非常全面和精准，肯定做了很多优化，但万变不离其宗，底层最基本的原理就是今天要讲的这种数据结构：Trie 树。
什么是“Trie 树”？
Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。
当然，这样一个问题可以有多种解决方法，比如散列表、红黑树，或者我们前面几节讲到的一些字符串匹配算法，但是，Trie 树在这个问题的解决上，有它特有的优点。不仅如此，Trie 树能解决的问题也不限于此，我们一会儿慢慢分析。
现在，我们先来看下，Trie 树到底长什么样子。
我举个简单的例子来说明一下。我们有 6 个字符串，它们分别是：how，hi，her，hello，so，see。我们希望在里面多次查找某个字符串是否存在。如果每次查找，都是拿要查找的字符串跟这 6 个字符串依次进行字符串匹配，那效率就比较低，有没有更高效的方法呢？
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
Trie树，又称字典树，是一种用于解决字符串匹配问题的高效数据结构。本文介绍了Trie树的基本概念和实现方法，包括构造Trie树和字符串查找的时间复杂度。Trie树能够快速查找字符串是否存在于给定的字符串集合中，并通过合并重复的前缀来构建高效的数据结构。虽然Trie树在某些情况下可能会浪费内存，但它在搜索引擎的搜索关键词提示功能等场景中表现出色。文章还对Trie树与散列表、红黑树进行了比较，并指出Trie树更适合于查找前缀匹配的字符串。此外，文章还探讨了Trie树在搜索关键词提示功能和自动输入补全等领域的应用。总之，Trie树是一种高效的数据结构，尤其适用于频繁查询字符串的场景，能够极大地提升搜索效率。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《数据结构与算法之美》，新⼈⾸单¥68
《数据结构与算法之美》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(128)
- 最新
- 精选
Jerry银银找到了一个Trie树的开源库：Apache Commons，里面有关于Trie的实现作者回复: 👍
2018-12-2814244- kepmovtrie树实际项目中由于内存问题用的不是很多，老师可以讲解下DAT（双数组trie树）的具体实现吗
作者回复: 这个还是自己研究吧 内容太多了 文章有限。或者后面我收集下 统一写几篇加餐文章吧
2018-12-1229 
雨天if (p.isEndingChar == false) return false; // 不能完全匹配，只是前缀 else return true; // 找到 pattern 这小段代码有点不大牛.^_^ return p.isEndingChar;就好了作者回复: 嗯嗯 怕看不懂嘛
2018-12-12219
ZX老师，字符串匹配这里，还差后缀树没讲，很多场合需要用到这种结构，希望老师可以讲一讲作者回复: 那个更高级 不讲了 自学吧亲
2018-12-17417
忽忽请问下老师，这些图是什么工具画的呀？作者回复: paper
2018-12-2515
蚂蚁内推+v老师 红黑树 如何实现字符串查找 方便王老师稍微点拨下吗作者回复: 把字符串整体当做一个数据 存储在节点里
2018-12-1211
想当上帝的司机26个字符的话TrieNode不要data也可以吧 数组下标就是data作者回复: 嗯嗯 是的
2018-12-3010
Lisa Li“而 Trie 树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。” 可以解释一下为什么吗？作者回复: 用指针串起来的数据在内存中是不连续的 对cpu缓存来说 不友好 你可以看下链表那一节
2018-12-1826- 追风者王老师，关于Trie树有两点疑问。 1.文中用‘he’和‘her’构建Trie树，当我要查询‘he’的时候怎么办？ 2.像jieba分词这种切词工具，为什么要用Trie树呢？
作者回复: 1. he的e节点也会被标记为结尾字符节点 2. jieba分词不怎么了解呢。。。
2019-01-0434 
莫弹弹想起来上一次需求是做敏感词检测，需要匹配到指定动词和指定名词才会触发屏蔽，经过实验，暴力for循环是最快的("▔㉨▔) trie太复杂了写完怕别人看不懂作者回复: 这个数据量小的话 确实暴力最快
2018-12-144
收起评论
