網(wǎng)絡(luò)爬蟲的設(shè)計與實(shí)現(xiàn) 畢業(yè)論文

1、摘要 摘要 網(wǎng)絡(luò)爬蟲是一種自動搜集互聯(lián)網(wǎng)信息的程序。通過網(wǎng)絡(luò)爬蟲不僅能夠?yàn)樗?索引擎采集網(wǎng)絡(luò)信息，而且可以作為定向信息采集器，定向采集某些網(wǎng)站下的 特定信息，如招聘信息，租房信息等。 本文通過 JAVA 實(shí)現(xiàn)了一個基于廣度優(yōu)先算法的多線程爬蟲程序。本論文 闡述了網(wǎng)絡(luò)爬蟲實(shí)現(xiàn)中一些主要問題：為何使用廣度優(yōu)先的爬行策略，以及如 何實(shí)現(xiàn)廣度優(yōu)先爬行；為何要使用多線程，以及如何實(shí)現(xiàn)多線程；系統(tǒng)實(shí)現(xiàn)過 程中的數(shù)據(jù)存儲；網(wǎng)頁信息解析等。 通過實(shí)現(xiàn)這一爬蟲程序，可以搜集某一站點(diǎn)的 URLs，并將搜集到的 URLs 存入數(shù)據(jù)庫。 【關(guān)鍵字】網(wǎng)絡(luò)爬蟲；JAVA；廣度優(yōu)先；多線程。 ABSTRACT II ABS

2、TRACT SPIDER 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

3、implements 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 how to implement multi-thread; data structure; HTML code parse. etc

4、. This SPIDER can collect URLs from one web site, and store URLs into database. 【KEY WORD】SPIDER; JAVA; Breadth First Search; multi-threads. 目錄 第一章第一章 引言引言.1 1 第二章第二章 相關(guān)技術(shù)介紹相關(guān)技術(shù)介紹.2 2 2.1 JAVA 線程.2 2.1.1 線程概述 .2 2.1.2 JAVA 線程模型.2 2.1.3 創(chuàng)建線程 .3 2.1.4 JAVA 中的線程的生命周期.4 2.1.5 JAVA 線程的結(jié)束方式.4 2.1.6 多線程同步

5、.5 2.2 URL 消重.5 2.2.1 URL 消重的意義.5 2.2.2 網(wǎng)絡(luò)爬蟲 URL 去重儲存庫設(shè)計 .5 2.2.3 LRU 算法實(shí)現(xiàn) URL 消重.7 2.3 URL 類訪問網(wǎng)絡(luò).8 2.4 爬行策略淺析 .8 2.4.1 寬度或深度優(yōu)先搜索策略.8 2.4.2 聚焦搜索策略 .9 2.4.3 基于內(nèi)容評價的搜索策略.9 2.4.4 基于鏈接結(jié)構(gòu)評價的搜索策略 .10 2.4.5 基于鞏固學(xué)習(xí)的聚焦搜索 .11 2.4.6 基于語境圖的聚焦搜索 .11 第三章第三章 系統(tǒng)需求分析及模塊設(shè)計系統(tǒng)需求分析及模塊設(shè)計.1313 3.1 系統(tǒng)需求分析 .13 3.2 SPIDER 體系

6、結(jié)構(gòu).13 3.3 各主要功能模塊（類）設(shè)計 .14 3.4 SPIDER 工作過程.14 第四章第四章 系統(tǒng)分析與設(shè)計系統(tǒng)分析與設(shè)計.1616 4.1 SPIDER 構(gòu)造分析.16 4.2 爬行策略分析 .17 4.3 URL 抽取，解析和保存.18 4.3.1 URL 抽取.18 4.3.2 URL 解析.19 4.3.3 URL 保存.19 第五章第五章 系統(tǒng)實(shí)現(xiàn)系統(tǒng)實(shí)現(xiàn).2121 5.1 實(shí)現(xiàn)工具 .21 5.2 爬蟲工作 .21 5.3 URL 解析.22 5.4 URL 隊(duì)列管理.24 5.4.1 URL 消重處理.24 5.4.2 URL 等待隊(duì)列維護(hù).26 5.4.3 數(shù)據(jù)庫設(shè)

7、計 .27 第六章第六章 系統(tǒng)測試系統(tǒng)測試.2929 第七章第七章 結(jié)論結(jié)論.3232 參考文獻(xiàn)參考文獻(xiàn).3333 致謝致謝.3434 外文資料原文外文資料原文.3535 譯文譯文.5151 第一章 引言 1 第一章 引言 隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)上的信息呈爆炸式增長。這使得人們在網(wǎng)上 找到所需的信息越來越困難，這種情況下搜索引擎應(yīng)運(yùn)而生。搜索引擎搜集互 聯(lián)網(wǎng)上數(shù)以億計的網(wǎng)頁，并為每個詞建立索引。在建立搜索引擎的過程中，搜 集網(wǎng)頁是非常重要的一個環(huán)節(jié)。爬蟲程序就是用來搜集網(wǎng)頁的程序。以何種策 略偏歷互聯(lián)網(wǎng)上的網(wǎng)頁，也成了爬蟲程序主要的研究方向?，F(xiàn)在比較流行的搜 索引擎，比如 google，百

8、度，它們爬蟲程序的技術(shù)內(nèi)幕一般都不公開。目前幾 種比較常用的爬蟲實(shí)現(xiàn)策略：廣度優(yōu)先的爬蟲程序，Repetitive 爬蟲程序，定義 爬行爬蟲程序，深層次爬行爬蟲程序。此外, 還有根據(jù)概率論進(jìn)行可用 Web 頁 的數(shù)量估算, 用于評估互聯(lián)網(wǎng) Web 規(guī)模的抽樣爬蟲程序; 采用爬行深度、頁面 導(dǎo)入鏈接量分析等方法, 限制從程序下載不相關(guān)的 Web 頁的選擇性爬行程序等 等。 爬蟲程序是一個自動獲取網(wǎng)頁的程序。它為搜索引擎從互聯(lián)網(wǎng)上下載網(wǎng)頁， 是搜索引擎的重要組成部分。爬蟲程序的實(shí)現(xiàn)策略，運(yùn)行效率直接影響搜索引 擎的搜索結(jié)果。不同的搜索引擎，會根據(jù)對搜索結(jié)果的不同需求，選擇最合適 的爬行策略來搜集互

