1、. . . . I / 65摘要網絡爬蟲是一種自動搜集互聯網信息的程序。通過網絡爬蟲不僅能夠為搜索引擎采集網絡信息，而且可以作為定向信息采集器，定向采集某些下的特定信息，如招聘信息，租房信息等。本文通過 JAVA 實現了一個基于廣度優先算法的多線程爬蟲程序。本論文闡述了網絡爬蟲實現中一些主要問題：為何使用廣度優先的爬行策略，以與如何實現廣度優先爬行；為何要使用多線程，以與如何實現多線程；系統實現過程中的數據存儲；網頁信息解析等。通過實現這一爬蟲程序，可以搜集某一站點的 URLs，并將搜集到的 URLs 存入數據庫。 關鍵字網絡爬蟲；JAVA；廣度優先；多線程。. . . . ABSTRACTS

2、PIDER is a program which can auto collect informations from internet. SPIDER can collect data for search engines, also can be a Directional information collector, collects specifically informations from some web sites, such as HR informations, house rent informations.In this paper, use JAVA implemen

3、ts a breadth-first algorithm multi-thread SPDIER.This paper expatiates some major problems of SPIDER: why to use breadth-first crawling strategy, and how to implement breadth-first crawling; why to use multi-threading, and howto implement multi-thread; data structure; HTML code parse. etc.This SPIDE

4、R can collect URLs from one web site, and store URLs into database. KEY WORDSPIDER; JAVA; Breadth First Search; multi-threads. . . . III / 65目錄第一章引言第一章引言 1 1第二章相關技術介紹第二章相關技術介紹 2 22.1 JAVA 線程 22.1.1 線程概述 22.1.2 JAVA 線程模型 22.1.3 創建線程 32.1.4 JAVA 中的線程的生命周期 42.1.5 JAVA 線程的結束方式 42.1.6 多線程同步 52.2 URL 消重 5

5、2.2.1 URL 消重的意義 52.2.2 網絡爬蟲 URL 去重儲存庫設計 52.2.3 LRU 算法實現 URL 消重 72.3 URL 類訪問網絡 82.4爬行策略淺析 82.4.1 寬度或深度優先搜索策略 82.4.2 聚焦搜索策略 92.4.3 基于容評價的搜索策略 92.4.4 基于結構評價的搜索策略 102.4.5 基于鞏固學習的聚焦搜索 112.4.6 基于語境圖的聚焦搜索 11第三章系統需求分析與模塊設計第三章系統需求分析與模塊設計 13133.1 系統需求分析 133.2 SPIDER 體系結構 133.3 各主要功能模塊（類）設計 143.4 SPIDER 工作過程 1

6、4第四章系統分析與設計第四章系統分析與設計 16164.1 SPIDER 構造分析 164.2 爬行策略分析 174.3 URL 抽取，解析和保存 184.3.1 URL 抽取 184.3.2 URL 解析 194.3.3 URL 保存 19第五章系統實現第五章系統實現 21215.1 實現工具 215.2 爬蟲工作 215.3 URL 解析 225.4 URL 隊列管理 24. . . . 5.4.1 URL 消重處理 245.4.2 URL 等待隊列維護 265.4.3 數據庫設計 27第六章系統測試第六章系統測試 2929第七章結論第七章結論 3232參考文獻參考文獻 3333致致 34

7、34外文資料原文外文資料原文 3535譯文譯文 5151. . . . 1 / 65第一章 引言隨著互聯網的飛速發展，網絡上的信息呈爆炸式增長。這使得人們在網上找到所需的信息越來越困難，這種情況下搜索引擎應運而生。搜索引擎搜集互聯網上數以億計的網頁，并為每個詞建立索引。在建立搜索引擎的過程中，搜集網頁是非常重要的一個環節。爬蟲程序就是用來搜集網頁的程序。以何種策略偏歷互聯網上的網頁，也成了爬蟲程序主要的研究方向。現在比較流行的搜索引擎，比如 google，百度，它們爬蟲程序的技術幕一般都不公開。目前幾種比較常用的爬蟲實現策略：廣度優先的爬蟲程序，Repetitive 爬蟲程序，定義爬行爬蟲程序

8、，深層次爬行爬蟲程序。此外, 還有根據概率論進行可用 Web 頁的數量估算, 用于評估互聯網 Web 規模的抽樣爬蟲程序; 采用爬行深度、頁面導入量分析等方法, 限制從程序下載不相關的 Web 頁的選擇性爬行程序等等。爬蟲程序是一個自動獲取網頁的程序。它為搜索引擎從互聯網上下載網頁，是搜索引擎的重要組成部分。爬蟲程序的實現策略，運行效率直接影響搜索引擎的搜索結果。不同的搜索引擎，會根據對搜索結果的不同需求，選擇最合適的爬行策略來搜集互聯網上的信息。高效，優秀的爬蟲程序可以使人們在互聯網上尋找到更與時，更準確的信息。實現網絡爬蟲的重點和難點有：多線程的實現；對臨界資源的分配；遍歷 web圖的遍歷

9、策略選擇和實現；存儲數據結構的選擇和實現。本文通過 JAVA 語言實現一個基于廣度優先偏歷算法的多線程爬蟲程序。通過實現此爬蟲程序可以定點搜集某一站點的 URLs，如果需要搜集其他信息，可以在解析 URLs 的同時，解析獲取相應信息。. . . . 第二章 相關技術介紹2.1 JAVA 線程2.1.1 線程概述幾乎每種操作系統都支持線程的概念進程就是在某種程度上相互隔離的，獨立運行的程序。一般來說，這些操作系統都支持多進程操作。所謂多進程，就是讓系統（好像）同時運行多個程序。比如，我在 Microsoft Word 編寫本論文的時候，我還打開了一個 mp3 播放器來播放音樂，偶爾的，我還會再編

