搜索引擎背后的经典数据结构和算法( 三 ) _搜索引擎

文章插图

这颗多叉树表示了关键字集合 ["to"，"tea"，"ted"，"ten"，"a"，"i"，"in", "inn"] 。从中可以看出 Trie 树具有以下性质：

根节点不包含字符，除根节点外的每一个子节点都包含一个字符
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串
每个节点的所有子节点包含的字符互不相同

通常在实现的时候，会在节点结构中设置一个标志，用来标记该结点处是否构成一个单词（关键字）。
另外我们不难发现一个规律，具有公共前缀的关键字（单词），它们前缀部分在 Trie 树中是相同的，这也是 Trie 树被称为前缀树的原因，有了这个思路，我们不难设计出上文所述搜索时展示一串搜索提示词的思路：
一般搜索引擎会维护一个词库，假设这个词库由所有搜索次数大于某个阈值（如 1000）的字符串组成，我们就可以用这个词库构建一颗 Trie 树，这样当用户输入字母的时候，就可以以这个字母作为前缀去 Trie 树中查找，以上文中提到的 Trie 树为例，则我们输入「te」时，由于以「te」为前缀的单词有 ["tea"，"ted"，"ted"，"ten"]，则在搜索引擎的搜索提示框中就可以展示这几个字符串以供用户选择。
五、寻找热门搜索字符串Trie 树除了作为前缀树来实现搜索提示词的功能外，还可以用来辅助寻找热门搜索字符串，只要对 Trie 树稍加改造即可。假设我们要寻找最热门的 10 个搜索字符串，则具体实现思路如下:
一般搜索引擎都会有专门的日志来记录用户的搜索词，我们用用户的这些搜索词来构建一颗 Trie 树，但要稍微对 Trie 树进行一下改造，上文提到，Trie 树实现的时候，可以在节点中设置一个标志，用来标记该结点处是否构成一个单词，也可以把这个标志改成以节点为终止字符的搜索字符串个数，每个搜索字符串在 Trie 树遍历，在遍历的最后一个结点上把字符串个数加 1，即可统计出每个字符串被搜索了多少次（根节点到结点经过的路径即为搜索字符串），然后我们再维护一个有 10 个节点的小顶堆（堆顶元素比所有其他元素值都小，如下图示）

文章插图

如图示：小顶堆中堆顶元素比其他任何元素都小
依次遍历 Trie 树的节点，将节点（字符串+次数）传给小顶堆，根据搜索次数不断调整小顶堆，这样遍历完 Trie 树的节点后，小顶堆里的 10 个节点对应的字符串即是最热门的搜索字符串。
总结本文简述了搜索引擎的工作原理，相信大家看完后对其工作原理应该有了比较清醒的认识，我们可以看到，搜索引擎中用到了很多经典的数据结构和算法，所以现在大家应该能明白为啥 Google, 百度这些公司对候选人的算法要求这么高了。