網絡爬蟲
目錄
1 概述
  引言
  隨着網絡的迅速發展,萬維網成為大量信息的載體,如何有效地提取並利用這些信息成為一個巨大的挑戰。搜索引擎(Search Engine),例如傳統的通用搜索引擎AltaVista,Yahoo!和Google等,作為一個輔助人們檢索信息的工具成為用戶訪問萬維網的入口和指南。但是,這些通用性搜索引擎也存在着一定的局限性,如:
  (1) 不同領域、不同背景的用戶往往具有不同的檢索目的和需求,通用搜索引擎所返回的結果包含大量用戶不關心的網頁。
  (2) 通用搜索引擎的目標是盡可能大的網絡覆蓋率,有限的搜索引擎服務器資源與無限的網絡數據資源之間的矛盾將進一步加深。
  (3) 萬維網數據形式的豐富和網絡技術的不斷發展,圖片、數據庫、音頻/視頻多媒體等不同數據大量出現,通用搜索引擎往往對這些信息含量密集且具有一定結構的數據無能為力,不能很好地發現和獲取。
  (4) 通用搜索引擎大多提供基於關鍵字的檢索,難以支持根據語義信息提出的查詢。
  為瞭解决上述問題,定嚮抓取相關網頁資源的聚焦爬蟲應運而生。聚焦爬蟲是一個自動下載網頁的程序,它根據既定的抓取目標,有選擇的訪問萬維網上的網頁與相關的鏈接,獲取所需要的信息。與通用爬蟲(generalpurpose web crawler)不同,聚焦爬蟲並不追求大的覆蓋,而將目標定為抓取與某一特定主題內容相關的網頁,為面嚮主題的用戶查詢準備數據資源。
  1 聚焦爬蟲工作原理及關鍵技術概述
  網絡爬蟲是一個自動提取網頁的程序,它為搜索引擎從萬維網上下載網頁,是搜索引擎的重要組成。傳統爬蟲從一個或若幹初始網頁的URL開始,獲得初始網頁上的URL,在抓取網頁的過程中,不斷從當前頁面上抽取新的URL放入隊列,直到滿足係統的一定停止條件,如圖1(a)流程圖所示。聚焦爬蟲的工作流程較為復雜,需要根據一定的網頁分析算法過濾與主題無關的鏈接,保留有用的鏈接並將其放入等待抓取的URL隊列。然後,它將根據一定的搜索策略從隊列中選擇下一步要抓取的網頁URL,並重複上述過程,直到達到係統的某一條件時停止,如圖1(b)所示。另外,所有被爬蟲抓取的網頁將會被係統存貯,進行一定的分析、過濾,並建立索引,以便之後的查詢和檢索;對於聚焦爬蟲來說,這一過程所得到的分析結果還可能對以後的抓取過程給出反饋和指導。
  相對於通用網絡爬蟲,聚焦爬蟲還需要解决三個主要問題:
  (1) 對抓取目標的描述或定義;
  (2) 對網頁或數據的分析與過濾;
  (3) 對URL的搜索策略。
  抓取目標的描述和定義是决定網頁分析算法與URL搜索策略如何製訂的基礎。而網頁分析算法和候選URL排序算法是决定搜索引擎所提供的服務形式和爬蟲網頁抓取行為的關鍵所在。這兩個部分的算法又是緊密相關的。
  2 抓取目標描述
  現有聚焦爬蟲對抓取目標的描述可分為基於目標網頁特徵、基於目標數據模式和基於領域概念3種。
  基於目標網頁特徵的爬蟲所抓取、存儲並索引的對象一般為網站或網頁。根據種子樣本獲取方式可分為:
  (1) 預先給定的初始抓取種子樣本;
  (2) 預先給定的網頁分類目錄和與分類目錄對應的種子樣本,如Yahoo!分類結構等;
  (3) 通過用戶行為確定的抓取目標樣例,分為:
  a) 用戶瀏覽過程中顯示標註的抓取樣本;
  b) 通過用戶日志挖掘得到訪問模式及相關樣本。
  其中,網頁特徵可以是網頁的內容特徵,也可以是網頁的鏈接結構特徵,等等。
  現有的聚焦爬蟲對抓取目標的描述或定義可以分為基於目標網頁特徵,基於目標數據模式和基於領域概念三種。
  基於目標網頁特徵的爬蟲所抓取、存儲並索引的對象一般為網站或網頁。具體的方法根據種子樣本的獲取方式可以分為:(1)預先給定的初始抓取種子樣本;(2)預先給定的網頁分類目錄和與分類目錄對應的種子樣本,如Yahoo!分類結構等;(3)通過用戶行為確定的抓取目標樣例。其中,網頁特徵可以是網頁的內容特徵,也可以是網頁的鏈接結構特徵,等等。
  作者: 齊保元 2006-1-10 10:11
