第六章web檢索技術

1、信息組織、存儲與檢索信息組織、存儲與檢索第六章第六章 Web 檢索技術檢索技術信息組織、存儲與檢索信息組織、存儲與檢索Web 檢索概述檢索概述信息組織、存儲與檢索信息組織、存儲與檢索The World Wide Webn 1989年，蒂姆伯納斯李在日內瓦歐洲離子物理研究所（CERN）開發(fā)計算機遠程控制時首次提出了Web概念，并在1990年圣誕節(jié)前推出了第一個瀏覽器。 n 接下來的幾年中，他設計出HTTP、URL和HTML的規(guī)范，使網絡能夠為普通大眾所應用 n超文本傳輸協議(HTTP，HyperText Transfer Protocol)是互聯網上應用最為廣泛的一種網絡傳輸協議 ;n統(tǒng)一資源定

2、位符（URL，UniformResourceLocator）也被稱為網頁地址，是因特網上標準的資源的地址;n超文本標注語言（HTML,HyperText Markup Language ）是為“網頁創(chuàng)建和其它可在網頁瀏覽器中看到的信息”設計的一種標記語言。信息組織、存儲與檢索信息組織、存儲與檢索Web Search 歷史歷史n1990年，搜索引擎的祖先Archie，是第一個自動索引互聯網上匿名FTP網站文件的程序；n1993年，早期的 web robots (spiders) 用于收集 URL:nWorld Wide Web WanderernALIWEB (Archie-Like Index

3、 of the WEB)nWWW Worm (The World Wide Web Worm)n1994年，Stanford 博士生 David Filo和Jerry Yang 開發(fā)手工劃分主題層次的Yahoo；信息組織、存儲與檢索信息組織、存儲與檢索Web Search 歷史歷史n1994年4月，WebCrawler是互聯網上第一個支持搜索文件全部文字的全文搜索引擎；n1994年7月，Lycos提供相關性排序、前綴匹配和字符相近限制，第一個在搜索結果中使用了網頁自動摘要，且數據量 較大；n1995年， Metacrawler元搜索引擎，用戶只需提交一次搜索請求，由元搜索引擎負責將從各獨立搜索

4、引擎返回的所有查詢結果，集中起來后返回給用戶；信息組織、存儲與檢索信息組織、存儲與檢索Web Search 歷史歷史n1995年12月，AltaVista是第一個支持自然語言搜索的搜索引擎，是第一個實現高級搜索語法的搜索引擎（如AND, OR, NOT等) ；n1995年，Larry Page開始學習搜索引擎設計，于1997年注冊了的域名，1997年底，開始提供Demo。1999年2月，Google完成了從Alpha版到Beta版的蛻變。Google公司則把1998年9月27日認作自己的生日。nGoogle在Pagerank、動態(tài)摘要、網頁快照、多文檔格式支持、多語言支持、用戶界面等功能上的革

5、新，再次永遠改變了搜索引擎的定義；信息組織、存儲與檢索信息組織、存儲與檢索Web Search 歷史歷史n北大天網 1997年10月29日正式在CERNET上提供服務；n2000年1月，李彥宏與徐勇在北京中關村創(chuàng)立了百度（Baidu）公司；n2001年8月發(fā)布B搜索引擎Beta版；n2001年10月22日正式發(fā)布Baidu搜索引擎；n核心技術：超鏈接分析，通過分析鏈接網站的多少來評價被鏈接的網站質量。信息組織、存儲與檢索信息組織、存儲與檢索Web Challenges for IRn 數據的分布性：數據的分布性：文檔散落在數以百萬計的不同服務器上，沒有預先定義的拓撲結構相連。n 不穩(wěn)定的數據高

