網(wǎng)絡(luò)爬蟲的設(shè)計(jì)與實(shí)現(xiàn)畢業(yè)論文（含外文翻譯）

1、<p><b>　　摘要</b></p><p>　　網(wǎng)絡(luò)爬蟲是一種自動(dòng)搜集互聯(lián)網(wǎng)信息的程序。通過網(wǎng)絡(luò)爬蟲不僅能夠?yàn)樗阉饕娌杉W(wǎng)絡(luò)信息，而且可以作為定向信息采集器，定向采集某些網(wǎng)站下的特定信息，如招聘信息，租房信息等。</p><p>　　本文通過JAVA實(shí)現(xiàn)了一個(gè)基于廣度優(yōu)先算法的多線程爬蟲程序。本論文闡述了網(wǎng)絡(luò)爬蟲實(shí)現(xiàn)中一些主要問題：為何使用廣度優(yōu)先的

2、爬行策略，以及如何實(shí)現(xiàn)廣度優(yōu)先爬行；為何要使用多線程，以及如何實(shí)現(xiàn)多線程；系統(tǒng)實(shí)現(xiàn)過程中的數(shù)據(jù)存儲(chǔ)；網(wǎng)頁信息解析等。</p><p>　　通過實(shí)現(xiàn)這一爬蟲程序，可以搜集某一站點(diǎn)的URLs，并將搜集到的URLs存入數(shù)據(jù)庫。</p><p>　　【關(guān)鍵字】網(wǎng)絡(luò)爬蟲；JAVA；廣度優(yōu)先；多線程。</p><p><b>　　ABSTRACT</b>&

3、lt;/p><p>　　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

4、 from some web sites, such as HR informations, house rent informations.</p><p>　　In this paper, use JAVA implements a breadth-first algorithm multi-thread SPDIER. This paper expatiates some major problems of

5、 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. This SPIDER can col

6、lect URLs from one web site, and store URLs into database.</p><p>　　【KEY WORD】SPIDER; JAVA; Breadth First Search; multi-threads.</p><p><b>　　目錄</b></p><p><b>　　第一章

7、 引言1</b></p><p>　　第二章 相關(guān)技術(shù)介紹2</p><p>　　2.1 JAVA線程2</p><p>　　2.1.1 線程概述2</p><p>　　2.1.2 JAVA線程模型2</p><p>　　2.1.3 創(chuàng)建線程3</p><p>　　2.

8、1.4 JAVA中的線程的生命周期4</p><p>　　2.1.5 JAVA線程的結(jié)束方式4</p><p>　　2.1.6 多線程同步5</p><p>　　2.2 URL消重5</p><p>　　2.2.1 URL消重的意義5</p><p>　　2.2.2 網(wǎng)絡(luò)爬蟲URL去重儲(chǔ)存庫設(shè)計(jì)5</

9、p><p>　　2.2.3 LRU算法實(shí)現(xiàn)URL消重7</p><p>　　2.3 URL類訪問網(wǎng)絡(luò)8</p><p>　　2.4　爬行策略淺析8</p><p>　　2.4.1寬度或深度優(yōu)先搜索策略8</p><p>　　2.4.2 聚焦搜索策略9</p><p>　　2.4.3基于內(nèi)容

10、評(píng)價(jià)的搜索策略9</p><p>　　2.4.4 基于鏈接結(jié)構(gòu)評(píng)價(jià)的搜索策略10</p><p>　　2.4.5 基于鞏固學(xué)習(xí)的聚焦搜索11</p><p>　　2.4.6 基于語境圖的聚焦搜索11</p><p>　　第三章 系統(tǒng)需求分析及模塊設(shè)計(jì)13</p><p>　　3.1 系統(tǒng)需求分析13<

11、/p><p>　　3.2 SPIDER體系結(jié)構(gòu)13</p><p>　　3.3 各主要功能模塊（類）設(shè)計(jì)14</p><p>　　3.4 SPIDER工作過程14</p><p>　　第四章 系統(tǒng)分析與設(shè)計(jì)16</p><p>　　4.1 SPIDER構(gòu)造分析16</p><p>　　4.

12、2 爬行策略分析17</p><p>　　4.3 URL抽取，解析和保存18</p><p>　　4.3.1 URL抽取18</p><p>　　4.3.2 URL解析19</p><p>　　4.3.3 URL保存19</p><p>　　第五章 系統(tǒng)實(shí)現(xiàn)21</p><p>　　

13、5.1 實(shí)現(xiàn)工具21</p><p>　　5.2 爬蟲工作21</p><p>　　5.3 URL解析22</p><p>　　5.4 URL隊(duì)列管理24</p><p>　　5.4.1 URL消重處理24</p><p>　　5.4.2 URL等待隊(duì)列維護(hù)26</p><p>　　

14、5.4.3 數(shù)據(jù)庫設(shè)計(jì)27</p><p>　　第六章 系統(tǒng)測(cè)試29</p><p><b>　　第七章 結(jié)論32</b></p><p><b>　　參考文獻(xiàn)33</b></p><p><b>　　致謝34</b></p><p><

15、b>　　外文資料原文35</b></p><p><b>　　譯文51</b></p><p><b>　　第一章 引言</b></p><p>　　隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)上的信息呈爆炸式增長。這使得人們?cè)诰W(wǎng)上找到所需的信息越來越困難，這種情況下搜索引擎應(yīng)運(yùn)而生。搜索引擎搜集互聯(lián)網(wǎng)上數(shù)以億計(jì)的網(wǎng)頁

16、，并為每個(gè)詞建立索引。在建立搜索引擎的過程中，搜集網(wǎng)頁是非常重要的一個(gè)環(huán)節(jié)。爬蟲程序就是用來搜集網(wǎng)頁的程序。以何種策略偏歷互聯(lián)網(wǎng)上的網(wǎng)頁，也成了爬蟲程序主要的研究方向?，F(xiàn)在比較流行的搜索引擎，比如google，百度，它們爬蟲程序的技術(shù)內(nèi)幕一般都不公開。目前幾種比較常用的爬蟲實(shí)現(xiàn)策略：廣度優(yōu)先的爬蟲程序，Repetitive爬蟲程序，定義爬行爬蟲程序，深層次爬行爬蟲程序。此外, 還有根據(jù)概率論進(jìn)行可用Web頁的數(shù)量估算, 用于評(píng)估互聯(lián)網(wǎng)W

17、eb規(guī)模的抽樣爬蟲程序; 采用爬行深度、頁面導(dǎo)入鏈接量分析等方法, 限制從程序下載不相關(guān)的Web頁的選擇性爬行程序等等。</p><p>　　爬蟲程序是一個(gè)自動(dòng)獲取網(wǎng)頁的程序。它為搜索引擎從互聯(lián)網(wǎng)上下載網(wǎng)頁，是搜索引擎的重要組成部分。爬蟲程序的實(shí)現(xiàn)策略，運(yùn)行效率直接影響搜索引擎的搜索結(jié)果。不同的搜索引擎，會(huì)根據(jù)對(duì)搜索結(jié)果的不同需求，選擇最合適的爬行策略來搜集互聯(lián)網(wǎng)上的信息。高效，優(yōu)秀的爬蟲程序可以使人們?cè)诨ヂ?lián)網(wǎng)上

18、尋找到更及時(shí)，更準(zhǔn)確的信息。</p><p>　　實(shí)現(xiàn)網(wǎng)絡(luò)爬蟲的重點(diǎn)和難點(diǎn)有：多線程的實(shí)現(xiàn)；對(duì)臨界資源的分配；遍歷web圖的遍歷策略選擇和實(shí)現(xiàn)；存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的選擇和實(shí)現(xiàn)。</p><p>　　本文通過JAVA語言實(shí)現(xiàn)一個(gè)基于廣度優(yōu)先偏歷算法的多線程爬蟲程序。通過實(shí)現(xiàn)此爬蟲程序可以定點(diǎn)搜集某一站點(diǎn)的URLs，如果需要搜集其他信息，可以在解析URLs的同時(shí)，解析獲取相應(yīng)信息。</p>