2 爬蟲技術研究綜述
  基於目標數據模式的爬蟲針對的是網頁上的數據,所抓取的數據一般要符合一定的模式,或者可以轉化或映射為目標數據模式。
  另一種描述方式是建立目標領域的本體或詞典,用於從語義角度分析不同特徵在某一主題中的重要程度。
3 網頁搜索策略
  網頁的抓取策略可以分為深度優先、廣度優先和最佳優先三種。深度優先在很多情況下會導致爬蟲的陷入(trapped)問題,目前常見的是廣度優先和最佳優先方法。
  3.1 廣度優先搜索策略
  廣度優先搜索策略是指在抓取過程中,在完成當前層次的搜索後,纔進行下一層次的搜索。該算法的設計和實現相對簡單。在目前為覆蓋盡可能多的網頁,一般使用廣度優先搜索方法。也有很多研究將廣度優先搜索策略應用於聚焦爬蟲中。其基本思想是認為與初始URL在一定鏈接距離內的網頁具有主題相關性的概率很大。另外一種方法是將廣度優先搜索與網頁過濾技術結合使用,先用廣度優先策略抓取網頁,再將其中無關的網頁過濾掉。這些方法的缺點在於,隨着抓取網頁的增多,大量的無關網頁將被下載並過濾,算法的效率將變低。
  3.2 最佳優先搜索策略
  最佳優先搜索策略按照一定的網頁分析算法,預測候選URL與目標網頁的相似度,或與主題的相關性,並選取評價最好的一個或幾個URL進行抓取。它衹訪問經過網頁分析算法預測為“有用”的網頁。存在的一個問題是,在爬蟲抓取路徑上的很多相關網頁可能被忽略,因為最佳優先策略是一種局部最優搜索算法。因此需要將最佳優先結合具體的應用進行改進,以跳出局部最優點。將在第4節中結合網頁分析算法作具體的討論。研究表明,這樣的閉環調整可以將無關網頁數量降低30%~90%。
