Google的排名算法分析

第20卷第2期景德镇高专学报Vol. 20 No.22005年6月Journal of Jingdezhen CollegeJun.2005Google的排名算法分析陈芸°(江苏信息职业技术学院计算机系江苏无锡214101 )摘要:介绍了Google的排名算法PageRank的原理及其具体实现,并对未来搜索引擎的排名算法研究进行了展望。关键词:搜索引擎;PageRank;Google中图分类号:TP 301.6文献标识码:A.文章编号:1008 - 8458(2005)02 - 0043-02网页u的PageRank值,C为规范化因子,作用是保证所有网0概述页的PageRank总和为常量。随着搜索引擎技术的发展,Google最终凭借其强大的功R(a)=cZNOyR( w(1能与简单的界面成为目前的搜索之王。Google 拥有多项专利技术，其中PageRank 算法是关键技术之一,它奠定公式(1)是递归定义的,可以开始于任何等级的集合,反Google强大检索及提供各种特色功能的基础。PageRank技复迭代直到汇聚一点。图1显示了等级在页面间的传播。术是Google检索结果的一种排序算法，中文通常译为页面所有的网页的PageRank值都可以根据其他网页的PageR-级别或页面等级，根据这个算法，Google认为每个网页都ank值和链接的数量来计算得到，即所有链接到它的网页的有一个反映其重要性的值，值越高表明其页面级别越高，即PageRank值除以各自向外的链接数的商进行求和。根据公式(1)，-个网页的链入数量越多、这些链入网页网页越重要。的PageRank 值越高、这些链入网页本身的链出数量越少，1基本原理则该网页的PageRank 值越高。PageRank的基本思想主要基于“从许多优质的网页链.10050|53接过来的网页，必定还是优质网页”的回归关系,来判定所有3网页的重要性。,当从网页A链接到网页B时,就认为”网页A投了网页B一票”,增加了网页B的重要性。最后根据网页的得票数评定其重要性,以此来帮助实现排序算法的国。350▼优化,而这个重要性的量化指标就是PageRank值。在实际计算网页的PageRank值时,Google还考虑到网页A的所有链入网页(链接到某网页的其它网页称为该网PageRank技术根据网页之间的链接结构对网页的重要页的链入网页)对它的推荐能力(即由于它们对网页A的链.性进行客观的评价，并将网页的PageRank值应用于检索结接，使人们认为网页A的重要程度)和推荐程度(即它们认果的排序。这样，PageRank 技术在很大程度上避免和减少为网页A的重要程度)。一个网页本身的PageRank值越了人为因素，客观地将最恰当的检索结果呈现给用户。高，则它对其链出网页(从某个网页链出的网页称为该网页的链出网页)的推荐能力就越大;一个网页的链出网页越2PageRank的计算及其具体实现少，那么它对其中一个链出网页的推荐程度就越高。也即假设网页A有网页T,T...T.的链接指向它。若把一篇文献被其它文献引用越多，则文献质量就越高。根据上面的基本原理,L. Page 等给出PageRank 的简公式中国煤化工R ank算法计算为:R(ui) +.+ R(T,)N(T,))单定义如公式(1):令u为一个网页，Nu表示从网页。向外MYHCNMHG'的链接数目，Bu表示链接到网页u的网页集合, R(u)表示①收稿日期:2005-01-12作者简介:陈芸(1974-),女,汉族,广东揭阳人,硕土,讲师。景德镇高专学报2005年6月T]是链点指向网页T的网页; R (TI)是网页Tl的网接数(非零要素数)。这样形成的行列被称为“推移概率行页级别PageRank的值(i=1,2,..n);N(T1)是指网页.列”,含有N个概率变量,各个行矢量表示状态之间的推移概T,的链出网页的数量(i= 1, 2, . ; C取值范围是0<率。倒置的理由是,PageRank并非重视链接到多少页面,而C<1，通常取0185; R(T.)C(T)为链接指向网页A的网是重视被多少页面链接。页T投与网页A的网页级别值，亦称M iniPageRank。3结束语根据以上公式，一个网页的链入数量越多,链出数量越少，则该网页的PageRank值越高。Google给每--个网页都PageRank是集页面关键词关联度和链接普遍度为一体赋予一个初始PageR ank值，然后根据PageRank算法计算的综合性排名算法,但是其技术本身也并不是十全十美的，其PageR ank值。算法的具体实现可以利用行列阵的形式Google还存在着许多问题,搜索引擎的完善与发展还有很来表达链接关系。从页面i链接到另一张页面j的时,将其长的路要走,研究PageRank是为了能在此基础上提出更有成分定义为1,反之则定义为0。即行列阵A中的元素的值创意的排序算法。同时,更多新技术的应用也将会给搜索引为:擎技术带来新的活力。a, =1(从页面i向页面j有链接的情况)a=0(从页面i向页面j没有链接的情况)参考文献:若存在N个页面,则该行列式成为NX N的方阵。因[1] L. Page，s. Brin，R. Motwani，T. Winograd. The PageR-此可以把Web的链接关系看做是采用了邻接关系有向图表ank Citation Rank2ing，January, 1998. .s。只要建立了链接,就应该有邻接关系。PageRank中的2] Taher H. Haveliwala, . Efficient Computation of PageRank ,行列阵是把这个邻接行列倒置后(行和列互换),为了将各列Stanford Technical Report, 1999.矢量的总和变成1 (全概率)，把各个列矢量除以各自的链Analysis Of The Google Rank AlgorithmCHEN Yun(Department of computer, JiangSu Information Technology College，Wuxi 214101)Abstract :This paper introduces the theory and implementation of Page Rank algorthms. Then ，it covers an initial study on thefuture directions for Search engine's rank algorithms.Keywords : Search engine ; PageRank; Google米米业业****业*业**业*业**业业**业***业业*业*业******业**业*业*业业业ψ(上接第42页)ty模板引擎。践中,被广为使用。4结语3. 2.2 JavaServer Faces(JSF) .JSF是以Web用户界面为侧重点的MVC应用框架,目开发一个企业级的J2EE架构的Web应用程序是一个的是通过对视图的组件化处理,进-步丰富Web用户界面非常庞大的工程,而且尤其是在开发的过程中用户需求的变的表现形式,并提供可视化及工具支持。JSF的一大特点是化.代码的复用、开发队伍的协调等等。都要求我们在开发将组件类与组建的表现技术分离,从而不把开发者局限在某之初就必须选择好一个好的开发模式。MVC 模式就提供了.种特定的脚本技术或标记语言上。这样一种模式,在开发实践中证明,按照MVC模式将Web3.2.3 WebWork应用分解成模型一视图-控制三个部分。将不同功能的代是一个开源的MVC应用框架,它基于命令设计模式，码分离出来,形成多个组件,并结合一些常用的应用框架,可力图将用户动作建模为不依赖于Servlet API 的命令对象。以做到事半功倍的效果。此外,WebWork不仅提供自己的JSP标签库,还支持Veloci-The Application of MVC Design Model in JIEE Software StructureHU Zhi - gangCHEN Zhi - gang(1. Information and Engineering College，Zhongnan University ,Changsha,4 10083 ;2. Computer Center, Jingdezhen College,中国煤化工Abstret: In the process of the development of large type of distributive :YHC N M H Gw to reduce the complexityof the development and increase the robustness and reuse of softwares. It is a common solution to resolve the complex softwarestructure into several layers. MVC Model is widely used,for it has the properties of separating the front and back stand andhaving no relation with platform. This present article discusses something about the application of MVC design model in JIEEsoftware structure.Key words: design model;JIEE software structure ;distributive system; MVC model