收藏本站|设为首页

您现在的位置: 首页 > 新闻中心 > 建站经验 > 详细内容

浅析PageRank算法

2012-07-05 09:44 来源: 卓杰科技 www.zhuojie.cc [ ]

很早就对 Google 的 PageRank 算法很感乐趣,但一向没有深究,只有个轮廓性的概念。前几天趁团队 outing 的机缘,在动车上看了一些相关的资料,连成一气,将所看的工具清算成此文。

本文首先会谈判搜索引擎的焦点难题,同时谈判早期搜索引擎关于结不美观页面主要性评价算法的困境,借此引出 PageRank 发生的布景。第二部门会具体谈判 PageRank 的思惟来历、基本框架,并连系互联网页面拓扑结构谈判 PageRank 措置 Dead Ends 及滑腻化的体例。第三部门谈判 Topic-Sensitive PageRank 算法。最后将谈判对 PageRank 的 Spam 抨击袭击体例:Spam Farm 以及搜索引擎对 Spam Farm 的防御。

编纂备注:本文内容涵盖编程常识,如站长在阅读时碰着涉及轨范算法公式时,建议只需体味年夜意即可,无需解读公式,重在体味PageRank算法的根基概念。

基于检索词评价的思惟很是朴质:和检索词匹配度越高的页面主要性越高。“匹配度”就是要界说的具体怀抱。一个最直接的设法是关头词呈现次数越多的页面匹配度越高。仍是搜索“张洋博客”的例子:假设A页面呈现“张洋”5次,“博客”10次;B页面呈现“张洋”2次,“博客”8次。于是A页面的匹配度为 5 + 10 = 15,B页面为 2 + 8 = 10,于是认为A页面的主要性高于B页面。良多伴侣可能意识到这里的不合理性:内容较长的网页往往更可能比内容较短的网页关头词呈现的次数多。是以,我们可以改削一下算法,用关头词呈现次数除以页面总词数,也就是经由过程关头词占比作为匹配度,这样可以战胜膳缦沔提到的不合理。

搜索引擎的难题

Google 早已成为全球最成功的互联网搜索引擎,但这个当前的搜索引擎巨无霸却不是最早的互联网搜索引擎,在 Google 呈现之前,曾呈现过良多通用或专业规模搜索引擎。Google 最终能击败所有竞争对手,很年夜水平上是因为它解决了困扰前辈们的最浩劫题:对搜索结不美观按主要性排序。而解决这个问题的算法就是 PageRank。毫不磕张的说,是 PageRank 算法成就了 Google 今天的低位。要理解为什么解决这个难题如斯主要,我们先来看一下搜索引擎的焦点框架。

虽然搜索引擎已经成长了良多年,可是其焦点却没有太年夜转变。年夜素质上说,搜索引擎是一个资料检索系统,搜索引擎拥有一个资料库(具体到这里就是互联网页面),用户提交一个检索前提(例如关头词),搜索引擎返回合适发芽前提的资料列表。理论上检索前提可以很是复杂,为了简单起见,我们不妨设检索前提是一至多个以空格分隔的词,而其表达的语义是同时含有这些辞书资料(等价于布尔代数的逻辑与)。例如,提交“张洋博客”,意思就是“给我既含有‘张洋’又含有‘博客’词语的页面”,以下是 Google 对这条关头辞书搜索结不美观:

image

搜索引擎的焦点框架

膳缦沔阐述了一个很是简单的搜索引擎工作框架,虽然现代搜索引擎的具体细节事理要复杂的多,但其素质饶暌闺这个简单的模子并无二异。现实 Google 在上述两点上对比其前辈并无高明之处。其最年夜的成功是解决了第三个、也是最为坚苦的问题:若何对发芽结不美观排序。

可以看到我的博客呈此刻第五条,而第四条是我之前在博客园的博客。

当然,现实上此刻的搜索引擎都是有分词机制的,例如如不美观以“张洋的博客”为关头词,搜索引擎会自动将其分化为“张洋的博客”三个词,而“的”作为遏制词(Stop Word)会被过滤失踪。关于分词及词权评价算法(如 TF-IDF 算法)是一个很年夜的话题,这里就不睁开谈判了,为了简单此处可以将搜索引擎想象为一个只会机械匹配词语的检索系统。

