Google 如何对搜索结果排序?

本文是架构师训练营第 13 周课后作业,主要分析 Google 是如何对搜索结果进行排序,以及 Google 网页排名 PageRank 算法。Google 搜索引擎是目前世上最强大的搜索引擎,也是我最喜欢使用的搜索引擎,没有之一。

一个正常的搜索引擎,其核心功能自然是网页搜索。那搜索结果应该怎样排序才最好呢?实际上,在谷歌主导互联网搜索之前,很多人为此伤透脑筋。 

当时人们认为,通过判断能够得知哪个网页更重要,对搜索引擎的发展十分有帮助——很显然,搜索引擎应该把重要的网页放到搜索结果中比较靠前的地方。

这个问题看起来很容易,但是解决的方法却没有想象的那么简单。

在谷歌诞生前期,各种流行的网页排名算法很类似,都使用了一个非常简单的思想:越是重要的网页,访问量就会越大。许多大公司就通过统计网页的访问量来进行网页排名。但是这种排名算法有两个很显著的问题:一是只能够抽样统计,导致统计数据不一定准确,而且访问量的波动会比较大,想要得到准确的统计需要大量的时间和人力,还只能维持很短的有效时间;二是访问量并不一定能体现网页的“重要程度”——一些比较早接触互联网的人可能还记得,当时有很多专门“刷访问量”的服务。

这就为什么早期的 Yahoo、搜狐和百度上的搜索,很难从搜索结果中得到自己想要的东西。直到 Google 问世后,将这个问题解决了。大家应该可以体验到,Google 搜索排序出来的结果中,前 3 个通常是想要的,几乎是 95% 命中率。

那么 Google 是怎么不通过统计访问量,就能够对网页的重要度排序呢?

1996 年初,Google 公司的创始人,当时还是斯坦福大学研究生的佩奇和布林开始了对网页排序问题的研究。在1999年,一篇以佩奇为第一作者的论文发表了,论文中介绍了一种叫做 PageRank 的算法,这种算法的主要思想是:越“重要”的网页,页面上的链接质量也越高,同时越容易被其它“重要”的网页链接。于是,算法完全利用网页之间互相链接的关系来计算网页的重要程度,将网页排序彻底变成一个数学问题。

那什么又是 PageRank 算法呢?

PageRank 通过网络浩瀚的超链接关系来确定一个页面的等级,Google 把从 A 页面到 B 页面的链接解释为 A 页面给 B 页面投票。Google 根据投票来源(甚至来源的来源,即链接到 A 页面的页面)和投票目标的等级来决定新的等级。简单的说,一个高等级的页面可以使其他低等级页面的等级得到提升。

一个页面的“得票数”由所有链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投一票。一个页面的 PageRank 是由所有链向它的页面(链入页面)的重要性经过递归算法得到,一个有较多链入的页面会有较高的等级,相反如果一个页面没有任何链入页面,那么它没有等级。

为了更好地理解上述 PageRank 算法,不妨用一个游戏来简单模拟 PageRank 算法的运行过程。

三兄弟分 30 枚硬币,起初每人 10 枚,他们每次都要把手里的硬币全部(或平均分)给自己喜欢的人。下图表示了三兄弟各自拥有的初始硬币数量、相互喜欢的关系(箭头方向表示喜欢,例如老二喜欢老大,老大喜欢老二和老三),以及他们之间硬币分配的游戏过程。

PageRank算法模拟游戏
PageRank算法模拟游戏

就这样,上述模拟游戏一直进行下去,直到他们手中的硬币数不再变化为止。

那么这个游戏到底是否可以结束呢,如果可以,最终的结果又是什么样的?在此我用计算机程序模拟了这个过程,得出的结果是:老大和老二各有 12 枚硬币,而老三有 6 枚硬币。这时候无论游戏怎么进行下去,他们各自的硬币数量都不会再变化。

将这个游戏和 PageRank 算法进行类比,实际上, PageRank 会给每个网页一个数值,这个数值越高,就说明这个网页越“重要”。而刚刚的游戏中,如果把硬币的数量看作这个数值(可以不是整数),把孩子们看作网页,那么游戏的过程就是 PageRank 的算法,而游戏结束时硬币的分配,就是网页的 PageRank 值。

由于 PageRank 数学模型公式涉及到高等数学知识,有点深奥,本文不再陈述。

参考资料:https://www.guokr.com/article/65304/

《Google 如何对搜索结果排序?》的相关评论

发表评论

必填项已用 * 标记,邮箱地址不会被公开。