6、比例：不穩(wěn)定的數據高比例：許多文檔迅速地添加或刪除n 大規(guī)模：大規(guī)模：網絡數據量的指數增長，由此引發(fā)了一系列難以處理的規(guī)模問題。n 無結構和冗余信息：無結構和冗余信息：每個HTML頁面沒有統(tǒng)一的結構, 許多網絡數據是重復的，將近 30% 的重復網頁.n 數據的質量數據的質量: 許多內容沒有經過編輯處理，數據可能是錯誤的，無效的。錯誤來源有錄入錯誤，語法錯誤等。n 異構數據：異構數據：多媒體數據, 語言,字符集等. 信息組織、存儲與檢索信息組織、存儲與檢索中文網頁增長情況中文網頁增長情況信息組織、存儲與檢索信息組織、存儲與檢索Web Search的三種形式的三種形式n 基于超文本/超媒體的信息瀏

7、覽；n 基于目錄的信息查詢；n由人工收集或者由Web站點的作者主動提交文檔；n人工對Web站點和文檔進行評價、分類并給出簡要描述；n按照主題分類并以樹狀的形式對Web信息資源進行組織；n對Web信息資源的分類以及描述信息建立索引；n 基于搜索引擎的信息檢索；n使用robot遍歷Web，將Web上的信息下載到本地文檔庫；n對文檔內容進行自動分析并建立索引；n檢查索引找出與用戶查詢相匹配的文檔（或鏈接）。信息組織、存儲與檢索信息組織、存儲與檢索Web信息檢索系統(tǒng)的分類信息檢索系統(tǒng)的分類Web搜索引擎元搜索引擎信息檢索agent目錄用戶信息組織、存儲與檢索信息組織、存儲與檢索信息組織、存儲與檢索信息

8、組織、存儲與檢索Web 搜索引擎工作原理搜索引擎工作原理信息組織、存儲與檢索信息組織、存儲與檢索Web搜索引擎的工作過程搜索引擎的工作過程n網頁爬行下來；n預處理：網頁去重，正文提取，分詞等；n建立索引；n接受用戶請求，檢索詞串的處理，查詢重構；n找到滿足要求的列表；n根據連接和文本中的詞進行排序輸出。信息組織、存儲與檢索信息組織、存儲與檢索Web搜索引擎的結構搜索引擎的結構信息組織、存儲與檢索信息組織、存儲與檢索Web搜索引擎的基本要求搜索引擎的基本要求n搜索引擎示意圖搜索引擎網頁數據庫q1, q2, q3 L1, L2, L3 qi：用戶通過瀏覽器提交的查詢詞或者短語Lj：在一個可接受的時

9、間可接受的時間內返回一個和用戶查詢匹配匹配的網頁信息列表列表信息組織、存儲與檢索信息組織、存儲與檢索Web搜索引擎的基本要求搜索引擎的基本要求n相關概念n可以接受的時間n即響應時間，通常在“秒”級，是衡量搜索引擎可用性的一個基本指標n匹配n網頁中以某種形式包含有 q 的內容n列表n蘊含著一種“序”信息組織、存儲與檢索信息組織、存儲與檢索Web搜索引擎體系結構搜索引擎體系結構n 小型的搜索引擎系統(tǒng)一般是集中式的結構 n系統(tǒng)實現簡單，花費的資源比較少 n自身處理能力比較弱，能支持同時訪問用戶數量也比較小 n 很多搜索引擎采用了升級Web數據采集系統(tǒng)硬件的方法 n使用大型機和并行機作為采集系統(tǒng)的硬件

10、使采集能力提高 n升級硬件的方法擴展性有限，性價比也不高 n 用網絡連接多臺微機組成一個分布式的機群系統(tǒng)提供的分布式網絡服務 n 現代網絡服務的體系結構已經由集中式向分布式轉變 信息組織、存儲與檢索信息組織、存儲與檢索分布式結構分布式結構:主次結構主次結構信息組織、存儲與檢索信息組織、存儲與檢索分布式結構分布式結構:對等結構對等結構信息組織、存儲與檢索信息組織、存儲與檢索Web搜索引擎系統(tǒng)組成搜索引擎系統(tǒng)組成nWeb搜索引擎系統(tǒng)可以被分成以下四個大的子系統(tǒng)：nWeb數據采集系統(tǒng)n網頁預處理系統(tǒng)n索引檢索系統(tǒng)n檢索結果排序系統(tǒng)信息組織、存儲與檢索信息組織、存儲與檢索Web信息采集信息采集信息組織