9、聯(lián)網(wǎng)上的信息。高效，優(yōu)秀的爬蟲程序可以使人們在互聯(lián) 網(wǎng)上尋找到更及時，更準(zhǔn)確的信息。 實(shí)現(xiàn)網(wǎng)絡(luò)爬蟲的重點(diǎn)和難點(diǎn)有：多線程的實(shí)現(xiàn)；對臨界資源的分配；遍歷 web 圖的遍歷策略選擇和實(shí)現(xiàn)；存儲數(shù)據(jù)結(jié)構(gòu)的選擇和實(shí)現(xiàn)。 本文通過 JAVA 語言實(shí)現(xiàn)一個基于廣度優(yōu)先偏歷算法的多線程爬蟲程序。 通過實(shí)現(xiàn)此爬蟲程序可以定點(diǎn)搜集某一站點(diǎn)的 URLs，如果需要搜集其他信息， 可以在解析 URLs 的同時，解析獲取相應(yīng)信息。 電子科技大學(xué)成都學(xué)院本科畢業(yè)設(shè)計論文 2 第二章 相關(guān)技術(shù)介紹 2.1 JAVA 線程 2.1.1 線程概述 幾乎每種操作系統(tǒng)都支持線程的概念進(jìn)程就是在某種程度上相互隔離的， 獨(dú)立運(yùn)行的程序

10、。一般來說，這些操作系統(tǒng)都支持多進(jìn)程操作。所謂多進(jìn)程， 就是讓系統(tǒng)（好像）同時運(yùn)行多個程序。比如，我在 Microsoft Word 編寫本論 文的時候，我還打開了一個 mp3 播放器來播放音樂，偶爾的，我還會再編輯 Word 的同時讓我的機(jī)器執(zhí)行一個打印任務(wù)，而且我還喜歡通過 IE 從網(wǎng)上下載 一個 Flash 動畫。對于我來說，這些操作都是同步進(jìn)行的，我不需要等一首歌 曲放完了再來編輯我的論文?？雌饋恚鼈兌纪瑫r在我的機(jī)器上給我工作。 事實(shí)的真相是，對于一個 CPU 而言，它在某一個時間點(diǎn)上，只能執(zhí)行一個 程序。CPU 不斷的在這些程序之間“跳躍”執(zhí)行。那么，為什么我們看不出任 何的中斷現(xiàn)

11、象呢？這是因?yàn)椋鄬τ谖覀兊母杏X，它的速度實(shí)在太快了。我們 人的感知時間可能以秒來計算。而對于 CPU 而言，它的時間是以毫秒來計算的， 從我們?nèi)庋劭磥?，它們就是一個連續(xù)的動作。 因此，雖然我們看到的都是一些同步的操作，但實(shí)際上，對于計算機(jī)而言， 它在某個時間點(diǎn)上只能執(zhí)行一個程序，除非你的計算機(jī)是多 CPU 的。 多線程（Multi-Thread）擴(kuò)展了多進(jìn)程（multi-Process）操作的概念，將任 務(wù)的劃分下降到了程序級別，使得各個程序似乎可以在同一個時間內(nèi)執(zhí)行多個 任務(wù)。每個任務(wù)稱為一個線程，能夠同時運(yùn)行多個線程的程序稱為多線程程序。 多線程和多進(jìn)程有什么區(qū)別呢？對于進(jìn)程來說，每個進(jìn)

12、程都有自己的一組 完整的變量，而線程則共享相同的數(shù)據(jù)。 2.1.2 JAVA 線程模型 我們知道，計算機(jī)程序得以執(zhí)行的三個要素是：CPU，程序代碼，可存取 的數(shù)據(jù)。在 JAVA 語言中，多線程的機(jī)制是通過虛擬 CPU 來實(shí)現(xiàn)的。可以形象 的理解為,在一個 JAVA 程序內(nèi)部虛擬了多臺計算機(jī)，每臺計算機(jī)對應(yīng)一個線程， 有自己的 CPU，可以獲取所需的代碼和數(shù)據(jù)，因此能獨(dú)立執(zhí)行任務(wù)，相互間還 可以共用代碼和數(shù)據(jù)。JAVA 的線程是通過 java.lang.Thread 類來實(shí)現(xiàn)的，它內(nèi) 第二章 相關(guān)技術(shù)介紹 3 部實(shí)現(xiàn)了虛擬 CPU 的功能，能夠接收和處理傳遞給它的代碼和數(shù)據(jù)，并提供了 獨(dú)立的運(yùn)行

13、控制功能。 我們知道，每個 JAVA 應(yīng)用程序都至少有一個線程，這就是所謂的主線程。 它由 JVM 創(chuàng)建并調(diào)用 JAVA 應(yīng)用程序的 main（）方法。 JVM 還通常會創(chuàng)建一些其他的線程，不過，這些線程對我們而言通常都是 不可見的。比如，用于自動垃圾收集的線程，對象終止或者其他的 JVM 處理任 務(wù)相關(guān)的線程。 2.1.3 創(chuàng)建線程 創(chuàng)建線程方式一 在 JAVA 中創(chuàng)建線程的一種方式是通過 Thread 來實(shí)現(xiàn)的。Thread 有很多個 構(gòu)造器來創(chuàng)建一個線程（Thread）實(shí)例： Thread();創(chuàng)建一個線程。 Thread(Runnable target);創(chuàng)建一個線程，

