網(wǎng)絡(luò)搜索引擎排序算法研究進(jìn)展

羅 武，方 逵，朱興輝

（湖南農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，湖南 長沙 410128）

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

1 基于詞頻統(tǒng)計——詞位置加權(quán)的搜索引擎

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

1.1 詞頻統(tǒng)計

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

1.2 詞位置加權(quán)

在搜索引擎中，主要針對網(wǎng)頁進(jìn)行詞位置加權(quán)。所以，頁面版式信息的分析至關(guān)重要。通過對檢索關(guān)鍵詞在Web頁面中不同位置和版式，給予不同的權(quán)值，從而根據(jù)權(quán)值來確定所搜索結(jié)果與檢索關(guān)鍵詞相關(guān)程度?？梢钥紤]的版式信息有：是否是標(biāo)題，是否為關(guān)鍵詞，是否是正文，字體大小，是否加粗等等。同時，錨文本的信息也是非常重要的，它一般能精確的描述所指向的頁面的內(nèi)容。

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

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

2.1 PageRank算法

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

PageRank算法的基本思想是：頁面的重要程度用PageRank值來衡量，PageRank值主要體現(xiàn)在兩個方面：引用該頁面的頁面?zhèn)€數(shù)和引用該頁面的頁面重要程度。一個頁面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：阻尼系數(shù)，由于某些頁面沒有入鏈接或者出鏈接，無法計算PageRank值，為避免這個問題（即LinkSink問題），而提出的。阻尼系數(shù)常指定為0.85。

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

C（Pi）：頁面鏈出的鏈接數(shù)量；

PageRank值的計算初始值相同，為了不忽視被重要網(wǎng)頁鏈接的網(wǎng)頁也是重要的這一重要因素，需要反復(fù)迭代運算，據(jù)文獻(xiàn)[3]的計算結(jié)果，需要進(jìn)行10次以上的迭代后鏈接評價值趨于穩(wěn)定，如此經(jīng)過多次迭代，系統(tǒng)的PR值達(dá)到收斂。

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

2.2 Topic-Sensitive PageRank算法

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

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

2.3 HillTop算法

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

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

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

2.4 HITS

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

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

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

2.5 農(nóng)業(yè)搜索引擎排序算法的思考

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

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

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

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

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

其中：N：排序因數(shù)個數(shù)；Wfactor：該因數(shù)的值；Weightfactor：該因數(shù)的權(quán)重；

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

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

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

3.1 相關(guān)性問題

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

解決相關(guān)性的的方法應(yīng)該是增加語意理解，分析檢索關(guān)鍵詞與網(wǎng)頁的相關(guān)程度，相關(guān)性分析越精準(zhǔn)，用戶的搜索效果就會越好。同時，相關(guān)性低的網(wǎng)頁可以剔除，有效地防止搜索引擎作弊現(xiàn)象。檢索關(guān)鍵詞和網(wǎng)頁的相關(guān)性是在線運行的，會給系統(tǒng)相應(yīng)時間很大的壓力，可以采用分布式體系結(jié)構(gòu)可以提高系統(tǒng)規(guī)模和性能。

3.2 搜索結(jié)果的單一化問題[5]

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

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

4 討論

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

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

[2]陳朝偉.搜索引擎的排序技術(shù)及其在計算機(jī)網(wǎng)絡(luò)上的應(yīng)用[J].科技經(jīng)濟(jì)市場，2006，（6）：28.

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

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

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

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