網(wǎng)絡(luò)爬蟲(chóng)de基礎(chǔ)知識(shí)

網(wǎng)絡(luò)爬蟲(chóng)1、網(wǎng)絡(luò)爬蟲(chóng)簡(jiǎn)介2、通用網(wǎng)絡(luò)爬蟲(chóng)和聚焦爬蟲(chóng)3、網(wǎng)絡(luò)爬蟲(chóng)的抓取策略4、幾種常見(jiàn)的網(wǎng)絡(luò)爬蟲(chóng)5、演示第一頁(yè)，共36頁(yè)。第一頁(yè)，共36頁(yè)。1、網(wǎng)絡(luò)爬蟲(chóng)簡(jiǎn)介

1.1定義1.2用途1.3原理第二頁(yè)，共36頁(yè)。第二頁(yè)，共36頁(yè)。1.1網(wǎng)絡(luò)爬蟲(chóng)定義網(wǎng)絡(luò)爬蟲(chóng)（Crawler）又被稱為網(wǎng)頁(yè)蜘蛛，網(wǎng)絡(luò)機(jī)器人，在FOAF（Friend-of-a-Friend）社區(qū)中，更經(jīng)常的被稱為網(wǎng)頁(yè)追逐者，它是一種按照一定的規(guī)則，自動(dòng)的抓取萬(wàn)維網(wǎng)信息的程序或者腳本。

另外一些不常使用的名字還有螞蟻，自動(dòng)索引，模擬程序或者蠕蟲(chóng)。第三頁(yè)，共36頁(yè)。第三頁(yè)，共36頁(yè)。1.2用途很多站點(diǎn)，尤其是搜索引擎，都使用爬蟲(chóng)提供最新的數(shù)據(jù)，它主要是提供它訪問(wèn)過(guò)頁(yè)面的一個(gè)副本，然后，搜索引擎就可以對(duì)得到的頁(yè)面進(jìn)行索引，以提供快速訪問(wèn)。

爬蟲(chóng)可以在web上用來(lái)自動(dòng)執(zhí)行一些任務(wù)，例如檢查鏈接，確認(rèn)html代碼；也可以用來(lái)抓取網(wǎng)頁(yè)上某種特定類型信息，例如抓取電子郵件地址（通常用于垃圾郵件）。

第四頁(yè)，共36頁(yè)。第四頁(yè)，共36頁(yè)。1.3原理一個(gè)網(wǎng)絡(luò)爬蟲(chóng)就是一種機(jī)器人，或者軟件代理。大體上，它從一組要訪問(wèn)的URL鏈接開(kāi)始，可以稱這些URL為種子。爬蟲(chóng)訪問(wèn)這些鏈接，它辨認(rèn)出這些頁(yè)面的所有超鏈接，然后添加到這個(gè)URL列表，可以稱作檢索前沿。這些URL按照一定的策略反復(fù)訪問(wèn)。第五頁(yè)，共36頁(yè)。第五頁(yè)，共36頁(yè)。2、通用網(wǎng)絡(luò)爬蟲(chóng)和聚焦爬蟲(chóng)2.1前言2.2通用網(wǎng)絡(luò)爬蟲(chóng)2.3聚焦爬蟲(chóng)2.4兩種爬蟲(chóng)比較第六頁(yè)，共36頁(yè)。第六頁(yè)，共36頁(yè)。2.1前言隨著網(wǎng)絡(luò)的迅速發(fā)展，萬(wàn)維網(wǎng)成為大量信息的載體，如何有效地提取并利用這些信息成為一個(gè)巨大的挑戰(zhàn)。搜索引擎(SearchEngine)，例如傳統(tǒng)的通用搜索引擎AltaVista，Yahoo!和Google等，作為一個(gè)輔助人們檢索信息的工具成為用戶訪問(wèn)萬(wàn)維網(wǎng)的入口和指南。但是，這些通用性搜索引擎也存在著一定的局限性：通用網(wǎng)絡(luò)爬蟲(chóng)的目標(biāo)就是盡可能多地采集信息頁(yè)面，在采集時(shí)只關(guān)注網(wǎng)頁(yè)采集的數(shù)量和質(zhì)量，并不考慮網(wǎng)頁(yè)采集的順序和被采集頁(yè)面的相關(guān)主題。第七頁(yè)，共36頁(yè)。第七頁(yè)，共36頁(yè)。為了解決通用搜索引擎的局限性，定向抓取相關(guān)網(wǎng)頁(yè)資源的聚焦爬蟲(chóng)應(yīng)運(yùn)而生。聚焦爬蟲(chóng)與通用爬蟲(chóng)不同，聚焦爬蟲(chóng)并不追求大的覆蓋，而將目標(biāo)定為抓取與某一特定主題內(nèi)容相關(guān)的網(wǎng)頁(yè)，為面向主題的用戶查詢準(zhǔn)備數(shù)據(jù)資源。第八頁(yè)，共36頁(yè)。第八頁(yè)，共36頁(yè)。2.2通用網(wǎng)絡(luò)爬蟲(chóng)