14、并指定一個目標(biāo)。 Thread(Runnable target,String name);創(chuàng)建一個名為 name 的目標(biāo)為 target 的線 程。 Thread(String name);創(chuàng)建一個名為 name 的線程。 Thread(ThreadGroup group,Runnable target);創(chuàng)建一個隸屬于 group 線程組， 目標(biāo)為 target 的線程。 通常，我們可以將一個類繼承 Thread，然后，覆蓋 Thread 中的 run()方法， 這樣讓這個類本身也就成了線程。 每個線程都是通過某個特定 Thread 對象所對應(yīng)的方法 run()來完成其操作的， 方法 run

15、()稱為線程體。 使用 start()方法，線程進(jìn)入 Runnable 狀態(tài)，它將線程調(diào)度器注冊這個線程。 調(diào)用 start()方法并不一定馬上會執(zhí)行這個線程，正如上面所說，它只是進(jìn)入 Runnble 而不是 Running。 創(chuàng)建線程方式二 通過實(shí)現(xiàn) Runnable 接口并實(shí)現(xiàn)接口中定義的唯一方法 run()，可以創(chuàng)建一個 線程。在使用 Runnable 接口時，不能直接創(chuàng)建所需類的對象并運(yùn)行它，而是必 須從 Thread 類的一個實(shí)例內(nèi)部運(yùn)行它。 電子科技大學(xué)成都學(xué)院本科畢業(yè)設(shè)計論文 4 從上面兩種創(chuàng)建線程的方法可以看出，如果繼承 Thread 類，則這個類本身 可以調(diào)用

16、 start 方法，也就是說將這個繼承了 Thread 的類當(dāng)作目標(biāo)對象；而如果 實(shí)現(xiàn) Runnable 接口，則這個類必須被當(dāng)作其他線程的目標(biāo)對象。 2.1.4 JAVA 中的線程的生命周期 JAVA 的線程從產(chǎn)生到消失,可分為 5 種狀態(tài)：新建（New），可運(yùn)行 （Runnable），運(yùn)行（Running），阻塞（Blocked）以及死亡（Dead）。其中， Running 狀態(tài)并非屬于 JAVA 規(guī)范中定義的線程狀態(tài)，也就是說，在 JAVA 規(guī) 范中，并沒有將運(yùn)行（Running）狀態(tài)真正的設(shè)置為一個狀態(tài)，它屬于可運(yùn)行狀 態(tài)的一種。 當(dāng)使用 new 來新建一個線程時，它處于 New 狀態(tài)

17、，這個時候，線程并未進(jìn) 行任何操作。 然后，調(diào)用線程的 start()方法，來向線程調(diào)度程序（通常是 JVM 或操作系 統(tǒng)）注冊一個線程，這個時候，這個線程一切就緒，就等待 CPU 時間了。 線程調(diào)度程序根據(jù)調(diào)度策略來調(diào)度不同的線程，調(diào)用線程的 run 方法給已經(jīng) 注冊的各個線程以執(zhí)行的機(jī)會，被調(diào)度執(zhí)行的線程進(jìn)入運(yùn)行（Running）狀態(tài)。 當(dāng)線程的 run 方法運(yùn)行完畢，線程將被拋棄，進(jìn)入死亡狀態(tài)。你不能調(diào)用 restart 方法來重新開始一個處于死亡狀態(tài)的線程，但是，你可以調(diào)用處于死亡狀態(tài)的 線程對象的各個方法。 如果線程在運(yùn)行（Running）狀態(tài)中因?yàn)?I/O 阻塞，等待鍵盤鍵入，調(diào)用

18、了 線程的 sleep 方法，調(diào)用了對象的 wait()方法等，則線程將進(jìn)入阻塞狀態(tài)，直到 這些阻塞原因被解除，如：IO 完成，鍵盤輸入了數(shù)據(jù)，調(diào)用 sleep 方法后的睡 眠時間到以及其他線程調(diào)用了對象的 notify 或 notifyAll 方法來喚醒這個因?yàn)榈?待而阻塞的線程等，線程將返回到 Runnable 狀態(tài)重新等待調(diào)度程序調(diào)度，注意， 被阻塞的線程不會直接返回到 Running 狀態(tài)，而是重新回到 Runnable 狀態(tài)等待 線程調(diào)度程序的調(diào)用。 線程調(diào)度程序會根據(jù)調(diào)度情況，將正在運(yùn)行中的線程設(shè)置為 Runnable 狀態(tài)， 例如，有一個比當(dāng)前運(yùn)行狀態(tài)線程更高運(yùn)行等級的線程進(jìn)入

19、Runnable 狀態(tài)，就 可能將當(dāng)前運(yùn)行的線程從 Running 狀態(tài)“踢出”,讓它回到 Runnable 狀態(tài)。 2.1.5 JAVA 線程的結(jié)束方式 線程會以以下三種方式之一結(jié)束： 線程到達(dá)其 run()方法的末尾； 第二章 相關(guān)技術(shù)介紹 5 線程拋出一個未捕獲到的 Exception 或 Error； 另一個線程調(diào)用一個 Deprecated 的 stop()方法。注意，因?yàn)檫@個方法會引起 線程的安全問題，已經(jīng)被不推薦使用了，所以，不要再程序調(diào)用這個方法。 2.1.6 多線程同步 當(dāng)同時運(yùn)行的相互獨(dú)立的線程需要共享數(shù)據(jù)并且需要考慮其他線程的狀態(tài) 時，就需要使用一套機(jī)制使得這些線程同步，

20、避免在爭用資源時發(fā)生沖突，甚 至發(fā)生死鎖。JAVA 提供了多種機(jī)制以實(shí)現(xiàn)線程同步。多數(shù) JAVA 同步是以對 象鎖定為中心的。JAVA 中從 Object 對象繼承來的每個對象都有一個單獨(dú)的鎖。 由于 JAVA 中的每個對象都是從 Object 繼承來的。所以 JAVA 中的每個對象都 有自己的鎖。這樣使它在共享的線程之間可以相互協(xié)調(diào)。在 JAVA 中實(shí)現(xiàn)線程 同步的另一個方法是通過使用 synchronized 關(guān)鍵字。JAVA 使用 synchronized 關(guān) 鍵字來定義程序中要求線程同步的部分。synchronized 關(guān)鍵字實(shí)現(xiàn)的基本操作是 把每個需要線程同步的部分定義為一個臨界區(qū)，