11、、存儲與檢索信息組織、存儲與檢索Web信息采集的特點及意義信息采集的特點及意義n信息采集是搜索引擎獲得數據來源的過程，保證了信息檢索的召回率；n信息采集的目標：快速獲得高質量的網頁；n最主要的作用n采集網上的信息n網頁，文本，ppt, doc ,音樂，圖片n及時更新信息n增加新出現的鏈接n刪除死鏈接信息組織、存儲與檢索信息組織、存儲與檢索Spiders (Robots/Crawlers/Wander)n從一個URL根集開始搜索；n根據這些網頁的鏈接尋找另外的網頁；n將遇到的所有新的網頁建立索引；n也允許直接索引用戶提交的網頁；信息組織、存儲與檢索信息組織、存儲與檢索爬取過程爬取過程WebURL

12、s frontierUnseen WebSeedpagesURLs crawledand parsed信息組織、存儲與檢索信息組織、存儲與檢索采集的遍歷算法采集的遍歷算法n廣度優(yōu)先 VS 深度優(yōu)先n廣度優(yōu)先：先采集完同一層的網頁，再采集下一層網頁；n深度優(yōu)先：先沿一條路徑采到葉節(jié)點，再從同層其他路徑進行采集；n網站采集 VS 全局URL采集n網站采集：一個網站一個網站采集；n全局URL采集：將所有URL放入一個URL池，從中使用某種方法進行選擇；信息組織、存儲與檢索信息組織、存儲與檢索Web數據采集系統(tǒng)的分類數據采集系統(tǒng)的分類n基于整個網絡的數據采集：基于整個網絡的數據采集：一段時間以后重新采

13、集所有網頁，全部采完以后替換原來的網頁；n采集數據廣，采集速度快，適用于廣泛主題的搜索；n采集數據亂，數據利用率低，頁面失效率高，采集周期長；n增量式數據采集：增量式數據采集：只按照某種策略采集那些可能新增、變化的網頁，并刪除那些已經不存在的網頁；n極大地減小數據采集量進而極大地減小采集時空開銷；n增加了一定的判別開銷。信息組織、存儲與檢索信息組織、存儲與檢索Web數據采集系統(tǒng)的分類數據采集系統(tǒng)的分類n 基于主題的數據采集：基于主題的數據采集：選擇性的搜尋那些與預先定義好的主題集相關頁面進行采集 ；n給定特定的種子URL，垂直搜索；n采集頁面更加有針對性，采集效率更高；n采集速度較慢，判別相關

14、性帶來較大的開銷n 遷移的遷移的Web數據采集：數據采集：被采集者自己上載到要采集的服務器中，在當地進行采集，并將采集結果壓縮后，回傳到本地 ；n大量的節(jié)省了Web資源，大量的剪裁工作將在被采集對象的服務器上完成 ；n不被采集對象所信任 ；信息組織、存儲與檢索信息組織、存儲與檢索Crawler基本思想基本思想信息組織、存儲與檢索信息組織、存儲與檢索WebWeb有向圖有向圖網頁為節(jié)點HTML鏈接引用為有向邊信息組織、存儲與檢索信息組織、存儲與檢索系統(tǒng)框圖系統(tǒng)框圖信息組織、存儲與檢索信息組織、存儲與檢索抓取網頁通信實例抓取網頁通信實例信息組織、存儲與檢索信息組織、存儲與檢索單個采集線程個工作過程單

