0.3973996608
0.3973996608
︸    404143424445
當然，由于整個網絡的頁面數量巨大，采用普通的迭代計算方式將會非常耗
時， L~ncePage和 sergcyBrin提出改進后的算法則大大降低了運算量，并成
功將其投入到實際的運用中。
.PageRank的不足
PageRank值較好地反映網頁之間的相互引用關系，被引用較多的網頁重要性
也較大，所以能較好地反映頁面權威性。但它和主題是相互獨立的，沒有考慮到
網頁和主題之間的相關性，容易造成“主題漂移”現象，即搜索到的網頁雖然具有
較高的權威性，但與用戶想要的主題無關。
此外，PageRank往往無法正確判斷剛剛放到互聯的網頁的重要性，因為剛放
入W七b的網頁有可能沒有任何的鏈接指向它，這時，即便是非常重要的網頁
PageRank值也會非常低。
.TOpic一sensitivepageRank算法
斯坦福大學計算機科學系口l’  aherHaveliwala【101提出了一種主題敏感
(Topi~sensitive)的PageRank算法解決了“主題漂流”問題。該算法考慮到有些頁
面在某些領域被認為是重要的，但并不表示它在其它領域也是重要的。
算法先根據O伴 nDirectory列出16個基本主題向量，并對每個網頁離線計
算出對這些基本主題向量的PageRank值。
在用戶查詢時，算法根據用戶輸入的查詢主題或查詢的上下文，計算出該主
題與已知的基本主題的相似度，在基本主題中選擇一個最接近的主題代替用戶的
查詢主題，并用該基本主題向量的PageRank值對結果進行排序。該算法可以有
效地避免一些明顯的主題漂移現象。浙江大學碩士學位論文第2章相關技術的研究現狀
 2.3.2HITS算法
HITs(H即eriink一  IndueedTopiesearch)算法[22]是由習einbe嗯在90年代末
提出的一種鏈接分析算法，它更為精確的分析了頁面權威性“Authority’’，Kleinberg
認為頁面的重要性應該建立在用戶查詢條件的基礎上，每一頁面都分別有
Authority值和Hub值。通常，好的Hub是指向許多好的權威頁面;好的權威頁
面有許多好的Hub頁面所指向。這種Hub和Authority之間的相互作用可用于權
威頁面的挖掘和高質量W七b結構和資源的自動發現，這就是HrrS方法的基本思
想。
為便于理解，心einberg用圖來表示鏈接關系，設超鏈頁面的集合v為一個
有向圖G二(v，E)，圖中的一個節點對應一張網頁，有向邊印， q)EE表示網頁p
鏈接指向網頁q，節點p的出度 (out-degree)指節點p鏈出的網頁數量，而節點p
的入度(in一degree)則指的是鏈接指向節點p的網頁數量。如果集合w是v的一個
子集，則用G[明來表示由w組成的有向圖，它的節點包含在w中，邊對應于
W中的所有鏈接?，F在假設給定一個泛指主題檢索提問。，需要通過鏈接分析確
定該提問的權威頁。HITS算法的流程如下:
l)獲得 RootSet用基于文本的搜索引擎如AltaVista或Hotbot來得到。
的查詢結果集，取排名最高的前t(t值通常設為200)位作為結果集R(稱Root
Set)。
2)擴充 RootSet擴充R分為兩個方面，一是將所有R中頁所指向的頁
面擴充進去;二是將指向R中的每一頁面的鏈接頁面取其中任意d(d值通常設定
為50，如果d不大于50，則取其所有頁面)個頁面擴充到原來的R中形成s(稱為
 BaseSet)。S的數量范圍一般在 1000至5000。
3)排除干擾為了提高計算效果，幻einberg還將S作了進一步的處理，
他將鏈接分為兩種情況:一是指有鏈接關系的兩個頁面處在不同域名之間，這樣
的鏈接稱為橫向鏈接;還有一種情況是指有鏈接關系的兩個頁面處于同一域名之
下，這樣的鏈接稱為內在鏈接?；胑inberg認為內在鏈接只具有網站內部的導航
功能，它幾乎不能傳遞網頁間的authority，因此需要將這種內在鏈接從s中刪去，
形成G。
4)計算hubs和authorities的值對于每一個頁面p，用a印)表示頁面p
的 authorityweight(權威權重)，用h的表示頁面p的 hubweight(中心權重)，使
用下列公式進行迭代計算。
a(尸)=藝h(r，)i=l
n
h(，)一藝a(。，)
 (2.9)
 (2.10)浙江大學碩士學位論文第2章相關技術的研究現狀