21、在臨界區(qū)中同一時刻只有一個 線程被執(zhí)行。 2.2 URL 消重 2.2.1 URL 消重的意義 在 SPIDER 系統(tǒng)實(shí)際運(yùn)行的過程中，每秒下載的 10 個頁面中，分析的 URL 大多數(shù)是重復(fù)的，實(shí)際上新的 URL 才幾個。在持續(xù)下載的過程中，新的 URL 非常少，還是以新浪網(wǎng)舉例，1 天 24 小時中總共出現(xiàn)的新 URL 也就是 10000 左右。這種情況非常類似于操作系統(tǒng)中虛擬儲存器管理。所謂的虛擬儲存器， 是指具有請求調(diào)入和置換功能，能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種儲存器 系統(tǒng)。其關(guān)鍵在于允許一個作業(yè)只裝入部分的頁或段就可以啟動運(yùn)行，當(dāng)作業(yè) 運(yùn)行的時候在內(nèi)存中找不到所需要的頁或段的時候

22、，就會發(fā)生請求調(diào)入，而從 外存中找到的頁或段將會置換內(nèi)存中暫時不運(yùn)行的頁面到外存。 URL 消重工作量是非常巨大的。以下在新浪新聞頁面為例，新浪一個新聞 頁面大小為 5060k，每個頁面有 90100 個 URL，如果每秒下載 10 個頁面， 就會產(chǎn)生 9001000 次的 URL 排重操作，每次排重操作都要在幾百萬至幾千萬 的 URL 庫中去查詢。這種操作對數(shù)據(jù)庫系統(tǒng)是一個災(zāi)難，理論上任何需要產(chǎn)生 磁盤 I/O 動作的存儲系統(tǒng)都無法滿足這種查詢的需求。 2.2.2 網(wǎng)絡(luò)爬蟲 URL 去重儲存庫設(shè)計 電子科技大學(xué)成都學(xué)院本科畢業(yè)設(shè)計論文 6 在爬蟲啟動工作的過程中，我們不希望同一個網(wǎng)頁被多次下

23、載，因?yàn)橹貜?fù) 下載不僅會浪費(fèi) CPU 機(jī)時，還會為搜索引擎系統(tǒng)增加負(fù)荷。而想要控制這種重 復(fù)性下載問題，就要考慮下載所依據(jù)的超鏈接，只要能夠控制待下載的 URL 不 重復(fù)，基本可以解決同一個網(wǎng)頁重復(fù)下載的問題。 非常容易想到，在搜索引擎系統(tǒng)中建立一個全局的專門用來檢測，是否某 一個 URL 對應(yīng)的網(wǎng)頁文件曾經(jīng)被下載過的 URL 存儲庫，這就是方案。接著要 考慮的就是如何能夠更加高效地讓爬蟲工作，確切地說，讓去重工作更加高效。 如果實(shí)現(xiàn)去重，一定是建立一個 URL 存儲庫，并且已經(jīng)下載完成的 URL 在進(jìn) 行檢測時候，要加載到內(nèi)存中，在內(nèi)存中進(jìn)行檢測一定會比直接從磁盤上讀取 速度快很多。我們先從

24、最簡單的情況說起，然后逐步優(yōu)化，最終得到一個非常 不錯的解決方案。 基于磁盤的順序存儲 這里，就是指把每個已經(jīng)下載過的 URL 進(jìn)行順序存儲。你可以把全部已經(jīng) 下載完成的 URL 存放到磁盤記事本文件中。每次有一個爬蟲線程得到一個任務(wù) URL 開始下載之前，通過到磁盤上的該文件中檢索，如果沒有出現(xiàn)過，則將這 個新的 URL 寫入記事本的最后一行，否則就放棄該 URL 的下載。 這種方式幾乎沒有人考慮使用了，但是這種檢查的思想是非常直觀的。試想， 如果已經(jīng)下載了 100 億網(wǎng)頁，那么對應(yīng)著 100 億個鏈接，也就是這個檢查 URL 是否重復(fù)的記事本文件就要存儲這 100 億 UR

25、L，況且，很多 URL 字符串的長 度也不小，占用存儲空間不說，查找效率超級低下，這種方案肯定放棄。 基于 Hash 算法的存儲 對每一個給定的 URL，都是用一個已經(jīng)建立好的 Hash 函數(shù)，映射到某個物 理地址上。當(dāng)需要進(jìn)行檢測 URL 是否重復(fù)的時候，只需要將這個 URL 進(jìn)行 Hash 映射，如果得到的地址已經(jīng)存在，說明已經(jīng)被下載過，放棄下載，否則， 將該 URL 及其 Hash 地址作為鍵值對存放到 Hash 表中。 這樣，URL 去重存儲庫就是要維護(hù)一個 Hash 表，如果 Hash 函數(shù)設(shè)計的不好， 在進(jìn)行映射的時候，發(fā)生碰撞的幾率很大，則再進(jìn)行碰撞的處理也非常復(fù)

26、雜。 而且，這里使用的是 URL 作為鍵，URL 字符串也占用了很大的存儲空間。 基于 MD5 壓縮映射的存儲 MD5 算法是一種加密算法，同時它也是基于 Hash 的算法。這樣就可以對 URL 字符串進(jìn)行壓縮，得到一個壓縮字符串，同時可以直接得到一個 Hash 地 址。另外，MD5 算法能夠?qū)⑷魏巫址畨嚎s為 128 位整數(shù)，并映射為物理地址， 第二章 相關(guān)技術(shù)介紹 7 而且 MD5 進(jìn)行 Hash 映射碰撞的幾率非常小，這點(diǎn)非常好。從另一個方面來說， 非常少的碰撞，對于搜索引擎的爬蟲是可以容忍的。況且，在爬蟲進(jìn)行檢測的 過程中，可以通過記錄日志來保存在進(jìn)行 MD5 時發(fā)生碰