19、;<p>　　第二章 相關(guān)技術(shù)介紹</p><p>　　2.1 JAVA線程</p><p>　　2.1.1 線程概述</p><p>　　幾乎每種操作系統(tǒng)都支持線程的概念—進(jìn)程就是在某種程度上相互隔離的，獨(dú)立運(yùn)行的程序。一般來說，這些操作系統(tǒng)都支持多進(jìn)程操作。所謂多進(jìn)程，就是讓系統(tǒng)（好像）同時(shí)運(yùn)行多個(gè)程序。比如，我在Microsoft Word編寫本

20、論文的時(shí)候，我還打開了一個(gè)mp3播放器來播放音樂，偶爾的，我還會(huì)再編輯Word的同時(shí)讓我的機(jī)器執(zhí)行一個(gè)打印任務(wù)，而且我還喜歡通過IE從網(wǎng)上下載一個(gè)Flash動(dòng)畫。對(duì)于我來說，這些操作都是同步進(jìn)行的，我不需要等一首歌曲放完了再來編輯我的論文。看起來，它們都同時(shí)在我的機(jī)器上給我工作。</p><p>　　事實(shí)的真相是，對(duì)于一個(gè)CPU而言，它在某一個(gè)時(shí)間點(diǎn)上，只能執(zhí)行一個(gè)程序。CPU不斷的在這些程序之間“跳躍”執(zhí)行。那

21、么，為什么我們看不出任何的中斷現(xiàn)象呢？這是因?yàn)?，相?duì)于我們的感覺，它的速度實(shí)在太快了。我們?nèi)说母兄獣r(shí)間可能以秒來計(jì)算。而對(duì)于CPU而言，它的時(shí)間是以毫秒來計(jì)算的，從我們?nèi)庋劭磥?，它們就是一個(gè)連續(xù)的動(dòng)作。</p><p>　　因此，雖然我們看到的都是一些同步的操作，但實(shí)際上，對(duì)于計(jì)算機(jī)而言，它在某個(gè)時(shí)間點(diǎn)上只能執(zhí)行一個(gè)程序，除非你的計(jì)算機(jī)是多CPU的。</p><p>　　多線程（Multi

22、-Thread）擴(kuò)展了多進(jìn)程（multi-Process）操作的概念，將任務(wù)的劃分下降到了程序級(jí)別，使得各個(gè)程序似乎可以在同一個(gè)時(shí)間內(nèi)執(zhí)行多個(gè)任務(wù)。每個(gè)任務(wù)稱為一個(gè)線程，能夠同時(shí)運(yùn)行多個(gè)線程的程序稱為多線程程序。</p><p>　　多線程和多進(jìn)程有什么區(qū)別呢？對(duì)于進(jìn)程來說，每個(gè)進(jìn)程都有自己的一組完整的變量，而線程則共享相同的數(shù)據(jù)。</p><p>　　2.1.2 JAVA線程模型<

23、;/p><p>　　我們知道，計(jì)算機(jī)程序得以執(zhí)行的三個(gè)要素是：CPU，程序代碼，可存取的數(shù)據(jù)。在JAVA語言中，多線程的機(jī)制是通過虛擬CPU來實(shí)現(xiàn)的。可以形象的理解為,在一個(gè)JAVA程序內(nèi)部虛擬了多臺(tái)計(jì)算機(jī)，每臺(tái)計(jì)算機(jī)對(duì)應(yīng)一個(gè)線程，有自己的CPU，可以獲取所需的代碼和數(shù)據(jù)，因此能獨(dú)立執(zhí)行任務(wù)，相互間還可以共用代碼和數(shù)據(jù)。JAVA的線程是通過java.lang.Thread類來實(shí)現(xiàn)的，它內(nèi)部實(shí)現(xiàn)了虛擬CPU的功能，能夠

24、接收和處理傳遞給它的代碼和數(shù)據(jù)，并提供了獨(dú)立的運(yùn)行控制功能。</p><p>　　我們知道，每個(gè)JAVA應(yīng)用程序都至少有一個(gè)線程，這就是所謂的主線程。它由JVM創(chuàng)建并調(diào)用JAVA應(yīng)用程序的main（）方法。</p><p>　　JVM還通常會(huì)創(chuàng)建一些其他的線程，不過，這些線程對(duì)我們而言通常都是不可見的。比如，用于自動(dòng)垃圾收集的線程，對(duì)象終止或者其他的JVM處理任務(wù)相關(guān)的線程。</p&

25、gt;<p>　　2.1.3 創(chuàng)建線程</p><p>　　2.1.3.1 創(chuàng)建線程方式一</p><p>　　在JAVA中創(chuàng)建線程的一種方式是通過Thread來實(shí)現(xiàn)的。Thread有很多個(gè)構(gòu)造器來創(chuàng)建一個(gè)線程（Thread）實(shí)例：</p><p>　　Thread();創(chuàng)建一個(gè)線程。</p><p>　　Thread(Runn

26、able target);創(chuàng)建一個(gè)線程，并指定一個(gè)目標(biāo)。</p><p>　　Thread(Runnable target,String name);創(chuàng)建一個(gè)名為name的目標(biāo)為target的線程。</p><p>　　Thread(String name);創(chuàng)建一個(gè)名為name的線程。</p><p>　　Thread(ThreadGroup group,Runn

27、able target);創(chuàng)建一個(gè)隸屬于group線程組，目標(biāo)為target的線程。</p><p>　　通常，我們可以將一個(gè)類繼承Thread，然后，覆蓋Thread中的run()方法，這樣讓這個(gè)類本身也就成了線程。</p><p>　　每個(gè)線程都是通過某個(gè)特定Thread對(duì)象所對(duì)應(yīng)的方法run()來完成其操作的，方法run()稱為線程體。</p><p>　　使

28、用start()方法，線程進(jìn)入Runnable狀態(tài)，它將線程調(diào)度器注冊(cè)這個(gè)線程。調(diào)用start()方法并不一定馬上會(huì)執(zhí)行這個(gè)線程，正如上面所說，它只是進(jìn)入Runnble而不是Running。</p><p>　　2.1.3.2 創(chuàng)建線程方式二</p><p>　　通過實(shí)現(xiàn)Runnable接口并實(shí)現(xiàn)接口中定義的唯一方法run()，可以創(chuàng)建一個(gè)線程。在使用Runnable接口時(shí)，不能直接創(chuàng)建所

29、需類的對(duì)象并運(yùn)行它，而是必須從Thread類的一個(gè)實(shí)例內(nèi)部運(yùn)行它。</p><p>　　從上面兩種創(chuàng)建線程的方法可以看出，如果繼承Thread類，則這個(gè)類本身可以調(diào)用start方法，也就是說將這個(gè)繼承了Thread的類當(dāng)作目標(biāo)對(duì)象；而如果實(shí)現(xiàn)Runnable接口，則這個(gè)類必須被當(dāng)作其他線程的目標(biāo)對(duì)象。</p><p>　　2.1.4 JAVA中的線程的生命周期</p><

30、;p>　　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è)置為一個(gè)狀態(tài)，它屬于可運(yùn)行狀態(tài)的一種。</p><p>　　當(dāng)使用new來新建一個(gè)線程時(shí)，它處于New狀態(tài)，這個(gè)

31、時(shí)候，線程并未進(jìn)行任何操作。</p><p>　　然后，調(diào)用線程的start()方法，來向線程調(diào)度程序（通常是JVM或操作系統(tǒng)）注冊(cè)一個(gè)線程，這個(gè)時(shí)候，這個(gè)線程一切就緒，就等待CPU時(shí)間了。</p><p>　　線程調(diào)度程序根據(jù)調(diào)度策略來調(diào)度不同的線程，調(diào)用線程的run方法給已經(jīng)注冊(cè)的各個(gè)線程以執(zhí)行的機(jī)會(huì)，被調(diào)度執(zhí)行的線程進(jìn)入運(yùn)行（Running）狀態(tài)。當(dāng)線程的run方法運(yùn)行完畢，線程將被

32、拋棄，進(jìn)入死亡狀態(tài)。你不能調(diào)用restart方法來重新開始一個(gè)處于死亡狀態(tài)的線程，但是，你可以調(diào)用處于死亡狀態(tài)的線程對(duì)象的各個(gè)方法。</p><p>　　如果線程在運(yùn)行（Running）狀態(tài)中因?yàn)镮/O阻塞，等待鍵盤鍵入，調(diào)用了線程的sleep方法，調(diào)用了對(duì)象的wait()方法等，則線程將進(jìn)入阻塞狀態(tài)，直到這些阻塞原因被解除，如：IO完成，鍵盤輸入了數(shù)據(jù)，調(diào)用sleep方法后的睡眠時(shí)間到以及其他線程調(diào)用了對(duì)象的n