10、輯Word 的同時讓我的機器執行一個打印任務，而且我還喜歡通過 IE 從網上下載一個 Flash 動畫。對于我來說，這些操作都是同步進行的，我不需要等一首歌曲放完了再來編輯我的論文。看起來，它們都同時在我的機器上給我工作。事實的真相是，對于一個 CPU 而言，它在某一個時間點上，只能執行一個程序。CPU 不斷的在這些程序之間“跳躍”執行。那么，為什么我們看不出任何的中斷現象呢？這是因為，相對于我們的感覺，它的速度實在太快了。我們人的感知時間可能以秒來計算。而對于 CPU 而言，它的時間是以毫秒來計算的，從我們肉眼看來，它們就是一個連續的動作。因此，雖然我們看到的都是一些同步的操作，但實際上，對

11、于計算機而言，它在某個時間點上只能執行一個程序，除非你的計算機是多 CPU 的。多線程（Multi-Thread）擴展了多進程（multi-Process）操作的概念，將任務的劃分下降到了程序級別，使得各個程序似乎可以在同一個時間執行多個任務。每個任務稱為一個線程，能夠同時運行多個線程的程序稱為多線程程序。多線程和多進程有什么區別呢？對于進程來說，每個進程都有自己的一組完整的變量，而線程則共享一樣的數據。2.1.2 JAVA 線程模型我們知道，計算機程序得以執行的三個要素是：CPU，程序代碼，可存取的數據。在 JAVA 語言中，多線程的機制是通過虛擬 CPU 來實現的。可以形象的理解為,在一個

12、 JAVA 程序部虛擬了多臺計算機，每臺計算機對應一個線程，有自己的 CPU，可以獲取所需的代碼和數據，因此能獨立執行任務，相互間還可以共用代碼和數據。JAVA 的線程是通過 java.lang.Thread 類來實現的，它部實. . . . 3 / 65現了虛擬 CPU 的功能，能夠接收和處理傳遞給它的代碼和數據，并提供了獨立的運行控制功能。我們知道，每個 JAVA 應用程序都至少有一個線程，這就是所謂的主線程。它由 JVM 創建并調用 JAVA 應用程序的 main（）方法。JVM 還通常會創建一些其他的線程，不過，這些線程對我們而言通常都是不可見的。比如，用于自動垃圾收集的線程，對象終止

13、或者其他的 JVM 處理任務相關的線程。2.1.3 創建線程2.1.3.1 創建線程方式一在 JAVA 中創建線程的一種方式是通過 Thread 來實現的。Thread 有很多個構造器來創建一個線程（Thread）實例：Thread();創建一個線程。Thread(Runnable target);創建一個線程，并指定一個目標。Thread(Runnable target,String name);創建一個名為 name 的目標為target 的線程。Thread(String name);創建一個名為 name 的線程。Thread(ThreadGroup group,Runnable ta

14、rget);創建一個隸屬于 group 線程組，目標為 target 的線程。通常，我們可以將一個類繼承 Thread，然后，覆蓋 Thread 中的 run()方法，這樣讓這個類本身也就成了線程。每個線程都是通過某個特定 Thread 對象所對應的方法 run()來完成其操作的，方法 run()稱為線程體。使用 start()方法，線程進入 Runnable 狀態，它將線程調度器注冊這個線程。調用 start()方法并不一定馬上會執行這個線程，正如上面所說，它只是進入 Runnble 而不是 Running。2.1.3.2 創建線程方式二通過實現 Runnable 接口并實現接口中定義的唯一

15、方法 run()，可以創建一個線程。在使用 Runnable 接口時，不能直接創建所需類的對象并運行它，而是必須從 Thread 類的一個實例部運行它。. . . . 從上面兩種創建線程的方法可以看出，如果繼承 Thread 類，則這個類本身可以調用 start 方法，也就是說將這個繼承了 Thread 的類當作目標對象；而如果實現 Runnable 接口，則這個類必須被當作其他線程的目標對象。2.1.4 JAVA 中的線程的生命周期JAVA 的線程從產生到消失,可分為 5 種狀態：新建（New） ，可運行（Runnable） ，運行（Running） ，阻塞（Blocked）以與死亡（Dea

16、d） 。其中，Running 狀態并非屬于 JAVA 規中定義的線程狀態，也就是說，在 JAVA 規中，并沒有將運行（Running）狀態真正的設置為一個狀態，它屬于可運行狀態的一種。當使用 new 來新建一個線程時，它處于 New 狀態，這個時候，線程并未進行任何操作。然后，調用線程的 start()方法，來向線程調度程序（通常是 JVM 或操作系統）注冊一個線程，這個時候，這個線程一切就緒，就等待 CPU 時間了。線程調度程序根據調度策略來調度不同的線程，調用線程的 run 方法給已經注冊的各個線程以執行的機會，被調度執行的線程進入運行（Running）狀態。當線程的 run 方法運行完畢