4 網頁分析算法
  
  網頁分析算法可以歸納為基於網絡拓撲、基於網頁內容和基於用戶訪問行為三種類型。
  4.1 基於網絡拓撲的分析算法
  基於網頁之間的鏈接,通過已知的網頁或數據,來對與其有直接或間接鏈接關係的對象(可以是網頁或網站等)作出評價的算法。又分為網頁粒度、網站粒度和網頁塊粒度這三種。
  4.1.1 網頁(Webpage)粒度的分析算法
  PageRank和HITS算法是最常見的鏈接分析算法,兩者都是通過對網頁間鏈接度的遞歸和規範化計算,得到每個網頁的重要度評價。PageRank算法雖然考慮了用戶訪問行為的隨機性和Sink網頁的存在,但忽略了絶大多數用戶訪問時帶有目的性,即網頁和鏈接與查詢主題的相關性。針對這個問題,HITS算法提出了兩個關鍵的概念:權威型網頁(authority)和中心型網頁(hub)。
  基於鏈接的抓取的問題是相關頁面主題團之間的隧道現象,即很多在抓取路徑上偏離主題的網頁也指嚮目標網頁,局部評價策略中斷了在當前路徑上的抓取行為。文獻提出了一種基於反嚮鏈接(BackLink)的分層式上下文模型(Context Model),用於描述指嚮目標網頁一定物理跳數半徑內的網頁拓撲圖的中心Layer0為目標網頁,將網頁依據指嚮目標網頁的物理跳數進行層次劃分,從外層網頁指嚮內層網頁的鏈接稱為反嚮鏈接。
  4.1.2 網站粒度的分析算法
  網站粒度的資源發現和管理策略也比網頁粒度的更簡單有效。網站粒度的爬蟲抓取的關鍵之處在於站點的劃分和站點等級(SiteRank)的計算。SiteRank的計算方法與PageRank類似,但是需要對網站之間的鏈接作一定程度抽象,並在一定的模型下計算鏈接的權重。
  網站劃分情況分為按域名劃分和按IP地址劃分兩種。文獻討論了在分佈式情況下,通過對同一個域名下不同主機、服務器的IP地址進行站點劃分,構造站點圖,利用類似PageRank的方法評價SiteRank。同時,根據不同文件在各個站點上的分佈情況,構造文檔圖,結合SiteRank分佈式計算得到DocRank。文獻證明,利用分佈式的SiteRank計算,不僅大大降低了單機站點的算法代價,而且剋服了單獨站點對整個網絡覆蓋率有限的缺點。附帶的一個優點是,常見PageRank 造假難以對SiteRank進行欺騙。
  4.1.3 網頁塊粒度的分析算法
  在一個頁面中,往往含有多個指嚮其他頁面的鏈接,這些鏈接中衹有一部分是指嚮主題相關網頁的,或根據網頁的鏈接錨文本表明其具有較高重要性。但是,在PageRank和HITS算法中,沒有對這些鏈接作區分,因此常常給網頁分析帶來廣告等噪聲鏈接的幹擾。在網頁塊級別(Blocklevel)進行鏈接分析的算法的基本思想是通過VIPS網頁分割算法將網頁分為不同的網頁塊(page block),然後對這些網頁塊建立pagetoblock和blocktopage的鏈接矩陣,分別記為Z和X。於是,在pagetopage圖上的網頁塊級別的PageRank為Wp=X×Z;在blocktoblock圖上的BlockRank為Wb=Z×X。已經有人實現了塊級別的PageRank和HITS算法,並通過實驗證明,效率和準確率都比傳統的對應算法要好。
  4.2 基於網頁內容的網頁分析算法
  基於網頁內容的分析算法指的是利用網頁內容(文本、數據等資源)特徵進行的網頁評價。網頁的內容從原來的以超文本為主,發展到後來動態頁面(或稱為Hidden Web)數據為主,後者的數據量約為直接可見頁面數據(PIW,Publicly Indexable Web)的400~500倍。另一方面,多媒體數據、Web Service等各種網絡資源形式也日益豐富。因此,基於網頁內容的分析算法也從原來的較為單純的文本檢索方法,發展為涵蓋網頁數據抽取、機器學習、數據挖掘、語義理解等多種方法的綜合應用。本節根據網頁數據形式的不同,將基於網頁內容的分析算法,歸納以下三類:第一種針對以文本和超鏈接為主的無結構或結構很簡單的網頁;第二種針對從結構化的數據源(如RDBMS)動態生成的頁面,其數據不能直接批量訪問;第三種針對的數據界於第一和第二類數據之間,具有較好的結構,顯示遵循一定模式或風格,且可以直接訪問。
  4.2.1 基於文本的網頁分析算法
  1) 純文本分類與聚類算法 
  很大程度上藉用了文本檢索的技術。文本分析算法可以快速有效的對網頁進行分類和聚類,但是由於忽略了網頁間和網頁內部的結構信息,很少單獨使用。
  2) 超文本分類和聚類算法