33、otify或notifyAll方法來喚醒這個(gè)因?yàn)榈却枞木€程等，線程將返回到Runnable狀態(tài)重新等待調(diào)度程序調(diào)度，注意，被阻塞的線程不會(huì)直接返回到Running狀態(tài)，而是重新回到Runnable狀態(tài)等待線程調(diào)度程序的調(diào)用。</p><p>　　線程調(diào)度程序會(huì)根據(jù)調(diào)度情況，將正在運(yùn)行中的線程設(shè)置為Runnable狀態(tài)，例如，有一個(gè)比當(dāng)前運(yùn)行狀態(tài)線程更高運(yùn)行等級(jí)的線程進(jìn)入Runnable狀態(tài)，就可能將當(dāng)前運(yùn)行

34、的線程從Running狀態(tài)“踢出”,讓它回到Runnable狀態(tài)。</p><p>　　2.1.5 JAVA線程的結(jié)束方式</p><p>　　線程會(huì)以以下三種方式之一結(jié)束：</p><p>　　線程到達(dá)其run()方法的末尾；</p><p>　　線程拋出一個(gè)未捕獲到的Exception或Error；</p><p>

35、;　　另一個(gè)線程調(diào)用一個(gè)Deprecated的stop()方法。注意，因?yàn)檫@個(gè)方法會(huì)引起線程的安全問題，已經(jīng)被不推薦使用了，所以，不要再程序調(diào)用這個(gè)方法。</p><p>　　2.1.6 多線程同步</p><p>　　當(dāng)同時(shí)運(yùn)行的相互獨(dú)立的線程需要共享數(shù)據(jù)并且需要考慮其他線程的狀態(tài)時(shí)，就需要使用一套機(jī)制使得這些線程同步，避免在爭(zhēng)用資源時(shí)發(fā)生沖突，甚至發(fā)生死鎖。JAVA提供了多種機(jī)制以實(shí)現(xiàn)

36、線程同步。多數(shù)JAVA同步是以對(duì)象鎖定為中心的。JAVA中從Object對(duì)象繼承來的每個(gè)對(duì)象都有一個(gè)單獨(dú)的鎖。由于JAVA中的每個(gè)對(duì)象都是從Object繼承來的。所以JAVA中的每個(gè)對(duì)象都有自己的鎖。這樣使它在共享的線程之間可以相互協(xié)調(diào)。在JAVA中實(shí)現(xiàn)線程同步的另一個(gè)方法是通過使用synchronized關(guān)鍵字。JAVA使用synchronized關(guān)鍵字來定義程序中要求線程同步的部分。synchronized關(guān)鍵字實(shí)現(xiàn)的基本操作是把每

37、個(gè)需要線程同步的部分定義為一個(gè)臨界區(qū)，在臨界區(qū)中同一時(shí)刻只有一個(gè)線程被執(zhí)行。</p><p><b>　　2.2 URL消重</b></p><p>　　2.2.1 URL消重的意義</p><p>　　在SPIDER系統(tǒng)實(shí)際運(yùn)行的過程中，每秒下載的10個(gè)頁面中，分析的URL大多數(shù)是重復(fù)的，實(shí)際上新的URL才幾個(gè)。在持續(xù)下載的過程中，新的URL

38、非常少，還是以新浪網(wǎng)舉例，1天24小時(shí)中總共出現(xiàn)的新URL也就是10000左右。這種情況非常類似于操作系統(tǒng)中虛擬儲(chǔ)存器管理。所謂的虛擬儲(chǔ)存器，是指具有請(qǐng)求調(diào)入和置換功能，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種儲(chǔ)存器系統(tǒng)。其關(guān)鍵在于允許一個(gè)作業(yè)只裝入部分的頁或段就可以啟動(dòng)運(yùn)行，當(dāng)作業(yè)運(yùn)行的時(shí)候在內(nèi)存中找不到所需要的頁或段的時(shí)候，就會(huì)發(fā)生請(qǐng)求調(diào)入，而從外存中找到的頁或段將會(huì)置換內(nèi)存中暫時(shí)不運(yùn)行的頁面到外存。</p><p&g

39、t;　　URL消重工作量是非常巨大的。以下在新浪新聞頁面為例，新浪一個(gè)新聞頁面大小為50～60k，每個(gè)頁面有90～100個(gè)URL，如果每秒下載10個(gè)頁面，就會(huì)產(chǎn)生900～1000次的URL排重操作，每次排重操作都要在幾百萬至幾千萬的URL庫中去查詢。這種操作對(duì)數(shù)據(jù)庫系統(tǒng)是一個(gè)災(zāi)難，理論上任何需要產(chǎn)生磁盤I/O動(dòng)作的存儲(chǔ)系統(tǒng)都無法滿足這種查詢的需求。</p><p>　　2.2.2 網(wǎng)絡(luò)爬蟲URL去重儲(chǔ)存庫設(shè)計(jì)&l

40、t;/p><p>　　在爬蟲啟動(dòng)工作的過程中，我們不希望同一個(gè)網(wǎng)頁被多次下載，因?yàn)橹貜?fù)下載不僅會(huì)浪費(fèi)CPU機(jī)時(shí)，還會(huì)為搜索引擎系統(tǒng)增加負(fù)荷。而想要控制這種重復(fù)性下載問題，就要考慮下載所依據(jù)的超鏈接，只要能夠控制待下載的URL不重復(fù)，基本可以解決同一個(gè)網(wǎng)頁重復(fù)下載的問題。</p><p>　　非常容易想到，在搜索引擎系統(tǒng)中建立一個(gè)全局的專門用來檢測(cè)，是否某一個(gè)URL對(duì)應(yīng)的網(wǎng)頁文件曾經(jīng)被下載過的U

41、RL存儲(chǔ)庫，這就是方案。接著要考慮的就是如何能夠更加高效地讓爬蟲工作，確切地說，讓去重工作更加高效。如果實(shí)現(xiàn)去重，一定是建立一個(gè)URL存儲(chǔ)庫，并且已經(jīng)下載完成的URL在進(jìn)行檢測(cè)時(shí)候，要加載到內(nèi)存中，在內(nèi)存中進(jìn)行檢測(cè)一定會(huì)比直接從磁盤上讀取速度快很多。我們先從最簡單的情況說起，然后逐步優(yōu)化，最終得到一個(gè)非常不錯(cuò)的解決方案。</p><p>　　2.2.2.1 基于磁盤的順序存儲(chǔ)</p><p&g

42、t;　　這里，就是指把每個(gè)已經(jīng)下載過的URL進(jìn)行順序存儲(chǔ)。你可以把全部已經(jīng)下載完成的URL存放到磁盤記事本文件中。每次有一個(gè)爬蟲線程得到一個(gè)任務(wù)URL開始下載之前，通過到磁盤上的該文件中檢索，如果沒有出現(xiàn)過，則將這個(gè)新的URL寫入記事本的最后一行，否則就放棄該URL的下載。</p><p>　　這種方式幾乎沒有人考慮使用了，但是這種檢查的思想是非常直觀的。試想，如果已經(jīng)下載了100億網(wǎng)頁，那么對(duì)應(yīng)著100億個(gè)鏈接

43、，也就是這個(gè)檢查URL是否重復(fù)的記事本文件就要存儲(chǔ)這100億URL，況且，很多URL字符串的長度也不小，占用存儲(chǔ)空間不說，查找效率超級(jí)低下，這種方案肯定放棄。</p><p>　　2.2.2.2 基于Hash算法的存儲(chǔ)</p><p>　　對(duì)每一個(gè)給定的URL，都是用一個(gè)已經(jīng)建立好的Hash函數(shù)，映射到某個(gè)物理地址上。當(dāng)需要進(jìn)行檢測(cè)URL是否重復(fù)的時(shí)候，只需要將這個(gè)URL進(jìn)行Hash映射，