其中ri是鏈接到p的頁面，qi是頁面p鏈接出去的頁面。
5)規范化處理每次迭代計算完之后都需要進行規范化處理，使其能收
斂，頁面p經規范化處理后滿足以下條件:
藝。(，)2=l
炸S
藝，(，)，=1
作S
 (2.11)
 (2.12)
6)重復過程4)一5)，直到a印)和h印)收斂為止。
 2.33PageRank和HITS算法比較
PageRank和Hrrs均為基于鏈接分析的搜索引擎排序算法。但兩者也存在較
大的差別:
 1)PageRank算法與主題無關，HITS算法同用戶的檢索主題相關。PageRank
算法獨立于檢索主題，因此也常被稱為query一indePendeni算法。PageRank借鑒
了引文分析的思想，并利用網絡自身的超鏈接結構給所有的網頁確定一個重要性
的等級數即PageRank值。HrrS的原理如前所述，其authority值只是相對于某個
檢索主題的權重，因此HrrS算法也常被稱為query一dePendent算法。
2)權重的傳播模型HITS是首先通過基于文本的搜索引擎來獲得最初
的處理數據，網頁重要性的傳播是通過hub頁向authority頁傳遞，而且Kleinberg
認為，hub與authority之間是相互增強的關系;而PageRank基于隨機沖浪 (random
surfer)模型，可以認為它將網頁的重要性從一個authority頁傳遞給另一個authority
頁。
3)查詢響應時間表面上看，由于authority和hub值的計算是在獲得用
戶的查詢關鍵字后進行的，雖然網頁數量一般為1000至5000個，但由于需要從
基于內容分析的搜索引擎中提取根集并擴充基本集，這個過程需要耗費相當的時
間;在PageRank算法中，PageRar正值計算工作在用戶查詢時己經由服務器端獨
立完成，不需要用戶端等待，因此，PageRank算法要比HrrS具有更高的反應速
度。
2.4本章小節
本章首先介紹了三大類的中文分詞方法:機械分詞、基于統計的分詞和基于
規則的分詞方法，然后介紹了用于主題相關度判別的計算模型:布爾模型和向量
空間模型，最后介紹了兩種較為出名的基于鏈接的分析技術PageRank和HrrS算
法，并對兩者做一個對比。浙江大學碩士學位論文第3章中文分詞和主題預測算法
第3章中文分詞和主題預測算法
垂直搜索引擎中的關鍵技術包括中文分詞、網絡蜘蛛、索引、分布式存儲等，
本文重點研究前兩項技術。
中文分詞是搜索引擎的基礎組成部分，分詞的好壞直接影響了搜索引擎的各
個環節的工作。中文分詞技術有機械分詞、基于統計的分詞方法和基于規則的統
計方法三種基本類型。結合垂直搜索引擎的特點，本文提出了基于主題的自適應
的分詞技術，使用候選詞典來指導分詞和歧義的消除。
垂直搜索引擎的網絡蜘蛛即專業網絡蜘蛛的目標是在盡量少地遍歷WEB的
前提下，發現盡量多的主題相關的網頁。專業網絡蜘蛛使用‘， BestFirst’’策略遍歷
M觸b，因此，需要對網頁的主題相關度做預測。本文提出了基于鏈入網頁計算模
型、基于父網頁的計算模型和TPR預測算法。
3.1基于主題的自適應的分詞方法
基于字符串匹配的分詞方法需要使用分詞詞典，詞典的大小和質量直接決定
了分詞的效率和質量，為此，維護一個數量適度、更新及時詞典具有較大的價值
與意義。結合搜索引擎的特點，本文提出了一種基于主題的自適應的分詞方法，
該方法主要包括利用候選詞典進行分詞、基于專業詞庫和統計方法消除歧義現
象。
3.1.1候選詞典
一般認為，用戶提交給搜索引擎的漢字串都是以詞的形式存在的，在真心想
通過搜索引擎查找資料的前提下，很少有用戶會提交不構成詞的漢字串作為搜索
條件提交給搜索引擎，例如，某用戶想查找數據庫方面關于“數據挖掘”方面的資
料，他可能會提交形如“數據挖掘”、“ datamining”等關鍵詞進行搜索，而不會提
交一些不構成詞的字符串給搜索引擎，如“掘挖據數”等亂碼。
對提交給搜索引擎的關鍵詞進行統計，當某些關鍵詞的頻度超過一定閥值
后，將其納入候選詞典中，另外一方面，當關鍵詞的頻度下降到某一閥值時，將
其從候選分詞典中移除，及時更新候選詞典。
使用候選詞典的優勢是能保證分詞系統與時俱進，能正確地識別某一時間段
特別熱門的詞如“超女”、‘，PK’，等，這些詞往往具有曇花一現的特點，即原先在詞
典中不存在這樣的詞，由于某種原因一段時間非常火暴，在這個時間內它往往作
為一個獨立存在的詞而存在，分詞系統需要將其作為一個詞條處理，但是隨著時
間的推移，這些詞將慢慢談出人們的視線。
為了正確處理這樣的情況，候選詞典提供了一個很好的解決方案，候選詞典1)1.“洲項士學位論文第3章中文分詞和主題預測算法
統計終端用戶輸入的關鍵詞，并將頻度高出一定閥值的入選為候選詞典中的詞
條，在分詞出現未登詞串時，將參考候選詞典中的詞條，如果有匹配成功，則利
用候選詞典分詞。
此外，如果某些候選詞條持續一段相當長的時間仍處于活躍的狀態，則將該
詞條入選為正式分詞詞典中的詞條。
增加了候選詞典后，用戶提交的數據流程如圖3一1所示:
用用用用用用用用戶孰入練仁嘴點點癱癱癱癱癱癱癱癱癱癱癱癱癱癱癱癱選詞典典典                典降降圈;粉翔‘娜娜械徽沈娜叨 叨        叨叨                叨
連詢控制器
圖3一1用戶提交的關鍵詞的數據流程
 3.1.2Aging技術