17、，線程將被拋棄，進入死亡狀態。你不能調用restart 方法來重新開始一個處于死亡狀態的線程，但是，你可以調用處于死亡狀態的線程對象的各個方法。如果線程在運行（Running）狀態中因為 I/O 阻塞，等待鍵盤鍵入，調用了線程的 sleep 方法，調用了對象的 wait()方法等，則線程將進入阻塞狀態，直到這些阻塞原因被解除，如：IO 完成，鍵盤輸入了數據，調用 sleep 方法后的睡眠時間到以與其他線程調用了對象的 notify 或 notifyAll 方法來喚醒這個因為等待而阻塞的線程等，線程將返回到 Runnable 狀態重新等待調度程序調度，注意，被阻塞的線程不會直接返回到 Runni

18、ng 狀態，而是重新回到 Runnable 狀態等待線程調度程序的調用。線程調度程序會根據調度情況，將正在運行中的線程設置為 Runnable 狀態，例如，有一個比當前運行狀態線程更高運行等級的線程進入 Runnable 狀態，就可能將當前運行的線程從 Running 狀態“踢出”,讓它回到 Runnable 狀態。2.1.5 JAVA 線程的結束方式線程會以以下三種方式之一結束：線程到達其 run()方法的末尾；. . . . 5 / 65線程拋出一個未捕獲到的 Exception 或 Error；另一個線程調用一個 Deprecated 的 stop()方法。注意，因為這個方法會引起線程的

19、安全問題，已經被不推薦使用了，所以，不要再程序調用這個方法。2.1.6 多線程同步當同時運行的相互獨立的線程需要共享數據并且需要考慮其他線程的狀態時，就需要使用一套機制使得這些線程同步，避免在爭用資源時發生沖突，甚至發生死鎖。JAVA 提供了多種機制以實現線程同步。多數 JAVA 同步是以對象鎖定為中心的。JAVA 中從 Object 對象繼承來的每個對象都有一個單獨的鎖。由于 JAVA 中的每個對象都是從 Object 繼承來的。所以 JAVA 中的每個對象都有自己的鎖。這樣使它在共享的線程之間可以相互協調。在 JAVA 中實現線程同步的另一個方法是通過使用 synchronized 關鍵字

20、。JAVA 使用 synchronized 關鍵字來定義程序中要求線程同步的部分。synchronized 關鍵字實現的基本操作是把每個需要線程同步的部分定義為一個臨界區，在臨界區中同一時刻只有一個線程被執行。2.2 URL 消重2.2.1 URL 消重的意義在 SPIDER 系統實際運行的過程中，每秒下載的 10 個頁面中，分析的 URL 大多數是重復的，實際上新的 URL 才幾個。在持續下載的過程中，新的 URL 非常少，還是以新浪網舉例，1 天 24 小時中總共出現的新 URL 也就是 10000 左右。這種情況非常類似于操作系統中虛擬儲存器管理。所謂的虛擬儲存器，是指具有請求調入和置換

21、功能，能從邏輯上對存容量加以擴充的一種儲存器系統。其關鍵在于允許一個作業只裝入部分的頁或段就可以啟動運行，當作業運行的時候在存中找不到所需要的頁或段的時候，就會發生請求調入，而從外存中找到的頁或段將會置換存中暫時不運行的頁面到外存。URL 消重工作量是非常巨大的。以下在新浪新聞頁面為例，新浪一個新聞頁面大小為 5060k，每個頁面有 90100 個 URL，如果每秒下載 10 個頁面，就會產生 9001000 次的 URL 排重操作，每次排重操作都要在幾百萬至幾千萬的URL 庫中去查詢。這種操作對數據庫系統是一個災難，理論上任何需要產生磁盤 I/O 動作的存儲系統都無法滿足這種查詢的需求。2.

22、2.2 網絡爬蟲 URL 去重儲存庫設計. . . . 在爬蟲啟動工作的過程中，我們不希望同一個網頁被多次下載，因為重復下載不僅會浪費 CPU 機時，還會為搜索引擎系統增加負荷。而想要控制這種重復性下載問題，就要考慮下載所依據的超，只要能夠控制待下載的 URL 不重復，基本可以解決同一個網頁重復下載的問題。非常容易想到，在搜索引擎系統中建立一個全局的專門用來檢測，是否某一個URL 對應的網頁文件曾經被下載過的 URL 存儲庫，這就是方案。接著要考慮的就是如何能夠更加高效地讓爬蟲工作，確切地說，讓去重工作更加高效。如果實現去重，一定是建立一個 URL 存儲庫，并且已經下載完成的 URL 在進行檢

23、測時候，要加載到存中，在存中進行檢測一定會比直接從磁盤上讀取速度快很多。我們先從最簡單的情況說起，然后逐步優化，最終得到一個非常不錯的解決方案。2.2.2.1 基于磁盤的順序存儲這里，就是指把每個已經下載過的 URL 進行順序存儲。你可以把全部已經下載完成的 URL 存放到磁盤記事本文件中。每次有一個爬蟲線程得到一個任務 URL開始下載之前，通過到磁盤上的該文件中檢索，如果沒有出現過，則將這個新的 URL 寫入記事本的最后一行，否則就放棄該 URL 的下載。這種方式幾乎沒有人考慮使用了，但是這種檢查的思想是非常直觀的。試想，如果已經下載了 100 億網頁，那么對應著 100 億個，也就是這個檢

