《網(wǎng)絡(luò)信息檢索》課件第3章

第3章網(wǎng)絡(luò)信息的自動(dòng)搜集3.1網(wǎng)絡(luò)信息的特點(diǎn)3.2網(wǎng)絡(luò)信息搜集的原理3.3網(wǎng)絡(luò)信息搜集的禮貌原則3.4高性能信息搜集3.5專題信息搜集3.6小結(jié)思考題

3.1網(wǎng)絡(luò)信息的特點(diǎn)

網(wǎng)絡(luò)信息有各種各樣的表現(xiàn)形式，這些信息都在WWW(WorldWideWeb，萬(wàn)維網(wǎng)，簡(jiǎn)稱Web)上產(chǎn)生、流轉(zhuǎn)和消亡，其中Web頁(yè)面(網(wǎng)頁(yè))已經(jīng)成為網(wǎng)絡(luò)信息最重要的載體。隨著網(wǎng)絡(luò)的普及，網(wǎng)頁(yè)的數(shù)量也成倍增加。據(jù)Cyveillance公司2000年關(guān)于網(wǎng)頁(yè)大小的調(diào)研報(bào)告稱[1]，Web上總網(wǎng)頁(yè)數(shù)高達(dá)21億，每天約增加730萬(wàn)個(gè)網(wǎng)頁(yè)，如果每個(gè)網(wǎng)頁(yè)按照平均15KB來(lái)計(jì)算，約需要109GB的存儲(chǔ)空間；到2005年1月為止，可見(jiàn)的網(wǎng)頁(yè)(surfaceweb)在115億左右[2]，還不包括估計(jì)約500倍于可見(jiàn)網(wǎng)頁(yè)的深度網(wǎng)頁(yè)(deepweb)[3]，如動(dòng)態(tài)網(wǎng)頁(yè)或搜索引擎無(wú)法到達(dá)的網(wǎng)頁(yè)。網(wǎng)頁(yè)之間或者具有鏈接的關(guān)系，或者毫無(wú)關(guān)系、或者短期內(nèi)消失。因此，要全面地搜集和管理網(wǎng)絡(luò)信息，并不是一件容易的事情。要有效地搜集信息，需要對(duì)萬(wàn)維網(wǎng)信息的組織結(jié)構(gòu)進(jìn)行深入的學(xué)習(xí)和了解。掌握了網(wǎng)絡(luò)信息的組織結(jié)構(gòu)和特點(diǎn)，就可以采用相應(yīng)的對(duì)策和方法盡可能全面地來(lái)搜集這些信息了。3.1.1Web的組成

簡(jiǎn)單地說(shuō)，Web由三部分組成：資源、資源標(biāo)識(shí)和傳輸協(xié)議。資源對(duì)應(yīng)著Web頁(yè)面或各種文件，資源標(biāo)識(shí)則是定位和指向資源的符號(hào)，而傳輸協(xié)議則負(fù)責(zé)在一些實(shí)體(如客戶端和服務(wù)器)之間傳送資源。

1．資源

Web上包含許多可用的資源，如文本、圖像、視頻片段和程序等。目前Web最主要的信息資源組織方式是HTML文檔。HTML(HyperTextMarkupLanguage)是超文本標(biāo)記語(yǔ)言，它由一系列的標(biāo)簽(tag)組成，說(shuō)明網(wǎng)絡(luò)信息的具體內(nèi)容及網(wǎng)絡(luò)信息的表現(xiàn)形式。HTML文檔的名字后綴一般是htm或html。HTML文檔包含的信息內(nèi)容可以通過(guò)Web瀏覽器(Browser)來(lái)顯示。Web瀏覽器可以對(duì)HTML文檔進(jìn)行解析，并將內(nèi)容按照標(biāo)簽指示，在瀏覽器中一頁(yè)頁(yè)地顯示出來(lái)。

HTML是簡(jiǎn)單的標(biāo)識(shí)語(yǔ)言，用來(lái)創(chuàng)建萬(wàn)維網(wǎng)上使用的超媒體文檔。HTML使用標(biāo)簽來(lái)標(biāo)識(shí)HTML元素，例如標(biāo)題、段落、列表、粗體或斜體文本，及其他類似的特性。標(biāo)簽通常成對(duì)出現(xiàn)，前面的標(biāo)簽為〈tag〉，后面的標(biāo)簽是〈/tag〉。Web瀏覽器分析原始HTML語(yǔ)言，并創(chuàng)建為一個(gè)用戶可讀的文檔版本。

HTML文檔之所以稱為超文本，就是因?yàn)樗c一般的文本不同，它可以創(chuàng)建指向其他文檔的超鏈接(hyperlink)。鏈接的定義是通過(guò)〈a〉標(biāo)識(shí)。例如以下是一個(gè)指向文件″peter.html″的鏈接：

〈ahref=″peter.html″〉Peter的頁(yè)面〈/a〉在〈a〉與〈/a〉標(biāo)簽對(duì)之間的文本是鏈接用的文字，也稱為錨文本(anchortext)。瀏覽器使用不同的顏色或字體顯示這些鏈接。在用戶選擇一個(gè)鏈接時(shí)，瀏覽器便顯示由鏈接指向的文檔。錨文本在網(wǎng)絡(luò)信息檢索中起著非常重要的作用。

關(guān)于HTML的詳細(xì)介紹，請(qǐng)參考HTML標(biāo)準(zhǔn)維護(hù)者W3C組織[4]發(fā)布的HTML語(yǔ)言規(guī)格標(biāo)準(zhǔn)或其他相關(guān)文獻(xiàn)資料。

2．資源標(biāo)識(shí)符

Web頁(yè)面通過(guò)HTML文檔指明它的內(nèi)容和表現(xiàn)形式，呈現(xiàn)給讀者。但是Web頁(yè)面如此眾多，如何找到這些網(wǎng)頁(yè)，定位這些資源呢？Web上的資源是通過(guò)通用資源標(biāo)志符(UniversalResourceLocator，URL)來(lái)定位的。

URL唯一地指明了一個(gè)Web頁(yè)面的位置。它的語(yǔ)法構(gòu)成如下：

accessmethod：∥servername[：port]/directory/name其中，“accessmethod”是指資源服務(wù)器的服務(wù)方式，稱為“使用協(xié)議”。在WWW系統(tǒng)中，最常用的就是HTTP(HypertextTransferProtocol，超文本傳輸協(xié)議)，也可以是FTP(FileTransferProtocol，文件傳輸協(xié)議)、NEWS等其他應(yīng)用協(xié)議?！皊ervername”指服務(wù)器域名，即接入到Internet中供訪問(wèn)的服務(wù)器，一般都有一個(gè)專用的域名，用戶要訪問(wèn)服務(wù)器上的資源，必須指明服務(wù)器的域名，也可以使用IP地址代替?！皃ort”是一個(gè)服務(wù)的端口號(hào)，用數(shù)字表示，例如HTTP服務(wù)對(duì)應(yīng)的缺省端口值是80?！癲irectory”指文件所在服務(wù)器的目錄或路徑?！皀ame”是文件名，在缺省的情況下，首先會(huì)調(diào)出稱為“主頁(yè)”的文件，如index.html。一般而言，URL可分為兩種類型，一種是絕對(duì)URL，另一種是相對(duì)URL。絕對(duì)URL就是指明需要訪問(wèn)的信息或資源的絕對(duì)位置，上面的URL語(yǔ)法定義實(shí)際上是絕對(duì)URL。相對(duì)URL就是定位資源的相對(duì)路徑，所謂“相對(duì)路徑”，就是所需資源相對(duì)于當(dāng)前位置的路徑。例如，如果服務(wù)器中的一個(gè)路徑中有多個(gè)文件需要訪問(wèn)，第一個(gè)訪問(wèn)文件已經(jīng)指明了絕對(duì)路徑，余下的僅需指明文件名就可以了。

3．傳輸協(xié)議

傳輸協(xié)議在Web中起著舉足輕重的作用，通過(guò)它，信息資源才能夠在網(wǎng)絡(luò)上流轉(zhuǎn)，起到信息共享的目的。目前支撐互聯(lián)網(wǎng)絡(luò)運(yùn)轉(zhuǎn)的是TCP/IP(TransmissionControlProtocol/InternetProtocol)協(xié)議簇，它由很多協(xié)議構(gòu)成，這些協(xié)議分別在TCP/IP模型的4個(gè)層次上起作用。圖3-1是TCP/IP協(xié)議簇的示意圖。圖3-1TCP/IP協(xié)議棧分層示意圖

HTTP是建立在TCP協(xié)議之上的應(yīng)用層協(xié)議，用來(lái)在WWW上傳遞文本網(wǎng)頁(yè)或各種其他資源，如圖片、音頻或者視頻等。HTTP協(xié)議采用請(qǐng)求/響應(yīng)模式工作。在這個(gè)模式中，客戶端發(fā)起HTTP請(qǐng)求，服務(wù)器端負(fù)責(zé)處理請(qǐng)求并發(fā)回HTTP響應(yīng)。HTTP客戶端的一個(gè)典型例子是Web瀏覽器，HTTP服務(wù)器，也叫Web服務(wù)器，著名的Web服務(wù)器有Tomcat[5]、Apache[6]和IIS[7]等。圖3-2是HTTP工作原理示意圖。圖3-2HTTP工作原理示意圖

HTTP請(qǐng)求和響應(yīng)的報(bào)文格式相似，而且都是基于字符的，這兩種報(bào)文遵循以下格式：

(1)一個(gè)起始行；

(2)零或若干個(gè)報(bào)頭行；

(3)一個(gè)空白行；

(4)可選的消息主體。

其中的起始行，對(duì)于請(qǐng)求和響應(yīng)報(bào)文是不同的。HTTP請(qǐng)求的起始行的結(jié)構(gòu)為：

MethodRequest-URIHTTP-VersionCRLF

Method表示請(qǐng)求的方法，比如get或者post，注意需要大寫(xiě)。HTTP的主要方法以及描述如表3-1所示。Request-URI表示一個(gè)統(tǒng)一資源標(biāo)識(shí)符；HTTP-Version表示請(qǐng)求的HTTP協(xié)議版本；CRLF表示回車換行(對(duì)應(yīng)的ASCII值分別為13和10)。例如：GET/somedir/page.htmlHTTP/1.1。

HTTP響應(yīng)的起始行稱為狀態(tài)行。HTTP響應(yīng)的狀態(tài)行的結(jié)構(gòu)為

HTTP-VersionStatus-CodeReason-PhraseCRLF其中：HTTP-Version表示服務(wù)器HTTP協(xié)議的版本；Status-Code表示服務(wù)器發(fā)回的狀態(tài)碼；Reason-Phrase表示狀態(tài)碼的文本描述；CRLF表示回車換行。狀態(tài)碼由3位數(shù)字組成，表示請(qǐng)求是否被理解或被滿足。狀態(tài)碼分五種類型，由第一位數(shù)字表示：

1xx：信息，請(qǐng)求收到，繼續(xù)處理；

2xx：成功，行為被成功地接受、理解和采納；

3xx：重定向，為了完成請(qǐng)求，必須進(jìn)一步執(zhí)行的動(dòng)作；

4xx：客戶端錯(cuò)誤，請(qǐng)求包含語(yǔ)法錯(cuò)誤或者請(qǐng)求無(wú)法實(shí)現(xiàn)；