27、撞的 URL，通過單獨(dú) 對該 URL 進(jìn)行處理也是可行的。 在 Java 中有一個 Map 類非常好，你可以將壓縮后的 URL 串作為 Key，而 將 Boolean 作為 Value 進(jìn)行存儲，然后將工作中的 Map 在爬蟲停止工作后序列 化到本地磁盤上；當(dāng)下一次啟動新的爬蟲任務(wù)的時候，再將這個 Map 反序列化 到內(nèi)存中，供爬蟲進(jìn)行 URL 去重檢測。 基于嵌入式 Berkeley DB 的存儲 Berkeley DB 的特點(diǎn)就是只存儲鍵值對類型數(shù)據(jù)，這和 URL 去重有很大關(guān) 系。去重，可以考慮對某個鍵，存在一個值，這個值就是那個鍵的狀態(tài)。使用 了 Berkeley DB

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

29、 過多個 Hash 函數(shù)進(jìn)行映射，映射到一個二進(jìn)制向量上，這種方式充分利用了比 特位。不過，我沒有用過這種方式，有機(jī)會可以嘗試一下?？梢詤⒖?Google 的 2.2.3 LRU 算法實(shí)現(xiàn) URL 消重 用雙向鏈表來實(shí)現(xiàn)大容量 cache 的 LRU 算法。原理是：cache 的所有位置都 用雙向鏈表連接起來，當(dāng)一個位置被命中后，就將通過調(diào)整鏈表的指向?qū)⒃撐?置調(diào)整到鏈表的頭位置，新加入的內(nèi)容直接放在鏈表的頭上。這樣，在進(jìn)行過 多次查找操作后，最近被命中過的內(nèi)容就像鏈表的頭移動，而沒有命中過的內(nèi) 容就向鏈表的后面移動。當(dāng)需要替換時，鏈表最后的位置就是最近最少被命中 位置，我們只需要將新的內(nèi)容放

30、在鏈表前面，淘汰鏈表最后的位置就實(shí)現(xiàn)了 LRU 算法。 電子科技大學(xué)成都學(xué)院本科畢業(yè)設(shè)計論文 8 2.3 URL 類訪問網(wǎng)絡(luò) JAVA 提供了許多支 Internet 連接的類，URL 類就是其中之一。在使用 URL 類之前，必須創(chuàng)建一個 URL 對象，創(chuàng)建的方法是使用其構(gòu)造函數(shù)，通過 向其指定一個 URL 地址，就能實(shí)例化該類。如：URL url=new URL（）； 如果傳遞無效的 URL 給 URL 對象，該對象會拋出 MalformedURLException 異常。當(dāng)成功創(chuàng)建一個 URL 對象后，我們調(diào)用 openConnection 函數(shù)建立與 URL 的通信，此時，我們就獲得了一

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

32、InputStream()函數(shù)明確打開到 URL 的連接，獲取輸入 流，再用 java.io 包中的 InputStreamReader 類讀取該輸入流，將網(wǎng)頁下載下來。 2.4 爬行策略淺析 2.4.1 寬度或深度優(yōu)先搜索策略 搜索引擎所用的第一代網(wǎng)絡(luò)爬蟲主要是基于傳統(tǒng)的圖算法, 如寬度優(yōu)先或深 度優(yōu)先算法來索引整個 Web, 一個核心的 U RL 集被用來作為一個種子集合, 這種算法遞歸的跟蹤超鏈接到其它頁面, 而通常不管頁面的內(nèi)容, 因?yàn)樽罱K的目 標(biāo)是這種跟蹤能覆蓋整個 Web. 這種策略通常用在通用搜索引擎中,因?yàn)橥ㄓ盟?索引擎獲得的網(wǎng)頁越多越好, 沒有特定的要求. 寬

33、度優(yōu)先搜索算法 寬度優(yōu)先搜索算法(又稱廣度優(yōu)先搜索) 是最簡便的圖的搜索算法之一, 這 一算法也是很多重要的圖的算法的原型. Dijkstra 單源最短路徑算法和 Prim 最 小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想.寬度優(yōu)先搜索算法是沿著樹 的寬度遍歷樹的節(jié)點(diǎn), 如果發(fā)現(xiàn)目標(biāo), 則算法中止. 該算法的設(shè)計和實(shí)現(xiàn)相對簡 單, 屬于盲目搜索. 在目前為覆蓋盡可能多的網(wǎng)頁, 一般使用寬度優(yōu)先搜索方法. 第二章 相關(guān)技術(shù)介紹 9 也有很多研究將寬度優(yōu)先搜索策略應(yīng)用于聚焦爬蟲中. 其基本思想是認(rèn)為與初 始 U RL 在一定鏈接距離內(nèi)的網(wǎng)頁具有主題相關(guān)性的概率很大. 另外一種方法 是將寬度優(yōu)先搜索

34、與網(wǎng)頁過濾技術(shù)結(jié)合使用, 先用廣度優(yōu)先策略抓取網(wǎng)頁, 再將 其中無關(guān)的網(wǎng)頁過濾掉. 這些方法的缺點(diǎn)在于, 隨著抓取網(wǎng)頁的增多, 大量的無 關(guān)網(wǎng)頁將被下載并過濾, 算法的效率將變低. 深度優(yōu)先搜索 深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索圖. 在深度優(yōu)先搜索 中, 對于最新發(fā)現(xiàn)的頂點(diǎn), 如果它還有以此為起點(diǎn)而未探測到的邊, 就沿此邊繼 續(xù)漢下去. 當(dāng)結(jié)點(diǎn) v 的所有邊都己被探尋過, 搜索將回溯到發(fā)現(xiàn)結(jié)點(diǎn) v 有那條 邊的始結(jié)點(diǎn). 這一過程一直進(jìn)行到已發(fā)現(xiàn)從源結(jié)點(diǎn)可達(dá)的所有結(jié)點(diǎn)為止. 如果還 存在未被發(fā)現(xiàn)的結(jié)點(diǎn), 則選擇其中一個作為源結(jié)點(diǎn)并重復(fù)以上過程, 整個進(jìn)程反 復(fù)進(jìn)行