44、如果得到的地址已經(jīng)存在，說明已經(jīng)被下載過，放棄下載，否則，將該URL及其Hash地址作為鍵值對(duì)存放到Hash表中。</p><p>　　這樣，URL去重存儲(chǔ)庫就是要維護(hù)一個(gè)Hash表，如果Hash函數(shù)設(shè)計(jì)的不好，在進(jìn)行映射的時(shí)候，發(fā)生碰撞的幾率很大，則再進(jìn)行碰撞的處理也非常復(fù)雜。而且，這里使用的是URL作為鍵，URL字符串也占用了很大的存儲(chǔ)空間。</p><p>　　2.2.2.3 基于M

45、D5壓縮映射的存儲(chǔ)</p><p>　　MD5算法是一種加密算法，同時(shí)它也是基于Hash的算法。這樣就可以對(duì)URL字符串進(jìn)行壓縮，得到一個(gè)壓縮字符串，同時(shí)可以直接得到一個(gè)Hash地址。另外，MD5算法能夠?qū)⑷魏巫址畨嚎s為128位整數(shù)，并映射為物理地址，而且MD5進(jìn)行Hash映射碰撞的幾率非常小，這點(diǎn)非常好。從另一個(gè)方面來說，非常少的碰撞，對(duì)于搜索引擎的爬蟲是可以容忍的。況且，在爬蟲進(jìn)行檢測(cè)的過程中，可以通過記錄

46、日志來保存在進(jìn)行MD5時(shí)發(fā)生碰撞的URL，通過單獨(dú)對(duì)該URL進(jìn)行處理也是可行的。</p><p>　　在Java中有一個(gè)Map類非常好，你可以將壓縮后的URL串作為Key，而將Boolean作為Value進(jìn)行存儲(chǔ)，然后將工作中的Map在爬蟲停止工作后序列化到本地磁盤上；當(dāng)下一次啟動(dòng)新的爬蟲任務(wù)的時(shí)候，再將這個(gè)Map反序列化到內(nèi)存中，供爬蟲進(jìn)行URL去重檢測(cè)。</p><p>　　2.2.2

47、.4 基于嵌入式Berkeley DB的存儲(chǔ)</p><p>　　Berkeley DB的特點(diǎn)就是只存儲(chǔ)鍵值對(duì)類型數(shù)據(jù)，這和URL去重有很大關(guān)系。去重，可以考慮對(duì)某個(gè)鍵，存在一個(gè)值，這個(gè)值就是那個(gè)鍵的狀態(tài)。使用了Berkeley DB，你就不需要考慮進(jìn)行磁盤IO操作的性能損失了，這個(gè)數(shù)據(jù)庫在設(shè)計(jì)的時(shí)候很好地考慮了這些問題，并且該數(shù)據(jù)庫支持高并發(fā)，支持記錄的順序存儲(chǔ)和隨機(jī)存儲(chǔ)，是一個(gè)不錯(cuò)的選擇。</p>

48、<p>　　URL去重存儲(chǔ)庫使用Berkeley DB，壓縮后的URL字符串作為Key，或者直接使用壓縮后的URL字節(jié)數(shù)組作為Key，對(duì)于Value可以使用Boolean，一個(gè)字節(jié)，或者使用字節(jié)數(shù)組，實(shí)際Value只是一個(gè)狀態(tài)標(biāo)識(shí)，減少Value存儲(chǔ)占用存儲(chǔ)空間。</p><p>　　2.2.2.5 基于布隆過濾器（Bloom Filter）的存儲(chǔ)</p><p>　　使用布

49、隆過濾器，設(shè)計(jì)多個(gè)Hash函數(shù)，也就是對(duì)每個(gè)字符串進(jìn)行映射是經(jīng)過多個(gè)Hash函數(shù)進(jìn)行映射，映射到一個(gè)二進(jìn)制向量上，這種方式充分利用了比特位。不過，我沒有用過這種方式，有機(jī)會(huì)可以嘗試一下?？梢詤⒖糋oogle的http://www.googlechinablog.com/2007/07/bloom-filter.html。</p><p>　　2.2.3 LRU算法實(shí)現(xiàn)URL消重</p><p&

50、gt;　　用雙向鏈表來實(shí)現(xiàn)大容量cache的LRU算法。原理是：cache的所有位置都用雙向鏈表連接起來，當(dāng)一個(gè)位置被命中后，就將通過調(diào)整鏈表的指向?qū)⒃撐恢谜{(diào)整到鏈表的頭位置，新加入的內(nèi)容直接放在鏈表的頭上。這樣，在進(jìn)行過多次查找操作后，最近被命中過的內(nèi)容就像鏈表的頭移動(dòng)，而沒有命中過的內(nèi)容就向鏈表的后面移動(dòng)。當(dāng)需要替換時(shí)，鏈表最后的位置就是最近最少被命中位置，我們只需要將新的內(nèi)容放在鏈表前面，淘汰鏈表最后的位置就實(shí)現(xiàn)了LRU算法。&l

51、t;/p><p>　　2.3 URL類訪問網(wǎng)絡(luò)</p><p>　　JAVA提供了許多支Internet連接的類，URL類就是其中之一。在使用URL類之前，必須創(chuàng)建一個(gè)URL對(duì)象，創(chuàng)建的方法是使用其構(gòu)造函數(shù)，通過向其指定一個(gè)URL地址，就能實(shí)例化該類。如：URL url=new URL（http://www.sina.com.cn）；</p><p>　　如果傳遞無效的

52、URL給URL對(duì)象，該對(duì)象會(huì)拋出MalformedURLException異常。當(dāng)成功創(chuàng)建一個(gè)URL對(duì)象后，我們調(diào)用openConnection函數(shù)建立與URL的通信，此時(shí)，我們就獲得了一個(gè)URLConnection對(duì)象的引用，URLConnection類包含了許多與網(wǎng)絡(luò)上的URL通信的函數(shù)。在下載網(wǎng)頁前，我們需要判斷目標(biāo)網(wǎng)頁是否存在，這時(shí)調(diào)用URLConnection類的getHeaderField()方法，獲得服務(wù)器返回給SPIDE

53、R 程序的響應(yīng)碼，如果響應(yīng)碼包含”20*”字樣，表示目標(biāo)網(wǎng)頁存在，下一步就下載網(wǎng)頁，否則就不下載。getHeaderField()方法僅僅獲得服務(wù)器返回的頭標(biāo)志，其通信開銷是最小的，因此在下載網(wǎng)頁前進(jìn)行此測(cè)試，不僅能減小網(wǎng)絡(luò)流量，而且能提高程序效率。當(dāng)目標(biāo)網(wǎng)頁存在時(shí)2調(diào)用URLConnection類getInputStream()函數(shù)明確打開到URL的連接，獲取輸入流，再用java.io包中的InputStreamReader類讀取該輸

54、入流，將網(wǎng)頁下載下來。</p><p>　　2.4　爬行策略淺析</p><p>　　2.4.1寬度或深度優(yōu)先搜索策略</p><p>　　搜索引擎所用的第一代網(wǎng)絡(luò)爬蟲主要是基于傳統(tǒng)的圖算法, 如寬度優(yōu)先或深度優(yōu)先算法來索引整個(gè)Web, 一個(gè)核心的U RL 集被用來作為一個(gè)種子集合, 這種算法遞歸的跟蹤超鏈接到其它頁面, 而通常不管頁面的內(nèi)容, 因?yàn)樽罱K的目標(biāo)是這種

55、跟蹤能覆蓋整個(gè)Web. 這種策略通常用在通用搜索引擎中,因?yàn)橥ㄓ盟阉饕娅@得的網(wǎng)頁越多越好, 沒有特定的要求.</p><p>　　2.4.1.1　寬度優(yōu)先搜索算法</p><p>　　寬度優(yōu)先搜索算法(又稱廣度優(yōu)先搜索) 是最簡便的圖的搜索算法之一, 這一算法也是很多重要的圖的算法的原型. Dijkstra 單源最短路徑算法和Prim 最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想.寬度

