谷歌的自动补全功能那么快，后台是如何工作的？ _谷歌

文章插图

google 搜索自动补全功能的强大，相信不少朋友都能感受到，它帮助我们更快地“补全”我们所要输入的搜索关键字。那么，它怎么知道我们要输入什么内容？它又是如何工作的？在这篇文章里，我带你一起看看。使用自动补全Google 搜索的自动补全功能可以在 Google 搜索应用的大多数位置使用，包括 Google[1] 主页、适用于 IOS 和 Android 的 Google 应用，我们只需要在 Google 搜索框上开始键入关键字，就可以看到联想词了。

文章插图

在上图示例中，我们可以看到，输入关键字 juej，Google 搜索会联想到“掘金”、“掘金小册”、“绝句”等等，好处就是，我们无须输入完整的关键字即可轻松完成针对这些 topics 的搜索。
谷歌搜索的自动补全功能对于使用移动设备的用户来说特别有用，用户可以轻松在难以键入的小屏幕上完成搜索。当然，对于移动设备用户和台式机用户而言，这都节省了大量的时间。根据 Google 官方报告，自动补全功能可以减少大约 25% 的打字，累积起来，预计每天可以节省 200 多年的打字时间。是的，每天！

注意，本文所提到的“联想词”与“预测”，是同一个意思。

基于“预测”而非“建议”Google 官方将自动补全功能称之为“预测”，而不是“建议”，为什么呢？其实是有充分理由的。自动补全功能是为了帮助用户完成他们打算进行的搜索，而不是建议用户要执行什么搜索。
那么，Google 是如何确定这些“预测”的？其实，Google 会根据趋势搜索 trends[2] 给到我们这些“预测” 。简单来说，哪个热门、哪个搜索频率高，就更可能推给我们。当然，这也与我们当前所处的位置以及我们的搜索历史相关。
另外，这些“预测”也会随着我们键入的关键字的变更而更改。例如，当我们把键入的关键字从 juej 更改为 juex 时，与“掘金”相关的预测会“消失”，同时，与“觉醒”、“决心”相关联的词会出现。

文章插图

为什么我们看不到某些联想词？如果我们在输入某个关键字时看不到联想词，那么表明 Google 的算法可能检测到：
•这个关键字不是热门字词；
•搜索的字词太新了，我们可能需要等待几天或几周才能看到联想词；
•这是一个侮辱性或敏感字词，这个搜索字词违反了 Google 的相关政策。更加详细的情况，可以了解 Google 搜索自动补全政策[3] 。
为什么我们会看到某些不当的联想词？Google 拥有专门设计的系统，可以自动捕获不适当的预测结果而不显示出来。然而，Google 每天需要处理数十亿次搜索，这意味着 Google 每天会显示数十亿甚至上百亿条预测。再好的系统，也可能存在缺陷，不正确的预测也可能随时会出现。
我们作为 Google 搜索的用户，如果认定某条预测违反了相关的搜索自动补全政策，可以进行举报反馈，点击右下角“举报不当的联想查询”并勾选相关选项即可。

文章插图

如何实现自动补全算法？目前，Google 官方似乎并没有公开搜索自动补全的算法实现，但是业界在这方面已经有了不少研究。
一个好的自动补全器必须是快速的，并且在用户键入下一个字符后立即更新联想词列表。自动补全器的核心是一个函数，它接受输入的前缀，并搜索以给定前缀开头的词汇或语句列表。通常来说，只需要返回少量的数目即可。
接下来，我们先从一个简单且低效的实现开始，并在此基础上逐步构建更高效的方法。
词汇表实现一个简单粗暴的实现方式是：顺序查找词汇表，依次检查每个词汇，看它是否以给定的前缀开头。
但是，此方法需要将前缀与每个词汇进行匹配检查，若词汇量较少，这种方式可能勉强行得通。但是，如果词汇量规模较大，效率就太低了。
一个更好的实现方式是：让词汇按字典顺序排序。借助二分搜索算法，可以快速搜索有序词汇表中的前缀。由于二分搜索的每一步都会将搜索的范围减半，因此，总的搜索时间与词汇表中单词数量的对数成正比，即时间复杂度是 O(log N) 。二分搜索的性能很好，但有没有更好的实现呢？当然有，往下看。