5xx：服務(wù)器錯(cuò)誤，服務(wù)器不能實(shí)現(xiàn)一種明顯無(wú)效的請(qǐng)求。

狀態(tài)碼的具體含義如表3-2所示。例子：HTTP/1.1200OK。一個(gè)HTTP報(bào)文具有零到若干個(gè)報(bào)頭字段，每個(gè)報(bào)頭字段由字段名和值組成，獨(dú)占一行，不同的報(bào)頭字段，描述著該HTTP報(bào)文的獨(dú)特屬性。消息主體表示的是報(bào)文要傳達(dá)的主要消息，它可以是ASCII字符或者是二進(jìn)制數(shù)據(jù)。每一行之間，需要以回車和換行(CRLF)來(lái)分割。HTTP報(bào)頭行的格式為

報(bào)頭字段名：值

HTTP請(qǐng)求的報(bào)頭字段很多，下面只介紹一些基本的以及與網(wǎng)絡(luò)信息搜索密切相關(guān)的字段。

(1)User-Agent：這個(gè)報(bào)頭字段存在于請(qǐng)求報(bào)文中，用于說(shuō)明是什么客戶端軟件發(fā)出請(qǐng)求。服務(wù)器接收到請(qǐng)求報(bào)文后，可以根據(jù)這個(gè)字段了解到發(fā)出請(qǐng)求的軟件名字，從而回應(yīng)不同的內(nèi)容以避免不兼容等問(wèn)題。

(2)Content-Type：用于指明消息主體內(nèi)所包含內(nèi)容的類型。對(duì)于不同的類型，瀏覽器有不同的處理方法。如果是圖像，則調(diào)入相應(yīng)的圖像處理函數(shù)進(jìn)行處理；若是文字，則直接顯示出來(lái)。

(3)Content-Length：用于指明消息主體的長(zhǎng)度。

(4)If-Modified-Since：這個(gè)字段存在于請(qǐng)求報(bào)文中，此字段的值是一個(gè)時(shí)間。當(dāng)一個(gè)請(qǐng)求報(bào)文包含此字段時(shí)，服務(wù)器檢查所請(qǐng)求的資源的修改日期，如果發(fā)現(xiàn)修改日期比字段中提供的日期晚，則返回整個(gè)資源文件，否則僅返回報(bào)頭信息。這對(duì)于優(yōu)化速度是有很大作用的。一般瀏覽器會(huì)把搜集過(guò)的資源緩存在本地磁盤(pán)上，當(dāng)同樣的資源被再次請(qǐng)求時(shí)，如果資源沒(méi)有被修改過(guò)，則可以直接利用本地磁盤(pán)上保存的內(nèi)容來(lái)加速瀏覽。瀏覽器就是利用這個(gè)字段，把本地磁盤(pán)上資源的日期發(fā)送到服務(wù)器。當(dāng)服務(wù)器認(rèn)為資源沒(méi)有被修改過(guò)時(shí)，就不需要發(fā)送資源的主體，大大節(jié)省了網(wǎng)絡(luò)開(kāi)銷。對(duì)于搜索引擎而言，在提高網(wǎng)絡(luò)信息搜集速度方面同樣可以利用此字段。下面舉例介紹一個(gè)HTTP會(huì)話的過(guò)程，如圖3-3所示。圖3-3一次簡(jiǎn)單的HTTP會(huì)話過(guò)程此會(huì)話描述的是訪問(wèn)華南理工大學(xué)網(wǎng)站的流程，是從客戶瀏覽器發(fā)出請(qǐng)求，到服務(wù)器發(fā)出回應(yīng)的一個(gè)完整過(guò)程。

第一步：客戶在瀏覽器地址欄鍵入http：//；

第二步：客戶端連接服務(wù)器的80端口，建立到服務(wù)器上的TCP連接；

第三步：客戶端在這個(gè)連接上發(fā)送請(qǐng)求；

第四步：服務(wù)器從客戶請(qǐng)求中知道請(qǐng)求的客戶端使用的是HTTP1.1的協(xié)議，且需要搜集根路徑上

的資源。服務(wù)器就將對(duì)應(yīng)的網(wǎng)頁(yè)內(nèi)容以響應(yīng)報(bào)文的方式發(fā)送給客戶機(jī)；第五步：客戶端的瀏覽器發(fā)現(xiàn)響應(yīng)碼為200，知道請(qǐng)求成功，從Content-length得到消息主體的長(zhǎng)度并從Content-Type獲知這是文本性的網(wǎng)頁(yè)，從消息主體上就可獲得網(wǎng)頁(yè)對(duì)應(yīng)的HTML代碼。這些信息經(jīng)瀏覽器解釋后顯示給用戶。

在較早版本的HTTP協(xié)議中，每完成一個(gè)請(qǐng)求，就要斷開(kāi)底層的TCP連接，這對(duì)于傳輸數(shù)目眾多的小文件來(lái)說(shuō)，效率不佳，需要頻繁地建立新連接。為此在HTTP1.1版本中，可以使用Connection：Keep-Alive來(lái)指定不要斷開(kāi)連接，繼續(xù)使用該連接傳輸后面的其他請(qǐng)求內(nèi)容。

3.1.2Web的特點(diǎn)

目前，萬(wàn)維網(wǎng)上存在著上萬(wàn)億網(wǎng)頁(yè)，有些網(wǎng)頁(yè)之間通過(guò)超鏈接連接起來(lái)，有些網(wǎng)頁(yè)卻孤零零的，和其他網(wǎng)頁(yè)無(wú)任何關(guān)系。如果把一個(gè)網(wǎng)頁(yè)看做一個(gè)節(jié)點(diǎn)，而把超鏈接看做邊，就可以得到一張巨大的Web圖。研究者從數(shù)學(xué)角度對(duì)這張圖及其派生進(jìn)行了許多研究，獲得了很多有意義的結(jié)論[8-10]。這些結(jié)論揭示了Web的一些統(tǒng)計(jì)規(guī)律，幫助我們從宏觀上、抽象層面上更好地認(rèn)識(shí)Web。從網(wǎng)絡(luò)信息搜索技術(shù)的角度來(lái)看，了解信息的來(lái)源——Web的規(guī)律，有助于我們改善網(wǎng)絡(luò)信息搜索的速度和質(zhì)量。

在討論Web圖的規(guī)律之前，有必要先來(lái)學(xué)習(xí)一些圖的基本概念。由點(diǎn)集合V和點(diǎn)與點(diǎn)之間的連線的集合E所組成的集合對(duì)(V，E)稱為圖，用G(V，E)表示。節(jié)點(diǎn)之間，可以存在若干條邊，如果這些邊是有方向的，則這個(gè)圖為有向圖，反之則稱為無(wú)向圖。把每個(gè)網(wǎng)頁(yè)看做單個(gè)節(jié)點(diǎn)，此網(wǎng)頁(yè)內(nèi)的超鏈接就可看做射出的邊，這樣就構(gòu)成了Web圖；也可以以一定的方法把一類的網(wǎng)頁(yè)聚集在一起，把這個(gè)網(wǎng)頁(yè)的集合看做一個(gè)節(jié)點(diǎn)，這個(gè)集合內(nèi)的網(wǎng)頁(yè)指向集合外網(wǎng)頁(yè)的超鏈接看做射出的邊。

Web圖是有向圖。以某節(jié)點(diǎn)v為起點(diǎn)的邊的條數(shù)稱為節(jié)點(diǎn)v的出度，以其為終點(diǎn)的邊的條數(shù)稱為v的入度。當(dāng)從某節(jié)點(diǎn)A出發(fā)，通過(guò)邊到達(dá)節(jié)點(diǎn)B，然后又從節(jié)點(diǎn)B出發(fā)，通過(guò)其上的邊到達(dá)節(jié)點(diǎn)C，最后到達(dá)節(jié)點(diǎn)Z，我們稱經(jīng)過(guò)的邊的集合為節(jié)點(diǎn)A到節(jié)點(diǎn)Z的路徑。兩個(gè)點(diǎn)之間可能存在不同的路徑，路徑上的邊的數(shù)目稱為路徑的長(zhǎng)度，兩節(jié)點(diǎn)之間具有最少長(zhǎng)度的路徑稱為最短路徑。在圖中，最長(zhǎng)的任意兩點(diǎn)的最短路徑稱做圖的直徑。

1．Web的冪律分布

冪律(powerlaw)指的是兩個(gè)變量x，y之間，存在著關(guān)系y=Cx－γ。當(dāng)一個(gè)概率分布的密度函數(shù)滿足冪律時(shí)，稱此分布為冪律分布。在Web上，冪律分布無(wú)處不在：網(wǎng)頁(yè)的大小、網(wǎng)頁(yè)的連接度和瀏覽網(wǎng)頁(yè)的行為等都被研究人員證實(shí)為滿足冪律分布[8-9，11-14]。

當(dāng)冪律分布被用于對(duì)數(shù)據(jù)進(jìn)行分級(jí)時(shí)，通常稱為Zipf分布或者Pareto-Zipf分布。例如，在語(yǔ)言研究領(lǐng)域，把詞與它們?cè)谌粘Ｉ钪谐霈F(xiàn)的頻率進(jìn)行分級(jí)所產(chǎn)生的分布總是滿足冪律分布的。

離散的冪律分布有以下形式：

P(X=k)=Ck－γ(γ>1，k=1，2，3，…)(3-1)而對(duì)于連續(xù)的冪律分布，則有以下的密度函數(shù)：

f(x)=Cx－γ，x∈[1，+∞)

(3-2)

如前所述，冪律分布存在于很多方面。在Web上，人們也發(fā)現(xiàn)了不少的滿足冪律分布的數(shù)據(jù)。Huberman和Adamic[8]曾對(duì)幾個(gè)著名搜索引擎抓取的好幾百萬(wàn)的網(wǎng)頁(yè)記錄進(jìn)行分析，發(fā)現(xiàn)當(dāng)以頁(yè)面數(shù)量去衡量網(wǎng)站大小時(shí)，網(wǎng)站的大小遵循冪律分布，其中γ在1.6~1.9之間。這個(gè)發(fā)現(xiàn)使得我們可以估算出一定大小的網(wǎng)站的數(shù)量。

除了網(wǎng)站的大小之外，Web圖中節(jié)點(diǎn)的度，無(wú)論是有向的情況還是無(wú)向的情況，都滿足冪律分布。例如，一項(xiàng)根據(jù)對(duì)印第安納NotreDama大學(xué)所在域的抓取結(jié)果進(jìn)行的研究[9]指出，其網(wǎng)頁(yè)的出度滿足冪律分布，γ大約為2.45；而入度也同樣滿足冪律分布，γ為2.1。

2．小世界理論