35、直到所有結(jié)點(diǎn)都被發(fā)現(xiàn)為止. 深度優(yōu)先在很多情況下會導(dǎo)致爬蟲的陷入( trapped) 問題, 所以它既不是完備的, 也不是最優(yōu)的. 2.4.2 聚焦搜索策略 基于第一代網(wǎng)絡(luò)爬蟲的搜索引擎抓取的網(wǎng)頁一般少于 1 000 000 個網(wǎng)頁, 極 少重新搜集網(wǎng)頁并去刷新索引. 而且其檢索速度非常慢, 一般都要等待 10 s 甚 至更長的時間. 隨著網(wǎng)頁頁信息的指數(shù)級增長及動態(tài)變化, 這些通用搜索引擎的 局限性越來越大, 隨著科學(xué)技術(shù)的發(fā)展, 定向抓取相關(guān)網(wǎng)頁資源的聚焦爬蟲便應(yīng) 運(yùn)而生.聚焦爬蟲的爬行策略只挑出某一個特定主題的頁面, 根據(jù)“最好優(yōu)先原 則”進(jìn)行訪問, 快速、有效地獲得更多的與主題相關(guān)的頁

36、面, 主要通過內(nèi)容和 Web 的鏈接結(jié)構(gòu)來指導(dǎo)進(jìn)一步的頁面抓取 2 . 聚焦爬蟲會給它所下載下來的頁面分配一個評價分, 然后根據(jù)得分排序, 最 后插入到一個隊(duì)列中. 最好的下一個搜索將通過對彈出隊(duì)列中的第一個頁面進(jìn) 行分析而執(zhí)行, 這種策略保證爬蟲能優(yōu)先跟蹤那些最有可能鏈接到目標(biāo)頁面的 頁面. 決定網(wǎng)絡(luò)爬蟲搜索策略的關(guān)鍵是如何評價鏈接價值, 即鏈接價值的計算方 法, 不同的價值評價方法計算出的鏈接的價值不同, 表現(xiàn)出的鏈接的“重要程度” 也不同, 從而決定了不同的搜索策略. 由于鏈接包含于頁面之中,而通常具有較 高價值的頁面包含的鏈接也具有較高的價值, 因而對鏈接價值的評價有時也轉(zhuǎn) 換為對頁面

37、價值的評價. 這種策略通常運(yùn)用在專業(yè)搜索引擎中, 因?yàn)檫@種搜索引 擎只關(guān)心某一特定主題的頁面. 2.4.3 基于內(nèi)容評價的搜索策略 基于內(nèi)容評價的搜索策略 3, 4 , 主要是根據(jù)主題(如關(guān)鍵詞、主題相關(guān)文檔) 電子科技大學(xué)成都學(xué)院本科畢業(yè)設(shè)計論文 10 與鏈接文本的相似度來評價鏈接價值的高低, 并以此決定其搜索策略: 鏈接文本 是指鏈接周圍的說明文字和鏈接 U RL 上的文字信息, 相似度的評價通常采用 以下公式: sim (d i, d j ) =mk= 1w ik w jk(mk= 1w 2ik ) (mk= 1w 2jk ) 其中, di 為新文本的特征向量, d j 為第 j 類的中

38、心向量,m 為特征向量的維 數(shù),wk 為向量的第 K 維.由于 Web 頁面不同于傳統(tǒng)的文本, 它是一種半結(jié)構(gòu)化 的文檔, 包含許多結(jié)構(gòu)信息 Web 頁面不是單獨(dú)存在的, 頁面中的鏈接指示了頁 面之間的相互關(guān)系, 因而有些學(xué)者提出了基于鏈接結(jié)構(gòu)評價鏈接價值的方法. 2.4.4 基于鏈接結(jié)構(gòu)評價的搜索策略 基于鏈接結(jié)構(gòu)評價的搜索策略, 是通過對 Web 頁面之間相互引用關(guān)系的分 析來確定鏈接的重要性, 進(jìn)而決定鏈接訪問順序的方法. 通常認(rèn)為有較多入鏈或 出鏈的頁面具有較高的價值. PageRank 和 Hits 是其中具有代表性的算法. PageRank 算法 基于鏈接評價的搜索

39、引擎的優(yōu)秀代表是 Google (http:/www.G) , 它 獨(dú)創(chuàng)的“鏈接評價體系”(PageRank 算法) 是基于這樣一種認(rèn)識, 一個網(wǎng)頁的重 要性取決于它被其它網(wǎng)頁鏈接的數(shù)量, 特別是一些已經(jīng)被認(rèn)定是“重要”的網(wǎng)頁 的鏈接數(shù)量. PageRank 算法最初用于 Google 搜索引擎信息檢索中對查詢結(jié)果 的排序過程 5 , 近年來被應(yīng)用于網(wǎng)絡(luò)爬蟲對鏈接重要性的評價, PageRank 算法 中, 頁面的價值通常用頁面的 PageRank 值表示, 若設(shè)頁面 p 的 PageRank 值為 PR (p ) , 則 PR (p ) 采用如下迭代公式計算: PR (p ) = C 1T+

40、 (1 - C) Cin (p )PR (p )ou t (C) 其中 T 為計算中的頁面總量, C 1 是阻尼常數(shù)因子, in (p ) 為所有指向p 的頁面 的集合, out (C) 為頁面 C 出鏈的集合. 基于 PageRank 算法的網(wǎng)絡(luò)爬蟲在搜索過 程中, 通過計算每個已訪問頁面的 PageRank 值來確定頁面的價值, 并優(yōu)先選擇 PageRank 值大的頁面中的鏈接進(jìn)行訪問. H ITS 算法 HITS 方法定義了兩個重要概念: Authority 和 Hub. Authority 表示一個權(quán)威 頁面被其它頁面引用的數(shù)量, 即該權(quán)威頁面的入度值. 網(wǎng)頁被引用的數(shù)

