微信图片_20181019114150

我们所熟知的搜索引擎的有百度、bing、Google等等,除了百度使用“靠钱排名法”,搜索引擎中最为基础且核心的排序算法是来自Google的pagerank算法,其发明者是Google的创始人拉里·佩奇和谢尔盖·布林。这项发明使得1998年前后搜索的相关性有了质的飞跃,夸张点说,可以认为谷歌整个公司的成功都基于这个算法。       


pagerank究竟是怎么一回事呢?简单的说就是民主表决。互联网上,如果一个网页被很多其他网页所链接,说明其受到普遍的承认和信赖,那么它的排名就高。比如说,对于与和同一个关键词相关的网页,一个网页被另外100个网页所链接,不妨设它得到100票,他的排名就会比只被十个 网页链接,也就是只有10票的网页排名更高


微信图片_20181019114134


但是这里有一个问题,作为”投票员”,不同网页的权威性不一样,比如一个网页被100个垃圾网站链接,另一个被50个权威网站链接,显然后者的50票比前者的100票更加可靠。为了解决这个问题,我们对不同的网页根据其可靠性赋给其相应的“权”,越可靠的网页“权”越大,再利用权重计算就可以避免这个问题了。以此为例,权威网站的“权”为5,垃圾网站为1,则前者得分为1x100=100,后者得分为5x50=250,所以后者排名高。这个结果显然更为合理。


然而还是有个问题需要解决,就是“权”怎么确定呢?佩奇和布林把这个转化为一个二维矩阵相乘的问题,先假定所有的网站的“权”是一样的,可以证明矩阵不断迭代之后结果是收敛到真实值的。在实际操作中网页的数量是巨大的,十亿个网页矩阵会有一百亿亿个元素,这么大规模计算量对现有技术来说不太现实,佩奇和布林又利用了稀疏矩阵的技巧简化了计算。具体的数学方法有兴趣可以自行了解。


时至今日,搜索引擎功能完善而且复杂了很多,但是pagerank算法仍是至关重要的。