15、個采集線程個工作過程n 將url解析成host和file；n例如：url： http:/ nfile: /asp/customercenter/center_home.aspn 根據host（ ）做DNS解析；n 創(chuàng)建一個socket，用于網絡通信；n 把創(chuàng)建的socket編號和DNS解析得到的網絡地址作為參數傳遞給connect()函數，進行本地服務器和遠程網頁服務器的連接操作；信息組織、存儲與檢索信息組織、存儲與檢索單個采集線程個工作過程單個采集線程個工作過程n在本地服務器緩沖區(qū)中組裝http請求；n用write()函數將組裝好的http頭發(fā)給網頁服務器；n調用read()函數讀從網頁服務

16、器返回的網頁數據；n當read()函數返回的字節(jié)數是0的時候，說明網頁已經下載完畢；n調用close()函數終止與網頁服務器的連接；n將網頁保存到本地服務器；信息組織、存儲與檢索信息組織、存儲與檢索采集中的采集中的“禮貌禮貌”問題問題n遵守網站上發(fā)布的Robot.txt 采集限制協議；n采集時盡量不要太過密集地采集某個網站，這種密集訪問導致普通用戶正常瀏覽網站產生困難。有些網站會嚴密控制這種密集訪問行為。信息組織、存儲與檢索信息組織、存儲與檢索網頁預處理網頁預處理信息組織、存儲與檢索信息組織、存儲與檢索網頁預處理任務網頁預處理任務n網頁去重n網絡上可能會出現多個域名對應同一個網站的情況或者網站

17、的互相轉載;n去除重復的網頁是為了避免同一個網站的內容被多次采集和索引;n網頁正文提取n在建立索引之前，將網頁中對建立索引無用的信息（如廣告信息，一些無用的連接信息，一些腳本語言等）進行清理;n分詞等信息組織、存儲與檢索信息組織、存儲與檢索網頁重復情況網頁重復情況n內容相同的網頁分為四種情況n網頁正文完全相同；n網頁正文大部分相同只是一些地方做了少量變動；n一個網頁的正文是另一個網頁的一部分；n兩個網頁的某些段落相同；n其中前兩種情況在相同網頁中所占比例最大，大致占到80%左右信息組織、存儲與檢索信息組織、存儲與檢索網頁去重方法網頁去重方法n現在廣泛使用的是基于指紋識別（fingerprint

18、ing）思想的網頁內容重復性判斷方法。n主要思想n是抽取出網頁內容中的一系列字符串，計算這些字符串hash值產生指紋；n判斷兩網頁是否相同時只需計算它們的相同指紋個數是否大于一定的閾值即可。信息組織、存儲與檢索信息組織、存儲與檢索網頁去重方法網頁去重方法基于文本塊基于文本塊n 網頁進行預處理，去除格式化信息以及非文字信息n 對網頁文本利用一定的策略進行分塊，利用hash函數計算每一塊的hash值，產生記錄文本塊信息的三元組，其中h是利用此文本塊計算出的hash值，r是文本塊所屬的網頁的編號，l是此文本塊在網頁正文中的位置；n 將信息存放到hash表中；n 對含有相同文本塊的所有網頁進行統(tǒng)計；n