24、查 URL 是否重復的記事本文件就要存儲這 100 億 URL，況且，很多 URL 字符串的長度也不小，占用存儲空間不說，查找效率超級低下，這種方案肯定放棄。2.2.2.2 基于 Hash 算法的存儲對每一個給定的 URL，都是用一個已經建立好的 Hash 函數，映射到某個物理地址上。當需要進行檢測 URL 是否重復的時候，只需要將這個 URL 進行 Hash 映射，如果得到的地址已經存在，說明已經被下載過，放棄下載，否則，將該 URL 與其 Hash 地址作為鍵值對存放到 Hash 表中。這樣，URL 去重存儲庫就是要維護一個 Hash 表，如果 Hash 函數設計的不好，在進行映射的時候，

25、發生碰撞的幾率很大，則再進行碰撞的處理也非常復雜。而且，這里使用的是 URL 作為鍵，URL 字符串也占用了很大的存儲空間。2.2.2.3 基于 MD5 壓縮映射的存儲MD5 算法是一種加密算法，同時它也是基于 Hash 的算法。這樣就可以對 URL 字符串進行壓縮，得到一個壓縮字符串，同時可以直接得到一個 Hash 地址。另外，MD5 算法能夠將任何字符串壓縮為 128 位整數，并映射為物理地址，而且 MD5. . . . 7 / 65進行 Hash 映射碰撞的幾率非常小，這點非常好。從另一個方面來說，非常少的碰撞，對于搜索引擎的爬蟲是可以容忍的。況且，在爬蟲進行檢測的過程中，可以通過記錄日

26、志來保存在進行 MD5 時發生碰撞的 URL，通過單獨對該 URL 進行處理也是可行的。在 Java 中有一個 Map 類非常好，你可以將壓縮后的 URL 串作為 Key，而將Boolean 作為 Value 進行存儲，然后將工作中的 Map 在爬蟲停止工作后序列化到本地磁盤上；當下一次啟動新的爬蟲任務的時候，再將這個 Map 反序列化到存中，供爬蟲進行 URL 去重檢測。2.2.2.4 基于嵌入式 Berkeley DB 的存儲Berkeley DB 的特點就是只存儲鍵值對類型數據，這和 URL 去重有很大關系。去重，可以考慮對某個鍵，存在一個值，這個值就是那個鍵的狀態。使用了Berkele

27、y DB，你就不需要考慮進行磁盤 IO 操作的性能損失了，這個數據庫在設計的時候很好地考慮了這些問題，并且該數據庫支持高并發，支持記錄的順序存儲和隨機存儲，是一個不錯的選擇。URL 去重存儲庫使用 Berkeley DB，壓縮后的 URL 字符串作為 Key，或者直接使用壓縮后的 URL 字節數組作為 Key，對于 Value 可以使用 Boolean，一個字節，或者使用字節數組，實際 Value 只是一個狀態標識，減少 Value 存儲占用存儲空間。2.2.2.5 基于布隆過濾器（Bloom Filter）的存儲使用布隆過濾器，設計多個 Hash 函數，也就是對每個字符串進行映射是經過多個

28、Hash 函數進行映射，映射到一個二進制向量上，這種方式充分利用了比特位。不過，我沒有用過這種方式，有機會可以嘗試一下。可以參考 Google 的.googlechinablog./2007/07/bloom-filter.html。2.2.3 LRU 算法實現 URL 消重用雙向鏈表來實現大容量 cache 的 LRU 算法。原理是：cache 的所有位置都用雙向鏈表連接起來，當一個位置被命中后，就將通過調整鏈表的指向將該位置調整到鏈表的頭位置，新加入的容直接放在鏈表的頭上。這樣，在進行過多次查找操作后，最近被命中過的容就像鏈表的頭移動，而沒有命中過的容就向鏈表的后面移動。當需要替換時，鏈表

29、最后的位置就是最近最少被命中位置，我們只需要將新的容放在鏈表前面，淘汰鏈表最后的位置就實現了 LRU 算法。2.3 URL 類訪問網絡. . . . JAVA 提供了許多支 Internet 連接的類，URL 類就是其中之一。在使用 URL 類之前，必須創建一個 URL 對象，創建的方法是使用其構造函數，通過向其指定一個 URL 地址，就能實例化該類。如：URL url=newURL（） ；如果傳遞無效的 URL 給 URL 對象，該對象會拋出 MalformedURLException異常。當成功創建一個 URL 對象后，我們調用 openConnection 函數建立與 URL的通信，此時

30、，我們就獲得了一個 URLConnection 對象的引用，URLConnection類包含了許多與網絡上的 URL 通信的函數。在下載網頁前，我們需要判斷目標網頁是否存在，這時調用 URLConnection 類的 getHeaderField()方法，獲得服務器返回給 SPIDER 程序的響應碼，如果響應碼包含”20*”字樣，表示目標網頁存在，下一步就下載網頁，否則就不下載。getHeaderField()方法僅僅獲得服務器返回的頭標志，其通信開銷是最小的，因此在下載網頁前進行此測試，不僅能減小網絡流量，而且能提高程序效率。當目標網頁存在時 2 調用URLConnection 類 getI

31、nputStream()函數明確打開到 URL 的連接，獲取輸入流，再用 java.io 包中的 InputStreamReader 類讀取該輸入流，將網頁下載下來。2.4爬行策略淺析2.4.1 寬度或深度優先搜索策略搜索引擎所用的第一代網絡爬蟲主要是基于傳統的圖算法, 如寬度優先或深度優先算法來索引整個 Web, 一個核心的 U RL 集被用來作為一個種子集合, 這種算法遞歸的跟蹤超到其它頁面, 而通常不管頁面的容, 因為最終的目標是這種跟蹤能覆蓋整個 Web. 這種策略通常用在通用搜索引擎中,因為通用搜索引擎獲得的網頁越多越好, 沒有特定的要求.2.4.1.1寬度優先搜索算法寬度優先搜索算

