劉興強(qiáng)　楊桃　范云琳　陳婷婷　閆自金　宋紹云

摘要：近年來(lái)，Intranet不斷飛速發(fā)展，導(dǎo)致信息量趨于龐大。于是如何讓用戶查找到自己想要的信息成為Intranet搜索引擎的一個(gè)難題。關(guān)于這個(gè)問題，它將對(duì)幾種經(jīng)典的Intranet搜索排序算法進(jìn)行分析、比較。希望在以后的開發(fā)中可以以它為參照，進(jìn)行相關(guān)算法的改進(jìn)，盡可能的讓算法更接近完美，使搜索結(jié)果更能符合用戶的需求。

關(guān)鍵詞：搜索引擎；算法；原理；特點(diǎn)；PageRank；HITS

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）01-0120-03

1 概述

隨著社會(huì)的發(fā)展，各種信息的飛速增長(zhǎng)，搜索引擎成為了人們查找信息的首選工具。搜索引擎的研究，國(guó)外比中國(guó)要早近10年，但國(guó)內(nèi)還是陸續(xù)涌現(xiàn)出優(yōu)秀的搜索引擎，如：百度、中搜。伴隨著搜索技術(shù)的成熟，Intranet搜索引擎將成為獲取信息、掌握知識(shí)的利器。而面對(duì)云信息時(shí)代的到來(lái)，傳統(tǒng)的搜索引擎提供的服務(wù)已不能滿足人們?nèi)找嬖鲩L(zhǎng)的對(duì)個(gè)性化服務(wù)的需要。因此，搜索引擎還將有較大的發(fā)展和進(jìn)步空間，檢索功能將更趨向于集成化和更具親和力、更顯人性化。

算法是搜索引擎的靈魂，要改善搜索服務(wù)實(shí)質(zhì)上就是改進(jìn)算法。要想在現(xiàn)有的算法基礎(chǔ)上進(jìn)一步改進(jìn)，就要先了解它。該文的先對(duì)兩種經(jīng)典算法PageRank和HITS進(jìn)行了分析和比較，并指出它們各自的優(yōu)缺點(diǎn)。還對(duì)這兩種算法的延伸算法Hilltop、SALSA進(jìn)行了介紹，他們?nèi)诤狭薍ITS和PageRank兩個(gè)算法的基本思想。最后指出了當(dāng)前算法仍有的問題和改進(jìn)方向。

2 兩種經(jīng)典的算法

PageRank算法和HITS算法都是比較經(jīng)典的搜索引擎算法。許多算法都是在它們的基礎(chǔ)上進(jìn)行改進(jìn)的，是搜索引擎算法分析的兩個(gè)最基礎(chǔ)且最重要的算法。

2.1 PageRank算法

PageRank算法是在1998年由Sergey Brin和Lawrence Page提出的[1]。該算法是從“被許多好的網(wǎng)頁(yè)引用的網(wǎng)頁(yè)一定是好網(wǎng)頁(yè)”的關(guān)系出發(fā)，來(lái)確定一個(gè)網(wǎng)頁(yè)的質(zhì)量。當(dāng)一個(gè)網(wǎng)頁(yè)被很多其他網(wǎng)頁(yè)包含，那么該網(wǎng)頁(yè)很可能是一個(gè)高質(zhì)量網(wǎng)頁(yè)；然而假如有一個(gè)網(wǎng)頁(yè)它的鏈接沒有被許多網(wǎng)頁(yè)頁(yè)所包含，而它卻擁有一個(gè)優(yōu)質(zhì)網(wǎng)頁(yè)的鏈接指向，則它或許也是高質(zhì)量網(wǎng)頁(yè)； 一個(gè)網(wǎng)頁(yè)的重要性值被平均分配并傳遞到它所引用的所有網(wǎng)頁(yè)中。當(dāng)用戶隨機(jī)的瀏覽當(dāng)前網(wǎng)頁(yè)集以外的某網(wǎng)頁(yè)時(shí)，將要訪問的網(wǎng)頁(yè)的可能性值等于被訪問網(wǎng)頁(yè)的PageRank值。