19、 如果相同文本塊個數占網頁中所有文本塊個數的比例大于一個閾值則認為兩個網頁是相同的。信息組織、存儲與檢索信息組織、存儲與檢索網頁去重方法網頁去重方法利用利用shingle和超級和超級shinglen 將文檔中一段連續(xù)的文字串稱為一個shinglen 判斷重復的方法n獲取網頁，對每一篇網頁進行預處理，去除結構信息和html信息，產生對應的文字信息；n利用文本信息產生與每個網頁對應的shingle集合；n利用兩文本的shingle集合來計算兩個文本的相同度，如果大于一個閾值則認為這兩個網頁是內容重復的網頁。 (A)、(B)分別是兩個文本中包含的shingle集合| )()(| )()(|),(BS

20、ASBSASBAr信息組織、存儲與檢索信息組織、存儲與檢索n兩種隨機選擇shingle的方法n將一篇文本D的所有shingle隨機排序，然后挑選出前m個保留，挑選出來的shingle記為Fm(D)；n將D中隨機排序后的所有shingle的序號對數m進行模運算，保留所有計算結果為0即序號是m的倍數的shingle，這些shingle的集合記為Vm(D)；| )()(| )()(|),(BVAVBVAVBArmmmm網頁去重方法網頁去重方法利用利用shingle和超級和超級shingle信息組織、存儲與檢索信息組織、存儲與檢索網頁去重方法網頁去重方法基于集合統(tǒng)計基于集合統(tǒng)計n 對文檔進行預處理，移

21、除文檔中的格式信息等，將文檔分解成單詞流;n 利用從樣本集合中統(tǒng)計出的詞的idf并利用一定的策略保留重要的單詞（相同的單詞只保留一個）；n 利用哈希算法將保留下來的單詞計算出一個hash值，并且生成二元組；n 將按照hash值的大小存放到樹形結構中，如果樹形結構中已經存在和此文檔相同hash值的文檔則說明它們是內容重復的文檔。信息組織、存儲與檢索信息組織、存儲與檢索網頁去重方法網頁去重方法其他其他n 利用相似度計算進行網頁去重n 基本思想：利用向量余弦夾角的方法n 計算每兩個網頁文本向量之間的余弦夾角值，如果該值小于一個閾值，則認為兩個網頁相同。信息組織、存儲與檢索信息組織、存儲與檢索信息組織

22、、存儲與檢索信息組織、存儲與檢索正文提取正文提取n大部分網頁中除了包含它的主要有用信息（正文）外還含有許多的噪聲信息：n網站的導航信息n相關鏈接和廣告等n正文提取的任務就是從給定的網頁中抽取出正文信息n文件信息組織、存儲與檢索信息組織、存儲與檢索基于基于DOM樹的正文提取樹的正文提取n DOM（Document Object Model）是由W3C組織發(fā)布的一種訪問和操作HTML文檔的規(guī)范。DocumentElement：Text：IloveIR-LABElement：Text：WelcometoHtmlElement：Element：信息組織、存儲與檢索信息組織、存儲與檢索基于基于DOM樹的

23、正文提取步驟樹的正文提取步驟n 利用網頁的源文件建立一個DOM樹結構；n 遍歷DOM樹，從網頁中刪除掉所有不是正文的信息n 廣告信息的移除：首先需要建立一個經常更新的廣告服務器列表，如果地址是指向列表中的廣告服務器地址則將此鏈接節(jié)點刪除n 鏈接群的移除：計算每一個節(jié)點所包含的鏈接個數相對非鏈接的詞個數的比例，如果比例大于一個給定的閾值則刪除此節(jié)點n 刪除不包含重要信息的節(jié)點：用戶事先指定一些不重要的HTML標簽以及一個有用標簽至少需要包含多少字符n 上述非正文信息移除掉后，DOM樹中剩余的內容就是正文信息，可以直接從余下的樹節(jié)點中抽取出正文信息信息組織、存儲與檢索信息組織、存儲與檢索相關排序相

24、關排序信息組織、存儲與檢索信息組織、存儲與檢索搜索引擎的排序重要性搜索引擎的排序重要性n 排序很重要n65%一70%的網民點擊搜索結果的第一頁。n20%-25%的網民點擊搜索結果第二頁n3%-4%的網民點擊量其他的網頁n 排序算法為各公司的機密n Google 擁有PageRank技術n百度擁有超鏈分析技術n SEO（ Search Engine Optimization搜索引擎優(yōu)化）n互相博弈信息組織、存儲與檢索信息組織、存儲與檢索早期的相關排序技術早期的相關排序技術n根據網頁中詞項出現的頻率進行相關性判斷；n用戶檢索詞在網頁中的權重高的網頁放在靠前的位置n導致關鍵詞堆砌作弊信息組織、存儲與

25、檢索信息組織、存儲與檢索超鏈接分析技術前提超鏈接分析技術前提nWeb頁面內的超鏈接包含了該頁面對其鏈出頁面的判斷信息；（出度）n對Internet上的任意一個頁面，被其他頁面的鏈接數（即該頁面的鏈入數）越多，表示該頁面越受歡迎，其重要性也就越高。（入度）信息組織、存儲與檢索信息組織、存儲與檢索鏈接分析技術分類鏈接分析技術分類n基于隨機沖浪模型，如：PageRank算法n基于Hub和Authority相互加強模型，如：HITS算法信息組織、存儲與檢索信息組織、存儲與檢索隨機沖浪模型隨機沖浪模型n用戶選擇的起始網頁是隨機的；n用戶會從起始網頁含有的超鏈接中隨機選擇一個頁面繼續(xù)瀏覽；n當用戶沿著超鏈

26、接前進了一定數量的網頁后，可能會對主題厭倦，這時用戶會重新隨機選擇一個網頁進行瀏覽；n用戶會重復以上的過程若干次。信息組織、存儲與檢索信息組織、存儲與檢索PageRank算法算法n Larry Page和 Sergey Brin于1998年提出PageRank算法；n 基于以下兩個基本假設：n數量假設：如果一個頁面節(jié)點接收到的其他網頁指向的入鏈數量越多，那么這個頁面越重要；n質量假設：越是質量高的頁面指向頁面A，則頁面A越重要。n 某個頁面可能被訪問的次數就被定義為網頁的權值，即PageRank值；n PageRank值是網頁的重要性評價，和用戶輸入的查詢沒有任何關系，即算法是主題無關的。信息

27、組織、存儲與檢索信息組織、存儲與檢索PageRank 基本思想基本思想n如果網頁T存在一個指向網頁A的連接，則表明T的所有者認為A比較重要，從而把T的一部分重要性得分賦予A。這個重要性得分值為：PR(T)/L(T)，其中PR(T) 為T的PageRank值，L(T)為T的出鏈數n網頁A的PageRank值為一系列類似于T的頁面重要性得分值的累加。信息組織、存儲與檢索信息組織、存儲與檢索PageRank計算過程計算過程n 在初始階段：在初始階段：每個頁面設置相同的PageRank值，通過若干輪的計算，會得到每個頁面所獲得的最終PageRank值。n 在一輪中更新頁面在一輪中更新頁面PageRan

28、k得分的計算方法：得分的計算方法：每個頁面將其當前的PageRank值平均分配到本頁面包含的出鏈上，每個鏈接即獲得了相應的權值。而每個頁面將所有指向本頁面的入鏈所傳入的權值求和，即可得到新的PageRank得分。當每個頁面都獲得了更新后的PageRank值，就完成了一輪PageRank計算。 信息組織、存儲與檢索信息組織、存儲與檢索PageRank 計算過程計算過程信息組織、存儲與檢索信息組織、存儲與檢索PageRank算法舉例算法舉例n 假設一個由只有4個頁面組成的集合：A，B，C和D。如果所有頁面都鏈向A，那么A的PR值將是B，C及D的和，則PR(A)=PR(B)+PR(C)+PR(D)；

29、n 繼續(xù)假設B也有鏈接到C，并且D也有鏈接到包括A 的3個頁面，則3)()(2)()(DPRCPRBPRAPR信息組織、存儲與檢索信息組織、存儲與檢索Pagerank計算公式計算公式NiiiPCPPRddAPR1)()()1 ()(其中，PR(A)是頁面A的Pagerank值，PR(Pi)是頁面Pi的Pagerank值，頁面Pi指向頁面A，C(Pi)是頁面Pi含有的鏈接數量，d是阻尼系數，一般取0.85。信息組織、存儲與檢索信息組織、存儲與檢索Pagerank算法的特點算法的特點n優(yōu)點：n是一個與查詢無關的靜態(tài)算法，所有網頁的PageRank值通過離線計算獲得；有效減少在線查詢時的計算量，極大

30、降低了查詢響應時間。n缺點：n1）人們的查詢具有主題特征，PageRank忽略了主題相關性，導致結果的相關性和主題性降低；n2）舊的頁面等級會比新頁面高。信息組織、存儲與檢索信息組織、存儲與檢索HITS (Hyperlink-Induced Topic Search)算法的提出算法的提出n 基于商業(yè)或競爭因素考慮，很少有WEB網頁指向其競爭領域的權威網頁n比如“Microsoft” 和 “Netscape”都是瀏覽器的權威主頁，但并不互指；n 權威網頁很少具有顯式的描述，n比如Google主頁不會明確給出WEB搜索引擎之類的描述信息；n PageRank算法中對于向外鏈接的權值貢獻是平均的，H

31、ITS算法考慮了不同鏈接的重要性 信息組織、存儲與檢索信息組織、存儲與檢索HITS算法基本思想算法基本思想n Kleinberg于1998年提出HITS算法n 兩個重要概念nAuthority 頁面(權威頁面權威頁面)：是指與某個領域或者某個話題相關的高質量網頁；nHub頁面(樞紐頁面樞紐頁面)：指的是包含了很多指向高質量“Authority”頁面鏈接的網頁。n 基本思想n一個好的” Authority”頁面會被很多好的” Hub ”頁面指向；n一個好的” Hub”頁面會指向很多好的” Authority”頁面；信息組織、存儲與檢索信息組織、存儲與檢索Hubs and Authoritiesn

32、合起來趨向于形成如圖:Hubs Authorities信息組織、存儲與檢索信息組織、存儲與檢索HITS算法簡介算法簡介n1.根集合(root set)n將查詢q提交給基于關鍵字查詢的檢索系統(tǒng)，從返回結果頁面的集合總取前n個網頁作為根集合，記為root，則root滿足：n1)root中的網頁數量較少；n2)root中的網頁是與查詢q相關的網頁 ；n3)root中的網頁包含較多的權威(Authority)網頁； 信息組織、存儲與檢索信息組織、存儲與檢索HITS算法簡介算法簡介n2.擴展集合basen在根集root的基礎上，凡是與根集內網頁有直接鏈接指向關系的網頁都被擴充到集合base。根集基本集信