32、法(又稱廣度優先搜索) 是最簡便的圖的搜索算法之一, 這一算法也是很多重要的圖的算法的原型. Dijkstra 單源最短路徑算法和 Prim 最小生成樹算法都采用了和寬度優先搜索類似的思想.寬度優先搜索算法是沿著樹的寬度遍歷樹的節點, 如果發現目標, 則算法中止. 該算法的設計和實現相對簡單, 屬于盲目搜索. 在目前為覆蓋盡可能多的網頁, 一般使用寬度優先搜索方法. 也有很多研究將寬度優先搜索策略應用于聚焦爬蟲中. 其基本思想是認為與初始 U RL 在一定距離的網頁具有主題相關性的概率很大. 另外一種方法是將寬度優先搜索與網頁過濾技術結合使用, 先用廣度優先策略抓取網頁, . . . . 9

33、/ 65再將其中無關的網頁過濾掉. 這些方法的缺點在于, 隨著抓取網頁的增多, 大量的無關網頁將被下載并過濾, 算法的效率將變低.2.4.1.2深度優先搜索深度優先搜索所遵循的搜索策略是盡可能“深”地搜索圖. 在深度優先搜索中, 對于最新發現的頂點, 如果它還有以此為起點而未探測到的邊, 就沿此邊繼續漢下去. 當結點 v 的所有邊都己被探尋過, 搜索將回溯到發現結點 v 有那條邊的始結點. 這一過程一直進行到已發現從源結點可達的所有結點為止. 如果還存在未被發現的結點, 則選擇其中一個作為源結點并重復以上過程, 整個進程反復進行直到所有結點都被發現為止. 深度優先在很多情況下會導致爬蟲的陷入(

34、 trapped) 問題, 所以它既不是完備的, 也不是最優的.2.4.2 聚焦搜索策略基于第一代網絡爬蟲的搜索引擎抓取的網頁一般少于 1 000 000 個網頁, 極少重新搜集網頁并去刷新索引. 而且其檢索速度非常慢, 一般都要等待 10 s甚至更長的時間. 隨著網頁頁信息的指數級增長與動態變化, 這些通用搜索引擎的局限性越來越大, 隨著科學技術的發展, 定向抓取相關網頁資源的聚焦爬蟲便應運而生.聚焦爬蟲的爬行策略只挑出某一個特定主題的頁面, 根據“最好優先原則”進行訪問, 快速、有效地獲得更多的與主題相關的頁面, 主要通過容和 Web 的結構來指導進一步的頁面抓取 2 . 聚焦爬蟲會給它所

35、下載下來的頁面分配一個評價分, 然后根據得分排序, 最后插入到一個隊列中. 最好的下一個搜索將通過對彈出隊列中的第一個頁面進行分析而執行, 這種策略保證爬蟲能優先跟蹤那些最有可能到目標頁面的頁面. 決定網絡爬蟲搜索策略的關鍵是如何評價價值, 即價值的計算方法, 不同的價值評價方法計算出的的價值不同, 表現出的的“重要程度”也不同, 從而決定了不同的搜索策略. 由于包含于頁面之中,而通常具有較高價值的頁面包含的也具有較高的價值, 因而對價值的評價有時也轉換為對頁面價值的評價. 這種策略通常運用在專業搜索引擎中, 因為這種搜索引擎只關心某一特定主題的頁面.2.4.3 基于容評價的搜索策略基于容評價

36、的搜索策略 3, 4 , 主要是根據主題(如關鍵詞、主題相關文檔) 與文本的相似度來評價價值的高低, 并以此決定其搜索策略: 文本是指周圍的說明文字和 U RL 上的文字信息, 相似度的評價通常采用以下公式:. . . . sim (d i, d j ) =mk= 1w ik w jk(mk= 1w 2ik ) (mk= 1w 2jk )其中, di 為新文本的特征向量, d j 為第 j 類的中心向量,m 為特征向量的維數,wk 為向量的第 K 維.由于 Web 頁面不同于傳統的文本, 它是一種半結構化的文檔, 包含許多結構信息 Web 頁面不是單獨存在的, 頁面中的指示了頁面之間的相互關系

37、, 因而有些學者提出了基于結構評價價值的方法.2.4.4 基于結構評價的搜索策略基于結構評價的搜索策略, 是通過對 Web 頁面之間相互引用關系的分析來確定的重要性, 進而決定訪問順序的方法. 通常認為有較多入鏈或出鏈的頁面具有較高的價值. PageRank 和 Hits 是其中具有代表性的算法.2.4.4.1PageRank 算法基于評價的搜索引擎的優秀代表是 Google (.Google.) ,它獨創的“評價體系”(PageRank 算法) 是基于這樣一種認識, 一個網頁的重要性取決于它被其它網頁的數量, 特別是一些已經被認定是“重要”的網頁的數量.PageRank 算法最初用于 Goo

38、gle 搜索引擎信息檢索中對查詢結果的排序過程 5 , 近年來被應用于網絡爬蟲對重要性的評價,PageRank 算法中, 頁面的價值通常用頁面的PageRank 值表示, 若設頁面p的 PageRank 值為 PR (p ), 則 PR (p )采用如下迭代公式計算:PR (p ) = C 1T+ (1 - C) Cin (p )PR (p )ou t (C) 其中T 為計算中的頁面總量, C 1 是阻尼常數因子, in (p )為所有指向p 的頁面的集合,out (C) 為頁面 C 出鏈的集合. 基于 PageRank 算法的網絡爬蟲在搜索過程中, 通過計算每個已訪問頁面的 PageRank