5 補充
  網絡爬蟲(又被稱為網頁蜘蛛,網絡機器人,在FOAF社區中間,更經常的稱為網頁追逐者),是一種按照一定的規則,自動的抓取萬維網信息的程序或者腳本。另外一些不常使用的名字還有螞蟻,自動索引,模擬程序或者蠕蟲。
  這些處理被稱為網絡抓取或者蜘蛛爬行。很多站點,尤其是搜索引擎,都使用爬蟲提供最新的數據,它主要用於提供它訪問過頁面的一個副本,然後,搜索引擎就可以對得到的頁面進行索引,以提供快速的訪問。蜘蛛也可以在web上用來自動執行一些任務,例如檢查鏈接,確認html代碼;也可以用來抓取網頁上某種特定類型信息,例如抓取電子郵件地址(通常用於垃圾郵件)。
  一個網絡蜘蛛就是一種機器人,或者軟件代理。大體上,它從一組要訪問的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)嘗試允許發現這些深層次的資源。
  深層頁面抓取器增加了抓取網頁的鏈接數。一些爬蟲僅僅抓取形如<a href=”url”鏈接。某些情況下,例如Googlebot,WEB抓取的是所有超文本所包含的內容,標簽和文本。
  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地址,可能被不同的爬蟲進程抓到。
  參考文獻
   Edwards, J., McCurley, K. S., and Tomlin, J. A. (2001). "An adaptive model for optimizing performance of an incremental web crawler". In Proceedings of the Tenth Conference on World Wide Web (Hong Kong: Elsevier Science): 106–113. doi:10.1145/371920.371960.
   Lawrence, Steve; C. Lee Giles (1999). "Accessibility of information on the web". Nature 400 (6740): 107. doi:10.1038/21987.
   Junghoo Cho. Hector Garcia-Molina. Lawrence Page (1998). Efficient Crawling Through URL Ordering. Computer Networks 30(1-7): 161-172
   Najork, M. and Wiener, J. L. (2001). Breadth-first crawling yields high-quality pages. In Proceedings of the 10th international Conference on World Wide Web (Hong Kong, May 01 - 05, 2001). WWW '01. ACM Press, 114-118.
   Serge Abiteboul, Mihai Preda, Gregory Cobena (2003). Adaptive on-line page importance computation.International World Wide Web Conference archive. Proceedings of the 12th international conference on World Wide Web. ACM Press, 280-290.
   Boldi, Paolo; Massimo Santini, Sebastiano Vigna (2004). "Do Your Worst to Make the Best: Paradoxical Effects in PageRank Incremental Computations". Algorithms and Models for the Web-Graph. pp. 168–180.
   Ricardo Baeza-Yates, Carlos Castillo, Mauricio Marin, Andrea Rodriguez (2005). Crawling a country: better strategies than breadth-first for web page ordering. International World Wide Web Conference archive Special interest tracks and posters of the 14th international conference on World Wide Web table of contents ( Chiba, Japan). ACM Press, 864 - 872.
   Sh. Daneshpajouh, Mojtaba Mohammadi Nasiri, M. Ghodsi (2008). A Fast Community Based Algorithm for Generating Crawler Seeds Set, In Proceeding of 4th International Conference on Web Information Systems and Technologies (WEBIST-2008), Funchal, Portugal, May 2008.
   Viv Cothey. Web-crawling reliability (2004). Journal of the American Society for Information Science and Technology, 55(14), pp 1228-1238.
   Menczer, F. (1997). ARACHNID: Adaptive Retrieval Agents Choosing Heuristic Neighborhoods for Information Discovery. In D. Fisher, ed., Machine Learning: Proceedings of the 14th International Conference (ICML97). Morgan Kaufmann
   Menczer, F. and Belew, R.K. (1998). Adaptive Information Agents in Distributed Textual Environments. In K. Sycara and M. Wooldridge (eds.) Proc. 2nd Intl. Conf. on Autonomous Agents (Agents '98). ACM Press
   Chakrabarti, S., van den Berg, M., and Dom, B. (1999). Focused crawling: a new approach to topic-specific web resource discovery. Computer Networks, 31(11–16):1623–1640.
   Pinkerton, B. (1994). Finding what people want: Experiences with the WebCrawler. In Proceedings of the First World Wide Web Conference, Geneva, Switzerland
   M. Diligenti, F.M. Coetzee, S. Lawrence, C.L. Giles, M. Gori (2000). Focused Crawling Using Context Graphs. 26th International Conference on Very Large Databases, VLDB 2000.
   Nelson, Michael L; Herbert Van de Sompel, Xiaoming Liu, Terry L Harrison, Nathan McFarland (2005). "mod_oai: An Apache Module for Metadata Harvesting". Cs/0503069.
   Junghoo Cho. Hector Garcia-Molina (2000). Synchronizing a database to improve freshness. ACM SIGMOD Record archive. Volume 29 , Issue 2 (June 2000) table of contents. Pages: 117 - 128.
   Jr, E. G. Coffman; Zhen Liu, Richard R. Weber (1998). "Optimal robot scheduling for Web search engines". Journal of Scheduling 1 (1): 15–29.
   Junghoo Cho. Hector Garcia-Molina (2003). Effective page refresh policies for Web crawlers. ACM Transactions on Database Systems (TODS). Pages: 390 - 426.
   Cho, Junghoo; Hector Garcia-Molina (2003). "Estimating frequency of change". ACM Trans. Interet Technol. 3 (3): 256–290.
   Ipeirotis, P., Ntoulas, A., Cho, J., Gravano, L. (2005) Modeling and managing content changes in text databases. In Proceedings of the 21st IEEE International Conference on Data Engineering, pages 606-617, April 2005, Tokyo.
   M. Koster (1995). Robots in the web:threat or treat? OII Spectrum, 1995, vol. 2, no9, pp. 8-18.
   M. Koster (1996). The Web Robots Page. Available at http://info.webcrawler.com/mak/projects/robots/robots.html.
   Koster, M. (1993). Guidelines for robots writers.
   Baeza-Yates, R. and Castillo, C. (2002). Balancing volume, quality and freshness in Web crawling. In Soft Computing Systems – Design, Management and Applications, pages 565–572, Santiago, Chile. IOS Press Amsterdam.
   Heydon, Allan; Najork, Marc (1999) . Mercator: A Scalable, Extensible Web Crawler. http://www.cindoc.csic.es/cybermetrics/pdf/68.pdf.
   Dill, S., Kumar, R., Mccurley, K. S., Rajagopalan, S., Sivakumar, D., and Tomkins, A. (2002). Self-similarity in the web. ACM Trans. Inter. Tech., 2(3):205–223.
  2. 網絡爬蟲體係結構
  網頁爬蟲的高層體係結構
  一個爬蟲不能像上面所說的,僅僅衹有一個好的抓取策略,還需要有一個高度優化的結構。
  Shkapenyuk和Suel(Shkapenyuk和Suel,2002)指出:設計一個短時間內,一秒下載幾個頁面的頗慢的爬蟲是一件很容易的事情,而要設計一個使用幾周可以下載百萬級頁面的高性能的爬蟲,將會在係統設計,I/O和網絡效率,健壯性和易用性方面遇到衆多挑戰。
  網路爬蟲是搜索引擎的核心,他們算法和結構上的細節被當作商業機密。當爬蟲的設計發佈時,總會有一些為了阻止別人復製工作而缺失的細節。人們也開始關註主要用於阻止主要搜索引擎發佈他們的排序算法的“搜索引擎垃圾郵件”。
  2.1 URL一般化
  爬蟲通常會執行幾種類型的URL規範化來避免重複抓取某些資源。URL一般化也被稱為URL標準化,指的是修正URL並且使其前後一致的過程。這裏有幾種一般化方法,包括轉化URL為小寫的,去除逗號(如‘.’ ‘..’等),對非空的路徑,在末尾加反斜杠。
  3. 爬蟲身份識別
  網絡爬蟲通過使用http請求的用戶代理字段來嚮網絡服務器表明他們的身份。網絡管理員則通過檢查網絡服務器的日志,使用用戶代理字段來辨認哪一個爬蟲曾經訪問過以及它訪問的頻率。用戶代理字段可能會包含一個可以讓管理員獲取爬蟲更多信息的URL。郵件抓取器和其他懷有惡意的網絡爬蟲通常不會留任何的用戶代理字段內容,或者他們也會將他們的身份偽裝成瀏覽器或者其他的知名爬蟲。
  對於網路爬蟲,留下用戶標志信息是十分重要的;這樣,網絡管理員在需要的時候就可以聯繫爬蟲的主人。有時,爬蟲可能會陷入爬蟲陷阱或者是一個服務器超負荷,這時,爬蟲主人需要使爬蟲停止。對那些有興趣瞭解特定爬蟲訪問時間網絡管理員來講,用戶標識信息是十分重要的。
  4.用戶爬蟲的例子
  以下是一係列已經發佈的一般用途的網絡爬蟲(除了主題檢索的爬蟲)的體係結構,包括了對不同組件命名和突出特點的簡短的描述。
   RBSE (Eichmann,1994)是第一個發佈的爬蟲。它有兩個基礎程序。第一個是“spider”,抓取隊列中的內容到一個關係數據庫中,第二個程序是“mite”,是一個修改後的www的ASCII瀏覽器,負責從網絡上下載頁面。
   WebCrawler(Pinkerton,1994)是第一個公開可用的 用來建立全文索引的一個子程序,他使用庫www來下載頁面;另外一個程序使用廣度優先來解析獲取URL並對其排序;它還包括一個根據選定文本和查詢相似程度爬行的實時爬蟲。
   World Wide Web Worm (McBryan, 1994)是一個用來為文件建立包括標題和URL簡單索引的爬蟲。索引可以通過grep式的Unix命令來搜索。
   Google Crawler (Brin and Page, 1998)用了一些細節來描述,但是這些細節僅僅是關於使用C++和Python編寫的、一個早期版本的體係結構。因為文本解析就是 文檢索和URL抽取的過程,所以爬蟲集成了索引處理。這裏擁有一個URL服務器,用來給幾個爬蟲程序發送要抓取的URL列表。在文本解析的時候,新發現的URL傳送給URL服務器並檢測這個URL是不是已經存在,如果不存在的話,該URL就加入到URL服務器中。
   CobWeb (da Silva et al., 1999)使用了一個中央“調度者”和一係列的“分佈式的搜集者”。搜集者解析下載的頁面並把找到的URL發送給調度者,然後調度者反過來分配給搜集者。調度者使用深度優先策略,並且使用平衡禮貌策略來避免服務器超載。爬蟲是使用Perl語言編寫的。
   Mercator (Heydon and Najork, 1999; Najork and Heydon, 2001)是一個分佈式的,模塊化的使用java編寫的網絡爬蟲。它的模塊化源自於使用可互換的的“協議模塊”和“處理模塊”。協議模塊負責怎樣獲取網頁(例如使用HTTP),處理模塊負責怎樣處理頁面。標準處理模塊僅僅包括瞭解析頁面和抽取URL,其他處理模塊可以用來檢索文本頁面,或者搜集網絡數據。
   WebFountain (Edwards et al., 2001)是一個與Mercator類似的分佈式的模塊化的爬蟲,但是使用C++編寫的。它的特點是一個管理員機器控製一係列的螞蟻機器。經過多次下載頁面後,頁面的變化率可以推測出來,這時,一個非綫性的方法必須用於求解方程以獲得一個最大的新鮮度的訪問策略。作者推薦在早期檢索階段使用這個爬蟲,然後用統一策略檢索,就是所有的頁面都使用相同的頻率訪問。
   PolyBot [Shkapenyuk and Suel, 2002]是一個使用C++和Python編寫的分佈式網絡爬蟲。它由一個爬蟲管理者,一個或多個下載者,一個或多個DNS解析者組成。抽取到的URL被添加到硬盤的一個隊列裏面,然後使用批處理的模式處理這些URL。平衡禮貌方面考慮到了第二、三級網域(例如www.example.com 和 www2.example.com 都是三級網域),因為第三級網域通常也會保存在同一個網絡服務器上。
   WebRACE (Zeinalipour-Yazti and Dikaiakos, 2002)是一個使用java實現的,擁有檢索模塊和緩存模塊的爬蟲,它是一個很通用的稱作eRACE的係統的一部分。係統從用戶得到下載頁面的請求,爬蟲的行為有點像一個聰明的代理服務器。係統還監視訂閱網頁的請求,當網頁發生改變的時候,它必須使爬蟲下載更新這個頁面並且通知訂閱者。WebRACE最大的特色是,當大多數的爬蟲都從一組URL開始的時候,WebRACE可以連續地的接收抓取開始的URL地址。
   Ubicrawer (Boldi et al., 2004)是一個使用java編寫的分佈式爬蟲。它沒有中央程序。它有一組完全相同的代理組成,分配功能通過主機前後一致的散列計算進行。這裏沒有重複的頁面,除非爬蟲崩潰了(然後,另外一個代理就會接替崩潰的代理重新開始抓取)。爬蟲設計為高伸縮性和允許失敗的。
   FAST Crawler (Risvik and Michelsen, 2002) 是一個分佈式的爬蟲,在Fast Search&Transfer中使用,關於其體係結構的一個大致的描述可以在[citation needed]找到。
   Labrador,一個工作在開源項目Terrier Search Engine上的非開源的爬蟲。
   TeezirCrawler是一個非開源的可伸縮的網頁抓取器,在Teezir上使用。該程序被設計為一個完整的可以處理各種類型網頁的爬蟲,包括各種JavaScript和HTML文檔。爬蟲既支持主題檢索也支持非主題檢索。
   Spinn3r, 一個通過博客構建Tailrank.com反饋信息的爬蟲。 Spinn3r是基於java的,它的大部分的體係結構都是開源的。
   HotCrawler,一個使用c語言和php編寫的爬蟲。
   ViREL Microformats Crawler,搜索公衆信息作為嵌入到網頁的一小部分。
  除了上面列出的幾個特定的爬蟲結構以外,還有Cho (Cho and Garcia-Molina, 2002)和Chakrabarti (Chakrabarti, 2003)發佈的一般的爬蟲體係結構。
  4.1 開源爬蟲
   DataparkSearch是一個在GNU GPL許可下發佈的爬蟲搜索引擎。
   GNU Wget是一個在GPL許可下,使用C語言編寫的命令行式的爬蟲。它主要用於網絡服務器和FTP服務器的鏡像。
   Heritrix是一個互聯網檔案館級的爬蟲,設計的目標為對大型網絡的大部分內容的定期存檔快照,是使用java編寫的。
   Ht://Dig在它和索引引擎中包括了一個網頁爬蟲。
   HTTrack用網絡爬蟲創建網絡站點鏡像,以便離綫觀看。它使用C語言編寫,在GPL許可下發行。
   ICDL Crawler是一個用C++編寫,跨平臺的網絡爬蟲。它僅僅使用空閑的CPU資源,在ICDL標準上抓取整個站點。
   JSpider是一個在GPL許可下發行的,高度可配置的,可定製的網絡爬蟲引擎。
   LLarbin由Sebastien Ailleret開發;
   Webtools4larbin由Andreas Beder開發;
   Methabot是一個使用C語言編寫的高速優化的,使用命令行方式運行的,在2-clause BSD許可下發佈的網頁檢索器。它的主要的特性是高可配置性,模塊化;它檢索的目標可以是本地文件係統,HTTP或者FTP。
   Nutch是一個使用java編寫,在Apache許可下發行的爬蟲。它可以用來連接Lucene的全文檢索套件;
   Pavuk是一個在GPL許可下發行的,使用命令行的WEB站點鏡像工具,可以選擇使用X11的圖形界面。與wget和httprack相比,他有一係列先進的特性,如以正則表達式為基礎的文件過濾規則和文件創建規則。
   WebVac是斯坦福WebBase項目使用的一個爬蟲。
   WebSPHINX(Miller and Bharat, 1998)是一個由java類庫構成的,基於文本的搜索引擎。它使用多綫程進行網頁檢索,html解析,擁有一個圖形用戶界面用來設置開始的種子URL和抽取下載的數據;
   WIRE-網絡信息檢索環境(Baeza-Yates 和 Castillo, 2002)是一個使用C++編寫,在GPL許可下發行的爬蟲,內置了幾種頁面下載安排的策略,還有一個生成報告和統計資料的模塊,所以,它主要用於網絡特徵的描述;
   LWP:RobotUA(Langheinrich,2004)是一個在Perl5許可下發行的,可以優異的完成並行任務的 Perl類庫構成的機器人。
   Web Crawler是一個為.net準備的開放源代碼的網絡檢索器(C#編寫)。
   Sherlock Holmes收集和檢索本地和網絡上的文本類數據(文本文件,網頁),該項目由捷剋門戶網站中樞(Czech web portal Centrum)贊助並且主用商用於這裏;它同時也使用在Onet.pl。
   YaCy是一個基於P2P網絡的免費的分佈式搜索引擎(在GPL許可下發行);
   Ruya是一個在廣度優先方面表現優秀,基於等級抓取的開放源代碼的網絡爬蟲。在英語和日語頁面的抓取表現良好,它在GPL許可下發行,並且完全使用Python編寫。按照robots.txt有一個延時的單網域延時爬蟲。
   Universal Information Crawler快速發展的網絡爬蟲,用於檢索存儲和分析數據;
   Agent Kernel,當一個爬蟲抓取時,用來進行安排,並發和存儲的java框架。
   Arachnod.net是一個使用C#編寫,需要SQL Server 2005支持的,在GPL許可下發行的多功能的開源的機器人。它可以用來下載,檢索,存儲包括電子郵件地址,文件,超鏈接,圖片和網頁在內的各種數據。
   Dine是一個多綫程的java的http客戶端。它可以在LGPL許可下進行二次開發。
相關詞
spider爬蟲程序sqllucenenetweb爬蟲
包含詞
網絡爬蟲程序