通用網(wǎng)絡(luò)爬蟲(chóng)從種子鏈接開(kāi)始，不斷抓取URL網(wǎng)頁(yè)，將這些URL全部放入到一個(gè)有序的待提取的URL隊(duì)列里。Web信息提取器從這個(gè)隊(duì)列里按順序取出URL，通過(guò)Web上的協(xié)議，獲取URL所指向的頁(yè)面，然后從這些頁(yè)面中分析提取出新的URL，并將它們放到等待提取的URL隊(duì)列里。通用爬蟲(chóng)就是通過(guò)這樣一種方式來(lái)不斷遍歷整個(gè)互聯(lián)網(wǎng)，一直到等待提取的URL隊(duì)列為空或者達(dá)到系統(tǒng)給定的停止條件為止。第九頁(yè)，共36頁(yè)。第九頁(yè)，共36頁(yè)。2.3聚焦爬蟲(chóng)

聚焦爬蟲(chóng)根據(jù)一定的網(wǎng)頁(yè)分析算法，過(guò)濾與主題無(wú)關(guān)的鏈接，保留有用的鏈接并將其放入等待抓取的URL隊(duì)列。然后，它將根據(jù)一定的搜索策略從隊(duì)列中選擇下一步要抓取的網(wǎng)頁(yè)URL，并重復(fù)上述過(guò)程，直到達(dá)到系統(tǒng)的某一條件時(shí)停止。第十頁(yè)，共36頁(yè)。第十頁(yè)，共36頁(yè)。2.4兩種爬蟲(chóng)比較通用網(wǎng)絡(luò)爬蟲(chóng)

聚焦爬蟲(chóng)

目標(biāo)

通用網(wǎng)絡(luò)爬蟲(chóng)的目標(biāo)是盡可能多的采集信息頁(yè)面，而在這一過(guò)程中它并不太在意頁(yè)面采集的順序和被采集頁(yè)面的相關(guān)主題。這需要消耗很多的系統(tǒng)資源和網(wǎng)絡(luò)帶寬，并且對(duì)這些資源的消耗并沒(méi)有換來(lái)采集頁(yè)面的較高利用率。

聚焦爬蟲(chóng)的目標(biāo)是盡可能快地爬行、采集盡可能多的與預(yù)先定義好的主題相關(guān)的網(wǎng)頁(yè)。聚焦爬蟲(chóng)可以通過(guò)對(duì)整個(gè)Web按主題分塊采集，并將不同塊的采集結(jié)果整合到一起，以提高整個(gè)Web的采集覆蓋率和頁(yè)面利用率。第十一頁(yè)，共36頁(yè)。第十一頁(yè)，共36頁(yè)。