39、 值來確定頁面的價值, 并優先選擇 PageRank 值大的頁面中的進行訪問.2.4.4.2H ITS 算法HITS 方法定義了兩個重要概念: Authority 和 Hub. Authority 表示一個權威頁面被其它頁面引用的數量, 即該權威頁面的入度值. 網頁被引用的數量越大, 則該網頁的 Authority 值越大;Hub 表示一個 Web 頁面指向其它頁面的數量, 即該頁面的出度值. 網頁的出度值越大, 其 Hub 值越高. 由于 Hub 值高的頁面通常都提供了指向權威頁面的, 因而起到了隱含說明某主題頁面權威性的作用.HITS (Hyperlink- Induced Top ic

40、Search)算法是利用 HubAuthority 方法的搜索方法,Authority 表示一個頁面被其它頁面引用的數量, 即該頁面的入度值. Hub 表示一個 Web 頁面指向其它頁面的數量, 即該頁面的出度值. 算法如下: 將查詢. . . . 11 / 65q 提交給傳統的基于關鍵字匹配的搜索引擎. 搜索引擎返回很多網頁, 從中取前n 個網頁作為根集, 用 S 表示.通過向 S 中加入被 S 引用的網頁和引用 S 的網頁將 S 擴展成一個更大的集合 T.以 T 中的 Hub 網頁為頂點集 V l,以權威網頁為頂點集V 2,V1 中的網頁到V 2 中的網頁的超為邊集E , 形成一個二分有向

41、圖S G = (V 1,V 2, E ).對V 1 中的任一個頂點v ,用H (v )表示網頁v 的 Hub值, 對V 2 中的頂點u,用A (u) 表示網頁的 Authority 值. 開始時H (v ) = A (u) = 1, 對u 執行公式(1)來修改它的A (u) ,對v 執行公式(2)來修改它的H (v ) ,然后規化A (u) , H (v ) ,如此不斷的重復計算上述運算, 直到A (u) , H (v )收斂.A (u) = v: (v , u) EH (v ) (1)H (v ) = v: (v, u) EA (v ) (2)式(1) 反映了若一個網頁由很多好的 Hub 指

42、向, 則其權威值會相應增加(即權威值增加為所有指向它的網頁的現有 Hub 值之和). 式(2) 反映了若一個網頁指向許多好的權威頁, 則 Hub 值也會相應增加(即 Hub 值增加為該網頁的所有網頁的權威值之和).雖然基于結構價的搜索考慮了的結構和頁面之間的引用關系, 但忽略了頁面與主題的相關性, 在某些情況下, 會出現搜索偏離主題的問題. 另外, 搜索過程中需要重復計算 PageRank 值或 Authority 以與 Hub 權重, 計算復雜度隨頁面和數量的增長呈指數級增長 6 .2.4.5 基于鞏固學習的聚焦搜索近年來對 Web 信息資源分布的研究表明很多類型一樣的在構建方式上, 主題一

43、樣的網頁在組織方式上都存在著一定的相似性, 有的學者就考慮將鞏固學習引入網絡爬蟲的訓練過程中, 從這些相似性獲取一些“經驗”, 而這些經驗信息在搜索距相關頁面集較遠的地方往往能獲得較好的回報, 而前兩種策略在這種情況下容易迷失方向.在鞏固學習模型中, 把網絡爬蟲經過若干無關頁面的訪問之后才能獲得的主題相關頁面稱為未來回報, 對未來回報的預測值稱為未來回報價值, 用 Q 價值表示. 這種方法的核心就是學習如何計算的 Q 價值, 根據未來回報價值確定正確的搜索方向. 目前這類搜索策略不足之處在于學習效率低的問題, 而且在訓練過程中增加了用戶的負擔.2.4.6 基于語境圖的聚焦搜索基于鞏固學習的網絡

44、爬蟲通過計算的 Q 價值可以確定搜索方向, 但它卻無法估計距離目標頁面的遠近. 為此, Diligent 等提出了基于“語境圖”的搜索策略, 它通過構建典型頁面的 web“語境圖”來估計離目標頁面的距離, 距離較近. . . . 的頁面較早得到訪問 7 .基于“語境圖”的搜索策略需要借助已有的通用搜索引擎構建“語境圖”, 而搜索引擎的檢索結果并非一定代表真實的 web 結構, 因而這種方式也具有局限性. . . . 13 / 65第三章 系統需求分析與模塊設計3.1 系統需求分析SPIDER 要獲取的對象是存在于網絡上數以億計的網頁，這些網頁以超形式互相聯系在一起，每一網頁對應一個超，也稱統一

45、資源定位符（URL） 。我們可以把網絡看做一個圖 M(V,E)，網絡中的網頁構成節點集 V，他們之間的構成邊集 E，SPIDER 正是從某一節點開始，沿著邊，遍歷圖 M，每訪問到圖中一個節點 Vi，就進行一定的處理。為了達到上述目的，一個 SPIDER 必須被設計成多線程的，A 個線程并發地在網絡上協同工作，才有可能在盡可能短的時間遍歷完網絡中的網頁。但網頁數目是如此之大，如果任 SPIDER 程序無窮地搜索下去，那么程序幾乎不能終止。所以我們限制 SPIDER 每次工作只訪問一個站點。一個再大型的站點，其中的網頁數目也是有限的，因此 SPIDER 程序能在有限的時間結束。當 SPIDER 程