56、優(yōu)先搜索算法是沿著樹的寬度遍歷樹的節(jié)點(diǎn), 如果發(fā)現(xiàn)目標(biāo), 則算法中止. 該算法的設(shè)計(jì)和實(shí)現(xiàn)相對(duì)簡單, 屬于盲目搜索. 在目前為覆蓋盡可能多的網(wǎng)頁, 一般使用寬度優(yōu)先搜索方法. 也有很多研究將寬度優(yōu)先搜索策略應(yīng)用于聚焦爬蟲中. 其基本思想是認(rèn)為與初始U RL 在一定鏈接距離內(nèi)的網(wǎng)頁具有主題相關(guān)性的概率很大. 另外一種方法是將寬度優(yōu)先搜索與網(wǎng)頁過濾技術(shù)結(jié)合使用, 先用廣度優(yōu)先策略抓取網(wǎng)頁, 再將其中無關(guān)的網(wǎng)頁過濾掉. 這些方法的缺點(diǎn)在于,

57、隨著抓取網(wǎng)頁的增多, 大量的無關(guān)網(wǎng)頁將被下載并過濾, 算法的效率將變低.</p><p>　　2.4.1.2　深度優(yōu)先搜索</p><p>　　深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索圖. 在深度優(yōu)先搜索中, 對(duì)于最新發(fā)現(xiàn)的頂點(diǎn), 如果它還有以此為起點(diǎn)而未探測(cè)到的邊, 就沿此邊繼續(xù)漢下去. 當(dāng)結(jié)點(diǎn)v 的所有邊都己被探尋過, 搜索將回溯到發(fā)現(xiàn)結(jié)點(diǎn)v 有那條邊的始結(jié)點(diǎn). 這一過程一直進(jìn)

58、行到已發(fā)現(xiàn)從源結(jié)點(diǎn)可達(dá)的所有結(jié)點(diǎn)為止. 如果還存在未被發(fā)現(xiàn)的結(jié)點(diǎn), 則選擇其中一個(gè)作為源結(jié)點(diǎn)并重復(fù)以上過程, 整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有結(jié)點(diǎn)都被發(fā)現(xiàn)為止. 深度優(yōu)先在很多情況下會(huì)導(dǎo)致爬蟲的陷入( trapped) 問題, 所以它既不是完備的, 也不是最優(yōu)的.</p><p>　　2.4.2 聚焦搜索策略</p><p>　　基于第一代網(wǎng)絡(luò)爬蟲的搜索引擎抓取的網(wǎng)頁一般少于1 000 000 個(gè)

59、網(wǎng)頁, 極少重新搜集網(wǎng)頁并去刷新索引. 而且其檢索速度非常慢, 一般都要等待10 s甚至更長的時(shí)間. 隨著網(wǎng)頁頁信息的指數(shù)級(jí)增長及動(dòng)態(tài)變化, 這些通用搜索引擎的局限性越來越大, 隨著科學(xué)技術(shù)的發(fā)展, 定向抓取相關(guān)網(wǎng)頁資源的聚焦爬蟲便應(yīng)運(yùn)而生.聚焦爬蟲的爬行策略只挑出某一個(gè)特定主題的頁面, 根據(jù)“最好優(yōu)先原則”進(jìn)行訪問, 快速、有效地獲得更多的與主題相關(guān)的頁面, 主要通過內(nèi)容和Web 的鏈接結(jié)構(gòu)來指導(dǎo)進(jìn)一步的頁面抓取[ 2 ]. <

60、/p><p>　　聚焦爬蟲會(huì)給它所下載下來的頁面分配一個(gè)評(píng)價(jià)分, 然后根據(jù)得分排序, 最后插入到一個(gè)隊(duì)列中. 最好的下一個(gè)搜索將通過對(duì)彈出隊(duì)列中的第一個(gè)頁面進(jìn)行分析而執(zhí)行, 這種策略保證爬蟲能優(yōu)先跟蹤那些最有可能鏈接到目標(biāo)頁面的頁面. 決定網(wǎng)絡(luò)爬蟲搜索策略的關(guān)鍵是如何評(píng)價(jià)鏈接價(jià)值, 即鏈接價(jià)值的計(jì)算方法, 不同的價(jià)值評(píng)價(jià)方法計(jì)算出的鏈接的價(jià)值不同, 表現(xiàn)出的鏈接的“重要程度”也不同, 從而決定了不同的搜索策略. 由于

61、鏈接包含于頁面之中,而通常具有較高價(jià)值的頁面包含的鏈接也具有較高的價(jià)值, 因而對(duì)鏈接價(jià)值的評(píng)價(jià)有時(shí)也轉(zhuǎn)換為對(duì)頁面價(jià)值的評(píng)價(jià). 這種策略通常運(yùn)用在專業(yè)搜索引擎中, 因?yàn)檫@種搜索引擎只關(guān)心某一特定主題的頁面.</p><p>　　2.4.3基于內(nèi)容評(píng)價(jià)的搜索策略</p><p>　　基于內(nèi)容評(píng)價(jià)的搜索策略[ 3, 4 ] , 主要是根據(jù)主題(如關(guān)鍵詞、主題相關(guān)文檔) 與鏈接文本的相似度來評(píng)價(jià)鏈

62、接價(jià)值的高低, 并以此決定其搜索策略: 鏈接文本是指鏈接周圍的說明文字和鏈接U RL 上的文字信息, 相似度的評(píng)價(jià)通常采用以下公式:</p><p>　　sim (d i, d j ) =Σmk= 1w ik ×w jk(Σmk= 1w 2ik ) (Σmk= 1w 2jk )</p><p>　　其中, di 為新文本的特征向量, d j 為第j 類的中心向量,m 為特征向量的

63、維數(shù),wk 為向量的第K 維.由于Web 頁面不同于傳統(tǒng)的文本, 它是一種半結(jié)構(gòu)化的文檔, 包含許多結(jié)構(gòu)信息Web 頁面不是單獨(dú)存在的, 頁面中的鏈接指示了頁面之間的相互關(guān)系, 因而有些學(xué)者提出了基于鏈接結(jié)構(gòu)評(píng)價(jià)鏈接價(jià)值的方法.</p><p>　　2.4.4 基于鏈接結(jié)構(gòu)評(píng)價(jià)的搜索策略</p><p>　　基于鏈接結(jié)構(gòu)評(píng)價(jià)的搜索策略, 是通過對(duì)Web頁面之間相互引用關(guān)系的分析來確定鏈接的