相對(duì)于通用網(wǎng)絡(luò)爬蟲(chóng)，聚焦爬蟲(chóng)還需要解決三個(gè)主要問(wèn)題：(1)對(duì)抓取目標(biāo)的描述或定義；

(2)對(duì)網(wǎng)頁(yè)或數(shù)據(jù)的分析與過(guò)濾；

(3)對(duì)URL的搜索策略。抓取目標(biāo)的描述和定義是決定網(wǎng)頁(yè)分析算法與URL搜索策略如何制訂的基礎(chǔ)。而網(wǎng)頁(yè)分析算法和候選URL排序算法是決定搜索引擎所提供的服務(wù)形式和爬蟲(chóng)網(wǎng)頁(yè)抓取行為的關(guān)鍵所在。這兩個(gè)部分的算法又是緊密相關(guān)的。第十二頁(yè)，共36頁(yè)。第十二頁(yè)，共36頁(yè)。3、網(wǎng)絡(luò)爬蟲(chóng)的抓取策略3.1網(wǎng)頁(yè)搜索策略3.2爬行策略

第十三頁(yè)，共36頁(yè)。第十三頁(yè)，共36頁(yè)。3.1網(wǎng)頁(yè)搜索策略網(wǎng)頁(yè)的抓取策略可以分為深度優(yōu)先、廣度優(yōu)先和最佳優(yōu)先三種。深度優(yōu)先在很多情況下會(huì)導(dǎo)致爬蟲(chóng)的陷入(trapped)問(wèn)題，目前常見(jiàn)的是廣度優(yōu)先和最佳優(yōu)先方法。第十四頁(yè)，共36頁(yè)。第十四頁(yè)，共36頁(yè)。3.1.1廣度優(yōu)先搜索策略廣度優(yōu)先搜索策略是指在抓取過(guò)程中，在完成當(dāng)前層次的搜索后，才進(jìn)行下一層次的搜索。該算法的設(shè)計(jì)和實(shí)現(xiàn)相對(duì)簡(jiǎn)單。在目前為覆蓋盡可能多的網(wǎng)頁(yè)，一般使用廣度優(yōu)先搜索方法。也有很多研究將廣度優(yōu)先搜索策略應(yīng)用于聚焦爬蟲(chóng)中。其基本思想是認(rèn)為與初始URL在一定鏈接距離內(nèi)的網(wǎng)頁(yè)具有主題相關(guān)性的概率很大。第十五頁(yè)，共36頁(yè)。第十五頁(yè)，共36頁(yè)。另外一種方法是將廣度優(yōu)先搜索與網(wǎng)頁(yè)過(guò)濾技術(shù)結(jié)合使用，先用廣度優(yōu)先策略抓取網(wǎng)頁(yè)，再將其中無(wú)關(guān)的網(wǎng)頁(yè)過(guò)濾掉。這些方法的缺點(diǎn)在于，隨著抓取網(wǎng)頁(yè)的增多，大量的無(wú)關(guān)網(wǎng)頁(yè)將被下載并過(guò)濾，算法的效率將變低。第十六頁(yè)，共36頁(yè)。第十六頁(yè)，共36頁(yè)。3.1.2最佳優(yōu)先搜索策略最佳優(yōu)先搜索策略按照一定的網(wǎng)頁(yè)分析算法，預(yù)測(cè)候選URL與目標(biāo)網(wǎng)頁(yè)的相似度，或與主題的相關(guān)性，并選取評(píng)價(jià)最好的一個(gè)或幾個(gè)URL進(jìn)行抓取。它只訪問(wèn)經(jīng)過(guò)網(wǎng)頁(yè)分析算法預(yù)測(cè)為“有用”的網(wǎng)頁(yè)。

