PageRank算法解剖-揭开搜索引擎背后的魔力 (PageRank是( )公司的专有算法)
简介
PageRank 算法是由谷歌创始人之一拉里·佩奇(Larry Page)命名的一种衡量网站页面重要性的方法。根据谷歌的说法,PageRank 通过计算页面链接的数量和质量来粗略估计分析网站的重要性。基本假设是:更重要的页面往往更多地被其他页面引用,或其他页面中会更多地加入通向该页面的超链接。PageRank 算法原理
PageRank 算法是一种链接分析算法,它通过对超链接集合(如万维网)中的元素实现数值权重赋值,实现衡量集合范围内某一元素的相关重要性的目的。该算法可以应用于带有相互引用或者引用关系的任何实体集合。 算法赋值给任何给定元素 E 的数值权重称为 E 的 PageRank,并且用 PR(E) 表示。PageRank 的结果来源于一种基于图论的数学算法。它将万维网上所有的网页视作节点,而将超链接视作边,并且考虑到了一些热门的网站。每个节点的权重值表示对应的页面的重要度。通向该网页的超链接称做对该网页的投票,每个网页的权重值大小被递归地定义,依托于所有链接该页面的页面的权重值。例如,一个被很多页面的链接的页面将会拥有较高的权重值。PageRank 算法的发展和应用
自拉里·佩奇和谢尔盖·布林(谷歌的另外一位创始人)的首篇本文发表以来,已经有许多关于 PageRank 的学术本文被发表。实际上,PageRank 概念可能很容易受到利用。相关的研究会关注那些因受到影响而出现错误的 PageRank 结果,以找到一种有效地避免其 PageRank 被错误影响的方法(如忽略部分错误的链接)。 PageRank 算法中的点击算法是由乔恩·克莱因伯格提出的。而其他的基于链接的网页排名算法有克莱因伯格发明的 HITS 算法、IBM CLEVER Project、TRank 算法以及 Hummingbird 算法等等。结语
虽然 PageRank 算法不再是谷歌用于排序搜索结果的唯一算法,但它是谷歌公司使用的第一个排序搜索算法,也是最著名的算法。截止至 2019 年 9 月 24 日,PageRank 及其所有的相关专利已过期。 PageRank 算法的发展和应用仍在不断推进,为搜索引擎排名提供了重要的参考依据。PageRank 算法的出现和应用,对于搜索引擎的发展和网页排名的提升起到了重要的作用。在未来,随着技术的不断进步和算法的不断优化,PageRank 算法将继续发挥重要的作用,为用户提供更加精准和有效的搜索结果。百度网站的开发技术
主要是PR技术以及匹配技术。
最著名的并且获得了专利的当然就是google的PR技术
家可能听说过,Google革命性的发明是它名为“PageRank”的网页排名算法,这项技术彻底解决了搜索结果排序的问题。其实最先试图给互联网上的众多网站排序的并不是Google。Yahoo!公司最初第一个用目录分类的方式让用户通过互联网检索信息,但由于当时计算机容量和速度的限制,当时的Yahoo!和同时代的其它搜索引擎都存在一个共同的问题:收录的网页太少,而且只能对网页中常见内容相关的实际用词进行索引。那时,用户很难找到很相关信息。我记得1999年以前查找一篇论文,要换好几个搜索引擎。后来DEC公司开发了AltaVista搜索引擎,只用一台ALPHA服务器,却收录了比以往引擎都多的网页,而且对里面的每个词进行索引。AltaVista虽然让用户搜索到大量结果,但大部分结果却与查询不太相关,有时找想看的网页需要翻好几页。所以最初的AltaVista在一定程度上解决了覆盖率的问题,但不能很好地对结果进行排序。
Google的“PageRank”(网页排名)是怎么回事呢?其实简单说就是民主表决。打个比方,假如我们要找李开复博士,有一百个人举手说自己是李开复。那么谁是真的呢?也许有好几个真的,但即使如此谁又是大家真正想找的呢?:-)如果大家都说在Google公司的那个是真的,那么他就是真的。
在互联网上,如果一个网页被很多其它很多网页所链接,说明它受到普遍的承认和信赖,那么它的排名就高。这就是PageRank的核心思想。当然Google的PageRank算法实际上要复杂得多。比如说,对来自不同网页的链接对待不同,本身网页排名高的链接更可靠,于是给这些链接予较大的权重。PageRank考虑了这个因素,可是现在问题又来了,计算搜索结果的网页排名过程中需要用到本身网页的排名,这不成了先有鸡还是先有蛋的问题了吗?
Google的两个创始人拉里?佩奇(LarryPage)和谢尔盖?布林(SergeyBrin)把这个问题变成了一个二维矩阵相乘的问题,并且用迭代的方法解决了这个问题。他们先假定所有网页的排名是相同的,并且根据这个初始值,算出各个网页的第一次迭代排名,然后再根据第一次迭代排名算出第二次的排名。他们两人从理论上证明了不论初始值如何选取,这种算法都保证了网页排名的估计值能收敛到他们的真实值。值得一提的事,这种算法是完全没有任何人工干预的。
理论问题解决了,又遇到实际问题。因为互联网上网页的数量是巨大的,上面提到的二维矩阵从理论上讲有网页数目平方之多个元素。如果我们假定有十亿个网页,那么这个矩阵就有一百亿亿个元素。这样大的矩阵相乘,计算量是非常大的。拉里和谢尔盖两人利用稀疏矩阵计算的技巧,大大的简化了计算量,并实现了这个网页排名算法。今天Google的工程师把这个算法移植到并行的计算机中,进一步缩短了计算时间,使网页更新的周期比以前短了许多。
我来Google后,拉里(Larry)在和我们几个新员工座谈时,讲起他当年和谢尔盖(Sergey)是怎么想到网页排名算法的。他说:当时我们觉得整个互联网就像一张大的图(Graph),每个网站就像一个节点,而每个网页的链接就像一个弧。我想,互联网可以用一个图或者矩阵描述,我也许可以在用这个发现做个博士论文。他和谢尔盖就这样发明了PageRank的算法。
网页排名的高明之处在于它把整个互联网当作了一个整体对待。它无意识中符合了系统论的观点。相比之下,以前的信息检索大多把每一个网页当作独立的个体对待,很多人当初只注意了网页内容和查询语句的相关性,忽略了网页之间的关系。
今天,Google搜索引擎比最初的复杂、完善了许多。但是网页排名在Google所有算法中依然是至关重要的。在学术界,这个算法被公认为是文献检索中最大的贡献之一,并且被很多大学引入了信息检索课程(InformationRetrieval)的教程。
1、抓取网页
每个独立的搜索引擎都有自己的网页抓取程序(spider)。Spider顺着网页中的超链接,连续地抓取网页。由于互联网中超链接的应用很普遍,理论上,从一定范围的网页出发,就能搜集到绝大多数的网页。
2、处理网页
搜索引擎抓到网页后,还要做大量的预处理工作,才能提供检索服务。其中,最重要的就是提取关键词,建立索引文件。其他还包括去除重复网页、分析超链接、计算网页的重要度。
3、提供检索服务
用户输入关键词进行检索,搜索引擎从索引数据库中找到匹配该关键词的网页;为了用户便于判断,除了网页标题和URL外,还会提供一段来自网页的摘要以及其他信息。
搜索引擎的排序算法都有哪些是怎么实现的
搜索引擎的排序算法:
![PageRank算法](https://tyye.cn/zb_users/theme/tpure/style/images/lazyload.png)
词频统计——词位置加权的搜索引擎
关键词在文档中词频越高,出现的位置越重要,则被认为和检索词的相关性越好。
1)词频统计2)词位置加权2.2基于链接分析排序的第二代搜索引擎1)PageRank算法PageRank算法的基本思想是:页面的重要程度用PageRank值来衡量,PageRank值主要体现在两个方面:引用该页面的页面个数和引用该页面的页面重要程度。其计算公式为:PR(A):页面A的PageRank值;d:阻尼系数,由于某些页面没有入链接或者出链接,无法计算PageRank值,为避免这个问题(即LinkSink问题),而提出的。阻尼系数常指定为0.85。R(Pi):页面Pi的PageRank值;C(Pi):页面链出的链接数量;
2)Topic-Sensitive PageRank算法
3)HillTop算法HillTop算法通过不同等级的评分确保了评价结果对关键词的相关性,通过不同位置的评分确保了主题(行业)的相关性,通过可区分短语数防止了关键词的堆砌。4)HITSHITS算法只计算主特征向量,处理不好主题漂移问题;其次,进行窄主题查询时,可能产生主题泛化问题;因此可据LIngmao了解看待,找寻适合的算法
免责声明:本文转载或采集自网络,版权归原作者所有。本网站刊发此文旨在传递更多信息,并不代表本网赞同其观点和对其真实性负责。如涉及版权、内容等问题,请联系本网,我们将在第一时间删除。同时,本网站不对所刊发内容的准确性、真实性、完整性、及时性、原创性等进行保证,请读者仅作参考,并请自行核实相关内容。对于因使用或依赖本文内容所产生的任何直接或间接损失,本网站不承担任何责任。