網絡搜索引擎排序算法研究進展

羅 武，方 逵，朱興輝

（湖南農業大學信息科學技術學院，湖南 長沙 410128）

隨著網絡技術的發展，互聯網查詢結果快速、準確的要求不斷提高，在使用搜索引擎檢索返回時，用戶往往只關心大量檢索結果的前幾頁的結果，而很靠后的檢索結果，被關注的機率微乎其微。用戶的這種瀏覽習慣使得搜索引擎的查準率備受關注，如何提高搜索引擎的查準率，給排序技術帶來了巨大的挑戰。檢索結果的排序效果直接影響到用戶能否方便地獲得所需的資源，同時也決定了用戶對該搜索引擎的滿意度[1]。按搜索引擎排序技術的發展歷程可將搜索引擎分為三個階段，現在正處于第二階段，同時正在向第三個階段搜索引擎發展[2]。

1 基于詞頻統計——詞位置加權的搜索引擎

利用關鍵詞在文檔中出現的頻率和位置排序是搜索引擎最早期排序的主要思想，其技術發展也最為成熟，是第一階段搜索引擎的主要排序技術，應用非常廣泛，至今仍是許多搜索引擎的核心排序技術。其基本原理是：關鍵詞在文檔中詞頻越高，出現的位置越重要，則被認為和檢索詞的相關性越好。

1.1 詞頻統計

文檔的詞頻是指查詢關鍵詞在文檔中出現的頻率。查詢關鍵詞詞頻在文檔中出現的頻率越高，其相關度越大。但當關鍵詞為常用詞時，使其對相關性判斷的意義非常小。TF/IDF很好的解決了這個問題。TF/IDF算法被認為是信息檢索中最重要的發明。TF（Term Frequency）：單文本詞匯頻率，用關鍵詞的次數除以網頁的總字數，其商稱為“關鍵詞的頻率”。IDF（Inverse Document Frequency）：逆文本頻率指數，其原理是，一個關鍵詞在N個網頁中出現過，那么N越大，此關鍵詞的權重越小，反之亦然。當關鍵詞為常用詞時，其權重極小，從而解決詞頻統計的缺陷。

1.2 詞位置加權

在搜索引擎中，主要針對網頁進行詞位置加權。所以，頁面版式信息的分析至關重要。通過對檢索關鍵詞在Web頁面中不同位置和版式，給予不同的權值，從而根據權值來確定所搜索結果與檢索關鍵詞相關程度。可以考慮的版式信息有：是否是標題，是否為關鍵詞，是否是正文，字體大小，是否加粗等等。同時，錨文本的信息也是非常重要的，它一般能精確的描述所指向的頁面的內容。

2 基于鏈接分析排序的第二代搜索引擎

鏈接分析排序的思想起源于文獻引文索引機制，即論文被引用的次數越多或被越權威的論文引用，其論文就越有價值。鏈接分析排序的思路與其相似，網頁被別的網頁引用的次數越多或被越權威的網頁引用，其價值就越大。被別的網頁引用的次數越多，說明該網頁越受歡迎，被越權威的網頁引用，說明該網頁質量越高。鏈接分析排序算法大體可以分為以下幾類：基于隨機漫游模型的，比如PageRank和Repution算法；基于概率模型的，如SALSA、PHITS；基于Hub和Authority相互加強模型的，如HITS及其變種；基于貝葉斯模型的，如貝葉斯算法及其簡化版本。所有的算法在實際應用中都結合傳統的內容分析技術進行了優化。本文主要介紹以下幾種經典排序算法：

2.1 PageRank算法

PageRank算法由斯坦福大學博士研究生Sergey Brin和Lwraence Page等提出的。PageRank算法是Google搜索引擎的核心排序算法，是Google成為全球最成功的搜索引擎的重要因素之一，同時開啟了鏈接分析研究的熱潮。

PageRank算法的基本思想是：頁面的重要程度用PageRank值來衡量，PageRank值主要體現在兩個方面：引用該頁面的頁面個數和引用該頁面的頁面重要程度。一個頁面P（A）被另一個頁面P（B）引用，可看成 P（B）推薦 P（A），P（B）將其重要程度（PageRank值）平均的分配P（B）所引用的所有頁面，所以越多頁面引用P（A），則越多的頁面分配PageRank值給 P（A），PageRank值也就越高，P（A）越重要。另外，P(B)越重要，它所引用的頁面能分配到的PageRank值就越多，P（A）的PageRank值也就越高，也就越重要。

其計算公式為：

PR（A）：頁面A的PageRank值；

d：阻尼系數，由于某些頁面沒有入鏈接或者出鏈接，無法計算PageRank值，為避免這個問題（即LinkSink問題），而提出的。阻尼系數常指定為0.85。

R（Pi）：頁面Pi的PageRank值；

C（Pi）：頁面鏈出的鏈接數量；