64、重要性, 進(jìn)而決定鏈接訪問順序的方法. 通常認(rèn)為有較多入鏈或出鏈的頁面具有較高的價(jià)值. PageRank 和Hits 是其中具有代表性的算法.</p><p>　　2.4.4.1　PageRank 算法</p><p>　　基于鏈接評(píng)價(jià)的搜索引擎的優(yōu)秀代表是Google (http://www.Google.com) , 它獨(dú)創(chuàng)的“鏈接評(píng)價(jià)體系”(PageRank 算法) 是基于這樣一種認(rèn)

65、識(shí), 一個(gè)網(wǎng)頁的重要性取決于它被其它網(wǎng)頁鏈接的數(shù)量, 特別是一些已經(jīng)被認(rèn)定是“重要”的網(wǎng)頁的鏈接數(shù)量. PageRank 算法最初用于Google 搜索引擎信息檢索中對(duì)查詢結(jié)果的排序過程[ 5 ] , 近年來被應(yīng)用于網(wǎng)絡(luò)爬蟲對(duì)鏈接重要性的評(píng)價(jià), PageRank 算法中, 頁面的價(jià)值通常用頁面的PageRank值表示, 若設(shè)頁面p 的PageRank 值為PR (p ) , 則PR (p ) 采用如下迭代公式計(jì)算:</p>

66、<p>　　PR (p ) = C 1T+ (1 - C) Σ C∈in (p )PR (p )ûou t (C) û</p><p>　　其中T 為計(jì)算中的頁面總量, C< 1 是阻尼常數(shù)因子, in (p ) 為所有指向p 的頁面的集合, out (C) 為頁面C出鏈的集合. 基于PageRank 算法的網(wǎng)絡(luò)爬蟲在搜索過程中, 通過計(jì)算每個(gè)已訪問頁面的PageRank 值

67、來確定頁面的價(jià)值, 并優(yōu)先選擇PageRank 值大的頁面中的鏈接進(jìn)行訪問.</p><p>　　2.4.4.2　H ITS 算法</p><p>　　HITS 方法定義了兩個(gè)重要概念: Authority 和Hub. Authority 表示一個(gè)權(quán)威頁面被其它頁面引用的數(shù)量, 即該權(quán)威頁面的入度值. 網(wǎng)頁被引用的數(shù)量越大, 則該網(wǎng)頁的Authority 值越大; Hub 表示一個(gè)Web

68、頁面指向其它頁面的數(shù)量, 即該頁面的出度值. 網(wǎng)頁的出度值越大, 其Hub 值越高. 由于Hub 值高的頁面通常都提供了指向權(quán)威頁面的鏈接, 因而起到了隱含說明某主題頁面權(quán)威性的作用.HITS (Hyperlink- Induced Top ic Search) 算法是利用HuböAuthority 方法的搜索方法,Authority表示一個(gè)頁面被其它頁面引用的數(shù)量, 即該頁面的入度值. Hub 表示一個(gè)Web 頁面指向其它頁

69、面的數(shù)量, 即該頁面的出度值. 算法如下: 將查詢q 提交給傳統(tǒng)的基于關(guān)鍵字匹配的搜索引擎. 搜索引擎返回很多網(wǎng)頁, 從中取前n 個(gè)網(wǎng)頁作為根集, 用S 表示.通過向S 中加入被S 引用的網(wǎng)頁和引用S 的網(wǎng)頁將S 擴(kuò)展成一個(gè)更大的集合T.以T 中的Hub 網(wǎng)頁為頂點(diǎn)集V l, 以權(quán)威網(wǎng)頁為頂點(diǎn)集V 2,V1 中的網(wǎng)頁到V 2 中</p><p>　　A (u) = Σ v: (v , u) ∈EH (v ) (1

70、)</p><p>　　H (v ) = Σ v: (v, u) ∈EA (v ) (2)</p><p>　　式(1) 反映了若一個(gè)網(wǎng)頁由很多好的Hub 指向, 則其權(quán)威值會(huì)相應(yīng)增加(即權(quán)威值增加為所有指向它的網(wǎng)頁的現(xiàn)有Hub 值之和). 式(2) 反映了若一個(gè)網(wǎng)頁指向許多好的權(quán)威頁, 則Hub 值也會(huì)相應(yīng)增加(即Hub 值增加為該網(wǎng)頁鏈接的所有網(wǎng)頁的權(quán)威值之和).雖然基于鏈接結(jié)構(gòu)價(jià)的搜

71、索考慮了鏈接的結(jié)構(gòu)和頁面之間的引用關(guān)系, 但忽略了頁面與主題的相關(guān)性, 在某些情況下, 會(huì)出現(xiàn)搜索偏離主題的問題. 另外, 搜索過程中需要重復(fù)計(jì)算PageRank 值或Authority 以及Hub 權(quán)重, 計(jì)算復(fù)雜度隨頁面和鏈接數(shù)量的增長呈指數(shù)級(jí)增長[ 6 ].</p><p>　　2.4.5 基于鞏固學(xué)習(xí)的聚焦搜索</p><p>　　近年來對(duì)Web 信息資源分布的研究表明很多類型相同

72、的網(wǎng)站在構(gòu)建方式上, 主題相同的網(wǎng)頁在組織方式上都存在著一定的相似性, 有的學(xué)者就考慮將鞏固學(xué)習(xí)引入網(wǎng)絡(luò)爬蟲的訓(xùn)練過程中, 從這些相似性獲取一些“經(jīng)驗(yàn)”, 而這些經(jīng)驗(yàn)信息在搜索距相關(guān)頁面集較遠(yuǎn)的地方往往能獲得較好的回報(bào), 而前兩種策略在這種情況下容易迷失方向.在鞏固學(xué)習(xí)模型中, 把網(wǎng)絡(luò)爬蟲經(jīng)過若干無關(guān)頁面的訪問之后才能獲得的主題相關(guān)頁面稱為未來回報(bào), 對(duì)未來回報(bào)的預(yù)測(cè)值稱為未來回報(bào)價(jià)值, 用Q價(jià)值表示. 這種方法的核心就是學(xué)習(xí)如何計(jì)算鏈

73、接的Q 價(jià)值, 根據(jù)未來回報(bào)價(jià)值確定正確的搜索方向. 目前這類搜索策略不足之處在于學(xué)習(xí)效率低的問題, 而且在訓(xùn)練過程中增加了用戶的負(fù)擔(dān).</p><p>　　2.4.6 基于語境圖的聚焦搜索</p><p>　　基于鞏固學(xué)習(xí)的網(wǎng)絡(luò)爬蟲通過計(jì)算鏈接的Q價(jià)值可以確定搜索方向, 但它卻無法估計(jì)距離目標(biāo)頁面的遠(yuǎn)近. 為此, Diligent 等提出了基于“語境圖”的搜索策略, 它通過構(gòu)建典型頁面的

74、web“語境圖”來估計(jì)離目標(biāo)頁面的距離, 距離較近的頁面較早得到訪問[ 7 ].基于“語境圖”的搜索策略需要借助已有的通用搜索引擎構(gòu)建“語境圖”, 而搜索引擎的檢索結(jié)果并非一定代表真實(shí)的web 結(jié)構(gòu), 因而這種方式也具有局限性.</p><p>　　第三章 系統(tǒng)需求分析及模塊設(shè)計(jì)</p><p>　　3.1 系統(tǒng)需求分析</p><p>　　SPIDER要獲取的對(duì)象

75、是存在于網(wǎng)絡(luò)上數(shù)以億計(jì)的網(wǎng)頁，這些網(wǎng)頁以超鏈接形式互相聯(lián)系在一起，每一網(wǎng)頁對(duì)應(yīng)一個(gè)超鏈接，也稱統(tǒng)一資源定位符（URL）。我們可以把網(wǎng)絡(luò)看做一個(gè)圖M(V,E)，網(wǎng)絡(luò)中的網(wǎng)頁構(gòu)成節(jié)點(diǎn)集V，他們之間的鏈接構(gòu)成邊集E，SPIDER正是從某一節(jié)點(diǎn)開始，沿著邊，遍歷圖M，每訪問到圖中一個(gè)節(jié)點(diǎn)Vi，就進(jìn)行一定的處理。</p><p>　　為了達(dá)到上述目的，一個(gè)SPIDER必須被設(shè)計(jì)成多線程的，A 個(gè)線程并發(fā)地在網(wǎng)絡(luò)上協(xié)同工作，

76、才有可能在盡可能短的時(shí)間內(nèi)遍歷完網(wǎng)絡(luò)中的網(wǎng)頁。但網(wǎng)頁數(shù)目是如此之大，如果任SPIDER程序無窮地搜索下去，那么程序幾乎不能終止。所以我們限制SPIDER每次工作只訪問一個(gè)站點(diǎn)。一個(gè)再大型的站點(diǎn)，其中的網(wǎng)頁數(shù)目也是有限的，因此SPIDER程序能在有限的時(shí)間內(nèi)結(jié)束。</p><p>　　當(dāng)SPIDER程序訪問到一個(gè)網(wǎng)頁，必須進(jìn)行以下幾項(xiàng)基本處理：抽取網(wǎng)頁中包含的文本；抽取網(wǎng)頁中包含的URL，并將其區(qū)分為網(wǎng)站內(nèi)URL或

77、網(wǎng)站外URL。</p><p>　　3.2 SPIDER體系結(jié)構(gòu)</p><p>　　此爬蟲程序主要分為三個(gè)部分：任務(wù)執(zhí)行端，任務(wù)調(diào)度端，數(shù)據(jù)服務(wù)端。每一個(gè)SPIDER 任務(wù)執(zhí)行端關(guān)聯(lián)一個(gè)站點(diǎn),一個(gè)線程下載一個(gè)基于URL 鏈接的頁面, 并進(jìn)行Web 頁面解析, 得到站內(nèi)URL 和發(fā)現(xiàn)新站點(diǎn)URL另外,將URL 隊(duì)列持久化到數(shù)據(jù)庫, 因此在SPIDER 任務(wù)執(zhí)行端以外Down 掉后, 能

78、夠斷點(diǎn)續(xù)傳.</p><p>　　SPIDER 客戶端線程間的協(xié)調(diào)通信采用Java 的線程同步技術(shù)synchronized,在數(shù)據(jù)服務(wù)端中對(duì)URL 進(jìn)行緩存提高了系統(tǒng)處理速度. SPIDER 的任務(wù)執(zhí)行和任務(wù)調(diào)度端都需要維持一個(gè)URL 隊(duì)列: 任務(wù)執(zhí)行端的URL 隊(duì)列中存儲(chǔ)了站內(nèi)URL; 任務(wù)調(diào)度端則是站點(diǎn)的URL. 在這些URL 隊(duì)列上有大量的操作, 包括URL 查找、 URL 插入、URL 狀態(tài)更新等. 如果

79、SPIDER 以300 頁ö秒的速度下載Web 頁面, 平均將會(huì)產(chǎn)生2000 多個(gè)URL [12] , 因此簡單的采用內(nèi)存數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)這些URL 隊(duì)列有一定的問題, 系統(tǒng)沒有足夠的內(nèi)存空間;而采用直接持久化到數(shù)據(jù)庫, 則需要大量的數(shù)據(jù)庫連接、查詢等操作, 系統(tǒng)效率會(huì)明顯下降. 如果采用URL 壓縮的辦法,盡管在一定程度上可以平衡空間和時(shí)間的矛盾, 但仍然不適用于大規(guī)模數(shù)據(jù)采集的SPIDER.</p><p&

