網路蜘蛛

網路蜘蛛

網路蜘蛛即Web Spider,是一個很形象的名字。把網際網路比喻成一個蜘蛛網,那么Spider就是在網上爬來爬去的蜘蛛。網路蜘蛛是通過網頁的連結地址來尋找網頁,從網站某一個頁面(通常是首頁)開始,讀取網頁的內容,找到在網頁中的其它連結地址,然後通過這些連結地址尋找下一個網頁,這樣一直循環下去,直到把這個網站所有的網頁都抓取完為止。

“蜘蛛”程式的出現,代表現代意義上的搜尋引擎才初露端倪。它實際上是採用一種程式,一種算法,形象的稱呼為電腦“機器人”(Computer Robot),電腦“機器人”是指某個能以人類無法達到的速度不間斷地執行某項任務的軟體程式。由於專門用於檢索信息的“機器人”程式就象蜘蛛一樣在網路間爬來爬去,反反覆覆,不知疲倦。所以,搜尋引擎的“機器人”程式就被稱為“蜘蛛”程式。

(圖)網路蜘蛛網路蜘結構圖蛛

網路蜘蛛

網路蜘蛛Web Spider,是一個很形象的名字。把網際網路比喻成一個蜘蛛網,那么Spider就是在網上爬來爬去的

網路蜘蛛網路蜘蛛
。網路蜘蛛是通過網頁的連結地址來尋找網頁,從網站某一個頁面(通常是首頁)開始,讀取網頁的內容,找到在網頁中的其它連結地址,然後通過這些連結地址尋找下一個網頁,這樣一直循環下去,直到把這個網站所有的網頁都抓取完為止。如果把整個網際網路當成一個網站,那么網路蜘蛛就可以用這個原理把網際網路上所有的網頁都抓取下來。對於搜尋引擎來說,要抓取網際網路上所有的網頁幾乎是不可能的,從目前公布的數據來看,容量最大的搜尋引擎也不過是抓取了整個網頁數量的百分之四十左右。這其中的原因一方面是抓取技術的瓶頸,無法遍歷所有的網頁,有許多網頁無法從其它網頁的連結中找到;另一個原因是存儲技術和處理技術的問題,如果按照每個頁面的平均大小為20K計算(包含圖片),100億網頁的容量是100×2000G位元組,即使能夠存儲,下載也存在問題(按照一台機器每秒下載20K計算,需要340台機器不停的下載一年時間,才能把所有網頁下載完畢)。同時,由於數據量太大,在提供搜尋時也會有效率方面的影響。因此,許多搜尋引擎的網路蜘蛛只是抓取那些重要的網頁,而在抓取的時候評價重要性主要的依據是某個網頁的連結深度。在抓取網頁的時候,網路蜘蛛一般有兩種策略:廣度優先和深度優先(如下圖所示)。廣度優先是指網路蜘蛛會先抓取起始網頁中連結的所有網頁,然後再選擇其中的一個連結網頁,繼續抓取在此網頁中連結的所有網頁。這是最常用的方式,因為這個方法可以讓網路蜘蛛並行處理,提高其抓取速度。深度優先是指網路蜘蛛會從起始頁開始,一個連結一個連結跟蹤下去,處理完這條線路之後再轉入下一個起始頁,繼續跟蹤連結。這個方法有個優點是網路蜘蛛在設計的時候比較容易。兩種策略的區別,下圖的說明會更加明確。由於不可能抓取所有的網頁,有些網路蜘蛛對一些不太重要的網站,設定了訪問的層數。例如,在上圖中,A為起始網頁,屬於0層,B、C、D、E、F屬於第1層,G、H屬於第2層,I屬於第3層。如果網路蜘蛛設定的訪問層數為2的話,網頁I是不會被訪問到的。這也讓有些網站上一部分網頁能夠在搜尋引擎上搜尋到,另外一部分不能被搜尋到。 對於網站設計者來說,扁平化的網站結構設計有助於搜尋引擎抓取其更多的網頁。