PageRank值的計算初始值相同，為了不忽視被重要網頁鏈接的網頁也是重要的這一重要因素，需要反復迭代運算，據文獻[3]的計算結果，需要進行10次以上的迭代后鏈接評價值趨于穩定，如此經過多次迭代，系統的PR值達到收斂。

PageRank是一個與查詢無關的靜態算法，因此所有網頁的PageRank值均可以通過離線計算獲得。這樣，減少了用戶檢索時需要的排序時間，極大地降低了查詢響應時間。但是PageRank存在兩個缺陷：首先PageRank算法嚴重歧視新加入的網頁，因為新的網頁的出鏈接和入鏈接通常都很少，PageRank值非常低。另外PageRank算法僅僅依靠外部鏈接數量和重要度來進行排名，而忽略了頁面的主題相關性，以至于一些主題不相關的網頁（如廣告頁面）獲得較大的PageRank值，從而影響了搜索結果的準確性。為此，各種主題相關算法紛紛涌現，其中以以下幾種算法最為典型。

2.2 Topic-Sensitive PageRank算法

由于最初PageRank算法中是沒有考慮主題相關因素的，斯坦福大學計算機科學系Taher Haveliwala提出了一種主題敏感（Topic-Sensitive）的PageRank算法解決了“主題漂流”問題。該算法考慮到有些頁面在某些領域被認為是重要的，但并不表示它在其它領域也是重要的。

網頁A鏈接網頁B，可以看作網頁A對網頁B的評分，如果網頁A與網頁B屬于相同主題，則可認為A對B的評分更可靠。因為A與B可形象的看作是同行，同行對同行的了解往往比不是同行的要多，所以同行的評分往往比不是同行的評分可靠。遺憾的是TSPR并沒有利用主題的相關性來提高鏈接得分的準確性[4]。

2.3 HillTop算法

HillTop是 Google的一個工程師 Bharat在2001年獲得的專利。HillTop是一種查詢相關性鏈接分析算法，克服了的PageRank的查詢無關性的缺點。HillTop算法認為具有相同主題的相關文檔鏈接對于搜索者會有更大的價值。在Hilltop中僅考慮那些用于引導人們瀏覽資源的專家頁面（Export Sources）。Hilltop在收到一個查詢請求時，首先根據查詢的主題計算出一列相關性最強的專家頁面，然后根據指向目標頁面的非從屬專家頁面的數量和相關性來對目標頁面進行排序。

HillTop算法確定網頁與搜索關鍵詞的匹配程度的基本排序過程取代了過分依靠PageRank的值去尋找那些權威頁面的方法，避免了許多想通過增加許多無效鏈接來提高網頁PageRank值的做弊方法。HillTop算法通過不同等級的評分確保了評價結果對關鍵詞的相關性，通過不同位置的評分確保了主題（行業）的相關性，通過可區分短語數防止了關鍵詞的堆砌。

但是，專家頁面的搜索和確定對算法起關鍵作用，專家頁面的質量對算法的準確性起著決定性作用，也就忽略了大多數非專家頁面的影響。專家頁面在互聯網中占的比例非常低（1.79%），無法代表互聯網全部網頁，所以HillTop存在一定的局限性。同時，不同于PageRank算法，HillTop算法的運算是在線運行的，對系統的響應時間產生極大的壓力。

2.4 HITS

HITS（Hyperlink Induced Topic Search）算法是Kleinberg在1998年提出的，是基于超鏈接分析排序算法中另一個最著名的算法之一。該算法按照超鏈接的方向，將網頁分成兩種類型的頁面：Authority頁面和Hub頁面。Authority頁面又稱權威頁面，是指與某個查詢關鍵詞和組合最相近的頁面，Hub頁面又稱目錄頁，該頁面的內容主要是大量指向Authority頁面的鏈接，它的主要功能就是把這些Authority頁面聯合在一起。對于Authority頁面P，當指向P的Hub頁面越多，質量越高，P的Authority值就越大；而對于Hub頁面H，當H指向的Authority的頁面越多，Authority頁面質量越高，H的Hub值就越大。對整個Web集合而言，Authority和Hub是相互依賴、相互促進，相互加強的關系。Authority和Hub之間相互優化的關系，即為HITS算法的基礎。

HITS基本思想是：算法根據一個網頁的入度（指向此網頁的超鏈接）和出度（從此網頁指向別的網頁）來衡量網頁的重要性。在限定范圍之后根據網頁的出度和入度建立一個矩陣，通過矩陣的迭代運算和定義收斂的閾值不斷對兩個向量Authority和Hub值進行更新直至收斂。

實驗數據表明，HITS的排名準確性要比PageRank高，HITS算法的設計符合網絡用戶評價網絡資源質量的普遍標準，因此能夠為用戶更好的利用網絡信息檢索工具訪問互聯網資源帶來便利。但卻存在以下缺陷：首先，HITS算法只計算主特征向量，處理不好主題漂移問題；其次，進行窄主題查詢時，可能產生主題泛化問題；第三，HITS算法可以說一種實驗性質的嘗試。它必須在網絡信息檢索系統進行面向內容的檢索操作之后，基于內容檢索的結果頁面及其直接相連的頁面之間的鏈接關系進行計算。盡管有人嘗試通過算法改進和專門設立鏈接結構計算服務器（Connectivity Server）等操作，可以實現一定程度的在線實時計算，但其計算代價仍然是不可接受的。