46、序訪問到一個網頁，必須進行以下幾項基本處理：抽取網頁中包含的文本；抽取網頁中包含的 URL，并將其區分為 URL 或外 URL。3.2 SPIDER 體系結構此爬蟲程序主要分為三個部分：任務執行端，任務調度端，數據服務端。每一個 SPIDER 任務執行端關聯一個站點,一個線程下載一個基于 URL 的頁面, 并進行 Web 頁面解析, 得到站 URL 和發現新站點 URL 另外,將 URL 隊列持久化到數據庫, 因此在 SPIDER 任務執行端以外 Down 掉后, 能夠斷點續傳.SPIDER 客戶端線程間的協調通信采用 Java 的線程同步技術 synchronized,在數據服務端中對 UR

47、L 進行緩存提高了系統處理速度. SPIDER 的任務執行和任務調度端都需要維持一個 URL 隊列: 任務執行端的 URL 隊列中存儲了站 URL; 任務調度端則是站點的 URL.在這些 URL 隊列上有大量的操作, 包括 URL 查找、 URL 插入、URL 狀態更新等. 如果 SPIDER 以 300 頁 秒的速度下載 Web 頁面, 平均將會產生 2000 多個 URL 12 ,因此簡單的采用存數據結構存儲這些 URL 隊列有一定的問題, 系統沒有足夠的存空間;而采用直接持久化到數據庫, 則需要大量的數據庫連接、查詢等操作, 系統效率會明顯下降. 如果采用 URL 壓縮的辦法,盡管在一定

48、程度上可以平衡空間和時間的矛盾, 但仍然不適用于大規模數據采集的 SPIDER. . . . 圖 3.2 SPIDER 體系結3.3 各主要功能模塊（類）設計SPIDERWorker 類：該類繼承自線程類，請求任務 URL，根據得到的 URL 下載相應的 HTML 代碼，利用 HTML 代碼調用其他模塊完成相關處理。SPIDERManager 類：該類用于控制 SPIDERWorker 線程。UrlQueueManager 類：該類用于維護 URL 等待隊列，分配任務 URL，URL 消重模塊。UrlParse 類：用于解析 HTML，獲取并過濾 URL。DateBaseConnect 類：用

49、于提供數據庫連接。3.4 SPIDER 工作過程將給定的初始 URL 加入到 URL 等待隊列。創建爬蟲線程，啟動爬蟲線程每個爬蟲線程從 URL 等待隊列中取得任務 URL。然后根據 URL 下載網頁，然. . . . 15 / 65后解析網頁，獲取超 URLs。如果獲取到的 URL 為相對地址，需要轉換為絕對地址，然后淘汰站外 URLs，錯誤 URLs 或者不能解析的 URL 地址。再判斷這些 URL是否已經被下載到，如果沒有則加入到 URL 等待隊列。繼續執行步驟，直到結束條件停止。將初始 URLs 加入到等待隊列是否為非法 URL創建啟動爬蟲線程從 URL 等待隊列獲取任務URL下載 U

50、RL 對應的 HTML 代碼將相對地址轉換為絕對地址解析 HTML，獲取 URLs將 URLs 加入到URL 等待隊列是否為絕對地址是否為重復 URL. . . . 第四章 系統分析與設計4.1 SPIDER 構造分析構造 SPIDER 程序有兩種方式：（1）把 SPIDER 程序設計為遞歸的程序；（2）編寫一個非遞歸的程序，它要維護一個要訪問的網頁列表。考慮使用哪一種方式的前提是，構造的 SPIDER 程序必須能夠訪問非常大的 Web 站點。本系統中使用了非遞歸的程序設計方法。這是因為，當一個遞歸程序運行時要把每次遞歸壓入堆棧，但在本系統設計中使用的是多線程，它允許一次運行多個任務，但是，多

51、線程與遞歸是不兼容的。因為在這一過程中每一個線程都有自己的堆棧，而當一個方法調用它自身時，它們需要使用同一個堆棧。這就意味著遞歸的 SPIDER 程序不能使用多線程。每個 SPIDER 線程都會獨立的去完成獲取 URLs 的任務，并將獲取到的 URLs加入一個公共的 URL 等待隊列中。圖 4.1圖 4.1 表示了該系統爬蟲線程的實現策略。假設線程 1 從 URL 隊列中獲取一條任務 URL 1，然后它會下載對應的 HTML，解析出里面包含 URLs，然后再將. . . . 17 / 65這些 URLs 加入到 URL 隊列中去。然后線程 1 會再從 URL 隊列中獲取新的 URL，下載 HT

52、ML 代碼，并解析出 URLs，再加入到 URL 隊列中去。而線程 2 同時也會下載它獲取到的 URL 2 對應的 HTML 代碼，解析出 URLs 加入到等待隊列中。以此類推，多個線程并發地去完成爬蟲工作。4.2 爬行策略分析圖 4.2.1因為本論文實現的爬蟲程序的初衷是盡可能遍歷某一站點所有的頁面。廣度優先算法的實行理論是覆蓋更多的節點，所以此爬蟲程序選擇了廣度優先算法。實現的策略是：先獲取初始 URL 對應 HTML 代碼里所有的 URLs。然后依次獲取這些 URLs 對應的 HTML 里的 URLs，當這一層所有的 URLs 都下載解析完后，在獲取下一層的信息。通過這種循環的獲取方式實

