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

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

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

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

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

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

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

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

聚焦爬蟲

目標(biāo)

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

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

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

(2)對網(wǎng)頁或數(shù)據(jù)的分析與過濾；

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

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

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

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

4.1Google爬蟲

4.2Mercator

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

4.5UbiCrawler

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

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

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

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