如何实现搜索引擎优化(6个字符串搜索关键词提示功能，你get到了吗？)

　　如何实现搜索引擎优化(6个字符串搜索关键词提示功能，你get到了吗？)

　　一、场景

　　搜索引擎的搜索关键词提示功能，你应该先熟悉了吧？为了方便和舒适，当你在搜索框中输入某部分文字时，搜索引擎会自动弹出一个带有各种关键词提示的下拉框。您可以从下拉框中选择要搜索的内容。

　　二、Trie 树定义

　　目前主流的搜索引擎，他们的关键词提示功能非常全面准确，肯定也做了很多优化，但最基本的原理是使用数据结构：Trie树。

　　Trie 树，也称为“字典树”。顾名思义，它是一种树结构，是一种专门用于字符串匹配的数据结构，用于解决在一组字符串中快速查找字符的问题。

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

　　1) 让我们来看看 Trie 树的样子。

　　举个简单的例子。我们有 6 个字符串：how、hi、her、hello、so、see。我们洗碗，并在其中多次寻找某个字符串的存在。如果每次都进行搜索，要搜索的字符串依次与这6个字符串匹配，效率相对较低。

　　我们可以先对六个字符串进行预处理，将它们组织成一个Trie树结构。每个词搜索完后，会在Trie树中进行匹配和搜索。

　　Trie 树的本质是利用字符串之间的公共前缀将重复的前缀合并在一起。最终构造成如图所示。

　　其中，根节点不收录任何信息。每个节点代表字符串中的一个字符，从根节点到红色节点的路径代表一个字符串（注意：红色节点并非都是叶子节点）。

　　2）看看如何构造Trie树

　　构建过程的每一步都相当于在Trie树中插入一个字符串。当所有的字符串都插入后，Trie 树就被构建了。

　　3) 匹配 Trie 树中的字符串

　　在 Trie 树中搜索字符串时，例如搜索字符串“her”，会将字符串拆分为单个字符 h、e、r，然后从 Trie 树的根节点开始匹配。如下图，绿色路径为Trie树中匹配的路径。

　　四、Trie树、红黑树、哈希表算法对比

　　1） 字符串中收录的字符集不能太大。如果字符集过大，可能会浪费大量的存储空间。

　　2） 字符串的前缀重叠很多，否则空间消耗巨大。

　　3） 如果我们想使用Trie树来解决问题，那么我们需要从头开始实现一个Trie树，并确保没有bug。这可能会使问题复杂化，一般不建议这样做。

　　4）Trie树是指针串起来的数据块不连续，所以对指针不友好，性能会受到影响。

　　综合这几点，对于在一组字符串中寻找字符串的问题，在工程上，更倾向于使用哈希表或者红黑树。由于这两种数据结构，可以直接使用现成的库。

　　转载：