另外一個(gè)關(guān)于Web圖的經(jīng)驗(yàn)性理論就是小世界(Smallworld)理論。通過(guò)實(shí)驗(yàn)，人們發(fā)現(xiàn)Web圖的直徑相對(duì)于整個(gè)Web圖來(lái)說(shuō)，是很小的。這個(gè)理論開(kāi)始于著名心理學(xué)家Milgram在1967年對(duì)社交網(wǎng)絡(luò)的研究[15]。Milgram認(rèn)為，當(dāng)?shù)厍蛏先我鈨蓚€(gè)人需要通信或者轉(zhuǎn)交物品時(shí)，可以通過(guò)托付給熟人的形式進(jìn)行，而被托付人也可以再繼續(xù)托付熟人，當(dāng)最終完成通信或者交換物品時(shí)，托付鏈的長(zhǎng)度一般不會(huì)超過(guò)6，這就是著名的六度分割(SixDegreesofSeparation)理論[16]。如果從圖論的角度來(lái)看，也就回到了圖的直徑的問(wèn)題上：在社交網(wǎng)絡(luò)圖中，網(wǎng)絡(luò)直徑一般不會(huì)超過(guò)6。因此社交網(wǎng)絡(luò)就是一個(gè)小世界網(wǎng)絡(luò)。然而Web圖實(shí)在是太大了，要精確地計(jì)算出Web圖的直徑或者平均最短路徑長(zhǎng)度很困難。一般地，在圖中尋找任意兩點(diǎn)的最短長(zhǎng)度需要O(n2)，即使使用了Cormen[17]的根據(jù)Web的稀疏特性提出的動(dòng)態(tài)規(guī)劃算法，也需要O(nlogn)。由于n非常大，還是無(wú)法在合理的時(shí)間內(nèi)完成計(jì)算。為此，人們?cè)谘芯縒eb圖的直徑時(shí)通常采用采樣的辦法。不過(guò)需要注意的是，使用這種辦法無(wú)法保證獲取精確的最長(zhǎng)的最短路徑，也就是無(wú)法精確獲取整個(gè)Web圖的直徑。

通過(guò)生成具有同樣的鏈接冪律分布的隨機(jī)圖，Albert等人發(fā)現(xiàn)[9]，兩節(jié)點(diǎn)之間的平均距離為(3-3)d=0.35+2.06logn例如，假設(shè)Web圖的節(jié)點(diǎn)數(shù)n=109，根據(jù)這個(gè)公式計(jì)算得到d=E[l]=18.89，相對(duì)于數(shù)10億節(jié)點(diǎn)規(guī)模來(lái)說(shuō)，Web圖直徑太小了，是一個(gè)小世界網(wǎng)絡(luò)。這個(gè)例子說(shuō)明，用戶通過(guò)19次點(diǎn)擊可從一個(gè)網(wǎng)頁(yè)到達(dá)另外一個(gè)目的網(wǎng)頁(yè)。這個(gè)研究結(jié)果在一定程度說(shuō)明了萬(wàn)維網(wǎng)的可用性和可管理性，否則當(dāng)我們?yōu)楂@取一個(gè)信息需要大量點(diǎn)擊時(shí)，互聯(lián)網(wǎng)將變得很難管理和使用。這個(gè)距離也為設(shè)計(jì)高效的搜索引擎的信息自動(dòng)搜集系統(tǒng)提供了理論依據(jù)。

3．蝴蝶結(jié)理論

Web圖的另外一個(gè)著名規(guī)律是蝴蝶結(jié)理論，研究人員把注意力放在了部件(component)間的關(guān)系研究上。這里的部件，是指一些網(wǎng)頁(yè)的集合。Broder等人的研究[10]表明，萬(wàn)維網(wǎng)上的網(wǎng)頁(yè)可以根據(jù)連接性分為四類。第一類稱為強(qiáng)互連部件(StrongConnectedComponent，SCC)，這類部件的特點(diǎn)是每一個(gè)在此集合內(nèi)的網(wǎng)頁(yè)都可以通過(guò)超鏈接組成的路徑彼此到達(dá)，這類部件內(nèi)的網(wǎng)站大多是一些著名的公共站點(diǎn)；第二類部件稱為IN部件，這里面的網(wǎng)頁(yè)都有超鏈接到達(dá)SCC，然而不能從SCC內(nèi)的網(wǎng)頁(yè)到達(dá)自身；第三類稱為OUT部件，這類部件與IN部件恰恰相反，能從SCC部件出發(fā)到達(dá)自身，但是不能從自身到達(dá)SCC；最后一類是由不能歸納為以上任何一類的網(wǎng)頁(yè)組成的，然而，它們或者能從IN部件中出發(fā)最后到達(dá)自身或者能從自身出發(fā)，最后到達(dá)OUT部件，表現(xiàn)為圖3-4中的觸須(tendril)或管道(tube)，還有少部分的網(wǎng)頁(yè)不算在以上四個(gè)類別中，稱為孤立部件(disconnectedcomponent)。圖3-4萬(wàn)維網(wǎng)的蝴蝶結(jié)形狀[10]通過(guò)上述的定義和Web本身數(shù)據(jù)的分析，Web可以被描述成圖3-4的宏觀圖，這就是Broder給出的萬(wàn)維網(wǎng)的宏觀寫(xiě)照。由于它酷似蝴蝶結(jié)，也被稱為蝴蝶結(jié)圖，Web的這個(gè)特性或規(guī)律也被稱為蝴蝶結(jié)理論。

3.2網(wǎng)絡(luò)信息搜集的原理

