Google的排名算法分析

第20卷第2期景德鎮高專(zhuān)學(xué)報Vol. 20 No.22005年6月Journal of Jingdezhen CollegeJun.2005Google的排名算法分析陳蕓°(江蘇信息職業(yè)技術(shù)學(xué)院計算機系江蘇無(wú)錫214101 )摘要:介紹了Google的排名算法PageRank的原理及其具體實(shí)現,并對未來(lái)搜索引擎的排名算法研究進(jìn)行了展望。關(guān)鍵詞:搜索引擎;PageRank;Google中圖分類(lèi)號:TP 301.6文獻標識碼:A.文章編號:1008 - 8458(2005)02 - 0043-02網(wǎng)頁(yè)u的PageRank值,C為規范化因子,作用是保證所有網(wǎng)0概述頁(yè)的PageRank總和為常量。隨著(zhù)搜索引擎技術(shù)的發(fā)展,Google最終憑借其強大的功R(a)=cZNOyR( w(1能與簡(jiǎn)單的界面成為目前的搜索之王。Google 擁有多項專(zhuān)利技術(shù)，其中PageRank 算法是關(guān)鍵技術(shù)之一,它奠定公式(1)是遞歸定義的,可以開(kāi)始于任何等級的集合,反Google強大檢索及提供各種特色功能的基礎。PageRank技復迭代直到匯聚一點(diǎn)。圖1顯示了等級在頁(yè)面間的傳播。術(shù)是Google檢索結果的一種排序算法，中文通常譯為頁(yè)面所有的網(wǎng)頁(yè)的PageRank值都可以根據其他網(wǎng)頁(yè)的PageR-級別或頁(yè)面等級，根據這個(gè)算法，Google認為每個(gè)網(wǎng)頁(yè)都ank值和鏈接的數量來(lái)計算得到，即所有鏈接到它的網(wǎng)頁(yè)的有一個(gè)反映其重要性的值，值越高表明其頁(yè)面級別越高，即PageRank值除以各自向外的鏈接數的商進(jìn)行求和。根據公式(1)，-個(gè)網(wǎng)頁(yè)的鏈入數量越多、這些鏈入網(wǎng)頁(yè)網(wǎng)頁(yè)越重要。的PageRank 值越高、這些鏈入網(wǎng)頁(yè)本身的鏈出數量越少，1基本原理則該網(wǎng)頁(yè)的PageRank 值越高。PageRank的基本思想主要基于“從許多優(yōu)質(zhì)的網(wǎng)頁(yè)鏈.10050|53接過(guò)來(lái)的網(wǎng)頁(yè)，必定還是優(yōu)質(zhì)網(wǎng)頁(yè)”的回歸關(guān)系,來(lái)判定所有3網(wǎng)頁(yè)的重要性。,當從網(wǎng)頁(yè)A鏈接到網(wǎng)頁(yè)B時(shí),就認為”網(wǎng)頁(yè)A投了網(wǎng)頁(yè)B一票”,增加了網(wǎng)頁(yè)B的重要性。最后根據網(wǎng)頁(yè)的得票數評定其重要性,以此來(lái)幫助實(shí)現排序算法的國。350▼優(yōu)化,而這個(gè)重要性的量化指標就是PageRank值。在實(shí)際計算網(wǎng)頁(yè)的PageRank值時(shí),Google還考慮到網(wǎng)頁(yè)A的所有鏈入網(wǎng)頁(yè)(鏈接到某網(wǎng)頁(yè)的其它網(wǎng)頁(yè)稱(chēng)為該網(wǎng)PageRank技術(shù)根據網(wǎng)頁(yè)之間的鏈接結構對網(wǎng)頁(yè)的重要頁(yè)的鏈入網(wǎng)頁(yè))對它的推薦能力(即由于它們對網(wǎng)頁(yè)A的鏈.性進(jìn)行客觀(guān)的評價(jià)，并將網(wǎng)頁(yè)的PageRank值應用于檢索結接，使人們認為網(wǎng)頁(yè)A的重要程度)和推薦程度(即它們認果的排序。這樣，PageRank 技術(shù)在很大程度上避免和減少為網(wǎng)頁(yè)A的重要程度)。一個(gè)網(wǎng)頁(yè)本身的PageRank值越了人為因素，客觀(guān)地將最恰當的檢索結果呈現給用戶(hù)。高，則它對其鏈出網(wǎng)頁(yè)(從某個(gè)網(wǎng)頁(yè)鏈出的網(wǎng)頁(yè)稱(chēng)為該網(wǎng)頁(yè)的鏈出網(wǎng)頁(yè))的推薦能力就越大;一個(gè)網(wǎng)頁(yè)的鏈出網(wǎng)頁(yè)越2PageRank的計算及其具體實(shí)現少，那么它對其中一個(gè)鏈出網(wǎng)頁(yè)的推薦程度就越高。也即假設網(wǎng)頁(yè)A有網(wǎng)頁(yè)T,T...T.的鏈接指向它。若把一篇文獻被其它文獻引用越多，則文獻質(zhì)量就越高。根據上面的基本原理,L. Page 等給出PageRank 的簡(jiǎn)公式中國煤化工R ank算法計算為:R(ui) +.+ R(T,)N(T,))單定義如公式(1):令u為一個(gè)網(wǎng)頁(yè)，Nu表示從網(wǎng)頁(yè)。向外MYHCNMHG'的鏈接數目，Bu表示鏈接到網(wǎng)頁(yè)u的網(wǎng)頁(yè)集合, R(u)表示①收稿日期:2005-01-12作者簡(jiǎn)介:陳蕓(1974-),女,漢族,廣東揭陽(yáng)人,碩土,講師。景德鎮高專(zhuān)學(xué)報2005年6月T]是鏈點(diǎn)指向網(wǎng)頁(yè)T的網(wǎng)頁(yè); R (TI)是網(wǎng)頁(yè)Tl的網(wǎng)接數(非零要素數)。這樣形成的行列被稱(chēng)為“推移概率行頁(yè)級別PageRank的值(i=1,2,..n);N(T1)是指網(wǎng)頁(yè).列”,含有N個(gè)概率變量,各個(gè)行矢量表示狀態(tài)之間的推移概T,的鏈出網(wǎng)頁(yè)的數量(i= 1, 2, . ; C取值范圍是0<率。倒置的理由是,PageRank并非重視鏈接到多少頁(yè)面,而C<1，通常取0185; R(T.)C(T)為鏈接指向網(wǎng)頁(yè)A的網(wǎng)是重視被多少頁(yè)面鏈接。頁(yè)T投與網(wǎng)頁(yè)A的網(wǎng)頁(yè)級別值，亦稱(chēng)M iniPageRank。3結束語(yǔ)根據以上公式，一個(gè)網(wǎng)頁(yè)的鏈入數量越多,鏈出數量越少，則該網(wǎng)頁(yè)的PageRank值越高。Google給每--個(gè)網(wǎng)頁(yè)都PageRank是集頁(yè)面關(guān)鍵詞關(guān)聯(lián)度和鏈接普遍度為一體賦予一個(gè)初始PageR ank值，然后根據PageRank算法計算的綜合性排名算法,但是其技術(shù)本身也并不是十全十美的，其PageR ank值。算法的具體實(shí)現可以利用行列陣的形式Google還存在著(zhù)許多問(wèn)題,搜索引擎的完善與發(fā)展還有很來(lái)表達鏈接關(guān)系。從頁(yè)面i鏈接到另一張頁(yè)面j的時(shí),將其長(cháng)的路要走,研究PageRank是為了能在此基礎上提出更有成分定義為1,反之則定義為0。即行列陣A中的元素的值創(chuàng )意的排序算法。同時(shí),更多新技術(shù)的應用也將會(huì )給搜索引為:擎技術(shù)帶來(lái)新的活力。a, =1(從頁(yè)面i向頁(yè)面j有鏈接的情況)a=0(從頁(yè)面i向頁(yè)面j沒(méi)有鏈接的情況)參考文獻:若存在N個(gè)頁(yè)面,則該行列式成為NX N的方陣。因[1] L. Page，s. Brin，R. Motwani，T. Winograd. The PageR-此可以把Web的鏈接關(guān)系看做是采用了鄰接關(guān)系有向圖表ank Citation Rank2ing，January, 1998. .s。只要建立了鏈接,就應該有鄰接關(guān)系。PageRank中的2] Taher H. Haveliwala, . Efficient Computation of PageRank ,行列陣是把這個(gè)鄰接行列倒置后(行和列互換),為了將各列Stanford Technical Report, 1999.矢量的總和變成1 (全概率)，把各個(gè)列矢量除以各自的鏈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米米業(yè)業(yè)****業(yè)*業(yè)**業(yè)*業(yè)**業(yè)業(yè)**業(yè)***業(yè)業(yè)*業(yè)*業(yè)******業(yè)**業(yè)*業(yè)*業(yè)業(yè)業(yè)ψ(上接第42頁(yè))ty模板引擎。踐中,被廣為使用。4結語(yǔ)3. 2.2 JavaServer Faces(JSF) .JSF是以Web用戶(hù)界面為側重點(diǎn)的MVC應用框架,目開(kāi)發(fā)一個(gè)企業(yè)級的J2EE架構的Web應用程序是一個(gè)的是通過(guò)對視圖的組件化處理,進(jìn)-步豐富Web用戶(hù)界面非常龐大的工程,而且尤其是在開(kāi)發(fā)的過(guò)程中用戶(hù)需求的變的表現形式,并提供可視化及工具支持。JSF的一大特點(diǎn)是化.代碼的復用、開(kāi)發(fā)隊伍的協(xié)調等等。都要求我們在開(kāi)發(fā)將組件類(lèi)與組建的表現技術(shù)分離,從而不把開(kāi)發(fā)者局限在某之初就必須選擇好一個(gè)好的開(kāi)發(fā)模式。MVC 模式就提供了.種特定的腳本技術(shù)或標記語(yǔ)言上。這樣一種模式,在開(kāi)發(fā)實(shí)踐中證明,按照MVC模式將Web3.2.3 WebWork應用分解成模型一視圖-控制三個(gè)部分。將不同功能的代是一個(gè)開(kāi)源的MVC應用框架,它基于命令設計模式，碼分離出來(lái),形成多個(gè)組件,并結合一些常用的應用框架,可力圖將用戶(hù)動(dòng)作建模為不依賴(lài)于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