由于客戶端的輸入行為是無法控制的，各種各樣的輸入結果都有可能被提交
給搜索引擎，如果存儲每一種可能的輸入，那需要極高的代價，同時也是沒有必
要的，為此，為了防止候選詞典無限制地擴張，必須控制控制候選詞典在某一合
理的范圍內。
為了解決這個問題，本文提出了aging技術，該技術使候選詞典中的所有詞
條都在不停地衰老(aging)，另外一方面，用戶的輸入又讓相應的詞匯增加生命力。
aging技術移除那些提交的次數不多，不被人們所認可的詞匯，由于這些詞
條生命力的增長速度(跟被提交的頻度成正比)沒有衰老速度快，最終會被系統
移除，而另外一些熱門詞匯，反復地被用戶提交，增長速度遠快于衰老速度，因
此能長久地保持在候選詞典中。
當一個新詞條進入候選詞典時，我們將該詞條的age初始化為。，系統每隔
一段時間(如每天)對候選詞典中的所有的詞條的age更新一次，使所有詞條的
age增加一定的步長(如l)。當發現候選詞典中的某些詞條的頻度被age追趕上
時，即有詞條的頻度 frequency<=age，則該詞條將從候選詞典中被移除。
當候選詞典中的詞條的age超過某一閥值時，我們認定，該詞已經生存了相
當長的時間了，可以作為正式的詞條進行分詞詞典中，當然進入分詞詞典的過程浙江大學碩士學位論文第3章中文分詞和主題預測算法
需要人工的干預，以保證分詞詞典的完整性與正規性。相應地，如果發現某一詞
條的生命力不足時，可以將其從正式的分詞詞典中移除。
3.1.3基于主題的自適應分詞算法
分詞算法往往分成詞串的切分和歧義消除兩部分，在詞串的切分過程中往往
使用機械分詞方法進行初分，然后利用基于統計的方法和其它方法相結合來消除
歧義。這樣既發揮了機械分詞效率高，又發揮了統計方法能識別新詞的優點。
分詞工作中最難的部分是歧義和未登詞的識別，中文分詞問題中歧義字段切
分是影響分詞系統切分精度的重要因素，它是中文分詞系統設計中的一個最困難
也是最核心的問題。特別是在科技發展日新月異的今天，某些新興行業的專業術
語層出不窮，這給分詞工作帶了挑戰。
中文分詞中存在交集型歧義和多義型歧義兩種:
l)交集型歧義字段:在字段ABC中， ABow并且 BCow，則稱ABC為
交集型歧義字段。其中A，B，C為字串，W為詞典。
2)多義型字段:在字段AB中， ABEW， Aow， BCow，W為詞