網(wǎng)絡(luò)信息的自動(dòng)搜集實(shí)質(zhì)是利用一種專用程序，向不同的Web服務(wù)器發(fā)出請(qǐng)求，以獲取一個(gè)Web文檔及遞歸地獲取其指向的文檔信息。這些專用程序俗稱網(wǎng)絡(luò)爬蟲(chóng)(crawler)，還有其他不同的名稱，如網(wǎng)絡(luò)蜘蛛(spider)、網(wǎng)絡(luò)機(jī)器人(robot)、網(wǎng)絡(luò)漫游者(webwanderers)、網(wǎng)絡(luò)蠕蟲(chóng)(webworm)等，其中的網(wǎng)絡(luò)蠕蟲(chóng)因?yàn)槿菀滓鹫`解，已經(jīng)很少在這個(gè)意義上使用。如果要區(qū)分的話，網(wǎng)絡(luò)蜘蛛是用來(lái)下載網(wǎng)頁(yè)，如瀏覽器一樣分析HTML的源碼；網(wǎng)絡(luò)爬蟲(chóng)是用來(lái)發(fā)現(xiàn)網(wǎng)頁(yè)上的所有鏈接，它的工作是決定網(wǎng)絡(luò)爬蟲(chóng)的爬行方向。在本文中，并不嚴(yán)格區(qū)分網(wǎng)絡(luò)蜘蛛和網(wǎng)絡(luò)爬蟲(chóng)，而是把采集程序統(tǒng)稱為網(wǎng)絡(luò)爬蟲(chóng)。最早(20世紀(jì)90年代中葉)的網(wǎng)絡(luò)爬蟲(chóng)主要用來(lái)進(jìn)行網(wǎng)絡(luò)統(tǒng)計(jì)分析、網(wǎng)絡(luò)維護(hù)、鏡像等，較早的用來(lái)搜索信息的網(wǎng)絡(luò)爬蟲(chóng)是“fishsearchmechanism”，這是面對(duì)Mosaic(第一個(gè)Web瀏覽器)用戶的搜集器，而且針對(duì)用戶提交的查詢，立刻到Web上搜集相關(guān)信息，即使下一個(gè)用戶查詢同樣的東西，也需要再次到Web上進(jìn)行信息搜集。

雖然網(wǎng)絡(luò)爬蟲(chóng)很形象地描述了這些程序在Web爬行以搜集網(wǎng)絡(luò)信息，但它并不真正在Web上爬行，而是充當(dāng)客戶端，向眾多的Web服務(wù)器發(fā)出請(qǐng)求，并獲得相應(yīng)的Web頁(yè)面文檔。3.2.1信息搜集的基本流程

從Web上搜集信息，就是遍歷整個(gè)圖的各個(gè)節(jié)點(diǎn)，向各節(jié)點(diǎn)URL請(qǐng)求網(wǎng)頁(yè)，并對(duì)其進(jìn)行解析。

圖3-5給出了網(wǎng)絡(luò)爬蟲(chóng)的基本流程圖。

網(wǎng)絡(luò)爬蟲(chóng)最主要的一個(gè)數(shù)據(jù)結(jié)構(gòu)是待處理URL列表，國(guó)外一些文獻(xiàn)將它稱為Frontier，在信息采集流程開(kāi)始的時(shí)候，F(xiàn)rontier被起始網(wǎng)頁(yè)URL(種子URL)填充，接著進(jìn)入信息采集循環(huán)流程，在采集流程中，URL列表不斷被更新。

信息采集開(kāi)始時(shí)，首先判斷循環(huán)是否應(yīng)該結(jié)束。對(duì)于不同目的的網(wǎng)絡(luò)爬蟲(chóng)，可能有不同的停止條件。例如待處理URL列表為空，且無(wú)正在工作的網(wǎng)頁(yè)信息采集分析的線程，就可以作為網(wǎng)絡(luò)爬蟲(chóng)停止的條件；又如某網(wǎng)絡(luò)爬蟲(chóng)僅僅是搜集某方面的信息，當(dāng)發(fā)現(xiàn)已經(jīng)搜集足夠滿足需求的資料時(shí)，就停止搜集。圖3-5網(wǎng)頁(yè)信息搜集的基本流程圖接下來(lái)從列表中選取一個(gè)URL，根據(jù)遍歷策略的不同，有不同的選取方法。對(duì)于簡(jiǎn)單的隊(duì)列或者堆棧來(lái)說(shuō)，只需要出隊(duì)或出棧即可。對(duì)于復(fù)雜的實(shí)現(xiàn)，可能還需要通過(guò)計(jì)算，才能確定從待處理URL中挑選出哪個(gè)URL進(jìn)行抓取。

選取了待處理的URL之后，網(wǎng)絡(luò)爬蟲(chóng)一般使用HTTP協(xié)議來(lái)獲取指定URL對(duì)應(yīng)的網(wǎng)頁(yè)內(nèi)容。這一步雖然比較直接簡(jiǎn)單，但由于需要遍歷的Web太大，以及存在網(wǎng)絡(luò)時(shí)延的原因，為了提高效率，通常都需要通過(guò)采用并行技術(shù)來(lái)優(yōu)化該項(xiàng)工作。接下來(lái)對(duì)采集到的網(wǎng)頁(yè)進(jìn)行解析。將網(wǎng)頁(yè)的基本內(nèi)容進(jìn)行處理、存儲(chǔ)和索引；另外需要分析出網(wǎng)頁(yè)中是否含有新的URL，對(duì)URL進(jìn)行處理和去重，將無(wú)重復(fù)的新的URL加入到待處理URL列表中；這一步還可以進(jìn)行一些網(wǎng)頁(yè)的統(tǒng)計(jì)信息處理等。

從圖3-5來(lái)看，似乎網(wǎng)絡(luò)信息的采集流程比較簡(jiǎn)單。確實(shí)如此，如果不考慮太多效率、性能的問(wèn)題，單單完成信息采集的網(wǎng)絡(luò)爬蟲(chóng)只是一個(gè)小小的程序而已。但實(shí)際上網(wǎng)絡(luò)信息采集是一個(gè)復(fù)雜的工程問(wèn)題，我們將完成信息采集任務(wù)的系統(tǒng)稱之為網(wǎng)絡(luò)信息搜集系統(tǒng)。如果要寫(xiě)一個(gè)相對(duì)完美、性能優(yōu)越的網(wǎng)絡(luò)信息搜集系統(tǒng)，就要考慮到方方面面的問(wèn)題，比如遍歷的策略、停止的條件、URL去重處理等等。3.2.2遍歷策略

如前所述，可以將Web世界看做一個(gè)龐大的圖，網(wǎng)絡(luò)爬蟲(chóng)的任務(wù)就是從某個(gè)起始網(wǎng)頁(yè)集出發(fā)，沿著網(wǎng)頁(yè)中的超鏈接，試圖以某種策略遍歷Web圖，從而獲取Web上的全部信息。對(duì)于圖的遍歷，可以采用“廣度優(yōu)先(BreadthFirst)”、“深度優(yōu)先(DepthFirst)”這兩個(gè)基本策略。

1．廣度優(yōu)先遍歷策略

已知圖G=(V，E)和一個(gè)源節(jié)點(diǎn)s，廣度優(yōu)先搜索以一種系統(tǒng)的方式探尋G的邊，從而“發(fā)現(xiàn)”從s出發(fā)能到達(dá)的所有節(jié)點(diǎn)，并計(jì)算s到所有這些節(jié)點(diǎn)的距離(最少邊數(shù))，采用這種策略可產(chǎn)生一棵根為s且包括所有可達(dá)節(jié)點(diǎn)的寬度優(yōu)先樹(shù)。對(duì)從s可達(dá)的任意節(jié)點(diǎn)v，寬度優(yōu)先樹(shù)中從s到v的路徑對(duì)應(yīng)于圖G中從s到v的最短路徑，即包含最小邊數(shù)的路徑。采用廣度優(yōu)先策略的遍歷算法被稱為寬度優(yōu)先算法，它的本質(zhì)是自始至終通過(guò)已找到和未找到節(jié)點(diǎn)之間的邊界向外擴(kuò)展，就是說(shuō)，算法首先搜索與s距離為k的所有節(jié)點(diǎn)，然后再去搜索與s距離為k+1的其他節(jié)點(diǎn)，其中k是自然數(shù)。對(duì)于網(wǎng)絡(luò)爬蟲(chóng)來(lái)說(shuō)，如果把待處理的URL排成隊(duì)列，廣度優(yōu)先策略是先進(jìn)先出的搜索策略，每次從網(wǎng)頁(yè)解析得到的新URL都添加在隊(duì)列末尾，每次都從隊(duì)列的頭部選取URL進(jìn)行解析。按照廣度優(yōu)先策略爬行Web頁(yè)面可形象地描述為圖3-6，網(wǎng)絡(luò)爬蟲(chóng)先把位于同一層的網(wǎng)頁(yè)抓取完，再抓下一層的網(wǎng)頁(yè)，直到最底層為止，圖中的數(shù)字表示網(wǎng)絡(luò)爬蟲(chóng)抓取的順序。圖3-6采用廣度優(yōu)先策略遍歷的示意圖由圖3-6可知，廣度優(yōu)先從根網(wǎng)頁(yè)統(tǒng)一地向外搜索，但需要存儲(chǔ)前一層次的所有節(jié)點(diǎn)，這些節(jié)點(diǎn)的數(shù)量隨著深度的增加呈指數(shù)增長(zhǎng)。寬度優(yōu)先是常用的網(wǎng)絡(luò)爬蟲(chóng)搜索策略，下面給出采用寬度優(yōu)先策略的信息搜集的基本算法。在該算法中，只下載HTML頁(yè)面，而不處理其他類型的信息如圖片和PDF、PPT文檔等。

此算法描述如下：用已知的URL列表初始化隊(duì)列Q

循環(huán)直至Q為空或限定搜集時(shí)間到：

從Q的前部取出一個(gè)URL：L

如果L不是HTML頁(yè)面(例如后綴為.gif、.jpeg、.ps、.pdf、.ppt等)

繼續(xù)循環(huán)；

如果已經(jīng)訪問(wèn)過(guò)L，繼續(xù)循環(huán)；

下載L對(duì)應(yīng)的頁(yè)面P

如果無(wú)法下載P(如：404錯(cuò)誤，機(jī)器人排斥協(xié)議)

繼續(xù)循環(huán)；

解析P提取新的鏈接N

追加N到Q的后面

2．深度優(yōu)先遍歷策略

假設(shè)給定圖G的初態(tài)是所有節(jié)點(diǎn)均未曾訪問(wèn)過(guò)，在G中任選一節(jié)點(diǎn)s為初始出發(fā)點(diǎn)(源點(diǎn))，則深度優(yōu)先策略的遍歷可描述如下：首先訪問(wèn)出發(fā)點(diǎn)s，并將其標(biāo)記為已訪問(wèn)過(guò)；然后依次從s出發(fā)搜索s的每個(gè)鄰接點(diǎn)w，若w未曾訪問(wèn)過(guò)，則以w為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷，直至圖中所有和源節(jié)點(diǎn)s路徑相通的節(jié)點(diǎn)(亦稱為從源點(diǎn)可達(dá)的頂點(diǎn))均被訪問(wèn)為止；若此時(shí)圖中仍有未訪問(wèn)的節(jié)點(diǎn)，則另選一個(gè)尚未訪問(wèn)的頂點(diǎn)作為新的源點(diǎn)重復(fù)上述過(guò)程，直至圖中所有節(jié)點(diǎn)均被訪問(wèn)為止。深度優(yōu)先遵循先進(jìn)后出的原則，和廣度優(yōu)先相反，每次解析得到的新URL都放在隊(duì)列的頭部，這樣使得網(wǎng)絡(luò)爬蟲(chóng)從起始頁(yè)面s出發(fā)，沿著s的某一個(gè)鏈接一直搜索到某個(gè)不包含任何鏈接的文件為止，這樣形成一條完整的鏈，再返回s繼續(xù)選擇其他鏈接進(jìn)行類似的訪問(wèn)，訪問(wèn)結(jié)束的標(biāo)志是不再有其他超級(jí)鏈接可以搜索，深度優(yōu)先遍歷過(guò)程可用圖3-7表示。

深度優(yōu)先相對(duì)寬度優(yōu)先而言，使用的存儲(chǔ)空間較少，存儲(chǔ)的節(jié)點(diǎn)數(shù)只隨深度的增加呈線性增長(zhǎng)。但是，采用深度優(yōu)先策略的網(wǎng)絡(luò)爬蟲(chóng)在抓取的過(guò)程中，可能因?yàn)闊o(wú)限制地在一條路上抓取而導(dǎo)致迷航。實(shí)際應(yīng)用中，可以通過(guò)設(shè)置抓取的最大深度來(lái)限制網(wǎng)絡(luò)爬蟲(chóng)的抓取，避免迷航現(xiàn)象的發(fā)生。圖3-7采用深度優(yōu)先策略遍歷的示意圖3.2.3頁(yè)面解析

要遍歷整個(gè)Web圖，關(guān)鍵要從獲取到的網(wǎng)頁(yè)中提取超鏈接URL。而為了進(jìn)一步地進(jìn)行索引和檢索，還需要從網(wǎng)頁(yè)中提取更多的信息，如整個(gè)頁(yè)面的主要內(nèi)容，并區(qū)分哪些是題目，標(biāo)題和錨文本等。因此HTML文檔解析非常重要。

從HTML文檔中獲取主要內(nèi)容，首先要對(duì)HTML標(biāo)簽進(jìn)行分析。假設(shè)需要從一份HTML文檔中提取URL和鏈接文本，該文檔包括如下標(biāo)簽的內(nèi)容：

〈ahref=″http：//″〉O′ReillyMedia〈/a〉因?yàn)椤碼〉標(biāo)簽的內(nèi)容可能相當(dāng)復(fù)雜，可以分兩步實(shí)現(xiàn)這個(gè)任務(wù)。第一個(gè)是提取〈a〉標(biāo)簽內(nèi)部的內(nèi)容，也就是錨文本，然后從〈a〉標(biāo)簽中提取URL地址。

最簡(jiǎn)單的方法是采用正則表達(dá)式。例如可用以下的正則表達(dá)式(Perl語(yǔ)言)：

〈a＼b([^>]+)〉(.*?)〈/a〉

來(lái)分開(kāi)〈a〉的內(nèi)容和錨文本的內(nèi)容。

提取出〈a〉的內(nèi)容后，就可以提取URL了。注意到，URL是“href=value”屬性的值。HTML允許等號(hào)的任意一側(cè)出現(xiàn)空白字符，值可以以引用形式出現(xiàn)，也可以以非引用形式出現(xiàn)。實(shí)際上很多的網(wǎng)頁(yè)撰寫(xiě)并不規(guī)范，提取出的URL也五花八門(mén)，所以需要對(duì)提取出的URL進(jìn)行正規(guī)化處理，以便網(wǎng)絡(luò)爬蟲(chóng)以沿著URL爬行。URL正規(guī)化主要包括以下內(nèi)容：

(1)大小寫(xiě)轉(zhuǎn)換：URL一般不區(qū)分大小寫(xiě)，但是不同的Web服務(wù)器或網(wǎng)絡(luò)爬蟲(chóng)運(yùn)行的操作系統(tǒng)不一樣，可能會(huì)給網(wǎng)頁(yè)的抓取帶來(lái)問(wèn)題。所以一般需要將URL字符串的大小寫(xiě)統(tǒng)一，以避免出現(xiàn)意想不到的問(wèn)題。方法是統(tǒng)一URL字符串中的協(xié)議名和域名部分的字符串，URL中的這兩個(gè)部分都是不區(qū)分大小寫(xiě)的，但是后面的路徑部分可能是大小寫(xiě)敏感的。例如：HTTP：//www.SCUT./AbC可被轉(zhuǎn)換為http：///AbC。

(2)刪除URL中的分塊部分：在比較長(zhǎng)的網(wǎng)頁(yè)中，頁(yè)內(nèi)定位分塊經(jīng)常使用。一般地，http：///intro.html#canten被刪減為http：///intro.html。

(3)統(tǒng)一URL中的編碼：URL中允許使用%20之類的形式來(lái)表示字符，http：///~zcai也可以表示為http：///%7Ezcai(其中%7E代表~)。對(duì)于這種情況，需要統(tǒng)一翻譯為ASCII字符。

(4)相對(duì)路徑處理：在Web頁(yè)面中存在大量的相對(duì)路徑，提取URL需要將相對(duì)路徑轉(zhuǎn)換為絕對(duì)路徑。主要包括以下幾種情況：

·以“/”開(kāi)頭的相對(duì)路徑，從站點(diǎn)的根目錄開(kāi)始計(jì)算，那么首先需要知道站點(diǎn)的主機(jī)名，然后拼接成以協(xié)議名稱開(kāi)頭的絕對(duì)路徑。如在http：//頁(yè)面中提取到一個(gè)URL為“/aa/index.jsp”,則應(yīng)該拼接成http：///aa/index.jsp。

·以“../”開(kāi)頭的相對(duì)路徑，是當(dāng)前頁(yè)面所在目錄的上級(jí)目錄。那么首先需要知道當(dāng)前頁(yè)面的URL，然后拼接成以協(xié)議名稱開(kāi)頭的絕對(duì)路徑。如在http：///aa/index.jsp頁(yè)面中提取到一個(gè)URL為“../test.jsp”，則應(yīng)該拼接成http：///test.jsp。

·以“./”開(kāi)頭的相對(duì)路徑，是當(dāng)前頁(yè)面的當(dāng)前目錄。那么首先需要知道當(dāng)前頁(yè)面的URL，然后拼接成以協(xié)議名稱開(kāi)頭的絕對(duì)路徑。如在http：///aa/index.jsp頁(yè)面中提取到一個(gè)URL為“./bb/test.jsp”，則應(yīng)該拼接成http：//www.scut./aa/bb/test.jsp。除了提取URL外，很多應(yīng)用還需要從HTML文檔中獲取各種不同的內(nèi)容，包括標(biāo)題、關(guān)鍵詞和摘要等可用來(lái)概括某個(gè)頁(yè)面的主要內(nèi)容。正文是原始網(wǎng)頁(yè)中真正描述主題的部分，因此在某些具體應(yīng)用中用正文代替原始網(wǎng)頁(yè)更合理。這就意味著需要對(duì)各種不同的HTML標(biāo)簽進(jìn)行分析，從而提取出相應(yīng)網(wǎng)頁(yè)的內(nèi)容。這是一個(gè)HTML解析器(parser)所要完成的工作。但是，設(shè)計(jì)一個(gè)好的HTML解析器并不是件容易的事情，因?yàn)楹芏嗑W(wǎng)站的建設(shè)并沒(méi)有嚴(yán)格地遵循W3C的相關(guān)標(biāo)準(zhǔn)，因此，要求HTML解析器必須能夠識(shí)別不規(guī)范的甚至殘缺不全的HTML文檔。網(wǎng)絡(luò)上有許多開(kāi)源的HTML解析器，例如Tidy[18]。最早的Tidy由DaveRagget采用C語(yǔ)言實(shí)現(xiàn)，JTidy[19]是Tidy的Java版本。Apache的全文檢索引擎Lucene[20]提供了DocumentHandler接口，調(diào)用了Jtidy的parseDOM方法來(lái)解析HTML文檔。

3.3網(wǎng)絡(luò)信息搜集的禮貌原則

網(wǎng)絡(luò)爬蟲(chóng)總是試圖抓取Web上的所有信息。但是有些網(wǎng)站并不希望它的站點(diǎn)內(nèi)容提供給公眾，或者只希望提供部分的信息供公眾檢索。就像一個(gè)房子，主人的臥室不能讓客人隨意進(jìn)入，但客廳是可以隨便參觀的。網(wǎng)絡(luò)爬蟲(chóng)就像到訪的客人，要尊重主人的隱私和意愿，不要竄到私人空間去。站點(diǎn)的所有者可以將自己的意愿發(fā)布出來(lái)，要求網(wǎng)絡(luò)爬蟲(chóng)遵守一定的禮貌原則。目前禮貌原則的實(shí)現(xiàn)主要有兩種機(jī)制，機(jī)器人排斥協(xié)議(RobotsExclusionProtocol)和機(jī)器人元標(biāo)簽(RobotsMETATag)。3.3.1機(jī)器人排斥協(xié)議

1994年，Koster[21]提出了機(jī)器人排斥協(xié)議，它既不是官方標(biāo)準(zhǔn)，也不屬于某個(gè)商業(yè)機(jī)構(gòu)。它不強(qiáng)制任何機(jī)構(gòu)遵循，但它是一個(gè)事實(shí)標(biāo)準(zhǔn)，很多著名搜索引擎的網(wǎng)絡(luò)爬蟲(chóng)都遵循這個(gè)標(biāo)準(zhǔn)。

需要內(nèi)容保護(hù)和指導(dǎo)網(wǎng)絡(luò)爬蟲(chóng)禮貌搜集的網(wǎng)站，把名為robots.txt的文件放到網(wǎng)站的根目錄下，禮貌的爬蟲(chóng)爬行到該網(wǎng)站，首先讀取這個(gè)文件，然后再根據(jù)文件中的規(guī)則，決定是否搜集該網(wǎng)站或搜集哪些子目錄。事實(shí)上，robots.txt文件是一些簡(jiǎn)單規(guī)則的說(shuō)明，注明了該網(wǎng)站哪些地方不能去，哪些地方可以去。當(dāng)然網(wǎng)絡(luò)爬蟲(chóng)是否遵循這個(gè)協(xié)議，取決于網(wǎng)絡(luò)爬蟲(chóng)程序的設(shè)計(jì)者。robots.txt文件由若干條記錄組成，記錄之間用一個(gè)或多個(gè)空行隔開(kāi)。其中每條記錄均由兩個(gè)域組成：User-agent域和Disallow域，前者指明受限的網(wǎng)絡(luò)爬蟲(chóng)名稱，后者指明受限的范圍。每條記錄由若干行組成，每行的格式如下(其中域名大小寫(xiě)敏感):

〈field〉：〈value〉

(1)User-agent(用戶代理)。User-agent行用于指定網(wǎng)絡(luò)爬蟲(chóng)的名字，如需要指明Google的網(wǎng)絡(luò)爬蟲(chóng)程序Googlebot，則可用User-agent:Googlebot。

一個(gè)robots.txt文件中至少要有一條User-agent記錄。如果有多條User-agent記錄，則說(shuō)明有多個(gè)爬蟲(chóng)程序會(huì)受到規(guī)則的限制。如果要匹配所有的爬蟲(chóng)程序，可以使用通配符“*”，即User-agent:*。

(2)Disallow(拒絕訪問(wèn)聲明)。在robots.txt文件中，每條記錄的第二個(gè)域一定是Disallow指令行。這些Disallow行聲明了該網(wǎng)站中不希望被訪問(wèn)的文件和(或)目錄。例如“Disallow：email.htm”對(duì)文件的訪問(wèn)進(jìn)行了聲明，禁止網(wǎng)絡(luò)爬蟲(chóng)下載網(wǎng)站上的email.htm文件；又如“Disallow：/cgi-bin/”則對(duì)cgi-bin目錄的訪問(wèn)進(jìn)行了聲明，拒絕網(wǎng)絡(luò)爬蟲(chóng)進(jìn)入該目錄及其子目錄。Disallow聲明行還具有通配符功能。例如“Disallow:/bob”則拒絕網(wǎng)絡(luò)爬蟲(chóng)對(duì)/bob.html和/bob/的訪問(wèn)(即無(wú)論是名為bob的文件還是名為bob的目錄下的文件都不允許網(wǎng)絡(luò)爬蟲(chóng)訪問(wèn))。Disallow記錄如果留空，則說(shuō)明該網(wǎng)站的所有部分都向網(wǎng)絡(luò)爬蟲(chóng)開(kāi)放。另外，在robots.txt文件中，凡以“#”開(kāi)頭的行，均被視為注解內(nèi)容，這和UNIX中的慣例是一樣的。

下面給出robot禁止協(xié)議的一些實(shí)例：

禁止所有爬蟲(chóng)的訪問(wèn)：

User-agent:*

Disallow:/

禁止指定的目錄：

User-agent:*

Disallow:/tmp/

Disallow:/cgi-bin/

Disallow:/users/paranoid/禁止指定的爬蟲(chóng):

User-agent:GoogleBot

Disallow:/

允許指定的爬蟲(chóng)：

User-agent:GoogleBot

Disallow:3.3.2機(jī)器人元標(biāo)簽

除了機(jī)器人排除協(xié)議外，HTML文檔中的META標(biāo)簽也可指定網(wǎng)絡(luò)爬蟲(chóng)是否對(duì)本網(wǎng)頁(yè)進(jìn)行抓取、跟蹤。META標(biāo)簽的格式如下：

〈metaname=“robots”content=“none”〉

其中，content的內(nèi)容值可取如下這些值或它們的組合：

(1)index|noindex：表示允許｜不允許索引這個(gè)網(wǎng)頁(yè)；

(2)follow｜nofollow：表示允許｜不允許跟蹤這個(gè)頁(yè)面上的鏈接；

(3)all：表示允許索引這個(gè)頁(yè)面，并且允許沿這個(gè)頁(yè)面上的鏈接跟蹤抓?。?/p>

(4)none：表示既不允許索引這個(gè)頁(yè)面，也不允許跟蹤這個(gè)頁(yè)面上的鏈接。

例如：〈metaname=“robots”content=“noindex，follow”〉表示不允許索引這個(gè)頁(yè)面，但允許跟蹤這個(gè)頁(yè)面上的超鏈接。

3.4高性能信息搜集

前面介紹了網(wǎng)絡(luò)爬蟲(chóng)的基本抓取流程和原理。一個(gè)好的網(wǎng)絡(luò)爬蟲(chóng)應(yīng)該具有以下特征：

(1)友好的：網(wǎng)絡(luò)服務(wù)器有潛在的和外在的用以判斷一個(gè)網(wǎng)絡(luò)爬蟲(chóng)是否可以訪問(wèn)它們的策略，網(wǎng)絡(luò)爬蟲(chóng)應(yīng)該遵守這些禮貌規(guī)則。

(2)可擴(kuò)展的：網(wǎng)絡(luò)爬蟲(chóng)應(yīng)該能夠有效利用處理器、存儲(chǔ)器和網(wǎng)絡(luò)帶寬等各種不同的系統(tǒng)資源，并允許通過(guò)增加額外的機(jī)器和帶寬來(lái)提高抓取速度。網(wǎng)絡(luò)爬蟲(chóng)應(yīng)該設(shè)計(jì)為在許多方面是可擴(kuò)展的，可將任務(wù)分布到多臺(tái)機(jī)器或多個(gè)處理器上并行執(zhí)行，可應(yīng)對(duì)新的數(shù)據(jù)格式和新的抓取協(xié)議等。

(3)高質(zhì)量的：如果抓取回來(lái)的重要網(wǎng)頁(yè)不夠全面，對(duì)于滿足用戶的查詢需要是沒(méi)有意義的，因此網(wǎng)絡(luò)爬蟲(chóng)應(yīng)該盡可能抓取重要的和有用的網(wǎng)頁(yè)。

(4)更新及時(shí)的：大多數(shù)的應(yīng)用程序均要求網(wǎng)絡(luò)爬蟲(chóng)獲得所需要頁(yè)面的最新版本。一個(gè)網(wǎng)絡(luò)爬蟲(chóng)應(yīng)該能夠以接近頁(yè)面更新速度的頻率來(lái)抓取頁(yè)面，以保證更新及時(shí)。

(5)魯棒的：網(wǎng)絡(luò)上存在的蜘蛛陷阱(SpiderTrap)等可能誤導(dǎo)網(wǎng)絡(luò)爬蟲(chóng)在一個(gè)特定領(lǐng)域內(nèi)抓取無(wú)限多的網(wǎng)頁(yè)，網(wǎng)絡(luò)爬蟲(chóng)必須設(shè)定為對(duì)這些圈套有較強(qiáng)的處理能力。

因此，要編寫(xiě)一個(gè)高效的網(wǎng)絡(luò)爬蟲(chóng)程序，實(shí)現(xiàn)高性能信息采集，還需采用適當(dāng)?shù)臋C(jī)制解決一些現(xiàn)實(shí)的問(wèn)題。3.4.1并行搜集

搜索引擎總是希望它的信息搜集系統(tǒng)所采集的信息是最新的信息，即希望更新速度足夠快，以便為用戶提供最新的信息。

下面舉個(gè)例子簡(jiǎn)單地說(shuō)明網(wǎng)絡(luò)爬蟲(chóng)爬行的速度[22]。假設(shè)廣域網(wǎng)往返時(shí)間RTT為200ms，服務(wù)器處理時(shí)間為100ms，網(wǎng)頁(yè)大小為13KB，網(wǎng)絡(luò)報(bào)文長(zhǎng)1500B，那么爬蟲(chóng)程序發(fā)起HTTP請(qǐng)求到獲取某個(gè)網(wǎng)頁(yè)需要的時(shí)間為(13KB/1500B)×(2×200+100)ms≈4s。如果爬蟲(chóng)程序晝夜不停地爬行，一天可以抓取網(wǎng)頁(yè)24×60×60s/4s=21600個(gè)。這樣算來(lái)，如果要遍歷Web圖，大約需要120億/21600=555556天，約1522年！即使只抓取其中十分之一，也需要100多年，這樣的網(wǎng)絡(luò)信息搜集系統(tǒng)不具有實(shí)際應(yīng)用價(jià)值。上面的例子也說(shuō)明了這樣的事實(shí)：網(wǎng)絡(luò)爬蟲(chóng)消耗了大部分的時(shí)間來(lái)等候數(shù)據(jù)。所以，可以同時(shí)開(kāi)啟多個(gè)采集線程，以充分利用等候數(shù)據(jù)的時(shí)間，這就是并行信息采集。只要管理好這些采集線程，抓取性能可以得到大幅度的提升。仍然是剛才那個(gè)例子，假設(shè)同時(shí)開(kāi)啟300個(gè)采集線程，則遍歷Web圖需要的時(shí)間約為120億/(21600×300)=1851天，約5年，這個(gè)時(shí)間也太長(zhǎng)，所以可以采用更多的并行采集線程，并行多級(jí)后臺(tái)管理等技術(shù)進(jìn)行采集優(yōu)化，讓更新周期縮短到1~2周。

并行采集的關(guān)鍵是如何管理協(xié)調(diào)好這些采集線程。其一是要解決多個(gè)線程之間的通信問(wèn)題，其二是要解決控制多個(gè)線程對(duì)同一站點(diǎn)的同時(shí)訪問(wèn)，防止過(guò)頻訪問(wèn)對(duì)被訪問(wèn)站點(diǎn)的沖擊。多個(gè)采集線程并行運(yùn)行，很可能出現(xiàn)重復(fù)的網(wǎng)頁(yè)抓取，線程間的有效溝通可以避免這個(gè)問(wèn)題?？梢圆捎貌煌姆椒▉?lái)解決，一種解決方法叫動(dòng)態(tài)分配法，之所以叫動(dòng)態(tài)分配法，是因?yàn)槊總€(gè)線程的URL通常由一個(gè)中心管理進(jìn)程來(lái)臨時(shí)分配。中心管理進(jìn)程負(fù)責(zé)線程間的協(xié)調(diào)溝通和負(fù)載均衡，這種集權(quán)管理方式易于實(shí)現(xiàn)，但是也容易引發(fā)單點(diǎn)失效和瓶頸。圖3-8給出了一個(gè)采用動(dòng)態(tài)分配法的網(wǎng)絡(luò)信息搜集系統(tǒng)示意圖。圖3-8動(dòng)態(tài)分配法的網(wǎng)絡(luò)爬蟲(chóng)示意圖另一種方法稱為靜態(tài)分配法，根據(jù)某種規(guī)則，預(yù)先對(duì)采集線程進(jìn)行工作范圍劃分，每個(gè)線程負(fù)責(zé)一部分的URL。之所以稱為靜態(tài)分配法，是因?yàn)槌绦騿?dòng)之初分配好了線程的URL工作范圍后，就基本不再動(dòng)態(tài)地分配URL。這種方法不需要中心控制。但是，各線程在解析頁(yè)面提取新的URL時(shí)，不可避免地會(huì)發(fā)現(xiàn)屬于別的線程工作范圍的新的URL，這就需要做出相應(yīng)的處理，例如將采集到的URL做進(jìn)一步的分配。

各個(gè)線程在實(shí)際工作過(guò)程中碰到的情況千差萬(wàn)別，但分配機(jī)制應(yīng)盡量保證：

(1)平衡性：每個(gè)線程都應(yīng)該分配大致相同的URL，避免出現(xiàn)“一些爬蟲(chóng)累死，一些爬蟲(chóng)閑死”的情況出現(xiàn)；

(2)擴(kuò)展性：當(dāng)增加線程時(shí)，每個(gè)線程的工作量應(yīng)該相應(yīng)地減少；

(3)靈活性：允許動(dòng)態(tài)地添加或者減少采集線程，而不影響系統(tǒng)運(yùn)行。

為了多、快(搜集到的網(wǎng)頁(yè)質(zhì)量好)、省(帶寬省)地搜集網(wǎng)絡(luò)信息，直觀的想法就是派出大量的網(wǎng)絡(luò)爬蟲(chóng)并行地工作。但是并行爬蟲(chóng)數(shù)量受到網(wǎng)絡(luò)帶寬、Web服務(wù)器性能等因素的制約?？梢韵胂螅粋€(gè)網(wǎng)站的帶寬是一定的，且其HTTP監(jiān)聽(tīng)端口也只能容納一定的并發(fā)連接，當(dāng)大量的網(wǎng)絡(luò)爬蟲(chóng)試圖同時(shí)連接一個(gè)站點(diǎn)時(shí)，很可能就會(huì)把其帶寬消耗光或者把它的連接輪候隊(duì)列擠滿，從而造成非故意的拒絕服務(wù)(DenyofService，DoS)攻擊。有些網(wǎng)站管理員對(duì)這種情況非常反感，甚至?xí)鈿O不禮貌的網(wǎng)絡(luò)爬蟲(chóng)。所以，網(wǎng)絡(luò)信息搜集系統(tǒng)的設(shè)計(jì)者應(yīng)該限制網(wǎng)絡(luò)爬蟲(chóng)不停地抓取同一站點(diǎn)。至于怎樣限制，做法不盡相同，以不影響站點(diǎn)正常運(yùn)行為限。例如HP實(shí)驗(yàn)室設(shè)計(jì)的網(wǎng)絡(luò)信息搜集系統(tǒng)Mercator[23]設(shè)立了一前一后的優(yōu)先級(jí)隊(duì)列,并通過(guò)帶權(quán)重的隨機(jī)選擇器來(lái)做到這一點(diǎn)。3.4.2DNS優(yōu)化

網(wǎng)絡(luò)爬蟲(chóng)在向Web服務(wù)器發(fā)出HTTP請(qǐng)求時(shí)，需要把Web服務(wù)器的域名解析為IP地址，也就是要不斷地詢問(wèn)DNS服務(wù)器。局域網(wǎng)中，DNS服務(wù)器通常較小，對(duì)付幾百個(gè)工作站的常規(guī)操作有沒(méi)問(wèn)題。但一個(gè)網(wǎng)絡(luò)爬蟲(chóng)產(chǎn)生的壓力將很大，需要解析的URL數(shù)以億計(jì)，對(duì)應(yīng)的Web主機(jī)域名也數(shù)以百萬(wàn)計(jì)，而且DNS解析系統(tǒng)調(diào)用是同步調(diào)用(synchronized)的。另外，為了避免同時(shí)從一個(gè)服務(wù)器抓許多網(wǎng)頁(yè)，需要在多個(gè)服務(wù)器間輪回，這樣也使DNS的緩存能力發(fā)揮不出來(lái)。如果不采取措施，DNS地址解析會(huì)成為網(wǎng)絡(luò)信息搜集系統(tǒng)一個(gè)主要的性能瓶頸。一般操作系統(tǒng)，如UNIX和Linux等，提供的DNS客戶端沒(méi)有考慮網(wǎng)絡(luò)信息搜集系統(tǒng)的需求，DNS查找的標(biāo)準(zhǔn)實(shí)現(xiàn)一般是同步的。這意味著一旦一個(gè)請(qǐng)求被發(fā)送到DNS服務(wù)器，在那個(gè)節(jié)點(diǎn)的采集線程就會(huì)被阻塞，直到第一個(gè)請(qǐng)求完成。操作系統(tǒng)本身設(shè)有DNS緩存功能，對(duì)于小型的網(wǎng)絡(luò)爬蟲(chóng)程序來(lái)說(shuō)已經(jīng)足夠。如果需要大規(guī)模地搜索Web，為了保證高效的信息采集，則需要建立DNS緩存機(jī)制。

因此有必要設(shè)計(jì)一個(gè)專用的DNS解析模塊，作為DNS服務(wù)器的客戶端，對(duì)網(wǎng)絡(luò)爬蟲(chóng)發(fā)出的多個(gè)DNS請(qǐng)求進(jìn)行并發(fā)異步處理，并根據(jù)所要搜集的URL進(jìn)行適當(dāng)調(diào)度，在多個(gè)DNS服務(wù)器之間做負(fù)載分配，并通過(guò)有緩存(cache)、預(yù)取(prefetch)等技術(shù)提高DNS解析性能。如果沒(méi)有DNS緩存，網(wǎng)絡(luò)爬蟲(chóng)每次搜集新的URL，即使剛在上一次的任務(wù)中解析過(guò)該主機(jī)名，也要重新進(jìn)行域名解析。頻繁地查詢DNS服務(wù)器，一方面容易造成一定程度的拒絕服務(wù)攻擊，可能會(huì)被禁掉或者使得DNS服務(wù)器崩潰；另一方面，解析過(guò)程增加了網(wǎng)絡(luò)帶寬消耗。所以，有必要在爬蟲(chóng)程序里建立DNS緩存機(jī)制，將最近解析過(guò)的域名信息保存下來(lái)，以便后續(xù)線程直接利用。

DNS緩存機(jī)制的實(shí)現(xiàn)有很多方式，這里介紹一個(gè)簡(jiǎn)單的方法：通過(guò)建立一個(gè)高層域名解釋函數(shù)來(lái)完成。首先，建立一個(gè)哈希表，以域名為鍵，以對(duì)應(yīng)的IP為值，可以保證快速查找；然后完成這個(gè)高層域名解析函數(shù)，其算法流程如圖3-9所示。圖3-9域名解析流程圖在網(wǎng)絡(luò)爬蟲(chóng)程序中，所有需要解釋域名的地方都使用此函數(shù)，則會(huì)增量地在內(nèi)存中產(chǎn)生DNS緩存，把最近搜集過(guò)的域名解析結(jié)果信息保存起來(lái)。因?yàn)閺捻?yè)面提取出的URL，成批地?fù)碛邢嗤挠蛎?，使用上面的DNS解析函數(shù)，可以大大減少對(duì)DNS服務(wù)器訪問(wèn)的頻度，節(jié)約了帶寬，提高了效率。

為了減少等待查找新主機(jī)地址的時(shí)間，還可以采用預(yù)取(prefetch)技術(shù)，即盡早將主機(jī)名發(fā)送給DNS服務(wù)器進(jìn)行解析。網(wǎng)絡(luò)爬蟲(chóng)分析剛得到的網(wǎng)頁(yè)，直接從HREF等鏈接屬性中提取主機(jī)名而不是完整的URL，向緩存服務(wù)器提交DNS解析請(qǐng)求，結(jié)果放到DNS緩存中。雖然這些預(yù)先解析的域名可能有部分在后面用不上，但通過(guò)預(yù)取，可以將DNS解析并行于整個(gè)解析過(guò)程，從而減少DNS解析所花費(fèi)的時(shí)間。因?yàn)橛貌恢却馕龅耐瓿?，所以通常用UDP實(shí)現(xiàn)，UDP是基于非連接包的通信協(xié)議，不保證包的投遞，可以采用異步(Asynchronous)調(diào)用，降低阻塞。3.4.3優(yōu)先搜集策略

目前Web上的網(wǎng)頁(yè)有上萬(wàn)億，要把它們?nèi)孔ネ?，非常困難，也沒(méi)有必要，因?yàn)閃eb中存在大量重復(fù)的網(wǎng)頁(yè)內(nèi)容，而且Web上的網(wǎng)頁(yè)內(nèi)容良莠不齊，存在大量的垃圾網(wǎng)頁(yè)。因此在Web信息量指數(shù)級(jí)增長(zhǎng)的情況下，網(wǎng)絡(luò)爬蟲(chóng)應(yīng)該優(yōu)先搜集重要的和高質(zhì)量的網(wǎng)頁(yè)。

網(wǎng)頁(yè)是否重要和高質(zhì)量受很多因素影響，下面給出一些特征[22]：

(1)網(wǎng)頁(yè)的入度大，表明被其他網(wǎng)頁(yè)引用的次數(shù)多；

(2)某網(wǎng)頁(yè)的父網(wǎng)頁(yè)的入度大；

(3)網(wǎng)頁(yè)的鏡像度高，說(shuō)明網(wǎng)頁(yè)內(nèi)容可能是熱點(diǎn)；

(4)網(wǎng)頁(yè)的目錄深度小，易于用戶瀏覽。以網(wǎng)頁(yè)所在網(wǎng)站的根目錄為層次0形成遞增的目錄層次，網(wǎng)頁(yè)所在目錄的層次就是目錄深度。如某網(wǎng)頁(yè)URL為http：//，則該網(wǎng)頁(yè)的目錄深度為0；如果某網(wǎng)頁(yè)URL為http：///cs，則該網(wǎng)頁(yè)的目錄深度為1。

上面這些特征不是獨(dú)立無(wú)關(guān)的。綜合考慮這些特征，網(wǎng)頁(yè)的權(quán)重可以形式化表示為[22]：

weight(p)=f(indegree(p)，indegree(father_p)，

mirror(p)，directorydepth(p))

(3-4)

其中，weight(p)表示網(wǎng)頁(yè)p的權(quán)重，indegree(p)表示網(wǎng)頁(yè)p的入度函數(shù)，indegree(father_p)表示網(wǎng)頁(yè)p的父網(wǎng)頁(yè)的入度函數(shù)，mirror(p)表示網(wǎng)頁(yè)p的鏡像度函數(shù)，directorydepth(p)表示網(wǎng)頁(yè)p的目錄深度函

數(shù)。網(wǎng)絡(luò)爬蟲(chóng)開(kāi)始爬行時(shí)，既不知道要搜集的網(wǎng)頁(yè)入度大小(即不知道要訪問(wèn)的網(wǎng)頁(yè)URL被哪些其他網(wǎng)頁(yè)指向)，也不知道網(wǎng)頁(yè)內(nèi)容是什么，所以對(duì)于表征網(wǎng)頁(yè)重要性的第(1)、(2)、(3)項(xiàng)特征在搜集工作開(kāi)始時(shí)無(wú)法確定，這些因素只能在獲得網(wǎng)頁(yè)或幾乎所有的Web鏈接結(jié)構(gòu)之后才能夠知道。只有第(4)項(xiàng)特征根據(jù)URL即可確定，所以可以考慮根據(jù)網(wǎng)頁(yè)目錄深度來(lái)確定重要程度的初值。在再次搜集之前，則可以對(duì)已經(jīng)搜集到的網(wǎng)頁(yè)進(jìn)行計(jì)算，獲取入度數(shù)、鏡像度等信息，以指導(dǎo)網(wǎng)絡(luò)爬蟲(chóng)的優(yōu)先搜集。優(yōu)先策略的制定比較復(fù)雜，也比較困難，網(wǎng)絡(luò)信息搜集系統(tǒng)的設(shè)計(jì)者要根據(jù)信息采集的目的定制優(yōu)先搜集策略，以保證高效準(zhǔn)確地完成信息采集任務(wù)。很多搜索引擎會(huì)維護(hù)一個(gè)重要網(wǎng)頁(yè)的URL庫(kù)，如一些知名門(mén)戶網(wǎng)站的URL，這個(gè)庫(kù)可以人工維護(hù)，并調(diào)度網(wǎng)絡(luò)爬蟲(chóng)優(yōu)先訪問(wèn)這些重要網(wǎng)頁(yè)。3.4.4網(wǎng)頁(yè)更新

有研究[24]表明，網(wǎng)頁(yè)的平均生命周期約為50天，所以，搜集回來(lái)的網(wǎng)絡(luò)信息很快就會(huì)“過(guò)期”，搜索引擎為了給用戶提供最新的信息，必須驅(qū)動(dòng)網(wǎng)絡(luò)爬蟲(chóng)不斷地去抓取，這就涉及到如何處理網(wǎng)頁(yè)更新的問(wèn)題。

用最新抓取到的網(wǎng)頁(yè)去更新以前已經(jīng)搜集到的網(wǎng)頁(yè)，這是最直觀且最簡(jiǎn)單的做法，叫做“定期搜集更新”。例如Google在一段時(shí)間曾是每隔28天“爬行”一次。但是網(wǎng)頁(yè)的數(shù)量實(shí)在太多了，更新周期很難趕上網(wǎng)頁(yè)自身的更新速度，尤其是一些新聞網(wǎng)站，甚至天天時(shí)時(shí)在更新；而且重復(fù)搜集帶來(lái)額外的帶寬消耗；有些網(wǎng)頁(yè)根本就沒(méi)有更新，也需要重新搜集，極大地浪費(fèi)了資源。Fetterly等人研究了不同域名下面網(wǎng)頁(yè)數(shù)量演化的快慢[25]，如圖3-10所示，可以看出不同網(wǎng)站的網(wǎng)頁(yè)變化的頻度差別是很大的。所以有必要針對(duì)網(wǎng)站的網(wǎng)頁(yè)更新頻度來(lái)制定搜集更新策略。圖3-10按域聚類的網(wǎng)頁(yè)的更新頻度[25]很多網(wǎng)絡(luò)信息搜集系統(tǒng)更多地采用增量搜集更新的方法。所謂增量搜集，是指系統(tǒng)在開(kāi)始運(yùn)作時(shí)搜集一批網(wǎng)頁(yè)，以后不再去遍歷Web圖，而只是：

(1)搜集新出現(xiàn)的網(wǎng)頁(yè)。

(2)搜集那些在上次搜集后有過(guò)改變的網(wǎng)頁(yè)。

(3)發(fā)現(xiàn)自從上次搜集后已經(jīng)不再存在了的網(wǎng)頁(yè)，從存儲(chǔ)器上刪除。

這種更新方法，也就是變化的網(wǎng)頁(yè)、消失的網(wǎng)頁(yè)和新增的網(wǎng)頁(yè)，可以保證網(wǎng)絡(luò)信息的時(shí)新性。3.4.5網(wǎng)頁(yè)消重

即使在優(yōu)先采集高質(zhì)量網(wǎng)頁(yè)策略的導(dǎo)引下，網(wǎng)絡(luò)爬蟲(chóng)在爬行過(guò)程中，也不可避免地采集到相當(dāng)多的垃圾網(wǎng)頁(yè)，這些垃圾網(wǎng)頁(yè)不僅僅會(huì)影響用戶的搜索結(jié)果，而且會(huì)嚴(yán)重影響網(wǎng)絡(luò)爬蟲(chóng)的執(zhí)行效率。對(duì)這些垃圾網(wǎng)頁(yè)來(lái)講，一部分是含有無(wú)用信息的網(wǎng)頁(yè)，如無(wú)法登錄的信息或者是內(nèi)容為空的網(wǎng)頁(yè)，還有一類網(wǎng)頁(yè)就是大量重復(fù)內(nèi)容的網(wǎng)頁(yè)。這些網(wǎng)頁(yè)擁有相同的內(nèi)容，卻擁有不同的URL。造成這種情況的原因很多，比如鏡像網(wǎng)站，網(wǎng)站之間文章的轉(zhuǎn)載，這兩種情況屬于正常的網(wǎng)頁(yè)重復(fù)，但還有些重復(fù)的網(wǎng)頁(yè)則是不正常的重復(fù)，如某些動(dòng)態(tài)網(wǎng)頁(yè)，使用不同的參數(shù)訪問(wèn)它們，得到的結(jié)果頁(yè)面都是相同的。重復(fù)解析這些已抓取網(wǎng)頁(yè)的鏈接是沒(méi)有必要的，因此需要進(jìn)行網(wǎng)頁(yè)消重以減少處理時(shí)間和存儲(chǔ)開(kāi)銷等。網(wǎng)頁(yè)消重的主要思路是，將所有網(wǎng)頁(yè)的有效信息進(jìn)行提取，為每篇網(wǎng)頁(yè)制作一個(gè)數(shù)字指紋(fingerprint)，然后比較數(shù)字指紋，數(shù)字指紋相同的網(wǎng)頁(yè)則認(rèn)為是相同的網(wǎng)頁(yè)，可以集合進(jìn)行處理，例如只索引一份相同內(nèi)容的網(wǎng)頁(yè)，對(duì)其他內(nèi)容相同的網(wǎng)頁(yè)不再索引，但可以記錄它們不同的URL，以供檢索。由于數(shù)字指紋是判斷網(wǎng)頁(yè)內(nèi)容唯一性的標(biāo)志，在此可以定義一個(gè)網(wǎng)頁(yè)庫(kù)文件，其中的內(nèi)容以〈key，value〉的格式存儲(chǔ)。其中：(3-5)這里的PageURL是網(wǎng)頁(yè)的URL，PageContent是去噪后的網(wǎng)頁(yè)正文，value正是某篇網(wǎng)頁(yè)的數(shù)字指紋，這個(gè)指紋在整個(gè)網(wǎng)頁(yè)庫(kù)中應(yīng)該是唯一的。

H()函數(shù)保證每個(gè)URL在網(wǎng)頁(yè)中對(duì)應(yīng)的數(shù)字指紋絕對(duì)唯一。目前通用的算法是計(jì)算某篇文檔的哈希值來(lái)確定數(shù)字指紋。其中比較經(jīng)典的算法是MD5算法[26]，MD5算法廣泛應(yīng)用于網(wǎng)絡(luò)安全系統(tǒng)中，例如用于生成數(shù)字簽名等。MD5算法可以很方便地檢測(cè)完全相同的文檔，但即使是一個(gè)字符的改變也

會(huì)完全改變MD5摘要值，而網(wǎng)頁(yè)的轉(zhuǎn)載常伴隨有日期或者網(wǎng)站管理者名字的變化，這些網(wǎng)頁(yè)可以稱為近重復(fù)網(wǎng)頁(yè)(near-duplicates)。檢測(cè)接近重復(fù)的網(wǎng)頁(yè)可以采用計(jì)算全文分段數(shù)字指紋的分段(Shingling)方法。

Broder的Shingling算法[27-28]用兩個(gè)文檔的相似度(resemblance)和包含度(containment)來(lái)衡量其相似性。文檔A和文檔B的相似度是位于區(qū)間[0，1]中的一個(gè)數(shù)值，越接近于1，這兩個(gè)文檔越相似。類似地，包含度也是位于區(qū)間[0，1]中的一個(gè)數(shù)值，越接近于1，說(shuō)明文檔A被文檔B包含的程度越高。

給定一個(gè)長(zhǎng)的文檔A和一個(gè)分段長(zhǎng)度w，將A按長(zhǎng)度w進(jìn)行滑動(dòng)分段，形成的分段集合記為S(A，w)。例如文檔A內(nèi)容為“a，rose，is，a，rose，is，a，rose”，則分段長(zhǎng)度為4的分段集合S(A，4)為：{(a，rose，is，a)；(rose,is,a,rose)；(is，a，rose，is)；(a，rose，is，a)；(rose，is，a，rose)}。

文檔A、B之間的相似度定義為文檔A、B之間的包含度定義為

Shingling算法已經(jīng)廣泛應(yīng)用在搜索引擎的冗余網(wǎng)頁(yè)識(shí)別上。Schleimer的Winnowing算法[29]對(duì)經(jīng)典的Shingling算法做了改進(jìn)，其主要流程是：將文章劃分成長(zhǎng)度為k的片段，每w個(gè)片段為一個(gè)窗口，在每個(gè)窗口中取最小的片段哈希值作為該窗口的哈希值。所有被選擇的哈希值作為文章的指紋。該算法能夠保證檢測(cè)出長(zhǎng)度大于等于w+k－1的相匹配字符串。3.4.6避免蜘蛛陷阱

網(wǎng)絡(luò)爬蟲(chóng)通過(guò)解析頁(yè)面中的URL來(lái)嘗試遍歷Web圖，實(shí)際應(yīng)用中，URL存在不規(guī)范、重復(fù)引用、虛擬主機(jī)等問(wèn)題。這些問(wèn)題直接影響可采集到的信息的質(zhì)量和數(shù)量。

在Web上，還存在大量的動(dòng)態(tài)網(wǎng)頁(yè)，所謂動(dòng)態(tài)網(wǎng)頁(yè)，一般指的是采用ASP、JSP、PHP、ColdFusion、CGI等程序動(dòng)態(tài)生成的頁(yè)面。動(dòng)態(tài)網(wǎng)頁(yè)中的大部分內(nèi)容來(lái)自與網(wǎng)站相連的數(shù)據(jù)庫(kù)，只有接到用戶的訪問(wèn)要求后才生成并傳輸?shù)接脩舻臑g覽器中，即動(dòng)態(tài)網(wǎng)頁(yè)是當(dāng)用戶在變量區(qū)中輸入一些值后自動(dòng)生成的。在動(dòng)態(tài)頁(yè)面的URL中可能包含了問(wèn)號(hào)(?)和百分號(hào)(%)，還有一些符號(hào)諸如&，+和$等。支撐動(dòng)態(tài)網(wǎng)頁(yè)的后臺(tái)數(shù)據(jù)庫(kù)可能十分龐大，導(dǎo)致某些網(wǎng)站的動(dòng)態(tài)網(wǎng)頁(yè)URL層出不窮。如果網(wǎng)絡(luò)爬蟲(chóng)沒(méi)有意識(shí)到這個(gè)問(wèn)題，就會(huì)被該網(wǎng)站“粘住”，掉入所謂的蜘蛛陷阱，網(wǎng)絡(luò)爬蟲(chóng)不僅被套牢，而且它頻繁的造訪可能導(dǎo)致相應(yīng)的服務(wù)器崩潰。這就是很多網(wǎng)絡(luò)爬蟲(chóng)不敢抓取動(dòng)態(tài)網(wǎng)頁(yè)的原因。但是，動(dòng)態(tài)網(wǎng)頁(yè)以其鮮明的特色給用戶留下了深刻的印象，很多網(wǎng)站的建設(shè)越來(lái)越多地采用動(dòng)態(tài)網(wǎng)頁(yè)的形式。為了給用戶提供全面的信息，網(wǎng)絡(luò)爬蟲(chóng)必須能夠抓取動(dòng)態(tài)網(wǎng)頁(yè)，但為了確保其網(wǎng)絡(luò)爬蟲(chóng)程序免遭死循環(huán)之災(zāi)，網(wǎng)絡(luò)爬蟲(chóng)在對(duì)動(dòng)態(tài)頁(yè)面中的鏈接進(jìn)行深入訪問(wèn)時(shí)，會(huì)有適當(dāng)?shù)脑L問(wèn)策略控制網(wǎng)絡(luò)爬蟲(chóng)陷入蜘蛛陷阱。例如檢查URL的長(zhǎng)度(站點(diǎn)深度)，清除非文本類型的網(wǎng)頁(yè)，進(jìn)行網(wǎng)頁(yè)消重，定期收集爬取中的統(tǒng)計(jì)數(shù)據(jù)，發(fā)現(xiàn)在搜集過(guò)程中過(guò)多出現(xiàn)的網(wǎng)站就進(jìn)行屏蔽等。

3.5專題信息搜集

一般的搜索引擎總是力圖遍歷Web圖，盡可能采集所有可采集的網(wǎng)絡(luò)信息。但是隨著Web上信息的爆炸性增長(zhǎng)，網(wǎng)絡(luò)信息搜集系統(tǒng)對(duì)這種全面遍歷越來(lái)越力不從心了。即使大型的信息采集系統(tǒng)，它對(duì)Web的覆蓋率也只有30%~40%，而且更新時(shí)間往往需要幾個(gè)星期到數(shù)月[30]。另外，即使采集到了大量的Web信息，它的更新和維護(hù)也需要消耗大量的資源，更新周期變長(zhǎng)，失效信息增多。所以，很多研究人員和公司專注于研究專題搜索引擎，以提供垂直檢索(VerticalSearch)服務(wù)，如Google的學(xué)術(shù)搜索引擎，專門(mén)提供對(duì)學(xué)術(shù)論文和專著的檢索。這就需要進(jìn)行專題信息的采集，即只關(guān)注某一主題的信息，盡量采全該主題的全部信息，其他主題的信息作為無(wú)用信息被過(guò)濾掉了。因此專題信息采集(FocusedCrawling)主要是指選擇性地搜集那些與預(yù)先定義好的主題集相關(guān)的頁(yè)面的采集行為[31]。3.5.1網(wǎng)頁(yè)的主題特性

專題信息采集的關(guān)鍵是搜集相關(guān)主題信息，怎樣判定一個(gè)網(wǎng)頁(yè)是否屬于該主題呢？很多研究發(fā)現(xiàn)，同一個(gè)主題的Web頁(yè)面還是有規(guī)律可循的，這些規(guī)律用如下幾個(gè)特性來(lái)表征[32]。

1．中心特性

美國(guó)康奈爾大學(xué)的教授JonMKleinberg發(fā)現(xiàn)Web上存在大量的中心網(wǎng)頁(yè)(Hub)[33],這種頁(yè)面不但含有許多指出鏈接(outlink)，并且這些鏈接通常指向同一個(gè)主題相關(guān)的網(wǎng)頁(yè)，即中心網(wǎng)頁(yè)是某主題相關(guān)頁(yè)面的一個(gè)中心，是出度大的網(wǎng)頁(yè)。這一特性被稱為中心特性，或Hub特性。

另外，Kleinberg還定義了權(quán)威網(wǎng)頁(yè)(Authority)，它是被很多網(wǎng)頁(yè)指向的網(wǎng)頁(yè)，即入度大的網(wǎng)頁(yè)。好的中心網(wǎng)頁(yè)一般指向多個(gè)權(quán)威網(wǎng)頁(yè)，且所指向的權(quán)威網(wǎng)頁(yè)越權(quán)威，其質(zhì)量也越好；反過(guò)來(lái)，中心網(wǎng)頁(yè)的質(zhì)量越好，它所指向的每個(gè)網(wǎng)頁(yè)也越權(quán)威。這個(gè)特性被鏈接分析算法HITS所采用，詳見(jiàn)第7章的介紹。

2．局部特性

在Hub特性的基礎(chǔ)上，人們又提出了兩個(gè)局部特性[34]。

(1)鏈接局部性(LinkageLocality)：即某網(wǎng)頁(yè)的主題趨向于指向它的網(wǎng)頁(yè)的主題；

(2)同胞局部性(SiblingLocality)：對(duì)于鏈接到某主題頁(yè)面的頁(yè)面，它所鏈接到的其他頁(yè)面也趨向于擁有這個(gè)主題。

這兩個(gè)特性實(shí)際上是Hub特性的變形，主要是從頁(yè)面設(shè)計(jì)者設(shè)計(jì)的角度考慮的。一個(gè)頁(yè)面的設(shè)計(jì)者趨向于把本頁(yè)面指向于與本頁(yè)面相關(guān)的其他頁(yè)面，因此又稱為Sibling/Linkage局部性。

3．站點(diǎn)主題特性

一個(gè)站點(diǎn)趨向于說(shuō)明一個(gè)或幾個(gè)主題，并且那些說(shuō)明每個(gè)主題的頁(yè)面較緊密地在此站點(diǎn)內(nèi)部鏈接成團(tuán)，而各個(gè)主題團(tuán)之間卻鏈接較少。這主要與網(wǎng)站設(shè)計(jì)者的設(shè)計(jì)思路有關(guān)。每個(gè)網(wǎng)站在設(shè)計(jì)時(shí)都有目標(biāo)，而這種目標(biāo)往往就集中在一個(gè)或幾個(gè)主題中。而網(wǎng)站的瀏覽者往往也有一定的目的性，這個(gè)目的性一般體現(xiàn)在用戶趨向于瀏覽同一主題的頁(yè)面。為了滿足瀏覽者的這一需求，網(wǎng)站設(shè)計(jì)者需要將相關(guān)內(nèi)容緊密地鏈接在一起。

4．隧道特性

在Web中還有一類現(xiàn)象，就是主題頁(yè)面組之間往往需要經(jīng)過(guò)較多的無(wú)關(guān)鏈接才能相互到達(dá)。這些無(wú)關(guān)鏈接就像一個(gè)長(zhǎng)長(zhǎng)的隧道，連接著兩個(gè)主題團(tuán)，這種現(xiàn)象稱為隧道(Tunnel)特性。在基于主題的頁(yè)面采集過(guò)程中，Tunnel的存在極大地影響著采集的質(zhì)量。為了提高采集頁(yè)面的準(zhǔn)確率，需要提高過(guò)濾相關(guān)性判定閾值，而閾值的提高將過(guò)濾掉大量的Tunnel，使得采集系統(tǒng)很可能丟失Tunnel另一端的主題團(tuán)，進(jìn)而影響了查全率(或者說(shuō)資源發(fā)現(xiàn)率)。反過(guò)來(lái)，為了提高查全率，就得大量發(fā)現(xiàn)Tunnel，降低過(guò)濾相關(guān)性判定閾值，但是閾值的降低使得混進(jìn)了大量的無(wú)關(guān)頁(yè)面，從而大大降低了頁(yè)面的準(zhǔn)確率。

這是一個(gè)兩難問(wèn)題，但關(guān)鍵還在于能否有效地區(qū)別Tunnel和其他大量無(wú)關(guān)頁(yè)面。

Web中的頁(yè)面對(duì)于主題來(lái)說(shuō)是雜亂的，但也存在一些規(guī)律。Hub特性說(shuō)明了主題容易成團(tuán)出現(xiàn)的現(xiàn)象，Linkage/Sibling