53、現廣度優先爬行。如圖 4.2.1，假如 a 代表初始 URL，bcd 為以 a 獲取的 3 個 URLs，efg 為以b 獲取的 URLs，以此類推。那么這些 URLs 獲取的順序就是 abcdefghijklmnop這樣一個順序。當獲取到 b 的 URLs 之后，并不會馬上去解析這些 URLs，而是先解析同 b 在同一層中的 cd 對應的 URLs。當這一層 URLs 全部解析完后，再開始下一層 URLs。廣度優先算法的等待隊列設計如圖 4.2.2 所示。. . . . 圖 4.2.2圖 4.2.2 列舉了不同時間段時，URL 等待隊列的存儲狀態。第一個方框是將初始 URL：a 加入到等待隊

54、列。第二個方框為，解析 a 對應 HTML 獲取URLs：bcd，同時刪除 a。第三個方框為，解析 b 對應 HTML 獲取 URLs：efg，同時刪除 URL：b。第四個方框為，解析 e 對應 HTML 獲取 URLs：nop，并刪除 e。通過這樣的存儲方法實現如圖 4.2.1 的廣度爬行算法。4.3 URL 抽取，解析和保存4.3.1 URL 抽取通過觀察研究 HTML 代碼，我們可以知道。HTML 代碼中，頁面之間的跳轉，關聯是通過 href 標簽來實現的。我們需要獲取 HTML 代碼中的 URLs，就可以通過尋找 href 標簽來達到目的。我猜200905315-31火影忍者331，頁

55、面上 303 既是. . . . 19 / 65通過觀察得知，一般 href 標簽是以 href=這樣的形式出現的。但是不同的href=后面的容有所不同。比如 href=”url”這樣情況，我們就可以通過截取雙引號之間的容來獲取 URL；如果是 href=url這種情況，我們就需要截取單引號之間的容來獲取 URL；或者有些是 href=url，我們需要以等號為開始標記，而這種情況通常結尾是空格或者符號。通過這種方法，我們獲取網頁部分的 URLs。但是有些 URLs 是通過提交表單，或者通過 javascript 來跳轉的。這些情況就需要更細致的考慮，才能獲取。4.3.2 URL 解析截取出來的

56、字符串，可能為相對地址或者絕對地址。所以需要判斷 URL 為絕對地址，還是相對地址。相對地址需要先轉化為絕對地址，再進行過濾。因為解析出來的 URL 地址可能是一些文件的地址，或者為 javascript 文件或者css 文件。這些格式的 URL 是無法獲取 HTML 代碼的，也就不可能進行 URL 解析。所以我們需要過濾掉這些 URLs。然后再進行 URL 消重處理，最后加入到 URL 等待隊列。為了把爬行限制在同一站點需要截斷指向站外的,保證 SPIDER 總在站執行,即準確地根據超鏈 URL 判斷超鏈是否指向站外.由 RFC 對 URL 的定義可知,URL 的格式為protocol:/h

57、ost:port/path?query,一般情況下,同一所有頁面對應 URL的 host 是一樣的,所以可以使用 host 匹配作為判斷超鏈是否指向站外的標準. 進一步研究發現,很多大型中一個分類目錄對應一個主機, 所以前面的判斷標準必須改進.研究 host 的組成可知, host 的格式一般為站分類.站點標志串.站點類型各異的串.站點類型串只有 |edu|gov|net|國家域名幾種類型,所以我們取站點類型各異串前面的串,即站點標志串作匹配,超鏈 URL 的 host 中是否包含此串,為超鏈是否站的判斷標準.4.3.3 URL 保存因為等待 URLs 的數目非常多，如果全部采用 List 來

58、存儲非常的占用存空間。所以將等待 URLs 存入數據庫中，并設計 2 個緩存區，用于向隊列中加入和取得 URLs。URL 等待隊列設計成三段式：第一段為一個 List,用來加入新得到的 URL。當這個 List 中的數目過多時，則將 List 中的容加入到數據庫，并清空該 List，以便加入新的 URLs；第二段為數據庫，當第一段數據過多時，將第一段的數據存入數據庫；第三段也為一個 List，從這里面分配任務 URL，當該ListURL 不足時，將數據庫里的數據再轉存入。圖 4.3.3 表示了 URL 等待隊列的結構。. . . . 圖 4.3.3. . . . 21 / 65第五章 系統實現

59、5.1 實現工具操作系統是 winXP;JAVA 程序的編寫工具是 eclipse-SDK-3.2.1-win32；數據庫是 MYSQL 5 5.0.51a。5.2 爬蟲工作這個類繼承自線程類，實現線程在 java 中有兩種方法：一種是直接繼承Thread 類；一種是實現 Runnable 接口。我采用了第二種方法：public class SpiderWorker implements Runnable 在這個類中必須要實現重寫 run()這個方法。我在這個方法里定義了一個循環，這個線程會重復地執行爬蟲動作。在這個循環里，首先會向 URL 等待隊列里請求一個 URL。因為 URL 隊列會出現

60、為空或者被其他線程占用的情況。所以我在這里寫了一個循環：s = nullnull;whilewhile (s = nullnull) s = urlQueueManager.getWaitQueue();如果沒有得到 URL 就繼續向 URL 等待隊列申請。當得到任務 URL 以后，會通過這個 URL 得到對應的 HTML 代碼。具體方法是調用 getHtml(String sourse_url)這個方法： URLConnection connection = nullnull;InputStreamReader in = nullnull;BufferedReader br = nullnu