【畢業(yè)學位論文】（Word原稿）搜索引擎的信息覆蓋率評測模型研究-計算機系網(wǎng)絡與分布式系統(tǒng)

北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 1 搜索引擎的信息覆蓋率評測模型研究 北京大學計算機科學技術系 ， 100871 摘 要 本文從 向圖結(jié)構(gòu)出發(fā)，總結(jié)分析了搜索引擎搜集子系統(tǒng)網(wǎng)頁搜集不完全性的若干因素，指出信息覆蓋率這一概念的研究意義，由此提出了三類比較重要的信息覆蓋率概念。在對信息覆蓋率建立量化研究模型之后，本文以北大天網(wǎng) 臺為考察對象，以不同的方式對中國 行取樣，用 兩類典型的權值算法計算出其中的重要網(wǎng)頁作為樣本，從量和質(zhì)的角度上考察 信息覆蓋率，得到合理的數(shù)量覆蓋率和質(zhì)量覆蓋率實驗數(shù)據(jù)，從而驗證了 息覆蓋率結(jié)論的合理性和信息覆蓋率評測模型的可靠性。 關鍵詞 搜索引擎，信息覆蓋率，取樣，權值計算，驗證，數(shù)量覆蓋率，質(zhì)量覆蓋率 1 研究背景 1989 年誕生并于次年開始運行以來 ,在迄今為止的十多年里發(fā)展迅猛，已逐漸成為人類社會信息資源中的一個重要組成部分。它以超文本和超媒體為核心技術，將文本、圖形、圖像、音頻和視頻等信息有機結(jié)合起來，給人們以豐富的信息表示空間。隨著 術 和應用的不斷發(fā)展，社會的信息化進程不斷加快，越來越多的社會信息資源開始選擇 為其載體。 當前， 大約有 8,745,000 個網(wǎng)站，約 2,500,000,000 網(wǎng)頁，包含了至少 19且這些網(wǎng)頁正以每天凈增 7,500,000 的速度膨脹 1 2 。而在中國，根據(jù)中國互聯(lián)網(wǎng)絡中心（ 2002 年 1 月進行的互聯(lián)網(wǎng)統(tǒng)計報告 3， 注冊的域名數(shù)為 127,319 個，共有 277,100 個 點。到 2002 年為止，中國境內(nèi)的 點共有 53,432,598 個網(wǎng)頁，主要分布在 約 49,146 個網(wǎng)站中 4。 面對浩瀚的互聯(lián)網(wǎng)絡資源，人們?nèi)舨唤柚渌ぞ吆茈y快速的查找到自己所需要的信息，這帶來了搜索引擎的誕生。從 1994 年誕生的第一代搜索引擎 展到當前流行的 系統(tǒng)，它們已逐漸成為人們進行網(wǎng)際沖浪的重要工具之一。根據(jù)弗吉尼亞理工大學 心的調(diào)查報告 5 ，全世界有 戶通過搜索引擎獲得自己所需網(wǎng)頁，足見搜索引擎功用之一斑。 我們將每一條獨立的 息稱為一個網(wǎng)頁，它有一個唯一的資源定位地址稱為搜索引擎便是利用 間的連接關系，搜集其對應的網(wǎng)頁信息，建立索引，供用戶查詢。因此，搜索引擎搜集的網(wǎng)頁集合便是用戶所能得到查詢結(jié)果的最大范圍；這個范圍越接近 索引擎越優(yōu)秀。事實上，沒有任何一個搜索引擎能搜集完 所有網(wǎng)頁。著名的搜索引擎 統(tǒng)和 北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 2 統(tǒng)，搜集到并提供給用戶查詢的網(wǎng)頁數(shù)量分別是 2,073,418,204 個 6和 1,571,413,2077個，最多不過靜態(tài)網(wǎng)頁總數(shù)的 80%。而根據(jù) 200？年 3 月發(fā)表的搜索引擎統(tǒng)計數(shù)據(jù) 8？ ，這兩個系統(tǒng)的網(wǎng)頁數(shù)據(jù)量是最大的。 網(wǎng)絡上的信息數(shù)量巨大而且種類繁多，任何一個實際運行的搜集系統(tǒng)都不可能將其全部搜盡。優(yōu)秀的搜索引擎總會搜集盡量多的網(wǎng)頁，更好的滿足用戶的查詢要求?？疾焖阉饕鎸?息資源的搜集覆蓋程度，可作為不斷改進搜集系統(tǒng)的根據(jù)，對評價搜索引擎的性能好壞具有積極的作用。 另一方面，隨著社會信息化程度的不斷提高， 是該階段人類社會信息資源在網(wǎng)絡上的投影，記錄著人類社會的歷史發(fā)展進程?；谒阉饕婕夹g開發(fā)的網(wǎng)絡信息博物館正以 此為目的，力圖通過搜索引擎的網(wǎng)頁搜集系統(tǒng)不斷搜集 的所有網(wǎng)頁，若干年后能夠同時在時間和空間上展示 每一個角落。因此，研究搜索引擎的信息覆蓋率對驗證網(wǎng)絡信息博物館網(wǎng)頁資源的有效性也有著十分重大的意義。 本文的研究工作基于上述目的，針對北京大學計算機系網(wǎng)絡與分布式系統(tǒng)實驗室開發(fā)的 索引擎 8及以此為基礎開發(fā)的網(wǎng)上信息博物館 ，采取多種方法從多個角度計算其信息覆蓋率，證明了該網(wǎng)頁搜集系統(tǒng)獲得的中國網(wǎng)絡信息資源是基本有效的。 2 模型概述 頁搜集的不完全性 如果把 的每一個網(wǎng)頁看作一個頂點，則這個頂點以 為它的唯一標記；又由于網(wǎng)頁中存在其它網(wǎng)頁的 以把這種網(wǎng)頁間的鏈接看作連接頂點的邊，則整個 成了一張有向圖，如圖 1 示。相應的，每一個頂點的入度和出度對應著鏈向該網(wǎng)頁的網(wǎng)頁數(shù)量和該網(wǎng)頁鏈向其他網(wǎng)頁的數(shù)量。顯然， 這是一張不完全圖，因為里面存在很多入度或出度為 0 的頂點。 當前的網(wǎng)頁搜集系統(tǒng)都是基于對這種 接結(jié)構(gòu)的理解， 依據(jù)網(wǎng)頁之間的鏈接關系，從某一個種子 始，不斷的從新搜到的網(wǎng)頁中提取出 而到達其它的網(wǎng)頁。搜集過程中，通常需要對網(wǎng)頁 重要性作初步的判斷，優(yōu)先搜集相對有價值的網(wǎng)頁。在這種搜集機制里面，存在著下列問題，導致無法遍歷所有的網(wǎng)頁。 北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 3 部分網(wǎng)頁的入度為 0，即從任何一個網(wǎng)頁開始，都不存在到它的路徑，這類網(wǎng)頁的數(shù)量約占全體網(wǎng)頁數(shù)量的 10%10 。 選擇的種子 合中，任何一個網(wǎng)頁都不存在到該網(wǎng)頁的路徑。 的有向圖結(jié)構(gòu)中，只有約 頂點能被選取作為起始點去遍歷剩下的約 90%的頂點 10。 由于在網(wǎng)頁搜集的過程中出現(xiàn)了優(yōu)先排序，搜集系統(tǒng)資源本身的限制（磁盤容量和時間限量）導致部分網(wǎng)頁直到搜集過程中止都沒有被搜集，出現(xiàn) 情況 11。 身處于不斷的膨脹過程之中，大量新出現(xiàn)的網(wǎng)頁來不及搜集。搜集系統(tǒng)自身一般都有搜集周期，而某些網(wǎng)頁（如實時新聞網(wǎng)頁）的更新頻率遠大于搜集頻率。 從廣義的角度而言，凡是 的信息都應該被搜集，而現(xiàn)在的搜索引擎一般只搜集了部分格式的網(wǎng)頁信息。當前搜集的一般都是靜態(tài)網(wǎng)頁中類似于檔的信息資源，沒有考慮到包括動態(tài)網(wǎng)頁在內(nèi)的巨量深層網(wǎng)絡文檔。據(jù)估計，當前 的所有網(wǎng)頁（包括深層網(wǎng)頁）約有 5500 億之多，搜索引擎所覆蓋的不到其百分之一 12！ 因此，可以肯定任何一個實 際運行的網(wǎng)頁搜集系統(tǒng)都不可能將當前 的所有網(wǎng)頁全部抓盡。這種搜集性能越優(yōu)異，意味著它所獲得網(wǎng)頁集合在數(shù)量和質(zhì)量上越接近于實際的 頁之間的鏈接關系也越逼近實際的 向圖結(jié)構(gòu)。搜索引擎的信息覆蓋率正是對這種接近程度的衡量，它體現(xiàn)了一個網(wǎng)頁搜集系統(tǒng)所獲得的網(wǎng)頁集合及鏈接關系所占實際 比例。 類重要的覆蓋率 廣義的信息資源，應該定義為互聯(lián)網(wǎng)上的一切信息，即所有存在于 的文檔。這些文檔有些能通過瀏覽器瀏覽，有些則不能；有些存在于網(wǎng)站的數(shù)據(jù)庫中，經(jīng)過動態(tài)的請求方能生成，有些則是靜態(tài)存在的 且被其它網(wǎng)頁鏈接到。搜索引擎當前所能搜集的絕大多數(shù)就是這種靜態(tài)的網(wǎng)頁，且在處理過程中進一步過濾掉了某些不可瀏覽的部分如可執(zhí)行文件等。在這里，我們所研究的搜集系統(tǒng)覆蓋目標是 的所有靜態(tài)網(wǎng)頁，它們通?？赏ㄟ^瀏覽器顯示內(nèi)容，且其 般靜態(tài)存在于其它網(wǎng)頁中。我們可以從多個角度來考慮搜索引擎對 息資源的覆蓋程度。 搜集系統(tǒng)應該力圖遍歷 所有網(wǎng)頁，在數(shù)量這一角度上達到完全覆蓋的程度。這提供一個衡量搜集系統(tǒng)覆蓋 息能力的全局標準。例如當前 的網(wǎng)頁估計約為 2,500,000,000 個 2 ， 統(tǒng)的網(wǎng)頁搜集數(shù)量是 2,073,418,204 個 6 ，因此可以估計其數(shù)量覆蓋率為百分之八十左右。如果系統(tǒng)的數(shù)量覆蓋率足夠高，我們就可以認為它基本上覆蓋了 的所有信息資源。高的數(shù)量覆蓋率應該是任何一個搜集系統(tǒng)及以此為基礎的網(wǎng)上信息博物館的首要目標。 網(wǎng)上信息資源極為豐富，但也存在不少冗余，大量的廣告頁面和內(nèi)容重復頁面便是北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 4 此例。即使去除這些冗余后，用戶感興趣的網(wǎng)頁通常也只是數(shù)以十億計的數(shù)量中的極少數(shù)。因此，考慮搜集系統(tǒng)在質(zhì)量上對 頁的覆蓋程度顯得尤為重要。這一指標可以告訴我們，對 那些用戶會感興趣的重要的網(wǎng)頁，系統(tǒng)覆蓋了其中的百分之幾。從更深的層次來說，如果搜集系統(tǒng)覆蓋了絕大多數(shù)的“重要”網(wǎng)頁，它也就覆蓋了當前社會信息在每一個重要主題上映射到 的部分，成為它的一個有效特征子集。類似于系統(tǒng)如果將這些重要網(wǎng)頁全部記錄下來，以后就能通過歷史網(wǎng)頁回放來重現(xiàn)人類社會信息資源在時間和空間兩維上的每一個角落。 從信息的表現(xiàn)形式來看，搜集系統(tǒng)當前存儲的信息中相當一部分日后將是不可見的。這一方面是由于存儲系統(tǒng)的資源所限，未能搜集類似于圖片影音之類的大文檔；另一方面是因為搜 集技術的不成熟，無法獲得類似于 格式的網(wǎng)頁。因此，考察搜集系統(tǒng)對可視網(wǎng)上信息資源的覆蓋率，也有著積極的意義。它可以告訴我們當前所搜集到的網(wǎng)頁當中，多大比例的一部分能夠在若干年后通過瀏覽器重新瀏覽。 在本文的研究中，將對前面的兩種進行詳細的討論和量化分析。 息覆蓋率評測模型 我們定義搜集系統(tǒng)的信息覆蓋率為它所收集的網(wǎng)頁集合在 所占的比例。考慮到 鏈接結(jié)構(gòu)，將其視為一張有向圖 G=（ V ， E），則搜集系統(tǒng)所獲得的網(wǎng)頁集合是 G 的強連通子圖？（不一定是強連通圖） G=（ V， E），每一個頂點都有唯一的標記 信息覆蓋率的表達式為： C=| | G的相關屬性在搜集過程中已得到，但是因為搜索引擎搜集網(wǎng)頁的不完全性， G 的相關屬性卻只能去估計。為了得到準確的信息覆蓋率數(shù)據(jù)，我們采取對 樣的方法，即采取隨機的方式從中獲得一張子圖0G=（ 考察 V中的頂點落在 0的比例 的近似值。如果0 則 。此時的 我們可以用類似的思想去計算搜集系統(tǒng)的質(zhì)量覆蓋率。考慮 的所有重要網(wǎng)頁構(gòu)成的連通子圖 們可以用隨機的辦法獲得某些重要網(wǎng)頁組成的集合 S 作為樣本，來考察搜集系統(tǒng)覆蓋 S 中的子集 為近似的質(zhì)量覆蓋率此質(zhì)量覆蓋率的表達式為：（為什么用雙豎線？） |S| | 0S 因此，我們需要通過對 機取樣獲得網(wǎng)頁樣本；需要采取某些方法得到隨機的重要網(wǎng)頁集合，這通常要利用網(wǎng)頁之間的鏈接關系來對網(wǎng) 頁進行權值估算；在得到網(wǎng)頁樣本之后，再檢查搜集系統(tǒng)的網(wǎng)頁覆蓋其中的比例，在檢查過程中，必須對網(wǎng)頁過濾，扔掉無法連接到的網(wǎng)頁?？傮w的工作流程大致如下圖所示： 北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 5 3 數(shù)量覆蓋率 我們可以從不同的角度來對 進行采樣。如果不考慮頂點之間的鏈接關系，僅從頂點的標記 對應的 址出發(fā)，可以采取隨機產(chǎn)生 方法來獲得一個網(wǎng)頁集合，從而得到樣本，這種考慮基于全局的視點；如果考慮到頂點之間的鏈接關系，則可以模仿搜索引擎搜集系統(tǒng)的工作方式，采取絕對廣度優(yōu)先的辦法，從某一個頂點（種子 發(fā)，逐漸擴展遍歷，得到 一個網(wǎng)頁集合作為樣本，這是一種從局部來進行取樣的辦法。 機 在 和 工作 13中，他們提出了通過隨機產(chǎn)生 行取樣的方法。首先獲得 已經(jīng)分配使用的所有 址，假設共有 M 個?？梢岳?分段將它們一一映射到 0 到 間的某個整數(shù)作為唯一標記。這樣，我們可以利用隨機算法產(chǎn)生小于 M 的整數(shù)，得到一個 記集合，再逆映射回到 址，即得到一組隨機 本。如果搜集系統(tǒng)以域名標志網(wǎng)站地址，還需要將其轉(zhuǎn)換為域名。這種取樣原理如圖 3 所示： 樣 我們在研究工作中獲得了中國國內(nèi)已分配的所有 址分段 4322 個， 其中一個分段，被分配給北京大學使用。如果統(tǒng)一用點北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 6 分十進制表示所有網(wǎng)絡地址，則所有的 段可以表示如下 12 n其中， 為 0 到 255 之間的整數(shù)?？梢娺@些分段不相交，統(tǒng)計出每一個分段中的 址數(shù)量 則可以找到一一映射 F 使得 址 t）的函數(shù)值為： F(10（ * 3256 +(* 2256 + (*256 + (于是我們將每一個 對應到一個整數(shù)，便可以用隨機算法在其中選取若干，逆映射 轉(zhuǎn)變?yōu)?址，便得到一個 址集合。去掉此集合中不提供 務（包括與網(wǎng)絡無連接）的元素，就得到了一個網(wǎng)站樣本。由于大約 14的網(wǎng)站通過 80 端口提供 務，我們可以順次掃描這些網(wǎng)絡地址上的 80 端口。得到的存在 務的址集合經(jīng)反向域名解析便可得到樣本 合。 通過對中國國內(nèi)的 行隨機取樣并進行掃描，我們得到了如下結(jié)果： 編號 1 2 3 4 5 6 7 8 9 10 隨機 100K 200K 300K 400K 500K 600K 700K 800K 900K 1M 存在 95 172 252 336 418 478 570 652 717 817 表格中間線太粗，而且第三條應該是不可見的 在上面的統(tǒng)計中，我們選取了多組不同數(shù)量的隨機 到的存在 務的 明選出的 址具有很好的隨機性。 證 由于搜集系統(tǒng)一般以包含域名的 記錄網(wǎng)頁，我們要檢驗這些網(wǎng)頁是否已被覆蓋，應該將其轉(zhuǎn)化為相應的域名。由于網(wǎng)絡中 務器提供的 向解析功能有限，而搜集系統(tǒng)在搜集過程中通常記錄了搜到的網(wǎng)頁 域名與 址的對應關系，我們可以由此直接檢驗被覆蓋的 址數(shù)量。 我們的目的是對所有的 址進行建模，接下來的問題應該是該用多少數(shù)據(jù)才能滿足要求使得樣本有效。盡管我們就這一問題無法給出精確的數(shù)量，但是可以從少量的數(shù)據(jù)開始，然后逐步增加數(shù)據(jù)量。如果我們這種通過隨機產(chǎn)生 樣的辦法是正確的，在原先樣本的基礎上逐步增加數(shù)據(jù)集將不會影響信息覆蓋率的結(jié)果。因此，我們可以對樣本容量從小到大的各組數(shù)據(jù)統(tǒng)計得到的覆蓋率進行分析，看是否滿足以上條件。 北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 7 下表是在各組隨機 址樣本中，被搜集系統(tǒng)覆蓋的 址所 占比例。 編號 1 2 3 4 5 6 7 8 9 10 存在 95 172 252 336 418 478 570 652 717 817 覆蓋 4 7 9 13 16 21 28 36 43 47 可以通過最小二乘法對結(jié)果進行線性擬合，得到以下的二維圖像。其中，橫軸代表隨機 址樣本容量，縱軸代表搜集系統(tǒng)覆蓋樣本的數(shù)量，直線的斜率則表示信息覆蓋率。從圖中可知，自變量和因變量之間存在很好的一次函數(shù)關系，右。由此可以推斷，當樣本擴展到所有的 址時， 覆蓋率將會保持在這個數(shù)量左右。 型修正和結(jié)果分析 隨機 產(chǎn)生了大量的隨機 址，用這種方法可以很好的對 的所有提供 務的 務器進行取樣；隨著樣本容量的增加，樣本的精確性也會增加。但是，這種采樣方法存在一些不足，導致信息覆蓋率具有較大偏差。 首先， 址標記的是 務器的網(wǎng)絡地址，在大多數(shù)情況下，它等同于該服務器上運行的網(wǎng)站首頁。這使得我們最終得到的網(wǎng)頁集合實際上是 網(wǎng)站首頁的一個樣本。使用 址將使得我們對所有的網(wǎng)站一視同仁，忽 略了網(wǎng)站的大小之別。一個只有三五個網(wǎng)頁的個人小網(wǎng)站（ 如 ）和一個有著上千網(wǎng)頁的大商業(yè)網(wǎng)站（ 如 ，為 ）是不等同的，然而這種區(qū)別在隨機 址取樣中無法體現(xiàn)。 另外，大量存在 務的服務器并非是實際意義上的網(wǎng)站。大多數(shù) 列操作系統(tǒng)自帶的 務器軟件， 統(tǒng)自帶安裝的 件，如此眾多，都會在缺省條件下提供 務，而這些“網(wǎng)站首頁”是沒有實際意義的測試網(wǎng)頁。類似的，也有大量的在某個 址短暫出現(xiàn)的網(wǎng)頁（例如臨時通過 務共享文件等等）。北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 8 在上述隨機 樣方法中，這些基本無效的網(wǎng)頁都被簡單的等同于重要網(wǎng)站首頁加入了樣本之中。 因此，我們有必要對此模型作出修正。既要利用隨機 法具有的優(yōu)異的隨機性和全局性，又要保證通 過隨機 址獲得的網(wǎng)頁的有效性。解決辦法是利用網(wǎng)頁之間的鏈接關系，不再將各個網(wǎng)頁看作獨立的點，通過發(fā)現(xiàn)網(wǎng)頁中的 進行適當擴展。我們在研究中將得到的所有隨機 址視為基本集合 R ，通過 議取得這些 取出其中的鏈接，加入 R，作為 頁樣本，如下圖所示： 為了將無效網(wǎng)頁的影響降至最低，還可以對鏈接作多級擴展。經(jīng)過這種處理后，上述第一種情況可以得到修正，因為大網(wǎng)站的首頁通常存在較大的出度；第二種情況中默認網(wǎng)頁鏈出的網(wǎng)頁一般指向該軟件生產(chǎn)廠家的首頁，頁面相同且數(shù) 量少，且因其通常在國外故可在研究 過濾掉。我們從上述的隨機樣本中抽取了 5 組，經(jīng)過擴展以后的網(wǎng)頁樣本數(shù)量以及覆蓋數(shù)量如下： 編號 1 3 5 7 10 存在 95 252 418 570 817 擴展樣本容量 1084 2584 3859 5484 8094 覆蓋 174 596 841 1204 1899 在驗證的過程中，我們將用 址表示的 化成域名 便搜集系統(tǒng)的驗證。這種轉(zhuǎn)換經(jīng)過了兩級反向解析，第一步是通過網(wǎng)上 務器的解析，第二步 是通過搜集系統(tǒng)保存的域名與 應數(shù)據(jù)。對得到的結(jié)果作線性擬合，得到的圖幾（沒有標）如下，從擬合結(jié)果可得到信息覆蓋率約為 可見，在對模型作修正之后，覆蓋率有很大的增幅；如果考慮到域名與 間的動態(tài)關系（即大量域名的 可變的， 統(tǒng)每隔幾分鐘更新一次），我們?nèi)コ魳颖局幸?示的 量覆蓋率數(shù)據(jù)將還會有小幅度的提高，這才是真正的數(shù)量覆蓋率大小。 通過隨機 產(chǎn)生的網(wǎng)頁樣本很好的考察了搜集系統(tǒng)對 向圖某些入度為 0或是從出發(fā)頂點無法達到頂點的覆蓋情況。這啟示我們在搜集網(wǎng)頁過程 中，選取適當數(shù)量的以隨機 產(chǎn)生的 為起始頂點集合的一部分，能提高搜集系統(tǒng)的數(shù)量信息北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 9 覆蓋率和 網(wǎng)頁信息的有效性。 度優(yōu)先法 隨機 雖然具有較好的隨機性和全局性，但在使用過程中發(fā)現(xiàn)許多有待改進之處；為了使對 取樣在邏輯結(jié)構(gòu)上與實際情況更加接近，考慮到對隨機 作修正時對邏輯鏈接關系的利用，我們提出了絕對廣度優(yōu)先搜集取樣的辦法。這種方法實現(xiàn)的實際就是一個最原始的搜集系統(tǒng)的工作過程，只是在搜集過程中按照絕對廣度優(yōu)先的方式一級級的擴展開去。這種取樣是從局部的角度來進行 的，原理如下圖所示。 樣 我們選取了五個 為起始點，采取上述絕對廣度優(yōu)先搜集網(wǎng)頁的辦法分別獲得五組 頁樣本，樣本容量從幾萬到數(shù)十萬不等。算法如下： （ 1）選取某個網(wǎng)頁 S 作為起始 （ 2）創(chuàng)建隊列 Q 存儲未搜集的網(wǎng)頁， S 入隊列；創(chuàng)建結(jié)構(gòu)數(shù)組 A 存儲已經(jīng)搜集過的網(wǎng)頁，按照 符串排序； （ 3）取得隊列頭元素，通過 議獲取 H 的源文件，提取出其中包含的的全部 接，并記錄鏈接關系； 北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 10 （ 4）在 A 中用二分法尋找（ 3）中得到的 否已被搜集，如果沒有搜集，則使其進入 隊列 Q； （ 5）判斷 A 中的網(wǎng)頁數(shù)量是否已達到要求，若沒有繼續(xù)（ 3）。 得到的結(jié)果列表如下： 樣本編組 1 2 3 4 5 種子 展 66891 211629 154314 723866 174078 證和分析 得到網(wǎng)頁樣本之后，我們可以在 網(wǎng)頁數(shù)據(jù)庫中驗證被覆蓋的比例。為了快速的檢驗數(shù)據(jù)，達到磁盤性能的極限，我們啟動了數(shù)百個進程從 表中讀取并通過 法從庫中查找。得到的覆蓋率數(shù)據(jù)如下表所示。 對于這組離散的覆蓋率值，我們 計算均值和方差分別為 者即為通過絕對廣度優(yōu)先法得到的數(shù)量覆蓋率。 樣本編組 1 2 3 4 5 擴展 66891 211629 154314 723866 174078 覆蓋數(shù)量 26732 87562 67178 273066 74370 數(shù)量覆蓋率 對于使用這種采樣方法得到的數(shù)量覆蓋率 較之采用隨機 具有較高的覆蓋率值是可以理解的。因為這兩批數(shù)據(jù)是從兩個不同的方面說明搜集系統(tǒng)的信息覆蓋 情況：隨機 著眼于全局，而絕對廣度優(yōu)先法著眼于局部，更類似于搜索引擎的搜集過程。 通常搜集系統(tǒng)是在 的最大連通子圖內(nèi)遍歷，絕對廣度優(yōu)先法恰好反映了搜集系統(tǒng)對這一最大連通子圖的覆蓋比例。由于這一最大連通子圖占據(jù)了 90%10左右的網(wǎng)頁，而且我們選取的起始 落在這一子圖之內(nèi)，故絕對廣度優(yōu)先法得到的結(jié)論應該修正為乘以 90%這一參數(shù)才能在全局角度上反映搜集系統(tǒng)的覆蓋率，因此準確的數(shù)量覆蓋率應該是 當樣本容量越大 ,覆蓋率就應該約逼近此值 ,這從我們采用的大容量樣本 (第 4 組 )結(jié)果中已經(jīng) 得到了驗證。 隨機 反映的是搜集系統(tǒng)對 所有點的覆蓋情況，因此這種采樣更容易采集到入度為 0 或由于其他原因?qū)е滤鸭到y(tǒng)無法遍歷到的網(wǎng)頁（稱為不可到達網(wǎng)頁）。由于不可到達網(wǎng)頁中大量的點是孤立點，在沒有很好的區(qū)分這些 址上所存在的網(wǎng)頁數(shù)據(jù)量的情況下，這種樣本需要經(jīng)過多級鏈接擴展才能全面的反映真實的 就是說，如果對初始 斷作鏈接擴展，最后的數(shù)據(jù)會不斷接近 這在我們作第北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 11 一級擴展之后已經(jīng)有了好的反映。 我們可以預測到，如果將兩種采樣方法的優(yōu)點結(jié)合起來，通過隨機 產(chǎn)生 絕對廣度優(yōu)先法取樣的種子集合再進行擴展，在樣本容量足夠大之后，最后的數(shù)量覆蓋率數(shù)據(jù)應該與通過文獻 10 的工作做的估計相符，在 近。 4 質(zhì)量覆蓋率 考察搜集系統(tǒng)在質(zhì)量上對 信息覆蓋率，需要通過有效的網(wǎng)頁重要性評測方法找到一組重要網(wǎng)頁樣本。盡管通?？梢酝ㄟ^用戶評選提交的方式得到他們在瀏覽網(wǎng)頁過程中發(fā)現(xiàn)的重要網(wǎng)頁集合作為樣本，但在本文研究中，為了保證樣本的隨機性和客觀性，我們采用兩類基于對 接結(jié)構(gòu)的分析而對 重要網(wǎng)頁進行取樣的有效方法。 這些方法的基本思想都是找到一組具有較強鏈接關 系的網(wǎng)頁（初始取樣），通過基于鏈接分析的網(wǎng)頁權值算法，求出其中所有網(wǎng)頁的相對重要性值，從而可以對網(wǎng)頁進行排序取出前若干位作為重要網(wǎng)頁的樣本。這些經(jīng)典的權值算法包括斯坦福大學開發(fā) 法 15和 究院開發(fā) 統(tǒng)提出的 法 16 （ 它們都是基于對 向圖鏈接結(jié)構(gòu)的理解提出的。 頁重要性評測方法 的信息資源數(shù)量如此之大，無論是搜集系統(tǒng)本身還是接受返回結(jié)果的查詢用戶，都要求有好的方法對網(wǎng)頁集合按照重要性進行排序，因為系統(tǒng)搜集的和用戶關心的一般都只是其中的某一子集。準確的辨別出重要的網(wǎng)頁加以優(yōu)先搜集，準確的計算出重要的網(wǎng)頁返回給用戶優(yōu)先瀏覽，要做到這些，我們需要合適的網(wǎng)頁重要性評定方法。這里，網(wǎng)頁的重要性用權值來衡量，權值越高表示網(wǎng)頁越重要。 我們可以從三個角度來分析網(wǎng)頁的權值，討論它的相關因素。 從網(wǎng)頁本身的唯一屬性 發(fā)來考慮：網(wǎng)頁的權值可以從 屬性中得到反映。一般而言， 在 網(wǎng)站的域名越短，所在網(wǎng)站上相對于根目錄的層次越淺，網(wǎng)頁的權值越大。例如， 北京大學的網(wǎng)站首頁 ；而 。這一原理可以在網(wǎng)頁搜集過程中加以利用。 從網(wǎng)頁作為 向圖的一個節(jié)點來考慮：網(wǎng)頁的權值可以根據(jù)它的認可度來判斷，由于網(wǎng)頁間的鏈接通常代表著認可度的傳遞，我們可以統(tǒng)計網(wǎng)頁的入度來評判其重要性。如果網(wǎng)頁 A 上存在網(wǎng)頁 B 的 除掉純粹導 航的因素，表示著網(wǎng)頁 A 的作者存在對網(wǎng)頁 B 的認可；而這種認可的增多則意味著網(wǎng)頁 B 權值的上升。因此，入度越大，權值通常越高。 北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 12 從網(wǎng)頁本身的內(nèi)容出發(fā)來考慮：在搜索引擎搜集網(wǎng)頁的過程中，通常都要保存網(wǎng)頁的關鍵詞或全文信息，以便建立索引。由于網(wǎng)頁的重要性一般又對應著用戶較高的關心程度，我們可以通過對用戶遞交給搜索引擎的查詢詞與網(wǎng)頁的內(nèi)容（全文或關鍵詞）進行匹配，匹配程度越高意味著網(wǎng)頁的權值越高。當然，這要求用戶遞交的查詢是希望得到大量相關網(wǎng)頁的寬主題查詢。該情況在論文 18中有詳細討論。 當前大 多數(shù)搜索引擎所采用的網(wǎng)頁權值計算方法正是上面提到的的 法和 法兩種，它們分別利用了上述中的后兩種原理，而且對其間的網(wǎng)頁鏈接關系作了更深層次的挖掘。 法 15是一種利用網(wǎng)頁間鏈接關系進行權值計算的典型方法，它是學術論文引用統(tǒng)計原理在 的推廣，它統(tǒng)計每個網(wǎng)頁被引用的次數(shù)，但每一次引用又因引用者權值的不同而不同；而 法 17 將網(wǎng)頁的權值分為目錄型權值和權威型權值分別進行計算，目錄型權值高表示它鏈向很多權威型權值高的網(wǎng)頁，而權威型權值高則表示它被很多目錄 型權值高的網(wǎng)頁所鏈接到。（目錄型、權威型沒有解釋） 基于這兩種權值算法，我們提出了下面的兩類質(zhì)量覆蓋率確定方法。 度優(yōu)先法 樣 法根據(jù)網(wǎng)頁間的鏈接關系來評判網(wǎng)頁的重要性，因此我們選取的初始網(wǎng)頁集合必須和 著大致相同的鏈接結(jié)構(gòu)，保證初始樣本中每個網(wǎng)頁的入度與實際互聯(lián)網(wǎng)絡相差不大，或者網(wǎng)頁入度的相對大小變化不大。這樣才能使得初始樣本中的相對網(wǎng)頁權值保持不變。 我們可以利用絕對廣度優(yōu)先的辦法，從初始 始向外遍歷。隨著初始樣本容量的加大，每個樣本網(wǎng)頁的入度越來越接近于它 在 的實際入度，樣本網(wǎng)頁的入度相對大小也越來越固定。我們以數(shù)量覆蓋率研究中的廣度優(yōu)先法所獲樣本作為初始樣本，它們的數(shù)量一般在數(shù)十萬，已能基本保證其中相當數(shù)量網(wǎng)頁的相對入度大小。用法從中計算選出權值在前 M 位的網(wǎng)頁集合作為樣本。顯然， M 值越小，樣本的有效性越容易得到保證。 法 假定網(wǎng)頁 A 在 面被網(wǎng)頁 鏈到， C(A)表示從 A 鏈出去的網(wǎng)頁數(shù)量（即出度），則 A 的權值可以表示如下： )=)( 17 這種基本思想可以從下圖中體現(xiàn)： 北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 13 考慮到用戶從 發(fā)只有 d（ 0的形式存入關系數(shù)據(jù)庫。當網(wǎng)頁的數(shù)量足夠大時，所有的網(wǎng)頁及其鏈接屬性無法一次全部存入內(nèi)存中，故需要分塊對矩陣進行迭代。 具體的實現(xiàn)算法如下： （ 1） 創(chuàng)建數(shù)據(jù)結(jié)構(gòu)存儲網(wǎng)頁的整數(shù) 值、出度、入度以及所有鏈入網(wǎng)頁的此作為矢量 W 的單元； （ 2） 根據(jù)網(wǎng)頁的平均入度 2估計系統(tǒng)內(nèi)存一次能存放的 量 N，在我們的系統(tǒng)中，估計約為 1 （ 3） 從數(shù)據(jù)庫中導出 N 個 內(nèi)存，按 序；再將全部的鏈接關系導入，對于上述 N 中的每一個，填充進它的鏈接屬性； （ 4） 對于 N 中的每一個，用二分法找到它的鏈入 數(shù)組下標，如果不在當前內(nèi)存中則其權值以平均值計算，運用 法計算其權值； 北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 14 （ 5） 如果全部的 已經(jīng)導入計算過，則對該矢量進行處理使得所有 權值之和為 1；否則繼續(xù)（ 4）； （ 6） 如果先后兩次計算的 W 距離足夠小，則對權值排序選取前 M 個輸出到文件；否則繼續(xù)（ 3）。 （ 7） 將輸出文件中的所有 數(shù) 換為 符串。 實驗在 統(tǒng)上運行，主要硬件指標是 1存 ， P 50 們以數(shù)量覆蓋率計算中得到的五組樣本作為初始樣本，如果選擇權值排序位于前面約 5%左右的網(wǎng)頁作為重要網(wǎng)頁的標準，得到了如下結(jié)果： 樣本編組 1 2 3 4 5 種子 始擴展數(shù)量 66891 211629 154314 723866 174078 數(shù) 3523 8497 8702 33436 8408 占前百分之幾 覆蓋 1542 4032 4754 17717 3456 質(zhì)量覆蓋率 取前 M 個 ,為什么每組 占前百分之幾不相同。 對五組樣本檢驗得到的質(zhì)量覆蓋率計算均值和方差分別是 為了保證所求樣本網(wǎng)頁的重要性有效，我們選取了上述樣本中的第 2 組和第 4 組，改變判斷重要性的標準，質(zhì)量覆蓋率隨此而變化的情形如下表所示。 對于第二組網(wǎng)頁樣本： 重要網(wǎng)頁個數(shù) 1811 3434 5117 6808 8497 占前百分之幾 覆蓋網(wǎng)頁數(shù) 1145 2068 2788 3363 4032 質(zhì)量覆蓋率 下圖是隨著重要性標準的放松，質(zhì)量覆蓋率的變化情況： 北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 15 對于第四組網(wǎng)頁樣本： 重要網(wǎng)頁個數(shù) 17321 33436 49198 64450 79155 占前百分之幾 覆蓋網(wǎng)頁數(shù) 9903 17717 24718 31126 36780 質(zhì)量覆蓋率 下圖是隨著重要性標準的放松，質(zhì)量覆 蓋率的變化情況： 從這兩張圖中可以看出，當重要標準很苛刻時重要網(wǎng)頁樣本容量很小，此時搜集系統(tǒng)的覆蓋率很高；但隨著重要標準的放松導致樣本容量的增大，搜集系統(tǒng)的質(zhì)量覆蓋率會越來越低；當重要性的標準放至最低，即所有網(wǎng)頁的地位平等時，質(zhì)量覆蓋率變?yōu)樽钚。瑸閿?shù)量覆蓋率值。這兩張圖中都顯示，當重要標準降至約 5%左右時，曲線開始逐漸變得平緩，因此此點的覆蓋率數(shù)據(jù) 疑最適合作為我們所測的的搜集系統(tǒng)質(zhì)量覆蓋率。 北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 16 題查詢法 網(wǎng)頁具有作為 向圖結(jié)構(gòu)中一個頂點的相關邏輯屬性，它又可根據(jù)其內(nèi)容本身而屬于人類社 會信息資源的某一主題類別。例如，網(wǎng)頁可以根據(jù)其內(nèi)容分為屬于社會、人文或休閑娛樂等類別以及它們的子類的網(wǎng)頁?；谶@一點的考慮，我們的研究工作中采取了通過主題查詢獲得 要網(wǎng)頁樣本的方法。這類似于文獻 19 的工作中 于 同一主題的網(wǎng)頁之間具有較強的鏈接關系 19，我們可用 法對此網(wǎng)頁集合進行權值計算，進行排序后得到前若干網(wǎng)頁作為 這一主題類別的重要網(wǎng)頁樣本。 樣 假設我們希望得到 于主題 T 的重要網(wǎng)頁樣本，我們一般會通過遞交 若干與T 相關的查詢詞 Q 提交給搜索引擎，它返回的網(wǎng)頁集合為 R。對于通常的搜索引擎， 較高的相關度，因為查詢中通常使用字符串匹配，使得返回的網(wǎng)頁中大多含有 Q 之類的字樣。但是，也有大量的重要網(wǎng)頁不適合這種情況，例如天網(wǎng)系統(tǒng)的主頁并沒有搜索引擎的字樣供匹配。出于對這種特殊現(xiàn)象的考慮，需要對 R 以適當?shù)臄U展，加入 R 網(wǎng)頁鏈出去的網(wǎng)頁和鏈向 R 元素的網(wǎng)頁得到初始樣本 S ，如圖示： 我們選擇了八個主題的查詢詞遞交給天網(wǎng)搜索引擎，在用以上的方式對返回結(jié)果進行擴展之后，得到了八組初始網(wǎng)頁樣本如下： 樣本編 組 1 2 3 4 5 6 7 8 查詢詞 北京大學 考研 股票 江澤民 程 聯(lián)想集團 三個代表 世界杯 返回數(shù)量 1802 1802 1802 1802 1355 1802 1802 1802 擴展數(shù)量 11667 19379 13403 11006 26548 15498 11608 20823 法 北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 17 上圖中的 S 正是我們用 法進行權值計算的對象。對于 S 中的任意一個元素P ，設 H(P)表示其目錄型權值（ A(P)表示其權威型權值（ 2, ,鏈到 P 的網(wǎng)頁， 2, ,從 P 鏈出的網(wǎng)頁，則 A(P)和 H(P)可以從下面的式子計算： A(P)= H(P)= 同 法類似，我們可以將所有的網(wǎng)頁的目錄型權值看作矢量 H，將所有網(wǎng)頁的權威型權值看作矢量 A，設樣本中所有網(wǎng)頁及鏈接關系構(gòu)成的有向圖的鄰接矩陣為 M，考慮到兩個 間最多有一個鏈接使得若存在網(wǎng)頁 i 到網(wǎng)頁 j 的鏈接則 Mi,j=1否 則 Mi,j=0，那么上面的式子可以寫成： A= H H=M A 由此兩式可得 A= M A，即實際上 A 是 M 的特征向量；同理 H 是M 特征向量，我們因此也可以用冪法或 法等來通過迭代來求得 A 和 H 的值。但考慮到系統(tǒng)內(nèi)存對初始樣本容量的限制，若數(shù)量很大的時候需要分塊對兩個矩陣進行迭代。 驗結(jié)果 在我們 的研究工作中，我們沒有通過計算特征向量而采取了根據(jù)前一組公式直接進行迭代計算 A 和 H 值的辦法，具體的實現(xiàn)算法如下： （ 1） 采集初始樣本時將所有的 號存入數(shù)據(jù)庫，同時存入 間的鏈接關系； （ 2） 創(chuàng)建相關的數(shù)據(jù)結(jié)構(gòu)存儲每個 值及鏈接關系，從數(shù)據(jù)庫中導出所有 性并填充到數(shù)據(jù)結(jié)構(gòu)中； （ 3） 給予 H 和 A 某個初始值，分別計算 A（ i+1） = H（ i）和 H(i+1)=M A(i)，直至 A(i+1)和 A(i)的距離足夠小為止； （ 4） 分別對 進行 冒泡排序，輸出前若干個 文件中。 在確定重要網(wǎng)頁的界限時，我們選取的是初始網(wǎng)頁樣本中權值排在前面約 15%左右的部分，大致與搜索引擎響應查詢詞返回的網(wǎng)頁數(shù)量相當。即搜索引擎就此主題返回 們經(jīng)過計算后也給出 X 個“真正”重要的網(wǎng)頁，檢查搜集系統(tǒng)覆蓋其中的比例作為質(zhì)量覆蓋率。 對于具有較高 值的重要網(wǎng)頁，實驗的數(shù)據(jù)如下： 樣本編組 1 2 3 4 5 6 7 8 北京大學計算機科學技術系 網(wǎng)絡與分布式系統(tǒng)實驗室 孟濤學士論文 18 查詢詞 北京大學 考研 股票 江澤民 程 聯(lián)想集團 三個代表 世界杯 初始數(shù)量 11667 19379 13403 11006 26548 15498 11608 20823 數(shù) 1671 1701 1532 1040 1508 1428 1859 1961 覆蓋數(shù)量 958 956 578 312 772 514 793 651 覆蓋率 30% 八組樣本所得的質(zhì)量覆蓋率分別為表幾所示，它們的均值和方差分別為 者即為搜集系統(tǒng)對 重要網(wǎng)頁的覆蓋率。 對于具有較高 值的重要網(wǎng)頁，實 驗的數(shù)據(jù)如下： 樣本編組 1 2 3 4 5 6 7 8 查詢詞 北京大學 考研 股票 江澤民 程 聯(lián)想集團 三個代表 世界杯 初始數(shù)量 11667 19379 13403 11006 26548 15498 11608 20823 數(shù) 1400 1572