数据结构_如何实现搜索引擎的搜索关键词提示功能？

迷南。 2022-10-01 08:49 183阅读 0赞

## 一、场景 ##

搜索引擎的搜索关键词提示功能，我先你应该不陌生吧 ？为了方便舒服，当你在搜索框，输入文字的某一部分的时候，搜索引擎会自动弹出下拉框，里面有各种关键词提示。 你可以从下拉框中选中你要搜索的东西。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE4MTQ5_size_16_color_FFFFFF_t_70]

## 二、Trie 树定义 ##

现在主流的搜索引擎，他们的关键词提示功能非常全面和精确，肯定做了很多优化，但最基本的原理是用了数据结构：Trie 树。  
Trie 树 ，也叫“字典树”。顾名思义，它是一个树形结构，它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串中快速查找某个字符的问题。

## 三、Trie 树实现搜索关键词原理 ##

1 ）我们先看一下，Trie 树长什么样子。  
举一个简单的例子。我们有6个字符串，分别是：how，hi，her，hello，so,see。我们洗碗在里面多次查找某个字符串是否存在。如果每次查找，都是拿要查找的字符串跟这6个字符串依次进行字符串匹配，效率比较低。  
我们可以先对6个字符串做一下预处理，组织成一个Trie树的结构，字后每次查找，都在Trie树中匹配查找。  
Trie树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。最后构造出如图的样子。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE4MTQ5_size_16_color_FFFFFF_t_70 1]  
其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（注意：红色节点并不都是叶子节点）。  
2）看一下怎么构造Trie 树  
构造过程的每一步，相当于往Trie 树中插入一个字符串。当所有字符串都插入完成后，Trie 树就构造好了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE4MTQ5_size_16_color_FFFFFF_t_70 2]  
3 ）Trie 树中匹配字符串  
在Trie 树中查找一个字符串的时候，比如查找字符串“her”，那会将字符串分割成单个字符h,e,r,然后从Trie 树的根节点开始匹配。如下图，绿色的路径就是在Trie 树中匹配的路径。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE4MTQ5_size_16_color_FFFFFF_t_70 3]

## 四、Trie 树与红黑树、散列表算法对比 ##

1）字符串中包含的字符集不能太大。如果字符集太大，那存储空间可能就会浪费很多。  
2）字符串的前缀重合比较多，不然空间消耗会很大。  
3）如果要用Trie 树解决问题，那我们就需要从零实现一个Trie 树，还要保证没bug，这可能会导致问题复杂化，一般不建议这么做。  
4）Trie 树是通过指针串起来的数据块是不连续的，所以对指针并不友好，性能上会打折扣。

综合这几点，针对一组字符串中查找字符串的问题，在工程中，更倾向于用散列表或红黑树。因为这两种数据结构，可以直接用现成类库就行。

转载：[https://time.geekbang.org/column/article/72414][https_time.geekbang.org_column_article_72414]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE4MTQ5_size_16_color_FFFFFF_t_70]: /images/20220118/8bc60dc03c904acd9620faa60223b6bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE4MTQ5_size_16_color_FFFFFF_t_70 1]: /images/20220118/0cbe6fb381a24a45bdf790147f51cd26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE4MTQ5_size_16_color_FFFFFF_t_70 2]: /images/20220118/9cb2dd1ccf204c71b868887f2bce79d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE4MTQ5_size_16_color_FFFFFF_t_70 3]: /images/20220118/a24994a8affe4cb38497576c1c54849c.png
[https_time.geekbang.org_column_article_72414]: https://time.geekbang.org/column/article/72414