这样看来,成立一个搜索引擎的焦点问题就是两个:1、成立资料库;2、成立一种数据结构,可以按照关头词找到含有这个辞书页面。

搜索引擎的焦点难题

第一个问题一般是经由过程一种叫爬虫(Spider)的非凡轨范实现的(当然,专业规模搜索引擎例如某个学术会议的论文检索系统可能直接年夜数据库成立资料库),简单来说,爬虫就是年夜一个页面出发(例如新浪首页),经由过程 HTTP 和谈通信获取这个页面的所有内容,把这个页面 url 和内容记实下来(记实到资料库),然后剖析页面中的链接,再去分袂获取这些链接链向页面的内容,记实到资料库后再剖析这个页面的链接……一再这个过程,就可以将整个互联网的页面全数获取下来(当然这是理想情形,要求整个 Web 是一个强连通(Strongly Connected),而且所有页面的 robots 和谈许可爬虫抓取页面,为了简单,我们仍然假设 Web 是一个强连通图,且不考虑 robots 和谈)。抽象来看,可以将资料库看做一个巨年夜的 key-value 结构,key 是页面 url,value是页面内容。

第二个问题是经由过程一种叫倒排索引(inverted index)的数据结构实现的,抽象来说倒排索引也是一组 key-value 结构,key 是关头词,value 是一个页面编号集结(假设资料库中每个页面有独一编号),暗示这些页面含有这个关头词。本文不具体谈判倒排索引的成立体例。

我们知道 Web 页面数目很是巨年夜,所以一个检索的结不美观条目数目也很是多,例如膳缦沔“张洋博客”的检索返回了跨越 260 万条结不美观。用户不成能年夜如斯众多的结不美观一一一查找对自己有用的信息,所以,一个好的搜索引擎必需设法子将“质量”较高的页面排在前面。其实直不美观上也可以感受出,在使用搜索引擎时,我们并不太关心页面是否够全(上百万的结不美观,全不全有什么区别?而且现实上搜索引擎都是取 top,并不会真的返回全数结不美观。),而很关心前一两页是否都是质量较高的页面,是否能知足我们的现实需求。

早期搜索引擎的做法

不评价

是以,对搜索结不美观按主要性合理的排序就成为搜索引擎的最年夜焦点,也是 Google 最终成功的打破点。

后来,一些搜索引擎惹人了基于检索关头词去评价搜索结构主要性的体例,现实上,这类体例如 TF-IDF 算法在现代搜索引擎中仍在使用,但其已经不是评价质量的独一指标。完整描述 TF-IDF 斗劲繁琐,本文这里用一种更简单的抽象耐庞汨述这种体例。

基于检索辞书评价

这个看起来可能有点搞笑,但现实上早期良多搜索引擎(甚至搜罗此刻的良多专业规模搜索引擎)根柢不评价结不美观主要性,而是直接按照某自然挨次(例如时刻挨次或编号挨次)返回结不美观。这在结不美观集斗劲少的情形下还说得曩昔,可是一旦结不美观集变年夜,用户叫苦不迭,试想让你年夜几万条质量参差不齐的页面中寻找需要的内容,简直就是一场灾难,这也注定章种体例不成能用于现代的通用搜索引擎。

有了膳缦沔的剖析,就可以简要声名搜索引擎的焦点动作了:搜索引擎获取“张洋博客”发芽前提,将其分为“张洋”和“博客”两个词。然后分袂年夜倒排索引中找到“张洋”所对应的集结,假设是{1, 3, 6, 8, 11, 15};“博客”对应的集结是{1, 6, 10, 11, 12, 17, 20, 22},将两个集结做走运算(intersection),结不美观是{1, 6, 11}。最后,年夜资料库中找出1、6、11对应的页面返回给用户就可以了。

作者:张洋

早期一些搜索引擎确实是基于近似的算法评价网页主要性的。这种评价算法看似依据充实、实现直不美观简单,但却很是轻易受到一种叫“Term Spam”的抨击袭击。