80、gt;　　圖3.2 SPIDER體系結(jié)</p><p>　　3.3 各主要功能模塊（類）設(shè)計(jì)</p><p>　　SPIDERWorker類：該類繼承自線程類，請(qǐng)求任務(wù)URL，根據(jù)得到的URL下載相應(yīng)的HTML代碼，利用HTML代碼調(diào)用其他模塊完成相關(guān)處理。</p><p>　　SPIDERManager類：該類用于控制SPIDERWorker線程。</p&g

81、t;<p>　　UrlQueueManager類：該類用于維護(hù)URL等待隊(duì)列，分配任務(wù)URL，URL消重模塊。</p><p>　　UrlParse類：用于解析HTML，獲取并過濾URL。</p><p>　　DateBaseConnect類：用于提供數(shù)據(jù)庫連接。</p><p>　　3.4 SPIDER工作過程</p><p>

82、;　　①將給定的初始URL加入到URL等待隊(duì)列。</p><p>　?、趧?chuàng)建爬蟲線程，啟動(dòng)爬蟲線程</p><p>　?、勖總€(gè)爬蟲線程從URL等待隊(duì)列中取得任務(wù)URL。然后根據(jù)URL下載網(wǎng)頁，然后解析網(wǎng)頁，獲取超鏈接URLs。如果獲取到的URL為相對(duì)地址，需要轉(zhuǎn)換為絕對(duì)地址，然后淘汰站外URLs，錯(cuò)誤URLs或者不能解析的URL地址。再判斷這些URL是否已經(jīng)被下載到，如果沒有則加入到URL

83、等待隊(duì)列。</p><p>　　④繼續(xù)執(zhí)行步驟③，直到結(jié)束條件停止。</p><p>　　第四章 系統(tǒng)分析與設(shè)計(jì)</p><p>　　4.1 SPIDER構(gòu)造分析</p><p>　　構(gòu)造SPIDER 程序有兩種方式：（1）把SPIDER 程序設(shè)計(jì)為遞歸的程序；（2）編寫一個(gè)非遞歸的程序，它要維護(hù)一個(gè)要訪問的網(wǎng)頁列表。考慮使用哪一種方式的前提

84、是，構(gòu)造的SPIDER 程序必須能夠訪問非常大的Web 站點(diǎn)。本系統(tǒng)中使用了非遞歸的程序設(shè)計(jì)方法。這是因?yàn)?，?dāng)一個(gè)遞歸程序運(yùn)行時(shí)要把每次遞歸壓入堆棧，但在本系統(tǒng)設(shè)計(jì)中使用的是多線程，它允許一次運(yùn)行多個(gè)任務(wù)，但是，多線程與遞歸是不兼容的。因?yàn)樵谶@一過程中每一個(gè)線程都有自己的堆棧，而當(dāng)一個(gè)方法調(diào)用它自身時(shí)，它們需要使用同一個(gè)堆棧。這就意味著遞歸的SPIDER 程序不能使用多線程。</p><p>　　每個(gè)SPIDER

85、線程都會(huì)獨(dú)立的去完成獲取URLs的任務(wù)，并將獲取到的URLs加入一個(gè)公共的URL等待隊(duì)列中。</p><p><b>　　圖4.1</b></p><p>　　圖4.1表示了該系統(tǒng)爬蟲線程的實(shí)現(xiàn)策略。假設(shè)線程1從URL隊(duì)列中獲取一條任務(wù)URL 1，然后它會(huì)下載對(duì)應(yīng)的HTML，解析出里面包含URLs，然后再將這些URLs加入到URL隊(duì)列中去。然后線程1會(huì)再從URL隊(duì)列中

86、獲取新的URL，下載HTML代碼，并解析出URLs，再加入到URL隊(duì)列中去。而線程2同時(shí)也會(huì)下載它獲取到的URL 2對(duì)應(yīng)的HTML代碼，解析出URLs加入到等待隊(duì)列中。以此類推，多個(gè)線程并發(fā)地去完成爬蟲工作。</p><p>　　4.2 爬行策略分析</p><p><b>　　圖 4.2.1</b></p><p>　　因?yàn)楸菊撐膶?shí)現(xiàn)的爬蟲程

87、序的初衷是盡可能遍歷某一站點(diǎn)所有的頁面。廣度優(yōu)先算法的實(shí)行理論是覆蓋更多的節(jié)點(diǎn)，所以此爬蟲程序選擇了廣度優(yōu)先算法。實(shí)現(xiàn)的策略是：先獲取初始URL對(duì)應(yīng)HTML代碼里所有的URLs。然后依次獲取這些URLs對(duì)應(yīng)的HTML里的URLs，當(dāng)這一層所有的URLs都下載解析完后，在獲取下一層的信息。通過這種循環(huán)的獲取方式實(shí)現(xiàn)廣度優(yōu)先爬行。</p><p>　　如圖4.2.1，假如a代表初始URL，bcd為以a獲取的3個(gè)URL

88、s，efg為以b獲取的URLs，以此類推。那么這些URLs獲取的順序就是abcdefghijklmnop這樣一個(gè)順序。當(dāng)獲取到b的URLs之后，并不會(huì)馬上去解析這些URLs，而是先解析同b在同一層中的cd對(duì)應(yīng)的URLs。當(dāng)這一層URLs全部解析完后，再開始下一層URLs。</p><p>　　廣度優(yōu)先算法的等待隊(duì)列設(shè)計(jì)如圖4.2.2所示。</p><p><b>　　圖 4.2.

89、2</b></p><p>　　圖4.2.2列舉了不同時(shí)間段時(shí)，URL等待隊(duì)列的存儲(chǔ)狀態(tài)。第一個(gè)方框是將初始URL：a加入到等待隊(duì)列。第二個(gè)方框?yàn)椋馕鯽對(duì)應(yīng)HTML獲取URLs：bcd，同時(shí)刪除a。第三個(gè)方框?yàn)?，解析b對(duì)應(yīng)HTML獲取URLs：efg，同時(shí)刪除URL：b。第四個(gè)方框?yàn)?，解析e對(duì)應(yīng)HTML獲取URLs：nop，并刪除e。通過這樣的存儲(chǔ)方法實(shí)現(xiàn)如圖4.2.1的廣度爬行算法。</p&

90、gt;<p>　　4.3 URL抽取，解析和保存</p><p>　　4.3.1 URL抽取</p><p>　　通過觀察研究HTML代碼，我們可以知道。HTML代碼中，頁面之間的跳轉(zhuǎn)，關(guān)聯(lián)是通過href標(biāo)簽來實(shí)現(xiàn)的。我們需要獲取HTML代碼中的URLs，就可以通過尋找href標(biāo)簽來達(dá)到目的。</p><p>　　<li><a hre

91、f=movie_2004/html/6664.html target=_blank>我猜[20090531]</a><em>5-31</em></li></p><p>　　<li><a href="movie_2004/html/2088.html?2009528224729.html" target="_bl