2.5 農業搜索引擎排序算法的思考

目前，國內的農業搜索引擎研究還處于剛剛起步階段，研究水平相對滯后，具有獨立創新性的研究特別少，對于排序算法，Allan Borodin曾指出沒有一種算法是完美的，在某些查詢下，結果可能很好，在另外的查詢下，結果可能很差[7]。所以，綜合模型的建立是必要的。農業搜索引擎的排序需解決網頁和農業主題的相關性問題，本文擬建立如下模型更新PageRank值：

Sim(A)= α*PR（A）+ β*R（A）；

其中：A為抓取的網頁，PR（A）表示的是A網頁的PageRank值，α，β為0-1之間的相關度系數，通常 α+β=1，且 β>α，sim（A）表示 A 網頁的綜合相關度，R（A）表示網頁和農業主題的相關性系數，其計算方法可以采取向量空間模型，利用余弦法計算。

網頁的排名還需要考慮其他因素，如網站的重要性（可由Alexa網站排名決定，網站的重要性越高，其網頁的價值越大，排名也就越靠前）、網頁的層次(越頂層，網頁越重要)及網頁更新的時間等因素。

綜合以上因素及Sim（A）的值，可建立綜合排序模型，如下：

其中：N：排序因數個數；Wfactor：該因數的值；Weightfactor：該因數的權重；

以上排序模型綜合影響網頁排序的各種因素，其排序效果有待實驗的檢驗并完善，算法為離線計算，對實時查詢的效率無影響。

3 基于智能化排序的第三代搜索引擎

排序算法在搜索引擎中具有特別重要的地位，目前許多搜索引擎都在進一步研究新的排序方法，來提升用戶的滿意度。但目前第二代搜索引擎有著兩個不足之處，在此背景下，基于智能化排序的第三代搜索引擎也就應運而生。

3.1 相關性問題

相關性是指檢索詞和頁面的相關程度。由于語言復雜，僅僅通過鏈接分析及網頁的表面特征來判斷檢索詞與頁面的相關性是片面的。例如：檢索“稻瘟病”，有網頁是介紹水稻病蟲害信息的，但文中沒有“稻瘟病”這個詞，搜索引擎根本無法檢索到。正是以上原因，造成大量的搜索引擎作弊現象無法解決。

解決相關性的的方法應該是增加語意理解，分析檢索關鍵詞與網頁的相關程度，相關性分析越精準，用戶的搜索效果就會越好。同時，相關性低的網頁可以剔除，有效地防止搜索引擎作弊現象。檢索關鍵詞和網頁的相關性是在線運行的，會給系統相應時間很大的壓力，可以采用分布式體系結構可以提高系統規模和性能。

3.2 搜索結果的單一化問題[5]

在搜索引擎上，任何人搜索同一個詞的結果都是一樣。這并不能滿足用戶的需求。不同的用戶對檢索的結果要求是不一樣的。例如：普通的農民檢索“稻瘟病”，只是想得到稻瘟病的相關信息以及防治方法，但農業專家或科技工作者可能會想得到稻瘟病相關的論文。

解決搜索結果單一的方法是提供個性化服務，實現智能搜索[6]。通過Web數據挖掘，建立用戶模型(如用戶背景、興趣、行為、風格)，提供個性化服務。

4 討論

通過對以上算法分析，可以看出，每一種算法，在有著各自的優點的同時，都有缺陷，均有待進一步加以研究和完善。而目前現有的所有引擎排序算法并不能很好的滿足用戶的需求，搜索引擎將注定向智能化、個性化的方向發展。相關性問題的解決需要完善的自然語言處理技術，而個性化服務的提供需要記錄龐大訪問者信息和復雜的計算。相信這兩個問題的解決，在更好地滿足用戶需求的同時，將會給搜索引擎技術帶來巨大的發展。

[1]Witten I，Moffat A.Managing Gigabytes[M].San Francisco：Morgan Kaufumann Publishers，1999.20-30.

[2]陳朝偉.搜索引擎的排序技術及其在計算機網絡上的應用[J].科技經濟市場，2006，（6）：28.

[3]張映海，何中市，陳永鋒.搜索引擎結果中Web文檔的排序研究[J].計算機與數字工程，2007，35(2)：126-129.

[4]李紹華，高文宇.搜索引擎頁面排序算法研究綜述[J].計算機應用研究，2007，24（6）：4-7.

[5]袁占亭，張秋余，董建設.智能信息搜索系統中對搜索結果的排序策略[J].計算機工程與應用，2004，40（2）：148-150.

[6]李曉明，閆宏飛，王繼民.搜索引擎——原理、技術與系統[M].北京：科學出版社，2004.189-196.