41、量越大, 則該網(wǎng)頁的 Authority 值越大; Hub 表示一個 Web 頁面指向其它頁面的數(shù)量, 即 該頁面的出度值. 網(wǎng)頁的出度值越大, 其 Hub 值越高. 由于 Hub 值高的頁面通常 都提供了指向權(quán)威頁面的鏈接, 因而起到了隱含說明某主題頁面權(quán)威性的作用. 第二章 相關(guān)技術(shù)介紹 11 HITS (Hyperlink- Induced Top ic Search) 算法是利用 HubAuthority 方法的搜索 方法,Authority 表示一個頁面被其它頁面引用的數(shù)量, 即該頁面的入度值. Hub 表 示一個 Web 頁面指向其它頁面的數(shù)量, 即該頁面的出度值. 算法如下: 將

42、查詢 q 提交給傳統(tǒng)的基于關(guān)鍵字匹配的搜索引擎. 搜索引擎返回很多網(wǎng)頁, 從中取前 n 個網(wǎng)頁作為根集, 用 S 表示.通過向 S 中加入被 S 引用的網(wǎng)頁和引用 S 的網(wǎng)頁 將 S 擴(kuò)展成一個更大的集合 T.以 T 中的 Hub 網(wǎng)頁為頂點(diǎn)集 V l, 以權(quán)威網(wǎng)頁為 頂點(diǎn)集 V 2,V1 中的網(wǎng)頁到V 2 中的網(wǎng)頁的超鏈接為邊集 E , 形成一個二分有向 圖 S G = (V 1,V 2, E ).對 V 1 中的任一個頂點(diǎn) v , 用 H (v ) 表示網(wǎng)頁v 的 Hub 值, 對 V 2 中的頂點(diǎn) u, 用 A (u) 表示網(wǎng)頁的 Authority 值. 開始時 H (v ) = A

43、(u) = 1, 對 u 執(zhí)行公式(1) 來修改它的 A (u) , 對 v 執(zhí)行公式(2) 來修改它的 H (v ) , 然后 規(guī)范化 A (u) , H (v ) , 如此不斷的重復(fù)計算上述運(yùn)算, 直到 A (u) , H (v ) 收斂. A (u) = v: (v , u) EH (v ) (1) H (v ) = v: (v, u) EA (v ) (2) 式(1) 反映了若一個網(wǎng)頁由很多好的 Hub 指向, 則其權(quán)威值會相應(yīng)增加(即權(quán)威 值增加為所有指向它的網(wǎng)頁的現(xiàn)有 Hub 值之和). 式(2) 反映了若一個網(wǎng)頁指向 許多好的權(quán)威頁, 則 Hub 值也會相應(yīng)增加(即 Hub 值增

44、加為該網(wǎng)頁鏈接的所有 網(wǎng)頁的權(quán)威值之和).雖然基于鏈接結(jié)構(gòu)價的搜索考慮了鏈接的結(jié)構(gòu)和頁面之間的 引用關(guān)系, 但忽略了頁面與主題的相關(guān)性, 在某些情況下, 會出現(xiàn)搜索偏離主題 的問題. 另外, 搜索過程中需要重復(fù)計算 PageRank 值或 Authority 以及 Hub 權(quán) 重, 計算復(fù)雜度隨頁面和鏈接數(shù)量的增長呈指數(shù)級增長 6 . 2.4.5 基于鞏固學(xué)習(xí)的聚焦搜索 近年來對 Web 信息資源分布的研究表明很多類型相同的網(wǎng)站在構(gòu)建方式上, 主題相同的網(wǎng)頁在組織方式上都存在著一定的相似性, 有的學(xué)者就考慮將鞏固學(xué) 習(xí)引入網(wǎng)絡(luò)爬蟲的訓(xùn)練過程中, 從這些相似性獲取一些“經(jīng)驗(yàn)”, 而這些經(jīng)驗(yàn)信 息

45、在搜索距相關(guān)頁面集較遠(yuǎn)的地方往往能獲得較好的回報, 而前兩種策略在這種 情況下容易迷失方向.在鞏固學(xué)習(xí)模型中, 把網(wǎng)絡(luò)爬蟲經(jīng)過若干無關(guān)頁面的訪問 之后才能獲得的主題相關(guān)頁面稱為未來回報, 對未來回報的預(yù)測值稱為未來回報 價值, 用 Q 價值表示. 這種方法的核心就是學(xué)習(xí)如何計算鏈接的 Q 價值, 根據(jù)未 來回報價值確定正確的搜索方向. 目前這類搜索策略不足之處在于學(xué)習(xí)效率低的 問題, 而且在訓(xùn)練過程中增加了用戶的負(fù)擔(dān). 2.4.6 基于語境圖的聚焦搜索 基于鞏固學(xué)習(xí)的網(wǎng)絡(luò)爬蟲通過計算鏈接的 Q 價值可以確定搜索方向, 但它卻 電子科技大學(xué)成都學(xué)院本科畢業(yè)設(shè)計論文 12 無法估計距離目標(biāo)頁面的遠(yuǎn)