92、ank">火影忍者[331，頁面上303既是]</a></li></p><p>　　通過觀察得知，一般href標(biāo)簽是以href=這樣的形式出現(xiàn)的。但是不同的網(wǎng)站href=后面的內(nèi)容有所不同。比如href=”url”這樣情況，我們就可以通過截取雙引號(hào)之間的內(nèi)容來獲取URL；如果是href=’url’這種情況，我們就需要截取單引號(hào)之間的內(nèi)容來獲取URL；或者有些是href=u

93、rl，我們需要以等號(hào)為開始標(biāo)記，而這種情況通常結(jié)尾是空格或者>符號(hào)。</p><p>　　通過這種方法，我們獲取網(wǎng)頁中大部分的URLs。但是有些URLs是通過提交表單，或者通過javascript來跳轉(zhuǎn)的。這些情況就需要更細(xì)致的考慮，才能獲取。</p><p>　　4.3.2 URL解析</p><p>　　截取出來的字符串，可能為相對(duì)地址或者絕對(duì)地址。所以需

94、要判斷URL為絕對(duì)地址，還是相對(duì)地址。相對(duì)地址需要先轉(zhuǎn)化為絕對(duì)地址，再進(jìn)行過濾。因?yàn)榻馕龀鰜淼腢RL地址可能是一些文件的地址，或者為javascript文件或者css文件。這些格式的URL是無法獲取HTML代碼的，也就不可能進(jìn)行URL解析。所以我們需要過濾掉這些URLs。然后再進(jìn)行URL消重處理，最后加入到URL等待隊(duì)列。</p><p>　　為了把爬行限制在同一站點(diǎn)內(nèi)需要截?cái)嘀赶蛘就獾逆溄?保證SPIDER總在

95、站內(nèi)執(zhí)行,即準(zhǔn)確地根據(jù)超鏈URL判斷超鏈?zhǔn)欠裰赶蛘就?由RFC對(duì)URL的定義可知,URL的格式為[protocol://host:port/path?query],一般情況下,同一網(wǎng)站內(nèi)所有頁面對(duì)應(yīng)URL的host是相同的,所以可以使用host匹配作為判斷超鏈?zhǔn)欠裰赶蛘就獾臉?biāo)準(zhǔn). 進(jìn)一步研究發(fā)現(xiàn),很多大型網(wǎng)站中一個(gè)分類目錄對(duì)應(yīng)一個(gè)主機(jī), 所以前面的判斷標(biāo)準(zhǔn)必須改進(jìn).研究host的組成可知, host的格式一般為[站內(nèi)分類.站點(diǎn)標(biāo)志串.站

96、點(diǎn)類型各異的串].站點(diǎn)類型串只有[ com |edu|gov|net| 國家域名]幾種類型,所以我們?nèi)≌军c(diǎn)類型各異串前面的串,即站點(diǎn)標(biāo)志串作匹配,超鏈URL的host中是否包含此串,為超鏈?zhǔn)欠裾緝?nèi)的判斷標(biāo)準(zhǔn).</p><p>　　4.3.3 URL保存</p><p>　　因?yàn)榈却齍RLs的數(shù)目非常多，如果全部采用List來存儲(chǔ)非常的占用內(nèi)存空間。所以將等待URLs存入數(shù)據(jù)庫中，并設(shè)計(jì)2個(gè)

97、緩存區(qū)，用于向隊(duì)列中加入和取得URLs。URL等待隊(duì)列設(shè)計(jì)成三段式：第一段為一個(gè)List,用來加入新得到的URL。當(dāng)這個(gè)List中的數(shù)目過多時(shí)，則將List中的內(nèi)容加入到數(shù)據(jù)庫，并清空該List，以便加入新的URLs；第二段為數(shù)據(jù)庫，當(dāng)?shù)谝欢螖?shù)據(jù)過多時(shí)，將第一段內(nèi)的數(shù)據(jù)存入數(shù)據(jù)庫；第三段也為一個(gè)List，從這里面分配任務(wù)URL，當(dāng)該List內(nèi)URL不足時(shí)，將數(shù)據(jù)庫里的數(shù)據(jù)再轉(zhuǎn)存入。</p><p>　　圖4.3.

98、3表示了URL等待隊(duì)列的結(jié)構(gòu)。</p><p><b>　　圖4.3.3</b></p><p><b>　　第五章 系統(tǒng)實(shí)現(xiàn)</b></p><p><b>　　5.1 實(shí)現(xiàn)工具</b></p><p>　　操作系統(tǒng)是winXP;JAVA程序的編寫工具是eclipse-SDK

99、-3.2.1-win32；數(shù)據(jù)庫是MYSQL 5 5.0.51a。</p><p><b>　　5.2 爬蟲工作</b></p><p>　　這個(gè)類繼承自線程類，實(shí)現(xiàn)線程在java中有兩種方法：一種是直接繼承Thread類；一種是實(shí)現(xiàn)Runnable接口。我采用了第二種方法：</p><p>　　public class SpiderWorke

100、r implements Runnable {</p><p>　　在這個(gè)類中必須要實(shí)現(xiàn)重寫run()這個(gè)方法。我在這個(gè)方法里定義了一個(gè)循環(huán)，這個(gè)線程會(huì)重復(fù)地執(zhí)行爬蟲動(dòng)作。</p><p>　　在這個(gè)循環(huán)里，首先會(huì)向URL等待隊(duì)列里請(qǐng)求一個(gè)URL。因?yàn)閁RL隊(duì)列會(huì)出現(xiàn)為空或者被其他線程占用的情況。所以我在這里寫了一個(gè)循環(huán)：</p><p><b>　　s

101、= null;</b></p><p>　　while (s == null) {</p><p>　　s = urlQueueManager.getWaitQueue();</p><p><b>　　}</b></p><p>　　如果沒有得到URL就繼續(xù)向URL等待隊(duì)列申請(qǐng)。</p>&l

102、t;p>　　當(dāng)?shù)玫饺蝿?wù)URL以后，會(huì)通過這個(gè)URL得到對(duì)應(yīng)的HTML代碼。具體方法是調(diào)用getHtml(String sourse_url)這個(gè)方法：</p><p>　　HttpURLConnection connection = null;</p><p>　　InputStreamReader in = null;</p><p>　　BufferedR

103、eader br = null;</p><p>　　URL url = null;</p><p>　　url = new URL(sourse_url);</p><p>　　connection = (HttpURLConnection) url.openConnection();</p><p>　　connection.c

104、onnect();</p><p>　　// 打開的連接讀取的輸入流。</p><p>　　in = new InputStreamReader(url.openStream());</p><p>　　br = new BufferedReader(in);</p><p><b>　　String c;</b><

105、;/p><p>　　while ((c = br.readLine()) != null) {</p><p>　　html.append(c);</p><p><b>　　}</b></p><p>　　return html.toString();</p><p>　　這個(gè)方法是通過調(diào)用JAVA

106、里面的URL這個(gè)類，可以用給定的URL構(gòu)造這個(gè)類的一個(gè)實(shí)例，然后通過openStream()這個(gè)方法得到HTML代碼的數(shù)據(jù)流，然后再一行一行地把數(shù)據(jù)流轉(zhuǎn)換成String字符串，再用StringBuffer將這些字符串拼接成一個(gè)完整的HTML代碼。</p><p>　　當(dāng)?shù)玫紿TML代碼以后，程序就會(huì)調(diào)用Url_Parse這個(gè)類里面的方法來解析HTML。</p><p><b>　

107、　5.3 URL解析</b></p><p>　　從HTML代碼中提取URLs，主要是通過檢索字符串中的href字符串來實(shí)現(xiàn)的。對(duì)于一個(gè)HTML代碼，我尋找其中的href=字符串，然后記錄它的下表i。然后判斷下表i+1位置上的字符是雙引號(hào)，單引號(hào)或者兩者皆不是，然后選擇對(duì)應(yīng)的字符作為截取URL的終止標(biāo)記。截取過后的href標(biāo)記就剔除它與它前面的部分，以便而后的操作可以繼續(xù)檢索href標(biāo)記，直到正個(gè)HT

108、ML代碼中所有的href標(biāo)記都被解析過后，操作終止。</p><p>　　<a href="http://www.tom365.com/" class="focu">首頁</a><a href=’movie_2004/mlist/1_1.html’ target=_self>動(dòng)作片</a><a href=movie_20