架构师训练营第十三周 - 作业

用户头像
Lost Horizon
关注
发布于: 2020 年 09 月 08 日
架构师训练营第十三周 - 作业

Google 搜索引擎是如何对搜索结果进行排序的?(请用自己的语言描述 PageRank 算法。)



搜索引擎对一个查询的搜索结果进行排名,取决于两组关键信息:网页的质量,网页与搜索内容的相关性。



网页的质量

在互联网上,如果一个网页被很多其他网页锁链接,说明它受到普遍的承认和信赖,那么它的排名就越高。这就是 PageRank 的核心思想。它把整个互联网当作一个整体来对待,而不是将每个网页孤立考虑,不仅关注网页的内容,也关注网页之间的关系,利用网页之间的关系信息提高搜索结果排名质量。



在此基础上,对来自不同网页的链接区别对待,网页排名更高的那些网页的链接被认为更可靠,给予这些链接以更大的权重。类似于显示生活中的投票,大股东的表决权更大,大咖的话语受重视的程度更大。PageRank 算法中,排名高的网页贡献的链接权重也更大。



至此,遇到了一个问题:计算搜索结果的网页排名过程中需要用到网页本身的排名。 似乎成了“先有鸡还是先有蛋”的问题。



佩奇和布林用迭代方法解决了这个问题。先假定所有网页的排名是相同的(给出一个初始值),算出各个网页的第一次迭代排名,然后根据第一次迭代排名算出第二次迭代排名。他们两人从理论上证明了不论初始值如何选取,这种算法都保证了网页排名的估计值能收敛到排名的真实值。

网页本身和查询的相关性

对搜索结果进行排名时,应该将网页本身质量好,并且和搜索的关键词相关性高的网页排在前面。为了避免内容长的网页中同一关键词多次出现,比内容短的网页“占优”,需要根据网页的长度对关键词进行归一化,用关键词出现的次数除以网页的总字数,称为关键词频率(Term Frequency,缩写TF)。



另外,需要忽略一些对主题没什么用处,但会大量出现的词。例如“的”、“地”、“得”等。这些词称为停止词(Stop Word)。停止词的权重为零。



对待不同的词还要给予不同的权重,例如对于专业的词,在所有网页中出现的概率比较小,出现的时候对网页内容主题的重要性更高,需要给予更大的权重。而对于通用的词,被所有网页所使用的可能性更大,出现的时候对网页内容主题的重要性更小,需要给予更小的权重。现在使用最多的权重计算方法是逆文本频率指数(Inverse Document Frequency,缩写 IDF)。计算某个关键词的 IDF 的公式是 log(D/Dw),其中 D 是全部网页的数量,DW 是有这个关键词出现的网页的数量。



网页与搜索的 n 个关键词的相关性计算公式为:

TF1 * IDF1 + TF2 * IDF2 + ... + TFn * IDFn



综合以上两点考虑网页本身的质量,以及网页与搜索内容的相关性,从而计算出网页的搜索结果排名。



工程实现上,由于互联网上的网页数量十分巨大,因此需要采用稀疏矩阵计算的技巧简化计算量,并且采用并行计算的方式缩短响应时间。



用户头像

Lost Horizon

关注

给写代码的人写代码 2017.10.17 加入

Clojure

评论

发布
暂无评论
架构师训练营第十三周 - 作业