46、近. 為此, Diligent 等提出了基于“語境圖”的搜索 策略, 它通過構(gòu)建典型頁面的 web“語境圖”來估計離目標(biāo)頁面的距離, 距離較 近的頁面較早得到訪問 7 .基于“語境圖”的搜索策略需要借助已有的通用搜 索引擎構(gòu)建“語境圖”, 而搜索引擎的檢索結(jié)果并非一定代表真實(shí)的 web 結(jié)構(gòu), 因而這種方式也具有局限性. 第三章 系統(tǒng)需求分析及模塊設(shè)計 13 第三章 系統(tǒng)需求分析及模塊設(shè)計 3.1 系統(tǒng)需求分析 SPIDER 要獲取的對象是存在于網(wǎng)絡(luò)上數(shù)以億計的網(wǎng)頁，這些網(wǎng)頁以超鏈接 形式互相聯(lián)系在一起，每一網(wǎng)頁對應(yīng)一個超鏈接，也稱統(tǒng)一資源定位符 （URL）。我們可以把網(wǎng)絡(luò)看做一個圖 M(V,

47、E)，網(wǎng)絡(luò)中的網(wǎng)頁構(gòu)成節(jié)點(diǎn)集 V， 他們之間的鏈接構(gòu)成邊集 E，SPIDER 正是從某一節(jié)點(diǎn)開始，沿著邊，遍歷圖 M，每訪問到圖中一個節(jié)點(diǎn) Vi，就進(jìn)行一定的處理。 為了達(dá)到上述目的，一個 SPIDER 必須被設(shè)計成多線程的，A 個線程并發(fā) 地在網(wǎng)絡(luò)上協(xié)同工作，才有可能在盡可能短的時間內(nèi)遍歷完網(wǎng)絡(luò)中的網(wǎng)頁。但 網(wǎng)頁數(shù)目是如此之大，如果任 SPIDER 程序無窮地搜索下去，那么程序幾乎不 能終止。所以我們限制 SPIDER 每次工作只訪問一個站點(diǎn)。一個再大型的站點(diǎn)， 其中的網(wǎng)頁數(shù)目也是有限的，因此 SPIDER 程序能在有限的時間內(nèi)結(jié)束。 當(dāng) SPIDER 程序訪問到一個網(wǎng)頁，必須進(jìn)行以下幾項(xiàng)基

48、本處理：抽取網(wǎng)頁中包 含的文本；抽取網(wǎng)頁中包含的 URL，并將其區(qū)分為網(wǎng)站內(nèi) URL 或網(wǎng)站外 URL。 3.2 SPIDER 體系結(jié)構(gòu) 此爬蟲程序主要分為三個部分：任務(wù)執(zhí)行端，任務(wù)調(diào)度端，數(shù)據(jù)服務(wù)端。 每一個 SPIDER 任務(wù)執(zhí)行端關(guān)聯(lián)一個站點(diǎn),一個線程下載一個基于 URL 鏈接的頁面, 并進(jìn)行 Web 頁面解析, 得到站內(nèi) URL 和發(fā)現(xiàn)新站點(diǎn) URL 另外,將 URL 隊(duì)列持久化到數(shù)據(jù)庫, 因此在 SPIDER 任務(wù)執(zhí)行端以外 Down 掉后, 能夠 斷點(diǎn)續(xù)傳. SPIDER 客戶端線程間的協(xié)調(diào)通信采用 Java 的線程同步技術(shù) synchronized, 在數(shù)據(jù)服務(wù)端中對 URL 進(jìn)

49、行緩存提高了系統(tǒng)處理速度. SPIDER 的任務(wù)執(zhí)行和 任務(wù)調(diào)度端都需要維持一個 URL 隊(duì)列: 任務(wù)執(zhí)行端的 URL 隊(duì)列中存儲了站內(nèi) URL; 任務(wù)調(diào)度端則是站點(diǎn)的 URL. 在這些 URL 隊(duì)列上有大量的操作, 包括 URL 查找、 URL 插入、URL 狀態(tài)更新等. 如果 SPIDER 以 300 頁 秒的速 度下載 Web 頁面, 平均將會產(chǎn)生 2000 多個 URL 12 , 因此簡單的采用內(nèi)存數(shù) 據(jù)結(jié)構(gòu)存儲這些 URL 隊(duì)列有一定的問題, 系統(tǒng)沒有足夠的內(nèi)存空間;而采用直接 持久化到數(shù)據(jù)庫, 則需要大量的數(shù)據(jù)庫連接、查詢等操作, 系統(tǒng)效率會明顯下降. 如果采用 URL 壓縮的辦法

50、,盡管在一定程度上可以平衡空間和時間的矛盾, 但仍 電子科技大學(xué)成都學(xué)院本科畢業(yè)設(shè)計論文 14 然不適用于大規(guī)模數(shù)據(jù)采集的 SPIDER. 圖 3.2 SPIDER 體系結(jié) 3.3 各主要功能模塊（類）設(shè)計 SPIDERWorker 類：該類繼承自線程類，請求任務(wù) URL，根據(jù)得到的 URL 下載相應(yīng)的 HTML 代碼，利用 HTML 代碼調(diào)用其他模塊完成相關(guān)處理。 SPIDERManager 類：該類用于控制 SPIDERWorker 線程。 UrlQueueManager 類：該類用于維護(hù) URL 等待隊(duì)列，分配任務(wù) URL，URL 消重模塊。 UrlParse 類：用于解析 HTML，獲

51、取并過濾 URL。 DateBaseConnect 類：用于提供數(shù)據(jù)庫連接。 3.4 SPIDER 工作過程 將給定的初始 URL 加入到 URL 等待隊(duì)列。 創(chuàng)建爬蟲線程，啟動爬蟲線程 第三章 系統(tǒng)需求分析及模塊設(shè)計 15 每個爬蟲線程從 URL 等待隊(duì)列中取得任務(wù) URL。然后根據(jù) URL 下載網(wǎng) 頁，然后解析網(wǎng)頁，獲取超鏈接 URLs。如果獲取到的 URL 為相對地址，需要 轉(zhuǎn)換為絕對地址，然后淘汰站外 URLs，錯誤 URLs 或者不能解析的 URL 地址。 再判斷這些 URL 是否已經(jīng)被下載到，如果沒有則加入到 URL 等待隊(duì)列。 繼續(xù)執(zhí)行步驟，直到結(jié)束條件停止。 將初始 URLs 加 入到等待隊(duì)列 是否為非法 URL 創(chuàng)建啟動爬蟲線 程 從 URL 等待隊(duì) 列獲取任務(wù) URL 下載 URL 對應(yīng) 的 HTML 代碼 將相對地址轉(zhuǎn)換 為絕對地址 解析 HTML，獲 取 U