PageRank算法原理：首先根據(jù)網(wǎng)頁(yè)之間鏈接的引用關(guān)系建立關(guān)系圖，并給最底層的每個(gè)頁(yè)面賦予同樣的PageRank初始值；再根據(jù)網(wǎng)頁(yè)間的引用關(guān)系把它的值平均分配給它引用了的所有頁(yè)面；最后，將各個(gè)頁(yè)面自己所擁有的所有通過引用傳過來(lái)的值求和就是它的PageRank值。通過這樣層層計(jì)算，所有頁(yè)面最終求得它的PageRank值。根據(jù)每一遍的計(jì)算跟進(jìn)，各個(gè)網(wǎng)頁(yè)不斷更新自己的PageRank值。如圖1是一個(gè)簡(jiǎn)單的計(jì)算實(shí)例。

圖1 PageRank計(jì)算實(shí)例

由圖可得：PageRank（14） = PageRank（12）/2 + PageRank（24）/3 = 6 + 8 = 14

PageRank算法特點(diǎn)：它是一個(gè)與查詢主題不相關(guān)的離線求值算法，全部PageRank值在查詢前就預(yù)先計(jì)算獲得；極大的減少了有搜索到達(dá)時(shí)才來(lái)查詢的計(jì)算量，使得搜索更迅速。但是這種方法忽略了結(jié)果和用戶查詢相關(guān)與否，采用了平均分配權(quán)值反而對(duì)一些新的網(wǎng)頁(yè)存在不公平現(xiàn)象。這導(dǎo)致舊網(wǎng)頁(yè)權(quán)值高、查詢到無(wú)關(guān)結(jié)果等。

2.2 HITS算法

HITS（Hyperlink-Induced Topic Search）算法是由康奈爾大學(xué)（Cornell University）的Jon Kleinberg博士于1997年首次提出的。該算法將網(wǎng)頁(yè)分為兩種類型：Authority頁(yè)面和Hub頁(yè)面。Authority頁(yè)面是指某個(gè)方面或主題非常相關(guān)的優(yōu)質(zhì)網(wǎng)頁(yè)；Hub 頁(yè)面是指引用了許多優(yōu)質(zhì)頁(yè)面的網(wǎng)頁(yè)，例如：hao123等。HITS算法認(rèn)為好的Hub頁(yè)面會(huì)指向很多好的Authority頁(yè)面；當(dāng)然好的Authority頁(yè)面也會(huì)有許多Hub頁(yè)面所指向[3]。

HITS算法只計(jì)算與主題比較接近的頁(yè)面，它由一個(gè)頁(yè)面的入鏈數(shù)量來(lái)計(jì)算它的Authority權(quán)值，再根據(jù)該頁(yè)面的出鏈數(shù)量計(jì)算它的Hub權(quán)值。通過迭代計(jì)算和定義的收斂閉值不斷的對(duì)Authority權(quán)值和Hub權(quán)值進(jìn)行更新，直至結(jié)果收斂[2]。最后找出一定數(shù)量Authority權(quán)值和Hub權(quán)值都比較高的頁(yè)面作為最佳頁(yè)面集。

算法原理：

1） 獲取根集：用傳統(tǒng)的搜索引擎對(duì)用戶搜索的關(guān)鍵詞進(jìn)行搜索，獲得與主題相關(guān)的網(wǎng)頁(yè)，從這些網(wǎng)頁(yè)中拿出一些權(quán)威性比較高的網(wǎng)頁(yè)作為根集，且根集要比較小；2） 對(duì)根集進(jìn)行擴(kuò)展：在根集中加入它的集合內(nèi)頁(yè)面的入鏈頁(yè)面和出鏈頁(yè)面，形成一個(gè)更大的集合。

3） 獲取最佳頁(yè)面集合：以擴(kuò)展集合中的Hub 網(wǎng)頁(yè)看成一個(gè)頂點(diǎn)集Vl ， 權(quán)威網(wǎng)頁(yè)看成頂點(diǎn)集V2， Vl 中的網(wǎng)頁(yè)到V2中的網(wǎng)頁(yè)的引用關(guān)系為邊集E， 形成一個(gè)二分有向圖SG= （V1， V2， E）。如圖2所示：