網路蜘蛛在訪問網站網頁的時候,經常會遇到加密數據和網頁許可權的問題,有些網頁是需要會員許可權才能訪問。當然,網站的所有者可以通過協定讓網路蜘蛛不去抓取(下小節會介紹),但對於一些出售報告的網站,他們希望搜尋引擎能搜尋到他們的報告,但又不能完全免費的讓搜尋者查看,這樣就需要給網路蜘蛛提供相應的用戶名和密碼。網路蜘蛛可以通過所給的許可權對這些網頁進行網頁抓取,從而提供搜尋。而當搜尋者點擊查看該網頁的時候,同樣需要搜尋者提供相應的許可權驗證。

網站與網路蜘蛛

網路蜘蛛需要抓取網頁,不同於一般的訪問,如果控制不好,則會引起網站伺服器負擔過重。每個網路蜘蛛都有自己的名字,在抓取網頁的時候,都會向網站標明自己的身份。網路蜘蛛在抓取網頁的時候會傳送一個請求,這個請求中就有一個欄位為User-agent,用於標識此網路蜘蛛的身份。例如Google網路蜘蛛的標識為GoogleBot,Baidu網路蜘蛛的標識為baiduspider,Yahoo網路蜘蛛的標識為Inktomi slurp。如果在網站上有訪問日誌記錄,網站管理員就能知道,哪些搜尋引擎的網路蜘蛛過來過,什麼時候過來的,以及讀了多少數據等等。如果網站管理員發現某個蜘蛛有問題,就通過其標識來和其所有者聯繫。下面是部落格中國( http://www.blogchina.com)2004年5月15日的搜尋引擎訪問日誌。網路蜘蛛進入一個網站,一般會訪問一個特殊的文本檔案Robots.txt,這個檔案一般放在網站伺服器的根目錄下,如: http://www.blogchina.com/robots.txt。網站管理員可以通過robots.txt來定義哪些目錄網路蜘蛛不能訪問,或者哪些目錄對於某些特定的網路蜘蛛不能訪問。例如有些網站的執行檔目錄和臨時檔案目錄不希望被搜尋引擎搜尋到,那么網站管理員就可以把這些目錄定義為拒絕訪問目錄。Robots.txt語法很簡單,例如如果對目錄沒有任何限制,可以用以下兩行來描述: User-agent: * Disallow:

Robots.txt只是一個協定,如果網路蜘蛛的設計者不遵循這個協定,網站管理員也無法阻止網路蜘蛛對於某些頁面的訪問,但一般的網路蜘蛛都會遵循這些協定,而且網站管理員還可以通過其它方式來拒絕網路蜘蛛對某些網頁的抓取。網路蜘蛛在下載網頁的時候,會去識別網頁的HTML代碼,在其代碼的部分,會有META標識。通過這些標識,可以告訴網路蜘蛛本網頁是否需要被抓取,還可以告訴網路蜘蛛本網頁中的連結是否需要被繼續跟蹤。例如: 表示本網頁不需要被抓取,但是網頁內的連結需要被跟蹤。現在一般的網站都希望搜尋引擎能更全面的抓取自己網站的網頁,因為這樣可以讓更多的訪問者能通過搜尋引擎找到此網站。為了讓本網站的網頁更全面被抓取到,網站管理員可以建立一個網站地圖,即Site Map。許多網路蜘蛛會把sitemap.htm檔案作為一個網站網頁爬取的入口,網站管理員可以把網站內部所有網頁的連結放在這個檔案裡面,那么網路蜘蛛可以很方便的把整個網站抓取下來,避免遺漏某些網頁,也會減小對網站伺服器的負擔。

內容提取

搜尋引擎建立網頁索引,處理的對象是文本檔案。對於網路蜘蛛來說,抓取下來網頁包括各種格式,包括html、圖片、doc、pdf、多媒體、動態網頁及其它格式等。這些檔案抓取下來後,需要把這些檔案中的文本信息提取出來。準確提取這些文檔的信息,一方面對搜尋引擎的搜尋準確性有重要作用,另一方面對於網路蜘蛛正確跟蹤其它連結有一定影響。對於doc、pdf等文檔,這種由專業廠商提供的軟體生成的文檔,廠商都會提供相應的文本提取接口。網路蜘蛛只需要調用這些外掛程式的接口,就可以輕鬆的提取文檔中的文本信息和檔案其它相關的信息。

HTML等文檔不一樣,HTML有一套自己的語法,通過不同的命令標識符來表示不同的字型、顏色、位置等版式,如:、、 等,提取文本信息時需要把這些標識符都過濾掉。過濾標識符並非難事,因為這些標識符都有一定的規則,只要按照不同的標識符取得相應的信息即可。但在識別這些信息的時候,需要同步記錄許多版式信息,例如文字的字型大小、是否是標題、是否是加粗顯示、是否是頁面的關鍵字等,這些信息有助於計算單詞在網頁中的重要程度。同時,對於HTML網頁來說,除了標題和正文以外,會有許多廣告連結以及公共的頻道連結,這些連結和文本正文一點關係也沒有,在提取網頁內容的時候,也需要過濾這些無用的連結。例如某個網站有“產品介紹”頻道,因為導航條在網站內每個網頁都有,若不過濾導航條連結,在搜尋“產品介紹”的時候,則網站內每個網頁都會搜尋到,無疑會帶來大量垃圾信息。過濾這些無效連結需要統計大量的網頁結構規律,抽取一些共性,統一過濾;對於一些重要而結果特殊的網站,還需要個別處理。這就需要網路蜘蛛的設計有一定的擴展性。對於多媒體、圖片等檔案,一般是通過連結的錨文本(即,連結文本)和相關的檔案注釋來判斷這些檔案的內容。例如有一個連結文字為“張曼玉照片”,其連結指向一張bmp格式的圖片,那么網路蜘蛛就知道這張圖片的內容是“張曼玉的照片”。這樣,在搜尋“張曼玉”和“照片”的時候都能讓搜尋引擎找到這張圖片。另外,許多多媒體檔案中有檔案屬性,考慮這些屬性也可以更好的了解檔案的內容。動態網頁一直是網路蜘蛛面臨的難題。所謂動態網頁,是相對於靜態網頁而言,是由程式自動生成的頁面,這樣的好處是可以快速統一更改網頁風格,也可以減少網頁所占伺服器的空間,但同樣給網路蜘蛛的抓取帶來一些麻煩。由於開發語言不斷的增多,動態網頁的類型也越來越多,如:aspjspphp等。這些類型的網頁對於網路蜘蛛來說,可能還稍微容易一些。網路蜘蛛比較難於處理的是一些腳本語言(如JavaScript)生成的網頁,如果要完善的處理好這些網頁,網路蜘蛛需要有自己的腳本解釋程式。對於許多數據是放在資料庫的網站,需要通過本網站的資料庫搜尋才能獲得信息,這些給網路蜘蛛的抓取帶來很大的困難。對於這類網站,如果網站設計者希望這些數據能被搜尋引擎搜尋,則需要提供一種可以遍歷整個資料庫內容的方法。對於網頁內容的提取,一直是網路蜘蛛中重要的技術。整個系統一般採用外掛程式的形式,通過一個外掛程式管理服務程式,遇到不同格式的網頁採用不同的外掛程式處理。這種方式的好處在於擴充性好,以後每發現一種新的類型,就可以把其處理方式做成一個外掛程式補充到外掛程式管理服務程式之中。

更新周期

由於網站的內容經常在變化,因此網路蜘蛛也需不斷的更新其抓取網頁的內容,這就需要網路蜘蛛按照一定的周期去掃描網站,查看哪些頁面是需要更新的頁面,哪些頁面是新增頁面,哪些頁面是已經過期的死連結。搜尋引擎的更新周期對搜尋引擎搜尋的查全率有很大影響。如果更新周期太長,則總會有一部分新生成的網頁搜尋不到;周期過短,技術實現會有一定難度,而且會對頻寬、伺服器的資源都有浪費。搜尋引擎的網路蜘蛛並不是所有的網站都採用同一個周期進行更新,對於一些重要的更新量大的網站,更新的周期短,如有些新聞網站,幾個小時就更新一次;相反對於一些不重要的網站,更新的周期就長,可能一兩個月才更新一次。一般來說,網路蜘蛛在更新網站內容的時候,不用把網站網頁重新抓取一遍,對於大部分的網頁,只需要判斷網頁的屬性(主要是日期),把得到的屬性和上次抓取的屬性相比較,如果一樣則不用更新。

網路蜘蛛的評價指標

覆蓋率

網路蜘蛛的首要目標是抓取網際網路上所需的信息。因此,有價值的信息是否都收錄,收錄的比例(即覆蓋率)是網路蜘蛛的基本評價指標

時效性

用戶對搜尋引擎的查詢要求越來越高,其中重要的一點就是查詢時效性,即事件發生並在網際網路上傳播後(以新聞、論壇、部落格等各種形式),用戶需要通過搜尋引擎儘快能檢索到相應內容。而索引的前提是收錄,因此需要網路蜘蛛儘快的抓取網際網路上最新出現的資源

重複率

網際網路上重複的內容很多,如何儘早的發現頁面重複並消除之,是網路蜘蛛需要解決的問題。 除轉載導致的重複外,重複總能體現為各種不同的模式,站點級重複,目錄級重複,CGI級重複,參數級重複等等,及早發現這些模式並進行處理,能節省系統的存儲、抓取、建庫和展現資源

價值

搜尋引擎越來越成為人們生活中重要的一部分,找資料、查地圖、聽音樂,只有想不到的,沒有搜尋不到的。網路蜘蛛機器人技術,網路蜘蛛可以算得上是為Internet而開發的最有用處的工具之一。時至今日,要想從以千萬計的各不相同的站點中獲取信息。網路蜘蛛技術的完善與進步,將給信息社會生活帶來極大的進步與改變。新競爭力認為,高效的站內檢索可以讓用戶快速準確地找到目標信息,從而更有效地促進產品/服務的銷售,而且通過對網站訪問者搜尋行為的深度分析,對於進一步制定更為有效的網路行銷策略具有重要價值。因此,對於內容豐富的大型信息類網站和產品線豐富的線上銷售型網站來說,提供一般性的全文檢索是遠遠不夠的,很有必要開發能夠實現個性化需求的高級搜尋功能,這也是體現網站的網路行銷功能的重要方面。網路蜘蛛技術必定大行其道。

網路蜘蛛的爬行算法

一個網路蜘蛛就是一種機器人,或者軟體代理。大體上,它從一組要訪問的URL連結開始,可以稱這些URL為種子。爬蟲訪問這些連結,它辨認出這些頁面的所有超連結,然後添加到這個URL列表,可以稱作檢索前沿。這些URL按照一定的策略反覆訪問。
主要內容
• 1 爬行策略
o 1.1 選擇策略
§ 1.1.1 限定訪問連結
§ 1.1.2 路徑檢索
§ 1.1.3 聚焦檢索
§ 1.1.4 抓取深層的網頁
§ 1.1.5 web 3.0檢索
o 1.2 重新訪問策略
o 1.3 平衡禮貌策略
o 1.4 並行化策略
• 2 網路爬蟲體系結構
o 2.1 URL規範化
• 3 爬蟲身份識別
• 4 網路爬蟲的例子
o 4.1 開源的網路爬蟲
1. 爬行策略
下述的三種網路特徵,造成了設計網頁爬蟲抓取策略變得很難:
 它巨大的數據量;
 它快速的更新頻率;
 動態頁面的產生
它們三個特徵一起產生了很多種類的爬蟲抓取連結。
巨大的數據量暗示了爬蟲,在給定的時間內,只可以抓取所下載網路的一部分,所以,它需要對它的抓取頁面設定優先權;快速的更新頻率說明在爬蟲抓取下載某網站一個網頁的時候,很有可能在這個站點又有很的網頁被添加進來,或者這個頁面被更新或者刪除了。
最近新增的很多頁面都是通過伺服器端腳本語言產生的,無窮的參數組合也增加了爬蟲抓取的難度,只有一小部分這種組合會返回一些獨特的內容。例如,一個很小照片存儲庫僅僅通過get方式可能提供就給用戶三種操作方式。如果這裡存著四種分類方式,三種縮略圖方式,兩種檔案格式,和一個禁止用戶提供內容的選項,那么,同樣的內容就可以通過48種方式訪問。這種數學組合給網路爬蟲創造的難處就是,為了獲取不同的內容,他們必須篩選無窮僅有微小變化的組合。
正如愛德華等人所說的:“用於檢索的頻寬不是無限的,也不是免費的;所以,如果引入衡量爬蟲抓取質量或者新鮮度的有效指標的話,不但伸縮性,連有效性都將變得十分必要”(愛德華等人,2001年)。一個爬蟲就必須小心的選擇下一步要訪問什麼頁面。網頁爬蟲的行為通常是四種策略組合的結果。
♦ 選擇策略,決定所要下載的頁面;
♦ 重新訪問策略,決定什麼時候檢查頁面的更新變化;
♦ 平衡禮貌策略,指出怎樣避免站點超載;
♦ 並行策略,指出怎么協同達到分散式抓取的效果;
1.1 選擇策略:
就現在網路資源的大小而言,即使很大的搜尋引擎也只能獲取網路上可得到資源的一小部分。由勞倫斯河蓋爾斯共同做的一項研究指出,沒有一個搜尋引擎抓取的內容達到網路的16%(勞倫斯河蓋爾斯,2001)。網路爬蟲通常僅僅下載網頁內容的一部分,但是大家都還是強烈要求下載的部分包括最多的相關頁面,而不僅僅是一個隨機的簡單的站點。
這就要求一個公共標準來區分網頁的重要程度,一個頁面的重要程度與他自身的質量有關,與按照連結數、訪問數得出的受歡迎程度有關,甚至與他本身的網址(後來出現的把搜尋放在一個頂級域名或者一個固定頁面上的垂直搜尋)有關。設計一個好的搜尋策略還有額外的困難,它必須在不完全信息下工作,因為整個頁面的集合在抓取時是未知的。
Cho等人(Cho et al,1998)做了第一份抓取策略的研究。他們的數據是史丹福大學網站中的18萬個頁面,使用不同的策略分別模仿抓取。排序的方法使用了廣度優先,後鏈計數,和部分pagerank算法。計算顯示,如果你想要優先下載pagerank高的頁面,那么,部分PageRank策略是比較好的,其次是廣度優先和後鏈計數。並且,這樣的結果僅僅是針對一個站點的。
Najork和Wiener (Najork and Wiener, 2001)採用實際的爬蟲,對3.28億個網頁,採用廣度優先研究。他們發現廣度優先會較早的抓到PageRank高的頁面(但是他們沒有採用其他策略進行研究)。作者給出的解釋是:“最重要的頁面會有很多的主機連線到他們,並且那些連結會較早的發現,而不用考慮從哪一個主機開始。”
Abiteboul (Abiteboul 等人, 2003),設計了一種基於OPIC(線上頁面重要指數)的抓取戰略。在OPIC中,每一個頁面都有一個相等的初始權值,並把這些權值平均分給它所指向的頁面。這種算法與Pagerank相似,但是他的速度很快,並且可以一次完成。OPIC的程式首先抓取獲取權值最大的頁面,實驗在10萬個冪指分布的模擬頁面中進行。並且,實驗沒有和其它策略進行比較,也沒有在真正的WEB頁面測試。
Boldi等人(Boldi et al., 2004)的模擬檢索實驗進行在 從.it網路上取下的4000萬個頁面和從webbase得到的1億個頁面上,測試廣度優先和深度優先,隨機序列和有序序列。比較的基礎是真實頁面pageRank值和計算出來的pageRank值的接近程度。令人驚奇的是,一些計算pageRank很快的頁面(特別明顯的是廣度優先策略和有序序列)僅僅可以達到很小的接近程度。
Baeza-Yates等人(Baeza-Yates et al., 2005) 在從.gr域名和.cl域名子網站上獲取的300萬個頁面上模擬實驗,比較若干個抓取策略。結果顯示OPIC策略和站點佇列長度,都比廣度優先要好;並且如果可行的話,使用之前的爬行抓取結果來指導這次抓取,總是十分有效的。
Daneshpajouh等人(Daneshpajouh et al., 2008)設計了一個用於尋找好種子的社區。它們從來自不同社區的高PageRank頁面開始檢索的方法,疊代次數明顯小於使用隨機種子的檢索。使用這種方式,可以從以前抓取頁面之中找到好的種子,使用這些種子是十分有效的。
1.1.1 限定訪問連結
一個爬蟲可能僅僅想找到html頁面的種子而避免其他的檔案類型。為了僅僅得到html的資源,一個爬蟲可以首先做一個http head的請求,以在使用request方法獲取所有的資源之前,決定這個網路檔案的類型。為了避免要傳送過多的head請求,爬蟲可以交替的檢查url並且僅僅對以html,htm和反斜槓結尾的檔案傳送資源請求。這種策略會導致很多的html資源在無意中錯過,一種相似的策略是將網路資源的擴展名同已知是html檔案類型的一組擴展名(如.html,.htm,.asp,.php,.aspx,反斜槓)進行比較。
一些爬蟲也會限制對任何含有“?”的資源(這些是動態生成的)進行獲取請求,以避免蜘蛛爬行在某一個站點中陷入下載無窮無盡的URL的困境。
1.1.2 路徑檢索
一些爬蟲會儘可能多的嘗試下載一個特定站點的資源。Cothey(Cothey,2004)引入了一種路徑檢索的爬蟲,它會嘗試抓取需要檢索資源的所有URL。例如,給定一個種子地址:http://llama.org/hamster/monkey/page.html,它將會嘗試檢索/hamster/menkey/,/hamster/和/ 。Cothey發現路徑檢索對發現獨立資源,或者一些通常爬蟲檢索不到的的連線是非常有效的。
一些路徑檢索的爬蟲也被稱為收割機軟體,因為他們通常用於收割或者收集所有的內容,可能是從特定的頁面或者主機收集相冊的照片。
1.1.3 聚焦抓取
爬蟲所抓取頁面的重要程度也可以表述成它與給定查詢之間相似程度的函式。網路爬蟲嘗試下載相似頁面,可以稱為聚焦檢索或者主題檢索。關於主題檢索和聚焦檢索的概念,最早是由Menczer(Menczer 1997; Menczer and Belew, 1998)和Chakrabarti等人首先提出來的(Chakrabarti et al., 1999)。
聚焦檢索的主要問題是網頁爬蟲的使用環境,我們希望在實際下載頁面之前,就可以知道給定頁面和查詢之間的相似度。一個可能的方法就是在連結之中設定錨點,這就是在早期時候,Pinkerton(Pinkerton,1994)曾經在一個爬蟲中採用的策略。Diligenti等人(Diligenti等人,2000)建議使用已經抓取頁面的內容去推測查詢和未訪問頁的相似度。一個聚焦查詢的表現的好壞主要依賴於查詢主題內容的豐富程度,通常還會依賴頁面查詢引擎提供的查詢起點。
1.1.4 抓取深層的網頁
很多的頁面隱藏的很深或隱藏在在看不到的網路之中。這些頁面通常只有在向資料庫提交查詢的時候才可以訪問到,如果沒有連結指向他們的話,一般的爬蟲是不能訪問到這些頁面的。谷歌站點地圖協定和mod OAI(Nelson等人,2005)嘗試允許發現這些深層次的資源。
深層頁面抓取器增加了抓取網頁的連結數。一些爬蟲僅僅抓取形如1.1.5 WEB3.0檢索
Web3.0為下一代搜尋技術定義了更先進的技術和新的準則,可以概括為語義網路和網站模板解析的概念。第三代檢索技術將建立在人機巧妙的聯繫的基礎上。
1.2重新訪問策略
網路具有動態性很強的特性。抓取網路上的一小部分內容可能會花費真的很長的時間,通常用周或者月來衡量。當爬蟲完成它的抓取的任務以後,很多操作是可能會發生的,這些操作包括新建,更新和刪除。
從搜尋引擎的角度來看,不檢測這些事件是有成本的,成本就是我們僅僅擁有一份過時的資源。最常使用的成本函式,是新鮮度和過時性(2000年,Cho 和Garcia-Molina)
新鮮度:這是一個衡量抓取內容是不是準確的二元值。在時間t內,倉庫中頁面p的新鮮度是這樣定義的:
新鮮度
過時性:這是一個衡量本地已抓取的內容過時程度的指標。在時間t時,倉庫中頁面p的時效性的定義如下:
過時性
在頁面抓取中,新鮮度和過時性的發展
Coffman等人(Edward G. Coffman,1998)是從事爬蟲對象定義的,他們提出了一個相當於新鮮度的概念,但是使用了不同的措詞:他們建議爬蟲必須最小化過時頁面部分。他們指出網路爬行的問題就相當於多個佇列,一個投票系統;這裡,爬蟲是伺服器,不同的站點是佇列。頁面修改是到達的顧客,頁面切換的時間是頁面進入一個單一站點的間隔。在這個模型下,每一個顧客在投票系統的平均時間,相當於爬蟲的平均過時性。
爬蟲的目標是儘可能高的提高頁面的新鮮度,同時降低頁面的過時性。這一目標並不是完全一樣的,第一種情況,爬蟲關心的是有多少頁面時過時的;在第二種情況,爬蟲關心的頁面過時了多少。
兩種最簡單的重新訪問策略是由Cho和Garcia-Molina研究的(Cho 和Garcia-Molina,2003):
統一策略:使用相同的頻率,重新訪問收藏中的所有的連結,而不考慮他們更新頻率。
正比策略:對變化越多的網頁,重新訪問的頻率也越高。網頁訪問的頻率和網頁變化的頻率直接相關。
(兩種情況下,爬蟲的重新抓取都可以採用隨機方式,或者固定的順序)
Cho和Garcia-Molina證明了一個出人意料的結果。以平均新鮮度方式衡量,統一策略在模擬頁面和真實的網路抓取中都比正比策略出色。對於這種結果的解釋是:當一個頁面變化太快的時候,爬蟲將會將會在不斷的嘗試重新抓取而浪費很多時間,但是卻還是不能保證頁面的新鮮度。
為了提高頁面的新鮮度,我們應該宣判變化太快的頁面死罪(Cho和Garcia-Molina, 2003a)。最佳的重新訪問策略既不是統一策略,也不是正比策略;保持平均頁面新鮮度高的最佳方法策略包括忽略那些變化太快的頁面,而保持頁面平均過時性低的方法則是對每一頁按照頁面變化率單調變化的策略訪問。兩種情況下,最佳的策略較正比策略,都更接近統一策略。正如Coffman等人(Edward G.Coffman,1998)所注意到的:“為了最小化頁面過時的時間,對任一個頁面的訪問都應該儘可能的均勻間隔地訪問。”對於重新訪問的詳盡的策略在大體上是不可以達到的,但是他們可以從數學上得到,因為他們依賴於頁面的變化。(Cho和Garcia-Molina,2003a)指出指數變化是描述頁面變化的好方法,同時(Ipeirotis等人,2005)指出了怎么使用統計工具去發現適合這些變化的參數。注意在這裡的重新訪問策略認為每一個頁面都是相同的(網路上所有的頁面價值都是一樣的)這不是現實的情況,所以,為了獲取更好的抓取策略,更多有關網頁質量的信息應該考慮進去。
1.3 平衡禮貌策略
爬蟲相比於人,可以有更快的檢索速度和更深的層次,所以,他們可能使一個站點癱瘓。不需要說一個單獨的爬蟲一秒鐘要執行多條請求,下載大的檔案。一個伺服器也會很難回響多執行緒爬蟲的請求。
就像Koster(Koster,1995)所注意的那樣,爬蟲的使用對很多工作都是很有用的,但是對一般的社區,也需要付出代價。使用爬蟲的代價包括:
 網路資源:在很長一段時間,爬蟲使用相當的頻寬高度並行地工作。
 伺服器超載:尤其是對給定伺服器的訪問過高時。
 質量糟糕的爬蟲,可能是伺服器或者路由器癱瘓,或者會嘗試下載自己無法處理的頁面。
 個人爬蟲,如果過多的人使用,可能是網路或者伺服器阻塞。
對這些問題的一個部分解決方法是漫遊器排除協定(Robots exclusion protocol),也被稱為robots.txt議定書(Koster,1996),這份協定對於管理員指明網路伺服器的那一部分不能到達是一個標準。這個標準沒有包括重新訪問一台伺服器的間隔的建議,雖然訪問間隔是避免伺服器超載的最有效的辦法。最近的商業搜尋軟體,如ASK JEEVES,MSN和Yahoo可以在robots.txt中使用一個額外的 “Crawl-delay”參數來指明請求之間的延遲。
對連線間隔時間的第一個建議由Koster 1993年給出,時間是60秒。按照這個速度,如果一個站點有超過10萬的頁面,即使我們擁有零延遲和無窮頻寬的完美連線,它也會需要兩個月的時間來下載整個站點,並且,這個伺服器中的資源,只有一小部分可以使用。這似乎是不可以接受的。
Cho(Cho和Garcia-Molina, 2003)使用10秒作為訪問的間隔時間,WIRE爬蟲(Baeza-Yates and Castillo, 2002)使用15秒作為默認間隔。MercatorWeb(Heydon 和Najork, 1999)爬蟲使用了一種自適應的平衡策略:如果從某一伺服器下載一個文檔需要t秒鐘,爬蟲就等待10t秒的時間,然後開始下一個頁面。Dill等人 (Dill et al., 2002) 使用1秒。
對於那些使用爬蟲用於研究目的的,一個更詳細的成本-效益分析是必要的,當決定去哪一個站點抓取,使用多快的速度抓取的時候,倫理的因素也需要考慮進來。
訪問記錄顯示已知爬蟲的訪問間隔從20秒鐘到3-4分鐘不等。需要注意的是即使很禮貌,採取了所有的安全措施來避免伺服器超載,還是會引來一些網路伺服器管理員的抱怨的。Brin和Page注意到:運行一個針對超過50萬伺服器的爬蟲,會產生很多的郵件和電話。這是因為有無數的人在上網,而這些人不知道爬蟲是什麼,因為這是他們第一次見到。(Brin和Page,1998)
1.4 並行策略
一個並行爬蟲是並行運行多個進程的爬蟲。它的目標是最大化下載的速度,同時儘量減少並行的開銷和下載重複的頁面。為了避免下載一個頁面兩次,爬蟲系統需要策略來處理爬蟲運行時新發現的URL,因為同一個URL地址,可能被不同的爬蟲進程抓到。

相關詞條

相關搜尋

熱門詞條

聯絡我們