第十七頁(yè)，共36頁(yè)。第十七頁(yè)，共36頁(yè)。存在的一個(gè)問(wèn)題是，在爬蟲(chóng)抓取路徑上的很多相關(guān)網(wǎng)頁(yè)可能被忽略，因?yàn)樽罴褍?yōu)先策略是一種局部最優(yōu)搜索算法。因此需要將最佳優(yōu)先結(jié)合具體的應(yīng)用進(jìn)行改進(jìn)，以跳出局部最優(yōu)點(diǎn)。研究表明，這樣的閉環(huán)調(diào)整可以將無(wú)關(guān)網(wǎng)頁(yè)數(shù)量降低30%-90%。

第十八頁(yè)，共36頁(yè)。第十八頁(yè)，共36頁(yè)。3.2爬行策略更新頻率太快了數(shù)據(jù)量好大啊頁(yè)面是動(dòng)態(tài)的呀以上三種網(wǎng)絡(luò)特征使得設(shè)計(jì)網(wǎng)頁(yè)爬蟲(chóng)抓取策略變得很難。第十九頁(yè)，共36頁(yè)。第十九頁(yè)，共36頁(yè)。網(wǎng)頁(yè)爬蟲(chóng)的行為通常是四種策略組合的結(jié)果：(a)選擇策略，決定所要下載的頁(yè)面；(b)重新訪問(wèn)策略，決定什么時(shí)候檢查頁(yè)面的更新變化；(c)平衡禮貌策略，指出怎樣避免站點(diǎn)超載；(d)并行策略，指出怎么協(xié)同達(dá)到分布式抓取的效果。第二十頁(yè)，共36頁(yè)。第二十頁(yè)，共36頁(yè)。選擇策略就現(xiàn)在網(wǎng)絡(luò)資源的大小而言，即使很大的搜索引擎也只能獲取網(wǎng)絡(luò)上可得到資源的一小部分。由勞倫斯等人共同做的一項(xiàng)研究指出，沒(méi)有一個(gè)搜索引擎抓取的內(nèi)容達(dá)到網(wǎng)絡(luò)的16%。網(wǎng)絡(luò)爬蟲(chóng)通常僅僅下載網(wǎng)頁(yè)內(nèi)容的一部分，但是大家都還是強(qiáng)烈要求下載的部分包括最多的相關(guān)頁(yè)面，而不僅僅是一個(gè)隨機(jī)的簡(jiǎn)單的站點(diǎn)。這就要求一個(gè)公共標(biāo)準(zhǔn)來(lái)區(qū)分網(wǎng)頁(yè)的重要程度，一個(gè)頁(yè)面的重要程度與它自身的質(zhì)量有關(guān)，與按照鏈接數(shù)、訪問(wèn)數(shù)得出的受歡迎程度有關(guān)，甚至與它本身的網(wǎng)址（后來(lái)出現(xiàn)的把搜索放在一個(gè)頂級(jí)域名或者一個(gè)固定頁(yè)面上的垂直搜索）有關(guān)。設(shè)計(jì)一個(gè)好的搜索策略還有額外的困難，它必須在不完全信息下工作，因?yàn)檎麄€(gè)頁(yè)面的集合在抓取時(shí)是未知的。第二十一頁(yè)，共36頁(yè)。第二十一頁(yè)，共36頁(yè)。Cho（曹）等人做了第一份抓取策略的研究。他們的數(shù)據(jù)是斯坦福大學(xué)網(wǎng)站中的18萬(wàn)個(gè)頁(yè)面，使用不同的策略分別模仿抓取。排序的方法使用了廣度優(yōu)先，后鏈計(jì)數(shù)，和部分pagerank算法。計(jì)算顯示，如果你想要優(yōu)先下載pagerank高的頁(yè)面，那么，部分PageRank策略是比較好的，其次是廣度優(yōu)先和后鏈計(jì)數(shù)。并且，這樣的結(jié)果僅僅是針對(duì)一個(gè)站點(diǎn)的。Abiteboul設(shè)計(jì)了一種基于OPIC（在線頁(yè)面重要指數(shù)）的抓取戰(zhàn)略。在OPIC中，每一個(gè)頁(yè)面都有一個(gè)相等的初始權(quán)值，并把這些權(quán)值平均分給它所指向的頁(yè)面。這種算法與PageRank相似，但是它的速度很快，并且可以一次完成。OPIC的程序首先抓取獲取權(quán)值最大的頁(yè)面，實(shí)驗(yàn)在10萬(wàn)個(gè)冪指分布的模擬頁(yè)面中進(jìn)行。但是，實(shí)驗(yàn)沒(méi)有和其它策略進(jìn)行比較，也沒(méi)有在真正的WEB頁(yè)面測(cè)試。Baeza-Yates等人在從.gr域名和.cl域名子網(wǎng)站上獲取的300萬(wàn)個(gè)頁(yè)面上模擬實(shí)驗(yàn)，比較若干個(gè)抓取策略。結(jié)果顯示OPIC策略和站點(diǎn)隊(duì)列長(zhǎng)度，都比廣度優(yōu)先要好；并且如果可行的話，使用之前的爬行抓取結(jié)果來(lái)指導(dǎo)這次抓取，總是十分有效的。第二十二頁(yè)，共36頁(yè)。第二十二頁(yè)，共36頁(yè)。重新訪問(wèn)策略網(wǎng)絡(luò)具有動(dòng)態(tài)性很強(qiáng)的特性。抓取網(wǎng)絡(luò)上的一小部分內(nèi)容可能會(huì)花費(fèi)很長(zhǎng)的時(shí)間，通常用周或者月來(lái)衡量。當(dāng)爬蟲(chóng)完成它的抓取的任務(wù)以后，很多操作是可能會(huì)發(fā)生的，這些操作包括新建、更新和刪除。從搜索引擎的角度來(lái)看，不檢測(cè)這些事件是有成本的，成本就是我們僅僅擁有一份過(guò)時(shí)的資源。最常使用的成本函數(shù)，是新鮮度和過(guò)時(shí)性。第二十三頁(yè)，共36頁(yè)。第二十三頁(yè)，共36頁(yè)。新鮮度：這是一個(gè)衡量抓取內(nèi)容是不是準(zhǔn)確的二元值。在時(shí)間t內(nèi)，倉(cāng)庫(kù)中頁(yè)面p的新鮮度是這樣定義的：過(guò)時(shí)性:這是一個(gè)衡量本地已抓取的內(nèi)容過(guò)時(shí)程度的指標(biāo)。在時(shí)間t時(shí)，倉(cāng)庫(kù)中頁(yè)面p的時(shí)效性的定義如下：第二十四頁(yè)，共36頁(yè)。第二十四頁(yè)，共36頁(yè)。平衡禮貌策略爬蟲(chóng)的使用對(duì)很多工作都是很有用的，但是對(duì)一般的社區(qū)，也需要付出代價(jià)。使用爬蟲(chóng)的代價(jià)包括：網(wǎng)絡(luò)資源：在很長(zhǎng)一段時(shí)間，爬蟲(chóng)使用相當(dāng)?shù)膸捀叨炔⑿械毓ぷ?。服?wù)器超載：尤其是對(duì)給定服務(wù)器的訪問(wèn)過(guò)高時(shí)。質(zhì)量糟糕的爬蟲(chóng)：可能導(dǎo)致服務(wù)器或者路由器癱瘓，或者會(huì)嘗試下載自己無(wú)法處理的頁(yè)面。個(gè)人爬蟲(chóng)：如果過(guò)多的人使用，可能導(dǎo)致網(wǎng)絡(luò)或者服務(wù)器阻塞。第二十五頁(yè)，共36頁(yè)。第二十五頁(yè)，共36頁(yè)。對(duì)這些問(wèn)題的一個(gè)部分解決方法是漫游器排除協(xié)議（Robotsexclusionprotocol），即REP協(xié)議，這份協(xié)議對(duì)于管理員指明網(wǎng)絡(luò)服務(wù)器的那一部分不能到達(dá)是一個(gè)標(biāo)準(zhǔn)。這個(gè)標(biāo)準(zhǔn)沒(méi)有包括重新訪問(wèn)一臺(tái)服務(wù)器的間隔的建議，雖然訪問(wèn)間隔是避免服務(wù)器超載的最有效的辦法。最近的商業(yè)搜索軟件，如AskJeeves，MSN和Yahoo可以在robots.txt中使用一個(gè)額外的“Crawl-delay”參數(shù)來(lái)指明請(qǐng)求之間的延遲。第二十六頁(yè)，共36頁(yè)。第二十六頁(yè)，共36頁(yè)。并行策略一個(gè)并行爬蟲(chóng)是并行運(yùn)行多個(gè)進(jìn)程的爬蟲(chóng)。它的目標(biāo)是最大化下載的速度，同時(shí)盡量減少并行的開(kāi)銷和下載重復(fù)的頁(yè)面。為了避免下載一個(gè)頁(yè)面兩次，爬蟲(chóng)系統(tǒng)需要策略來(lái)處理爬蟲(chóng)運(yùn)行時(shí)新發(fā)現(xiàn)的URL，因?yàn)橥粋€(gè)URL地址，可能被不同的爬蟲(chóng)進(jìn)程抓到。第二十七頁(yè)，共36頁(yè)。第二十七頁(yè)，共36頁(yè)。4、幾種常見(jiàn)的網(wǎng)絡(luò)爬蟲(chóng)

