您当前的位置:首页 > 电脑百科 > 站长技术 > 搜索引擎

谷歌的自动补全功能那么快,后台是如何工作的?

时间:2019-10-25 16:35:02  来源:  作者:
谷歌的自动补全功能那么快,后台是如何工作的?

 

google 搜索自动补全功能的强大,相信不少朋友都能感受到,它帮助我们更快地“补全”我们所要输入的搜索关键字。那么,它怎么知道我们要输入什么内容?它又是如何工作的?在这篇文章里,我带你一起看看。

使用自动补全

Google 搜索的自动补全功能可以在 Google 搜索应用的大多数位置使用,包括 Google[1] 主页、适用于 IOSAndroid 的 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)。二分搜索的性能很好,但有没有更好的实现呢?当然有,往下看。

前缀树实现

通常来说,许多词汇都以相同的前缀开头,比如 need、nested 都以 ne 开头,seed、speed 都以 s 开头。要是为每个单词分别存储公共前缀似乎很浪费。

谷歌的自动补全功能那么快,后台是如何工作的?

 

前缀树是一种利用公共前缀来加速补全速度的数据结构。前缀树在节点树中排列一组单词,单词沿着从根节点到叶子节点的路径存储,树的层次对应于前缀的字母位置。

前缀的补全是顺着前缀定义的路径来查找的。例如,在上图的前缀树中,前缀 ne 对应于从子节点取左边缘 N 和唯一边缘 E 的路径。然后可以通过继续遍历从 E 节点可以达到的所有叶节点来生成补全列表。在图中,ne 的补全可以是两个分支:-ed 和 -sted。如果在数中找不到由前缀定义的路径,则说明词汇表中不包含以该前缀开头的单词。

有限状态自动机(DFA)实现

前缀树可以有效处理公共前缀,但是,对于其他共享词部分,仍会分别存储在每个分支中。比如,后缀 ed、ing、tion 在英文单词中特别常见。在上一个例子中,e、d 分别存放在了每一个分支上。

有没有一种方法可以更加节省存储空间呢?有的,那就是 DFA。

谷歌的自动补全功能那么快,后台是如何工作的?

 

在上面的例子中,单词 need、nested、seed 和 speed 仅由 9 个节点组成,而上一张图中的前缀树包含了 17 个节点。

可以看出,最小化前缀树 DFA 可以在很大程度上减少数据结构的大小。即使词汇量很大,最小化 DFA 通常也适合在内存中存储,避免昂贵的磁盘访问是实现快速自动补全的关键。

一些扩展

上面介绍了如何利用合理的数据结构实现基本的自动补全功能。这些数据结构可以通过多种方式进行扩展,从而改善用户体验。

通常,满足特定前缀的词汇可能很多,而用户界面上能够显示的却不多,我们更希望能显示最常搜索或者最有价值的词汇。这通常可以通过为词汇表中的每个单词增加一个代表单词值的权重 weight,并且按照权重高低来排序自动补全列表。

•对于排序后的词汇表来说,在词汇表每个元素上增加 weight 属性并不难;

•对于前缀树来说,将 weight 存储在叶子节点中,也是很简单的一个实现;

•对于 DFA 来说,则较为复杂。因为一个叶子节点可以通过多条路径到达。一种解决方案是将权重关联到路径而不是叶子节点。

目前有不少开源库都提供了这个功能,比如主流的搜索引擎框架 Elasticsearch[4]、Solr[5]等,基于此,我们可以实现高效而强大的自动补全功能。



Tags:谷歌 自动补全   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
Google 搜索自动补全功能的强大,相信不少朋友都能感受到,它帮助我们更快地“补全”我们所要输入的搜索关键字。那么,它怎么知道我们要输入什么内容?它又是如何工作的?在这篇文章...【详细内容】
2019-10-25  Tags: 谷歌 自动补全  点击:(156)  评论:(0)  加入收藏
▌简易百科推荐
今天不讲信息流,讲点其他的,比如搜索搜索是什么东西?见过开店卖东西吧,原理大同小异。比如我在步行街租个店铺,开个鞋店,每天在店里等着来步行街的人进我店里买我的鞋。百度搜索就...【详细内容】
2021-12-24  运营王明皓    Tags:搜索   点击:(9)  评论:(0)  加入收藏
在过去的时间中,我写了比较多的关于谷歌SEO推广,今天来写写GoogleAds广告账户免费诊断分析。今天我们的主题是:如何借助GoogleAds广告账户免费诊断分析工具,来诊断并优化你的Goo...【详细内容】
2021-10-26  优易化海外营销推广    Tags:GoogleAds   点击:(43)  评论:(0)  加入收藏
霸屏通俗来讲就是霸占屏幕,百度霸屏就是在百度搜索的结果中,除了竞价内容,剩下的都是我们品牌词或网站的内容。以用户的搜索习惯来说,一般翻两三页就不会再继续翻下去了。所以我...【详细内容】
2021-10-22  聪少爱学堂    Tags:霸屏引流   点击:(50)  评论:(0)  加入收藏
网络推广计划表示在网站优化时,内容优化也是重中之重,其中有关文章的优化也让站长们苦恼不已,因为不太清楚蜘蛛对网站文章的质量评判是如何的,很难做到更精准的蜘蛛“取向”,那么...【详细内容】
2021-10-22  云霸屏    Tags:搜索引擎   点击:(45)  评论:(0)  加入收藏
我们在做SEO优化的过程中,通常都会用到百度站长平台、5118、站长工具等seo工具,用来分析查询关键词排名。特别是百度站长平台中的分析数据很多,其中百度站长工具中的流量与关键...【详细内容】
2021-10-22  双丝网络    Tags:百度站长平台   点击:(36)  评论:(0)  加入收藏
网络推广费用了解到,网站关键词排名效果想要更好,就要扎实的做好优化工作。关键词排名高的网站能更优秀的出现在搜索引擎首页,获得更多的用户浏览,得到更高的权重,从而给企业带来...【详细内容】
2021-09-25  云霸屏  搜狐号  Tags:蜘蛛   点击:(39)  评论:(0)  加入收藏
百度搜索贸易风算法,消除了使用翻页键诱导用户行为,简单地告诉我们,只要你的翻页按钮存在异常跳转行为,无论跳转到哪个页面,都属于该算法的覆盖范围。百度的搜索交易风算法主要攻...【详细内容】
2021-08-31  羽西223    Tags:信风算法   点击:(66)  评论:(0)  加入收藏
1 前言现今互联网上的很多产品、战略决策都由数据驱动,以BulletTech为例,在运营微信公众号时,通过后台数据我们对每篇文章都会进行流量来源、裂变和阅读完关注等重要指标的监控...【详细内容】
2021-08-02  BulletTech    Tags:Google Analytics   点击:(95)  评论:(0)  加入收藏
昨晚松松编辑杰哥了解到,百度搜索最近对算法更新了,全面升级“蓝天算法”2.0版本,主要针对高权重网站出租二级目录和二级域名行为,这是要开始加大清洗目录出租站点了吗? 根据杰...【详细内容】
2021-07-29  卢松松    Tags:蓝天算法   点击:(76)  评论:(0)  加入收藏
网罗天下谈运营2021-07-20在做SEO的过程中,对于企业主而言,没有人刚开始建立网站的时候就会先知先觉,采用完全正确的SEO优化方法,这很必然会导致一些问题,比如:① 站内目录层级繁...【详细内容】
2021-07-21  Lollipop    Tags:网站不收录   点击:(82)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条