圖2 V1和V2的關(guān)系圖

對(duì)于集合V1中的任意一個(gè)網(wǎng)頁(yè)來(lái)說(shuō)，如果它指向的高質(zhì)量（權(quán)威性高的）頁(yè)面越多，那么它的中心性值越大；而對(duì)V2中的頁(yè)面來(lái)說(shuō)，如果它被好的Hub頁(yè)面引用的越多，則它的權(quán)威性值也越大。然后根據(jù)一個(gè)頁(yè)面的權(quán)威性權(quán)值等于所有指向它的頁(yè)面的中心性權(quán)值之和，中心性權(quán)值等于它指向的所有頁(yè)面的權(quán)威性權(quán)值之和。通過迭代計(jì)算和不斷的對(duì)權(quán)威性值和中心性值進(jìn)行更新，直至結(jié)果收斂。最后，根據(jù)各頁(yè)面最終的權(quán)威性值和中心性值進(jìn)行綜合分析，并從擴(kuò)展集合中得到最佳頁(yè)面。

HITS算法特點(diǎn)：

HITS算法能很好地對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行描述，它只是對(duì)網(wǎng)頁(yè)的一個(gè)小集合進(jìn)行權(quán)值計(jì)算，所以需要的時(shí)間很少。但該算法必須在接收到用戶查詢后才能根據(jù)相關(guān)主題進(jìn)行計(jì)算，而且需要進(jìn)行很多次迭代計(jì)算才能獲得最終結(jié)果，使得計(jì)算效率較低。當(dāng)“擴(kuò)充網(wǎng)頁(yè)集合”內(nèi)有網(wǎng)頁(yè)增減或者鏈接關(guān)系改變時(shí)，HITS算法的排名結(jié)果就會(huì)有非常大的改變，易受“垃圾鏈接”的影響使得評(píng)分異常，出現(xiàn)主題漂移、網(wǎng)頁(yè)作弊。

2.3 HITS算法與PageRank算法比較

根據(jù)以上對(duì)HITS算法和PageRank算法的思想、原理進(jìn)行分析，對(duì)這兩種算法一些特點(diǎn)的比較如表1。

3 改進(jìn)算法

3.1 Hilltop算法

1） 算法基本思想

Hilltop算法是由Krishna Baharat 在2000年左右研究的，于2001年申請(qǐng)專利，后來(lái)他加入了Google并授權(quán)給Google使用的。Hilltop算法不僅采納了PageRank算法使用某個(gè)頁(yè)面入鏈的數(shù)量以及質(zhì)量來(lái)計(jì)算該頁(yè)面的權(quán)值的方法，而且還吸收了HITS算法中根據(jù)與用戶查詢主題的相關(guān)性來(lái)獲得高質(zhì)量頁(yè)面子集的思想。此算法認(rèn)為只有與用戶搜索主題相同的頁(yè)面，才是用戶真正需要的。因此，與主題相關(guān)的頁(yè)面之間的鏈接比和主題不相關(guān)的頁(yè)面之間的鏈接擁有更大的貢獻(xiàn)值。

2） Hilltop 算法的過程

通過計(jì)算得到一個(gè)與用戶搜索的主題最為緊密關(guān)聯(lián)的專家頁(yè)面列表（專家頁(yè)面：它的全部出鏈數(shù)大于s且指向s個(gè)不是同一組織或其所有者之間沒有關(guān)系的網(wǎng)站頁(yè)面）；

由列表中專家頁(yè)面的出鏈找到結(jié)果頁(yè)面；

根據(jù)引用結(jié)果頁(yè)面的不是同一組織或其所有者之間沒有關(guān)系的網(wǎng)站頁(yè)面的數(shù)量和主題相關(guān)度情況來(lái)計(jì)算它的重要性權(quán)值，并將結(jié)果頁(yè)面按重要性值的高低情況進(jìn)行排序。