4.1Google爬蟲(chóng)

4.2Mercator

4.3北大天網(wǎng)4.4InternetArchive

4.5UbiCrawler

第二十八頁(yè)，共36頁(yè)。第二十八頁(yè)，共36頁(yè)。4.1Google爬蟲(chóng)斯坦福大學(xué)設(shè)計(jì)了用于Google的爬蟲(chóng)第二十九頁(yè)，共36頁(yè)。第二十九頁(yè)，共36頁(yè)。

早期的Google爬蟲(chóng)系統(tǒng)由5個(gè)模塊處理不同的任務(wù)。一個(gè)URL服務(wù)器從磁盤(pán)文件讀URL列表并將其轉(zhuǎn)發(fā)到Crawler上。每個(gè)Crawler單獨(dú)運(yùn)行在一臺(tái)機(jī)器上，采用單線程異步10方式，一次維持300個(gè)連接并行爬行。Crawler將網(wǎng)頁(yè)傳輸?shù)酱鎯?chǔ)服務(wù)器上壓縮并保存。索引進(jìn)程從HTML頁(yè)面中抽取鏈接并存放在不同的文件中。一個(gè)URL解析器讀取這些鏈接文件并轉(zhuǎn)化為絕對(duì)路徑，由URL服務(wù)器讀取。

第三十頁(yè)，共36頁(yè)。第三十頁(yè)，共36頁(yè)。后期Google的改進(jìn)主要有：(1)采用自有的文件系統(tǒng)(GFS)和數(shù)據(jù)庫(kù)系統(tǒng)(BigTable)來(lái)存取數(shù)據(jù)；(2)采用MapReduce技術(shù)來(lái)分布式處理各種數(shù)據(jù)的運(yùn)算。第三十一頁(yè)，共36頁(yè)。第三十一頁(yè)，共36頁(yè)。4.2Mercator

康柏系統(tǒng)研究中心的AIlanHeydon和MarcNajork設(shè)計(jì)了名叫Mercator的爬行器。系統(tǒng)采用Java的多線程同步方式實(shí)現(xiàn)并行處理，并加入了很多優(yōu)化策略如DNS緩沖、延遲存儲(chǔ)等以提升爬行器運(yùn)