33、息組織、存儲與檢索信息組織、存儲與檢索HITS算法簡介算法簡介n3.計算擴展集base中所有頁面的Hub值（中心度）和Authority值（權威度）n網頁i的Authority值a (i) = h (i) ；n網頁i的Hub值h (i) = a (i) ；n對a (i)、h (i)進行規(guī)范化處理：na (i) = a (i)/|a(i)| ；h (i) = h (i)/ |h(i)| ；n不斷重復，若權值沒有明顯變化，則結束計算；n4.輸出排序結果：將頁面根據Authority權值得分由高到低排序，取權值最高的若干頁面作為響應用戶查詢的搜索結果輸出。信息組織、存儲與檢索信息組織、存儲與檢索HI

34、TS算法舉例算法舉例信息組織、存儲與檢索信息組織、存儲與檢索HITS算法的特點算法的特點n優(yōu)點：n是與用戶輸入的查詢請求密切相關的；n缺點：n計算效率較低；n主題漂移問題；n易被作弊者操縱結果；n結構不穩(wěn)定。信息組織、存儲與檢索信息組織、存儲與檢索HITS算法與算法與PageRank算法比較算法比較n HITS算法是與用戶輸入的查詢請求密切相關的，而PageRank算法與查詢請求無關；n HITS算法計算效率比PageRank算法低；n HITS算法只計算base內網頁之間的鏈接關系，Pagerank算法對所有互聯網頁面進行計算；n PageRank適合部署在服務器端，而HITS算法適合部署在客戶端；n HITS算法適合處理具體的用戶查詢，而Page