3） 算法特點(diǎn)

HillTop算法是一種客觀衡量網(wǎng)頁(yè)質(zhì)量的排序方法，查詢與語(yǔ)言、內(nèi)容無(wú)關(guān)。在Hilltop算法中應(yīng)用專家頁(yè)面，該頁(yè)面的搜索和確定對(duì)算法起關(guān)鍵作用，較好的提高了搜索結(jié)果的質(zhì)量。然而專家頁(yè)面的質(zhì)量和公平性在一定程度上難以保證，該算法降低了人性操作的排序影響，并忽略了大多數(shù)非專家頁(yè)面對(duì)它的影響。并且HillTop算法沒有考慮搜索結(jié)果中存在的問題，當(dāng)計(jì)算中沒有找到足夠多的專家頁(yè)面，則它沒有結(jié)果返回。

3.2 SALSA算法

SALSA算法由以色列學(xué)者R.Lempel和S.Moran于2000年在第9屆國(guó)際互聯(lián)網(wǎng)大會(huì)上提出，其英文全稱為Stochastic Approach for Link-Structure Analysis[3]。

1） 算法基本思想

SALSA算法保留了PageRank 的隨機(jī)訪問和HITS 中與查詢主題相關(guān)的特點(diǎn)，它同樣把網(wǎng)頁(yè)分為Authority和Hub的網(wǎng)頁(yè)集合，但取消了Authority與Hub之間的相互貢獻(xiàn)評(píng)分的關(guān)系。SALSA算法不僅考慮了一般的用戶隨機(jī)向前瀏覽的習(xí)慣，而且也加入了用戶有時(shí)候會(huì)回退瀏覽網(wǎng)頁(yè)的事實(shí)，讓算法更具健壯性。該算法在應(yīng)用中可以大致劃分為與HITS算法基本相同確定計(jì)算對(duì)象集合和像PageRank算法那樣采用隨機(jī)訪問的鏈接關(guān)系傳播過程兩個(gè)階段。

2） 算法特點(diǎn)

SALSA 算法擯棄了HITS 中相互加強(qiáng)的迭代過程，節(jié)省了資源、減小了計(jì)算量，并且它在擴(kuò)展根集時(shí)忽略了一些無(wú)效的鏈接（如：廣告和贊助商鏈接等），在一定程度上解決了主題漂移問題使查找更為精確。但SALSA算法在求網(wǎng)頁(yè)的Authority值時(shí)，沒有考慮直接相鄰網(wǎng)頁(yè)集以外的其它網(wǎng)頁(yè)對(duì)它的影響。

4 結(jié)論

基于對(duì)以上幾種搜索引擎算法的分析，不管多么經(jīng)典的算法目前都還是不盡完美，它始終處在一個(gè)長(zhǎng)期發(fā)展的過程中。當(dāng)然，我們可以從多種算法中取長(zhǎng)補(bǔ)短以獲得更好的搜索效果，也有很多人這樣做了。但是，要想在這方面得到突破性的改進(jìn)，開發(fā)

者應(yīng)該多關(guān)注一下用戶或者從用戶的角度出發(fā)去發(fā)現(xiàn)一些存在的問題并想辦法解決。期待在不久的將來(lái)內(nèi)網(wǎng)搜索引擎算法方面會(huì)有更大的改善，以應(yīng)對(duì)云時(shí)代的到來(lái)，達(dá)到更高標(biāo)準(zhǔn)的用戶需求。

參考文獻(xiàn)：

[1] 韓金華.搜索引擎算法綜述[J].中國(guó)學(xué)術(shù)期刊電子出版社，2011.

[2] 陳凱.搜索引擎有關(guān)排序算法研究[D].武漢理工大學(xué)，2011.5.

[3] 張俊林.這就是搜索引擎：核心技術(shù)詳解[M].電子工業(yè)出版社，2012.1.

[4] 鄧仲華，李志芳，趙又霖.基于鏈接的網(wǎng)頁(yè)排序算法研究分析[J].中國(guó)學(xué)術(shù)期刊電子出版社，2010.