畢業(yè)設(shè)計(jì)---網(wǎng)絡(luò)爬蟲(chóng)的設(shè)計(jì)與實(shí)現(xiàn)

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

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

9、p><p>　　2.2.3 LRU算法實(shí)現(xiàn)URL消重7</p><p>　　2.3 URL類訪問(wèn)網(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 基于語(yǔ)境圖的聚焦搜索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工作過(guò)程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 爬蟲(chóng)工作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ù)庫(kù)設(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>　　第一章 引言</b></p><p>　　隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)上的信息呈爆炸式增長(zhǎng)。這使得人們?cè)诰W(wǎng)上找到所需的信息越來(lái)越困難，這種情況下搜索引擎應(yīng)運(yùn)而生。搜索引擎搜集互聯(lián)網(wǎng)上數(shù)以億計(jì)的網(wǎng)頁(yè)，并為每個(gè)詞建立索引。在建立搜索引擎的過(guò)程中，搜集網(wǎng)頁(yè)是非常重要的一個(gè)環(huán)節(jié)。爬蟲(chóng)程序就是用來(lái)搜集網(wǎng)頁(yè)的程序。以何種策略偏歷互聯(lián)網(wǎng)上的網(wǎng)頁(yè)，也成了爬蟲(chóng)程序主要的研究方向?，F(xiàn)在比較流行的搜索引擎，比如

16、google，百度，它們爬蟲(chóng)程序的技術(shù)內(nèi)幕一般都不公開(kāi)。目前幾種比較常用的爬蟲(chóng)實(shí)現(xiàn)策略：廣度優(yōu)先的爬蟲(chóng)程序，Repetitive爬蟲(chóng)程序，定義爬行爬蟲(chóng)程序，深層次爬行爬蟲(chóng)程序。此外, 還有根據(jù)概率論進(jìn)行可用Web頁(yè)的數(shù)量估算, 用于評(píng)估互聯(lián)網(wǎng)Web規(guī)模的抽樣爬蟲(chóng)程序; 采用爬行深度、頁(yè)面導(dǎo)入鏈接量分析等方法, 限制從程序下載不相關(guān)的Web頁(yè)的選擇性爬行程序等等。</p><p>　　爬蟲(chóng)程序是一個(gè)自動(dòng)獲取網(wǎng)頁(yè)的程

17、序。它為搜索引擎從互聯(lián)網(wǎng)上下載網(wǎng)頁(yè)，是搜索引擎的重要組成部分。爬蟲(chóng)程序的實(shí)現(xiàn)策略，運(yùn)行效率直接影響搜索引擎的搜索結(jié)果。不同的搜索引擎，會(huì)根據(jù)對(duì)搜索結(jié)果的不同需求，選擇最合適的爬行策略來(lái)搜集互聯(lián)網(wǎng)上的信息。高效，優(yōu)秀的爬蟲(chóng)程序可以使人們?cè)诨ヂ?lián)網(wǎng)上尋找到更及時(shí)，更準(zhǔn)確的信息。</p><p>　　實(shí)現(xiàn)網(wǎng)絡(luò)爬蟲(chóng)的重點(diǎn)和難點(diǎn)有：多線程的實(shí)現(xiàn)；對(duì)臨界資源的分配；遍歷web圖的遍歷策略選擇和實(shí)現(xiàn)；存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的選擇和實(shí)現(xiàn)。&

18、lt;/p><p>　　本文通過(guò)JAVA語(yǔ)言實(shí)現(xiàn)一個(gè)基于廣度優(yōu)先偏歷算法的多線程爬蟲(chóng)程序。通過(guò)實(shí)現(xiàn)此爬蟲(chóng)程序可以定點(diǎn)搜集某一站點(diǎn)的URLs，如果需要搜集其他信息，可以在解析URLs的同時(shí)，解析獲取相應(yīng)信息。</p><p>　　第二章 相關(guān)技術(shù)介紹</p><p>　　2.1 JAVA線程</p><p>　　2.1.1 線程概述</p&g

19、t;<p>　　幾乎每種操作系統(tǒng)都支持線程的概念—進(jìn)程就是在某種程度上相互隔離的，獨(dú)立運(yùn)行的程序。一般來(lái)說(shuō)，這些操作系統(tǒng)都支持多進(jìn)程操作。所謂多進(jìn)程，就是讓系統(tǒng)（好像）同時(shí)運(yùn)行多個(gè)程序。比如，我在Microsoft Word編寫(xiě)本論文的時(shí)候，我還打開(kāi)了一個(gè)mp3播放器來(lái)播放音樂(lè)，偶爾的，我還會(huì)再編輯Word的同時(shí)讓我的機(jī)器執(zhí)行一個(gè)打印任務(wù)，而且我還喜歡通過(guò)IE從網(wǎng)上下載一個(gè)Flash動(dòng)畫(huà)。對(duì)于我來(lái)說(shuō)，這些操作都是同步進(jìn)行的

20、，我不需要等一首歌曲放完了再來(lái)編輯我的論文?？雌饋?lái)，它們都同時(shí)在我的機(jī)器上給我工作。</p><p>　　事實(shí)的真相是，對(duì)于一個(gè)CPU而言，它在某一個(gè)時(shí)間點(diǎn)上，只能執(zhí)行一個(gè)程序。CPU不斷的在這些程序之間“跳躍”執(zhí)行。那么，為什么我們看不出任何的中斷現(xiàn)象呢？這是因?yàn)椋鄬?duì)于我們的感覺(jué)，它的速度實(shí)在太快了。我們?nèi)说母兄獣r(shí)間可能以秒來(lái)計(jì)算。而對(duì)于CPU而言，它的時(shí)間是以毫秒來(lái)計(jì)算的，從我們?nèi)庋劭磥?lái)，它們就是一個(gè)連續(xù)的

21、動(dòng)作。</p><p>　　因此，雖然我們看到的都是一些同步的操作，但實(shí)際上，對(duì)于計(jì)算機(jī)而言，它在某個(gè)時(shí)間點(diǎn)上只能執(zhí)行一個(gè)程序，除非你的計(jì)算機(jī)是多CPU的。</p><p>　　多線程（Multi-Thread）擴(kuò)展了多進(jìn)程（multi-Process）操作的概念，將任務(wù)的劃分下降到了程序級(jí)別，使得各個(gè)程序似乎可以在同一個(gè)時(shí)間內(nèi)執(zhí)行多個(gè)任務(wù)。每個(gè)任務(wù)稱為一個(gè)線程，能夠同時(shí)運(yùn)行多個(gè)線程的程序

22、稱為多線程程序。</p><p>　　多線程和多進(jìn)程有什么區(qū)別呢？對(duì)于進(jìn)程來(lái)說(shuō)，每個(gè)進(jìn)程都有自己的一組完整的變量，而線程則共享相同的數(shù)據(jù)。</p><p>　　2.1.2 JAVA線程模型</p><p>　　我們知道，計(jì)算機(jī)程序得以執(zhí)行的三個(gè)要素是：CPU，程序代碼，可存取的數(shù)據(jù)。在JAVA語(yǔ)言中，多線程的機(jī)制是通過(guò)虛擬CPU來(lái)實(shí)現(xiàn)的?？梢孕蜗蟮睦斫鉃?在一個(gè)J

23、AVA程序內(nèi)部虛擬了多臺(tái)計(jì)算機(jī)，每臺(tái)計(jì)算機(jī)對(duì)應(yīng)一個(gè)線程，有自己的CPU，可以獲取所需的代碼和數(shù)據(jù)，因此能獨(dú)立執(zhí)行任務(wù)，相互間還可以共用代碼和數(shù)據(jù)。JAVA的線程是通過(guò)java.lang.Thread類來(lái)實(shí)現(xiàn)的，它內(nèi)部實(shí)現(xiàn)了虛擬CPU的功能，能夠接收和處理傳遞給它的代碼和數(shù)據(jù)，并提供了獨(dú)立的運(yùn)行控制功能。</p><p>　　我們知道，每個(gè)JAVA應(yīng)用程序都至少有一個(gè)線程，這就是所謂的主線程。它由JVM創(chuàng)建并調(diào)用J

24、AVA應(yīng)用程序的main（）方法。</p><p>　　JVM還通常會(huì)創(chuàng)建一些其他的線程，不過(guò)，這些線程對(duì)我們而言通常都是不可見(jiàn)的。比如，用于自動(dòng)垃圾收集的線程，對(duì)象終止或者其他的JVM處理任務(wù)相關(guān)的線程。</p><p>　　2.1.3 創(chuàng)建線程</p><p>　　2.1.3.1 創(chuàng)建線程方式一</p><p>　　在JAVA中創(chuàng)建線程的

25、一種方式是通過(guò)Thread來(lái)實(shí)現(xiàn)的。Thread有很多個(gè)構(gòu)造器來(lái)創(chuàng)建一個(gè)線程（Thread）實(shí)例：</p><p>　　Thread();創(chuàng)建一個(gè)線程。</p><p>　　Thread(Runnable target);創(chuàng)建一個(gè)線程，并指定一個(gè)目標(biāo)。</p><p>　　Thread(Runnable target,String name);創(chuàng)建一個(gè)名為name的

26、目標(biāo)為target的線程。</p><p>　　Thread(String name);創(chuàng)建一個(gè)名為name的線程。</p><p>　　Thread(ThreadGroup group,Runnable target);創(chuàng)建一個(gè)隸屬于group線程組，目標(biāo)為target的線程。</p><p>　　通常，我們可以將一個(gè)類繼承Thread，然后，覆蓋Thread中的

27、run()方法，這樣讓這個(gè)類本身也就成了線程。</p><p>　　每個(gè)線程都是通過(guò)某個(gè)特定Thread對(duì)象所對(duì)應(yīng)的方法run()來(lái)完成其操作的，方法run()稱為線程體。</p><p>　　使用start()方法，線程進(jìn)入Runnable狀態(tài)，它將線程調(diào)度器注冊(cè)這個(gè)線程。調(diào)用start()方法并不一定馬上會(huì)執(zhí)行這個(gè)線程，正如上面所說(shuō)，它只是進(jìn)入Runnble而不是Running。<

28、;/p><p>　　2.1.3.2 創(chuàng)建線程方式二</p><p>　　通過(guò)實(shí)現(xiàn)Runnable接口并實(shí)現(xiàn)接口中定義的唯一方法run()，可以創(chuàng)建一個(gè)線程。在使用Runnable接口時(shí)，不能直接創(chuàng)建所需類的對(duì)象并運(yùn)行它，而是必須從Thread類的一個(gè)實(shí)例內(nèi)部運(yùn)行它。</p><p>　　從上面兩種創(chuàng)建線程的方法可以看出，如果繼承Thread類，則這個(gè)類本身可以調(diào)用sta

29、rt方法，也就是說(shuō)將這個(gè)繼承了Thread的類當(dāng)作目標(biāo)對(duì)象；而如果實(shí)現(xiàn)Runnable接口，則這個(gè)類必須被當(dāng)作其他線程的目標(biāo)對(duì)象。</p><p>　　2.1.4 JAVA中的線程的生命周期</p><p>　　JAVA的線程從產(chǎn)生到消失,可分為5種狀態(tài)：新建（New），可運(yùn)行（Runnable），運(yùn)行（Running），阻塞（Blocked）以及死亡（Dead）。其中，Running狀態(tài)

30、并非屬于JAVA規(guī)范中定義的線程狀態(tài)，也就是說(shuō)，在JAVA規(guī)范中，并沒(méi)有將運(yùn)行（Running）狀態(tài)真正的設(shè)置為一個(gè)狀態(tài)，它屬于可運(yùn)行狀態(tài)的一種。</p><p>　　當(dāng)使用new來(lái)新建一個(gè)線程時(shí)，它處于New狀態(tài)，這個(gè)時(shí)候，線程并未進(jìn)行任何操作。</p><p>　　然后，調(diào)用線程的start()方法，來(lái)向線程調(diào)度程序（通常是JVM或操作系統(tǒng)）注冊(cè)一個(gè)線程，這個(gè)時(shí)候，這個(gè)線程一切就緒，就

31、等待CPU時(shí)間了。</p><p>　　線程調(diào)度程序根據(jù)調(diào)度策略來(lái)調(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)行完畢，線程將被拋棄，進(jìn)入死亡狀態(tài)。你不能調(diào)用restart方法來(lái)重新開(kāi)始一個(gè)處于死亡狀態(tài)的線程，但是，你可以調(diào)用處于死亡狀態(tài)的線程對(duì)象的各個(gè)方法。</p><p>　　如果線程在運(yùn)行（R

32、unning）狀態(tài)中因?yàn)镮/O阻塞，等待鍵盤(pán)鍵入，調(diào)用了線程的sleep方法，調(diào)用了對(duì)象的wait()方法等，則線程將進(jìn)入阻塞狀態(tài)，直到這些阻塞原因被解除，如：IO完成，鍵盤(pán)輸入了數(shù)據(jù)，調(diào)用sleep方法后的睡眠時(shí)間到以及其他線程調(diào)用了對(duì)象的notify或notifyAll方法來(lái)喚醒這個(gè)因?yàn)榈却枞木€程等，線程將返回到Runnable狀態(tài)重新等待調(diào)度程序調(diào)度，注意，被阻塞的線程不會(huì)直接返回到Running狀態(tài)，而是重新回到Runna

33、ble狀態(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)行的線程從Running狀態(tài)“踢出”,讓它回到Runnable狀態(tài)。</p><p>　　2.1.5 JAVA線程的結(jié)束方式</p><p>　　線程

34、會(huì)以以下三種方式之一結(jié)束：</p><p>　　線程到達(dá)其run()方法的末尾；</p><p>　　線程拋出一個(gè)未捕獲到的Exception或Error；</p><p>　　另一個(gè)線程調(diào)用一個(gè)Deprecated的stop()方法。注意，因?yàn)檫@個(gè)方法會(huì)引起線程的安全問(wèn)題，已經(jīng)被不推薦使用了，所以，不要再程序調(diào)用這個(gè)方法。</p><p>

35、　　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)線程同步。多數(shù)JAVA同步是以對(duì)象鎖定為中心的。JAVA中從Object對(duì)象繼承來(lái)的每個(gè)對(duì)象都有一個(gè)單獨(dú)的鎖。由于JAVA中的每個(gè)對(duì)象都是從Object繼承來(lái)的。所以JAVA中的每個(gè)對(duì)象都有自己的

36、鎖。這樣使它在共享的線程之間可以相互協(xié)調(diào)。在JAVA中實(shí)現(xiàn)線程同步的另一個(gè)方法是通過(guò)使用synchronized關(guān)鍵字。JAVA使用synchronized關(guān)鍵字來(lái)定義程序中要求線程同步的部分。synchronized關(guān)鍵字實(shí)現(xiàn)的基本操作是把每個(gè)需要線程同步的部分定義為一個(gè)臨界區(qū)，在臨界區(qū)中同一時(shí)刻只有一個(gè)線程被執(zhí)行。</p><p><b>　　2.2 URL消重</b></p>

37、;<p>　　2.2.1 URL消重的意義</p><p>　　在SPIDER系統(tǒng)實(shí)際運(yùn)行的過(guò)程中，每秒下載的10個(gè)頁(yè)面中，分析的URL大多數(shù)是重復(fù)的，實(shí)際上新的URL才幾個(gè)。在持續(xù)下載的過(guò)程中，新的URL非常少，還是以新浪網(wǎng)舉例，1天24小時(shí)中總共出現(xiàn)的新URL也就是10000左右。這種情況非常類似于操作系統(tǒng)中虛擬儲(chǔ)存器管理。所謂的虛擬儲(chǔ)存器，是指具有請(qǐng)求調(diào)入和置換功能，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)

38、充的一種儲(chǔ)存器系統(tǒng)。其關(guān)鍵在于允許一個(gè)作業(yè)只裝入部分的頁(yè)或段就可以啟動(dòng)運(yùn)行，當(dāng)作業(yè)運(yùn)行的時(shí)候在內(nèi)存中找不到所需要的頁(yè)或段的時(shí)候，就會(huì)發(fā)生請(qǐng)求調(diào)入，而從外存中找到的頁(yè)或段將會(huì)置換內(nèi)存中暫時(shí)不運(yùn)行的頁(yè)面到外存。</p><p>　　URL消重工作量是非常巨大的。以下在新浪新聞頁(yè)面為例，新浪一個(gè)新聞頁(yè)面大小為50～60k，每個(gè)頁(yè)面有90～100個(gè)URL，如果每秒下載10個(gè)頁(yè)面，就會(huì)產(chǎn)生900～1000次的URL排重操作

39、，每次排重操作都要在幾百萬(wàn)至幾千萬(wàn)的URL庫(kù)中去查詢。這種操作對(duì)數(shù)據(jù)庫(kù)系統(tǒng)是一個(gè)災(zāi)難，理論上任何需要產(chǎn)生磁盤(pán)I/O動(dòng)作的存儲(chǔ)系統(tǒng)都無(wú)法滿足這種查詢的需求。</p><p>　　2.2.2 網(wǎng)絡(luò)爬蟲(chóng)URL去重儲(chǔ)存庫(kù)設(shè)計(jì)</p><p>　　在爬蟲(chóng)啟動(dòng)工作的過(guò)程中，我們不希望同一個(gè)網(wǎng)頁(yè)被多次下載，因?yàn)橹貜?fù)下載不僅會(huì)浪費(fèi)CPU機(jī)時(shí)，還會(huì)為搜索引擎系統(tǒng)增加負(fù)荷。而想要控制這種重復(fù)性下載問(wèn)題，就要考

40、慮下載所依據(jù)的超鏈接，只要能夠控制待下載的URL不重復(fù)，基本可以解決同一個(gè)網(wǎng)頁(yè)重復(fù)下載的問(wèn)題。</p><p>　　非常容易想到，在搜索引擎系統(tǒng)中建立一個(gè)全局的專門(mén)用來(lái)檢測(cè)，是否某一個(gè)URL對(duì)應(yīng)的網(wǎng)頁(yè)文件曾經(jīng)被下載過(guò)的URL存儲(chǔ)庫(kù)，這就是方案。接著要考慮的就是如何能夠更加高效地讓爬蟲(chóng)工作，確切地說(shuō)，讓去重工作更加高效。如果實(shí)現(xiàn)去重，一定是建立一個(gè)URL存儲(chǔ)庫(kù)，并且已經(jīng)下載完成的URL在進(jìn)行檢測(cè)時(shí)候，要加載到內(nèi)存中

41、，在內(nèi)存中進(jìn)行檢測(cè)一定會(huì)比直接從磁盤(pán)上讀取速度快很多。我們先從最簡(jiǎn)單的情況說(shuō)起，然后逐步優(yōu)化，最終得到一個(gè)非常不錯(cuò)的解決方案。</p><p>　　2.2.2.1 基于磁盤(pán)的順序存儲(chǔ)</p><p>　　這里，就是指把每個(gè)已經(jīng)下載過(guò)的URL進(jìn)行順序存儲(chǔ)。你可以把全部已經(jīng)下載完成的URL存放到磁盤(pán)記事本文件中。每次有一個(gè)爬蟲(chóng)線程得到一個(gè)任務(wù)URL開(kāi)始下載之前，通過(guò)到磁盤(pán)上的該文件中檢索，如果

42、沒(méi)有出現(xiàn)過(guò)，則將這個(gè)新的URL寫(xiě)入記事本的最后一行，否則就放棄該URL的下載。</p><p>　　這種方式幾乎沒(méi)有人考慮使用了，但是這種檢查的思想是非常直觀的。試想，如果已經(jīng)下載了100億網(wǎng)頁(yè)，那么對(duì)應(yīng)著100億個(gè)鏈接，也就是這個(gè)檢查URL是否重復(fù)的記事本文件就要存儲(chǔ)這100億URL，況且，很多URL字符串的長(zhǎng)度也不小，占用存儲(chǔ)空間不說(shuō)，查找效率超級(jí)低下，這種方案肯定放棄。</p><p&g

43、t;　　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映射，如果得到的地址已經(jīng)存在，說(shuō)明已經(jīng)被下載過(guò)，放棄下載，否則，將該URL及其Hash地址作為鍵值對(duì)存放到Hash表中。</p><p>　　這樣，URL去重存儲(chǔ)庫(kù)就是要維護(hù)一個(gè)

44、Hash表，如果Hash函數(shù)設(shè)計(jì)的不好，在進(jìn)行映射的時(shí)候，發(fā)生碰撞的幾率很大，則再進(jìn)行碰撞的處理也非常復(fù)雜。而且，這里使用的是URL作為鍵，URL字符串也占用了很大的存儲(chǔ)空間。</p><p>　　2.2.2.3 基于MD5壓縮映射的存儲(chǔ)</p><p>　　MD5算法是一種加密算法，同時(shí)它也是基于Hash的算法。這樣就可以對(duì)URL字符串進(jìn)行壓縮，得到一個(gè)壓縮字符串，同時(shí)可以直接得到一個(gè)H

45、ash地址。另外，MD5算法能夠?qū)⑷魏巫址畨嚎s為128位整數(shù)，并映射為物理地址，而且MD5進(jìn)行Hash映射碰撞的幾率非常小，這點(diǎn)非常好。從另一個(gè)方面來(lái)說(shuō)，非常少的碰撞，對(duì)于搜索引擎的爬蟲(chóng)是可以容忍的。況且，在爬蟲(chóng)進(jìn)行檢測(cè)的過(guò)程中，可以通過(guò)記錄日志來(lái)保存在進(jìn)行MD5時(shí)發(fā)生碰撞的URL，通過(guò)單獨(dú)對(duì)該URL進(jìn)行處理也是可行的。</p><p>　　在Java中有一個(gè)Map類非常好，你可以將壓縮后的URL串作為Key，

46、而將Boolean作為Value進(jìn)行存儲(chǔ)，然后將工作中的Map在爬蟲(chóng)停止工作后序列化到本地磁盤(pán)上；當(dāng)下一次啟動(dòng)新的爬蟲(chóng)任務(wù)的時(shí)候，再將這個(gè)Map反序列化到內(nèi)存中，供爬蟲(chóng)進(jìn)行URL去重檢測(cè)。</p><p>　　2.2.2.4 基于嵌入式Berkeley DB的存儲(chǔ)</p><p>　　Berkeley DB的特點(diǎn)就是只存儲(chǔ)鍵值對(duì)類型數(shù)據(jù)，這和URL去重有很大關(guān)系。去重，可以考慮對(duì)某個(gè)鍵，存

47、在一個(gè)值，這個(gè)值就是那個(gè)鍵的狀態(tài)。使用了Berkeley DB，你就不需要考慮進(jìn)行磁盤(pán)IO操作的性能損失了，這個(gè)數(shù)據(jù)庫(kù)在設(shè)計(jì)的時(shí)候很好地考慮了這些問(wèn)題，并且該數(shù)據(jù)庫(kù)支持高并發(fā)，支持記錄的順序存儲(chǔ)和隨機(jī)存儲(chǔ)，是一個(gè)不錯(cuò)的選擇。</p><p>　　URL去重存儲(chǔ)庫(kù)使用Berkeley DB，壓縮后的URL字符串作為Key，或者直接使用壓縮后的URL字節(jié)數(shù)組作為Key，對(duì)于Value可以使用Boolean，一個(gè)字節(jié)，

48、或者使用字節(jié)數(shù)組，實(shí)際Value只是一個(gè)狀態(tài)標(biāo)識(shí)，減少Value存儲(chǔ)占用存儲(chǔ)空間。</p><p>　　2.2.2.5 基于布隆過(guò)濾器（Bloom Filter）的存儲(chǔ)</p><p>　　使用布隆過(guò)濾器，設(shè)計(jì)多個(gè)Hash函數(shù)，也就是對(duì)每個(gè)字符串進(jìn)行映射是經(jīng)過(guò)多個(gè)Hash函數(shù)進(jìn)行映射，映射到一個(gè)二進(jìn)制向量上，這種方式充分利用了比特位。不過(guò)，我沒(méi)有用過(guò)這種方式，有機(jī)會(huì)可以嘗試一下?？梢詤⒖糋

49、oogle的http://www.googlechinablog.com/2007/07/bloom-filter.html。</p><p>　　2.2.3 LRU算法實(shí)現(xiàn)URL消重</p><p>　　用雙向鏈表來(lái)實(shí)現(xiàn)大容量cache的LRU算法。原理是：cache的所有位置都用雙向鏈表連接起來(lái)，當(dāng)一個(gè)位置被命中后，就將通過(guò)調(diào)整鏈表的指向?qū)⒃撐恢谜{(diào)整到鏈表的頭位置，新加入的內(nèi)容直接放在

50、鏈表的頭上。這樣，在進(jìn)行過(guò)多次查找操作后，最近被命中過(guò)的內(nèi)容就像鏈表的頭移動(dòng)，而沒(méi)有命中過(guò)的內(nèi)容就向鏈表的后面移動(dòng)。當(dāng)需要替換時(shí)，鏈表最后的位置就是最近最少被命中位置，我們只需要將新的內(nèi)容放在鏈表前面，淘汰鏈表最后的位置就實(shí)現(xiàn)了LRU算法。</p><p>　　2.3 URL類訪問(wèn)網(wǎng)絡(luò)</p><p>　　JAVA提供了許多支Internet連接的類，URL類就是其中之一。在使用URL類之

51、前，必須創(chuàng)建一個(gè)URL對(duì)象，創(chuàng)建的方法是使用其構(gòu)造函數(shù)，通過(guò)向其指定一個(gè)URL地址，就能實(shí)例化該類。如：URL url=new URL（http://www.sina.com.cn）；</p><p>　　如果傳遞無(wú)效的URL給URL對(duì)象，該對(duì)象會(huì)拋出MalformedURLException異常。當(dāng)成功創(chuàng)建一個(gè)URL對(duì)象后，我們調(diào)用openConnection函數(shù)建立與URL的通信，此時(shí)，我們就獲得了一個(gè)URL

52、Connection對(duì)象的引用，URLConnection類包含了許多與網(wǎng)絡(luò)上的URL通信的函數(shù)。在下載網(wǎng)頁(yè)前，我們需要判斷目標(biāo)網(wǎng)頁(yè)是否存在，這時(shí)調(diào)用URLConnection類的getHeaderField()方法，獲得服務(wù)器返回給SPIDER 程序的響應(yīng)碼，如果響應(yīng)碼包含”20*”字樣，表示目標(biāo)網(wǎng)頁(yè)存在，下一步就下載網(wǎng)頁(yè)，否則就不下載。getHeaderField()方法僅僅獲得服務(wù)器返回的頭標(biāo)志，其通信開(kāi)銷是最小的，因此在下載網(wǎng)頁(yè)

53、前進(jìn)行此測(cè)試，不僅能減小網(wǎng)絡(luò)流量，而且能提高程序效率。當(dāng)目標(biāo)網(wǎng)頁(yè)存在時(shí)2調(diào)用URLConnection類getInputStream()函數(shù)明確打開(kāi)到URL的連接，獲取輸入流，再用java.io包中的InputStreamReader類讀取該輸入流，將網(wǎng)頁(yè)下載下來(lái)。</p><p>　　2.4　爬行策略淺析</p><p>　　2.4.1寬度或深度優(yōu)先搜索策略</p><

54、;p>　　搜索引擎所用的第一代網(wǎng)絡(luò)爬蟲(chóng)主要是基于傳統(tǒng)的圖算法, 如寬度優(yōu)先或深度優(yōu)先算法來(lái)索引整個(gè)Web, 一個(gè)核心的U RL 集被用來(lái)作為一個(gè)種子集合, 這種算法遞歸的跟蹤超鏈接到其它頁(yè)面, 而通常不管頁(yè)面的內(nèi)容, 因?yàn)樽罱K的目標(biāo)是這種跟蹤能覆蓋整個(gè)Web. 這種策略通常用在通用搜索引擎中,因?yàn)橥ㄓ盟阉饕娅@得的網(wǎng)頁(yè)越多越好, 沒(méi)有特定的要求.</p><p>　　2.4.1.1　寬度優(yōu)先搜索算法<

55、/p><p>　　寬度優(yōu)先搜索算法(又稱廣度優(yōu)先搜索) 是最簡(jiǎn)便的圖的搜索算法之一, 這一算法也是很多重要的圖的算法的原型. Dijkstra 單源最短路徑算法和Prim 最小生成樹(shù)算法都采用了和寬度優(yōu)先搜索類似的思想.寬度優(yōu)先搜索算法是沿著樹(shù)的寬度遍歷樹(shù)的節(jié)點(diǎn), 如果發(fā)現(xiàn)目標(biāo), 則算法中止. 該算法的設(shè)計(jì)和實(shí)現(xiàn)相對(duì)簡(jiǎn)單, 屬于盲目搜索. 在目前為覆蓋盡可能多的網(wǎng)頁(yè), 一般使用寬度優(yōu)先搜索方法. 也有很多研究將寬度優(yōu)

56、先搜索策略應(yīng)用于聚焦爬蟲(chóng)中. 其基本思想是認(rèn)為與初始U RL 在一定鏈接距離內(nèi)的網(wǎng)頁(yè)具有主題相關(guān)性的概率很大. 另外一種方法是將寬度優(yōu)先搜索與網(wǎng)頁(yè)過(guò)濾技術(shù)結(jié)合使用, 先用廣度優(yōu)先策略抓取網(wǎng)頁(yè), 再將其中無(wú)關(guān)的網(wǎng)頁(yè)過(guò)濾掉. 這些方法的缺點(diǎn)在于, 隨著抓取網(wǎng)頁(yè)的增多, 大量的無(wú)關(guān)網(wǎng)頁(yè)將被下載并過(guò)濾, 算法的效率將變低.</p><p>　　2.4.1.2　深度優(yōu)先搜索</p><p>　　深度

57、優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索圖. 在深度優(yōu)先搜索中, 對(duì)于最新發(fā)現(xiàn)的頂點(diǎn), 如果它還有以此為起點(diǎn)而未探測(cè)到的邊, 就沿此邊繼續(xù)漢下去. 當(dāng)結(jié)點(diǎn)v 的所有邊都己被探尋過(guò), 搜索將回溯到發(fā)現(xiàn)結(jié)點(diǎn)v 有那條邊的始結(jié)點(diǎn). 這一過(guò)程一直進(jìn)行到已發(fā)現(xiàn)從源結(jié)點(diǎn)可達(dá)的所有結(jié)點(diǎn)為止. 如果還存在未被發(fā)現(xiàn)的結(jié)點(diǎn), 則選擇其中一個(gè)作為源結(jié)點(diǎn)并重復(fù)以上過(guò)程, 整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有結(jié)點(diǎn)都被發(fā)現(xiàn)為止. 深度優(yōu)先在很多情況下會(huì)導(dǎo)致爬蟲(chóng)的陷入( t

58、rapped) 問(wèn)題, 所以它既不是完備的, 也不是最優(yōu)的.</p><p>　　2.4.2 聚焦搜索策略</p><p>　　基于第一代網(wǎng)絡(luò)爬蟲(chóng)的搜索引擎抓取的網(wǎng)頁(yè)一般少于1 000 000 個(gè)網(wǎng)頁(yè), 極少重新搜集網(wǎng)頁(yè)并去刷新索引. 而且其檢索速度非常慢, 一般都要等待10 s甚至更長(zhǎng)的時(shí)間. 隨著網(wǎng)頁(yè)頁(yè)信息的指數(shù)級(jí)增長(zhǎng)及動(dòng)態(tài)變化, 這些通用搜索引擎的局限性越來(lái)越大, 隨著科學(xué)技術(shù)的發(fā)展

59、, 定向抓取相關(guān)網(wǎng)頁(yè)資源的聚焦爬蟲(chóng)便應(yīng)運(yùn)而生.聚焦爬蟲(chóng)的爬行策略只挑出某一個(gè)特定主題的頁(yè)面, 根據(jù)“最好優(yōu)先原則”進(jìn)行訪問(wèn), 快速、有效地獲得更多的與主題相關(guān)的頁(yè)面, 主要通過(guò)內(nèi)容和Web 的鏈接結(jié)構(gòu)來(lái)指導(dǎo)進(jìn)一步的頁(yè)面抓取[ 2 ]. </p><p>　　聚焦爬蟲(chóng)會(huì)給它所下載下來(lái)的頁(yè)面分配一個(gè)評(píng)價(jià)分, 然后根據(jù)得分排序, 最后插入到一個(gè)隊(duì)列中. 最好的下一個(gè)搜索將通過(guò)對(duì)彈出隊(duì)列中的第一個(gè)頁(yè)面進(jìn)行分析而執(zhí)行, 這

60、種策略保證爬蟲(chóng)能優(yōu)先跟蹤那些最有可能鏈接到目標(biāo)頁(yè)面的頁(yè)面. 決定網(wǎng)絡(luò)爬蟲(chóng)搜索策略的關(guān)鍵是如何評(píng)價(jià)鏈接價(jià)值, 即鏈接價(jià)值的計(jì)算方法, 不同的價(jià)值評(píng)價(jià)方法計(jì)算出的鏈接的價(jià)值不同, 表現(xiàn)出的鏈接的“重要程度”也不同, 從而決定了不同的搜索策略. 由于鏈接包含于頁(yè)面之中,而通常具有較高價(jià)值的頁(yè)面包含的鏈接也具有較高的價(jià)值, 因而對(duì)鏈接價(jià)值的評(píng)價(jià)有時(shí)也轉(zhuǎn)換為對(duì)頁(yè)面價(jià)值的評(píng)價(jià). 這種策略通常運(yùn)用在專業(yè)搜索引擎中, 因?yàn)檫@種搜索引擎只關(guān)心某一特定主題

61、的頁(yè)面.</p><p>　　2.4.3基于內(nèi)容評(píng)價(jià)的搜索策略</p><p>　　基于內(nèi)容評(píng)價(jià)的搜索策略[ 3, 4 ] , 主要是根據(jù)主題(如關(guān)鍵詞、主題相關(guān)文檔) 與鏈接文本的相似度來(lái)評(píng)價(jià)鏈接價(jià)值的高低, 并以此決定其搜索策略: 鏈接文本是指鏈接周圍的說(shuō)明文字和鏈接U RL 上的文字信息, 相似度的評(píng)價(jià)通常采用以下公式:</p><p>　　sim (d i,

62、 d j ) =Σmk= 1w ik ×w jk(Σmk= 1w 2ik ) (Σmk= 1w 2jk )</p><p>　　其中, di 為新文本的特征向量, d j 為第j 類的中心向量,m 為特征向量的維數(shù),wk 為向量的第K 維.由于Web 頁(yè)面不同于傳統(tǒng)的文本, 它是一種半結(jié)構(gòu)化的文檔, 包含許多結(jié)構(gòu)信息Web 頁(yè)面不是單獨(dú)存在的, 頁(yè)面中的鏈接指示了頁(yè)面之間的相互關(guān)系, 因而有些學(xué)者提出了

63、基于鏈接結(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à)的搜索策略, 是通過(guò)對(duì)Web頁(yè)面之間相互引用關(guān)系的分析來(lái)確定鏈接的重要性, 進(jìn)而決定鏈接訪問(wèn)順序的方法. 通常認(rèn)為有較多入鏈或出鏈的頁(yè)面具有較高的價(jià)值. PageRank 和Hits 是其中具有代表性的算法.</p><p>　　2.4.

64、4.1　PageRank 算法</p><p>　　基于鏈接評(píng)價(jià)的搜索引擎的優(yōu)秀代表是Google (http://www.Google.com) , 它獨(dú)創(chuàng)的“鏈接評(píng)價(jià)體系”(PageRank 算法) 是基于這樣一種認(rèn)識(shí), 一個(gè)網(wǎng)頁(yè)的重要性取決于它被其它網(wǎng)頁(yè)鏈接的數(shù)量, 特別是一些已經(jīng)被認(rèn)定是“重要”的網(wǎng)頁(yè)的鏈接數(shù)量. PageRank 算法最初用于Google 搜索引擎信息檢索中對(duì)查詢結(jié)果的排序過(guò)程[ 5 ]

65、 , 近年來(lái)被應(yīng)用于網(wǎng)絡(luò)爬蟲(chóng)對(duì)鏈接重要性的評(píng)價(jià), PageRank 算法中, 頁(yè)面的價(jià)值通常用頁(yè)面的PageRank值表示, 若設(shè)頁(yè)面p 的PageRank 值為PR (p ) , 則PR (p ) 采用如下迭代公式計(jì)算:</p><p>　　PR (p ) = C 1T+ (1 - C) Σ C∈in (p )PR (p )ûou t (C) û</p><p>　　

66、其中T 為計(jì)算中的頁(yè)面總量, C< 1 是阻尼常數(shù)因子, in (p ) 為所有指向p 的頁(yè)面的集合, out (C) 為頁(yè)面C出鏈的集合. 基于PageRank 算法的網(wǎng)絡(luò)爬蟲(chóng)在搜索過(guò)程中, 通過(guò)計(jì)算每個(gè)已訪問(wèn)頁(yè)面的PageRank 值來(lái)確定頁(yè)面的價(jià)值, 并優(yōu)先選擇PageRank 值大的頁(yè)面中的鏈接進(jìn)行訪問(wèn).</p><p>　　2.4.4.2　H ITS 算法</p><p>

67、　　HITS 方法定義了兩個(gè)重要概念: Authority 和Hub. Authority 表示一個(gè)權(quán)威頁(yè)面被其它頁(yè)面引用的數(shù)量, 即該權(quán)威頁(yè)面的入度值. 網(wǎng)頁(yè)被引用的數(shù)量越大, 則該網(wǎng)頁(yè)的Authority 值越大; Hub 表示一個(gè)Web 頁(yè)面指向其它頁(yè)面的數(shù)量, 即該頁(yè)面的出度值. 網(wǎng)頁(yè)的出度值越大, 其Hub 值越高. 由于Hub 值高的頁(yè)面通常都提供了指向權(quán)威頁(yè)面的鏈接, 因而起到了隱含說(shuō)明某主題頁(yè)面權(quán)威性的作用.HITS (

68、Hyperlink- Induced Top ic Search) 算法是利用HuböAuthority 方法的搜索方法,Authority表示一個(gè)頁(yè)面被其它頁(yè)面引用的數(shù)量, 即該頁(yè)面的入度值. Hub 表示一個(gè)Web 頁(yè)面指向其它頁(yè)面的數(shù)量, 即該頁(yè)面的出度值. 算法如下: 將查詢q 提交給傳統(tǒng)的基于關(guān)鍵字匹配的搜索引擎. 搜索引擎返回很多網(wǎng)頁(yè), 從中取前n 個(gè)網(wǎng)頁(yè)作為根集, 用S 表示.通過(guò)向S 中加入被S 引用的網(wǎng)頁(yè)和引

69、用S 的網(wǎng)頁(yè)將S 擴(kuò)展成一個(gè)更大的集合T.以T 中的Hub 網(wǎng)頁(yè)為頂點(diǎn)集V l, 以權(quán)威網(wǎng)頁(yè)為頂點(diǎn)集V 2,V1 中的網(wǎng)頁(yè)到V 2 中</p><p>　　A (u) = Σ v: (v , u) ∈EH (v ) (1)</p><p>　　H (v ) = Σ v: (v, u) ∈EA (v ) (2)</p><p>　　式(1) 反映了若一個(gè)網(wǎng)頁(yè)由很多好的

70、Hub 指向, 則其權(quán)威值會(huì)相應(yīng)增加(即權(quán)威值增加為所有指向它的網(wǎng)頁(yè)的現(xiàn)有Hub 值之和). 式(2) 反映了若一個(gè)網(wǎng)頁(yè)指向許多好的權(quán)威頁(yè), 則Hub 值也會(huì)相應(yīng)增加(即Hub 值增加為該網(wǎng)頁(yè)鏈接的所有網(wǎng)頁(yè)的權(quán)威值之和).雖然基于鏈接結(jié)構(gòu)價(jià)的搜索考慮了鏈接的結(jié)構(gòu)和頁(yè)面之間的引用關(guān)系, 但忽略了頁(yè)面與主題的相關(guān)性, 在某些情況下, 會(huì)出現(xiàn)搜索偏離主題的問(wèn)題. 另外, 搜索過(guò)程中需要重復(fù)計(jì)算PageRank 值或Authority 以及Hu

71、b 權(quán)重, 計(jì)算復(fù)雜度隨頁(yè)面和鏈接數(shù)量的增長(zhǎng)呈指數(shù)級(jí)增長(zhǎng)[ 6 ].</p><p>　　2.4.5 基于鞏固學(xué)習(xí)的聚焦搜索</p><p>　　近年來(lái)對(duì)Web 信息資源分布的研究表明很多類型相同的網(wǎng)站在構(gòu)建方式上, 主題相同的網(wǎng)頁(yè)在組織方式上都存在著一定的相似性, 有的學(xué)者就考慮將鞏固學(xué)習(xí)引入網(wǎng)絡(luò)爬蟲(chóng)的訓(xùn)練過(guò)程中, 從這些相似性獲取一些“經(jīng)驗(yàn)”, 而這些經(jīng)驗(yàn)信息在搜索距相關(guān)頁(yè)面集較遠(yuǎn)的地

72、方往往能獲得較好的回報(bào), 而前兩種策略在這種情況下容易迷失方向.在鞏固學(xué)習(xí)模型中, 把網(wǎng)絡(luò)爬蟲(chóng)經(jīng)過(guò)若干無(wú)關(guān)頁(yè)面的訪問(wèn)之后才能獲得的主題相關(guān)頁(yè)面稱為未來(lái)回報(bào), 對(duì)未來(lái)回報(bào)的預(yù)測(cè)值稱為未來(lái)回報(bào)價(jià)值, 用Q價(jià)值表示. 這種方法的核心就是學(xué)習(xí)如何計(jì)算鏈接的Q 價(jià)值, 根據(jù)未來(lái)回報(bào)價(jià)值確定正確的搜索方向. 目前這類搜索策略不足之處在于學(xué)習(xí)效率低的問(wèn)題, 而且在訓(xùn)練過(guò)程中增加了用戶的負(fù)擔(dān).</p><p>　　2.4.6 基

73、于語(yǔ)境圖的聚焦搜索</p><p>　　基于鞏固學(xué)習(xí)的網(wǎng)絡(luò)爬蟲(chóng)通過(guò)計(jì)算鏈接的Q價(jià)值可以確定搜索方向, 但它卻無(wú)法估計(jì)距離目標(biāo)頁(yè)面的遠(yuǎn)近. 為此, Diligent 等提出了基于“語(yǔ)境圖”的搜索策略, 它通過(guò)構(gòu)建典型頁(yè)面的web“語(yǔ)境圖”來(lái)估計(jì)離目標(biāo)頁(yè)面的距離, 距離較近的頁(yè)面較早得到訪問(wèn)[ 7 ].基于“語(yǔ)境圖”的搜索策略需要借助已有的通用搜索引擎構(gòu)建“語(yǔ)境圖”, 而搜索引擎的檢索結(jié)果并非一定代表真實(shí)的web 結(jié)

74、構(gòu), 因而這種方式也具有局限性.</p><p>　　第三章 系統(tǒng)需求分析及模塊設(shè)計(jì)</p><p>　　3.1 系統(tǒng)需求分析</p><p>　　SPIDER要獲取的對(duì)象是存在于網(wǎng)絡(luò)上數(shù)以億計(jì)的網(wǎng)頁(yè)，這些網(wǎng)頁(yè)以超鏈接形式互相聯(lián)系在一起，每一網(wǎng)頁(yè)對(duì)應(yīng)一個(gè)超鏈接，也稱統(tǒng)一資源定位符（URL）。我們可以把網(wǎng)絡(luò)看做一個(gè)圖M(V,E)，網(wǎng)絡(luò)中的網(wǎng)頁(yè)構(gòu)成節(jié)點(diǎn)集V，他們之間的鏈

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

76、中的網(wǎng)頁(yè)數(shù)目也是有限的，因此SPIDER程序能在有限的時(shí)間內(nèi)結(jié)束。</p><p>　　當(dāng)SPIDER程序訪問(wèn)到一個(gè)網(wǎng)頁(yè)，必須進(jìn)行以下幾項(xiàng)基本處理：抽取網(wǎng)頁(yè)中包含的文本；抽取網(wǎng)頁(yè)中包含的URL，并將其區(qū)分為網(wǎng)站內(nèi)URL或網(wǎng)站外URL。</p><p>　　3.2 SPIDER體系結(jié)構(gòu)</p><p>　　此爬蟲(chóng)程序主要分為三個(gè)部分：任務(wù)執(zhí)行端，任務(wù)調(diào)度端，數(shù)據(jù)服務(wù)端

77、。每一個(gè)SPIDER 任務(wù)執(zhí)行端關(guān)聯(lián)一個(gè)站點(diǎn),一個(gè)線程下載一個(gè)基于URL 鏈接的頁(yè)面, 并進(jìn)行Web 頁(yè)面解析, 得到站內(nèi)URL 和發(fā)現(xiàn)新站點(diǎn)URL另外,將URL 隊(duì)列持久化到數(shù)據(jù)庫(kù), 因此在SPIDER 任務(wù)執(zhí)行端以外Down 掉后, 能夠斷點(diǎn)續(xù)傳.</p><p>　　SPIDER 客戶端線程間的協(xié)調(diào)通信采用Java 的線程同步技術(shù)synchronized,在數(shù)據(jù)服務(wù)端中對(duì)URL 進(jìn)行緩存提高了系統(tǒng)處理速

78、度. 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)更新等. 如果SPIDER 以300 頁(yè)ö秒的速度下載Web 頁(yè)面, 平均將會(huì)產(chǎn)生2000 多個(gè)URL [12] , 因此簡(jiǎn)單的采用內(nèi)存數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)這些URL 隊(duì)列有一定的問(wèn)題, 系統(tǒng)沒(méi)有足夠的內(nèi)存空

79、間;而采用直接持久化到數(shù)據(jù)庫(kù), 則需要大量的數(shù)據(jù)庫(kù)連接、查詢等操作, 系統(tǒng)效率會(huì)明顯下降. 如果采用URL 壓縮的辦法,盡管在一定程度上可以平衡空間和時(shí)間的矛盾, 但仍然不適用于大規(guī)模數(shù)據(jù)采集的SPIDER.</p><p>　　圖3.2 SPIDER體系結(jié)</p><p>　　3.3 各主要功能模塊（類）設(shè)計(jì)</p><p>　　SPIDERWorker類：該類繼

80、承自線程類，請(qǐng)求任務(wù)URL，根據(jù)得到的URL下載相應(yīng)的HTML代碼，利用HTML代碼調(diào)用其他模塊完成相關(guān)處理。</p><p>　　SPIDERManager類：該類用于控制SPIDERWorker線程。</p><p>　　UrlQueueManager類：該類用于維護(hù)URL等待隊(duì)列，分配任務(wù)URL，URL消重模塊。</p><p>　　UrlParse類：用于解

81、析HTML，獲取并過(guò)濾URL。</p><p>　　DateBaseConnect類：用于提供數(shù)據(jù)庫(kù)連接。</p><p>　　3.4 SPIDER工作過(guò)程</p><p>　?、賹⒔o定的初始URL加入到URL等待隊(duì)列。</p><p>　?、趧?chuàng)建爬蟲(chóng)線程，啟動(dòng)爬蟲(chóng)線程</p><p>　?、勖總€(gè)爬蟲(chóng)線程從URL等待隊(duì)

82、列中取得任務(wù)URL。然后根據(jù)URL下載網(wǎng)頁(yè)，然后解析網(wǎng)頁(yè)，獲取超鏈接URLs。如果獲取到的URL為相對(duì)地址，需要轉(zhuǎn)換為絕對(duì)地址，然后淘汰站外URLs，錯(cuò)誤URLs或者不能解析的URL地址。再判斷這些URL是否已經(jīng)被下載到，如果沒(méi)有則加入到URL等待隊(duì)列。</p><p>　?、芾^續(xù)執(zhí)行步驟③，直到結(jié)束條件停止。</p><p>　　第四章 系統(tǒng)分析與設(shè)計(jì)</p><p&

83、gt;　　4.1 SPIDER構(gòu)造分析</p><p>　　構(gòu)造SPIDER 程序有兩種方式：（1）把SPIDER 程序設(shè)計(jì)為遞歸的程序；（2）編寫(xiě)一個(gè)非遞歸的程序，它要維護(hù)一個(gè)要訪問(wèn)的網(wǎng)頁(yè)列表?？紤]使用哪一種方式的前提是，構(gòu)造的SPIDER 程序必須能夠訪問(wèn)非常大的Web 站點(diǎn)。本系統(tǒng)中使用了非遞歸的程序設(shè)計(jì)方法。這是因?yàn)?，?dāng)一個(gè)遞歸程序運(yùn)行時(shí)要把每次遞歸壓入堆棧，但在本系統(tǒng)設(shè)計(jì)中使用的是多線程，它允許一次運(yùn)行

84、多個(gè)任務(wù)，但是，多線程與遞歸是不兼容的。因?yàn)樵谶@一過(guò)程中每一個(gè)線程都有自己的堆棧，而當(dāng)一個(gè)方法調(diào)用它自身時(shí)，它們需要使用同一個(gè)堆棧。這就意味著遞歸的SPIDER 程序不能使用多線程。</p><p>　　每個(gè)SPIDER線程都會(huì)獨(dú)立的去完成獲取URLs的任務(wù)，并將獲取到的URLs加入一個(gè)公共的URL等待隊(duì)列中。</p><p><b>　　圖4.1</b></p

85、><p>　　圖4.1表示了該系統(tǒng)爬蟲(chóng)線程的實(shí)現(xiàn)策略。假設(shè)線程1從URL隊(duì)列中獲取一條任務(wù)URL 1，然后它會(huì)下載對(duì)應(yīng)的HTML，解析出里面包含URLs，然后再將這些URLs加入到URL隊(duì)列中去。然后線程1會(huì)再?gòu)腢RL隊(duì)列中獲取新的URL，下載HTML代碼，并解析出URLs，再加入到URL隊(duì)列中去。而線程2同時(shí)也會(huì)下載它獲取到的URL 2對(duì)應(yīng)的HTML代碼，解析出URLs加入到等待隊(duì)列中。以此類推，多個(gè)線程并發(fā)地去完

86、成爬蟲(chóng)工作。</p><p>　　4.2 爬行策略分析</p><p><b>　　圖 4.2.1</b></p><p>　　因?yàn)楸菊撐膶?shí)現(xiàn)的爬蟲(chóng)程序的初衷是盡可能遍歷某一站點(diǎn)所有的頁(yè)面。廣度優(yōu)先算法的實(shí)行理論是覆蓋更多的節(jié)點(diǎn)，所以此爬蟲(chóng)程序選擇了廣度優(yōu)先算法。實(shí)現(xiàn)的策略是：先獲取初始URL對(duì)應(yīng)HTML代碼里所有的URLs。然后依次獲取這些U

87、RLs對(duì)應(yīng)的HTML里的URLs，當(dāng)這一層所有的URLs都下載解析完后，在獲取下一層的信息。通過(guò)這種循環(huán)的獲取方式實(shí)現(xiàn)廣度優(yōu)先爬行。</p><p>　　如圖4.2.1，假如a代表初始URL，bcd為以a獲取的3個(gè)URLs，efg為以b獲取的URLs，以此類推。那么這些URLs獲取的順序就是abcdefghijklmnop這樣一個(gè)順序。當(dāng)獲取到b的URLs之后，并不會(huì)馬上去解析這些URLs，而是先解析同b在同一層

88、中的cd對(duì)應(yīng)的URLs。當(dāng)這一層URLs全部解析完后，再開(kāi)始下一層URLs。</p><p>　　廣度優(yōu)先算法的等待隊(duì)列設(shè)計(jì)如圖4.2.2所示。</p><p><b>　　圖 4.2.2</b></p><p>　　圖4.2.2列舉了不同時(shí)間段時(shí)，URL等待隊(duì)列的存儲(chǔ)狀態(tài)。第一個(gè)方框是將初始URL：a加入到等待隊(duì)列。第二個(gè)方框?yàn)?，解析a對(duì)應(yīng)H

89、TML獲取URLs：bcd，同時(shí)刪除a。第三個(gè)方框?yàn)椋馕鯾對(duì)應(yīng)HTML獲取URLs：efg，同時(shí)刪除URL：b。第四個(gè)方框?yàn)椋馕鰁對(duì)應(yīng)HTML獲取URLs：nop，并刪除e。通過(guò)這樣的存儲(chǔ)方法實(shí)現(xiàn)如圖4.2.1的廣度爬行算法。</p><p>　　4.3 URL抽取，解析和保存</p><p>　　4.3.1 URL抽取</p><p>　　通過(guò)觀察研究HTML

90、代碼，我們可以知道。HTML代碼中，頁(yè)面之間的跳轉(zhuǎn)，關(guān)聯(lián)是通過(guò)href標(biāo)簽來(lái)實(shí)現(xiàn)的。我們需要獲取HTML代碼中的URLs，就可以通過(guò)尋找href標(biāo)簽來(lái)達(dá)到目的。</p><p>　　<li><a href=movie_2004/html/6664.html target=_blank>我猜[20090531]</a><em>5-31</em></l

91、i></p><p>　　<li><a href="movie_2004/html/2088.html?2009528224729.html" target="_blank">火影忍者[331，頁(yè)面上303既是]</a></li></p><p>　　通過(guò)觀察得知，一般href標(biāo)簽是以href=這

92、樣的形式出現(xiàn)的。但是不同的網(wǎng)站href=后面的內(nèi)容有所不同。比如href=”url”這樣情況，我們就可以通過(guò)截取雙引號(hào)之間的內(nèi)容來(lái)獲取URL；如果是href=’url’這種情況，我們就需要截取單引號(hào)之間的內(nèi)容來(lái)獲取URL；或者有些是href=url，我們需要以等號(hào)為開(kāi)始標(biāo)記，而這種情況通常結(jié)尾是空格或者>符號(hào)。</p><p>　　通過(guò)這種方法，我們獲取網(wǎng)頁(yè)中大部分的URLs。但是有些URLs是通過(guò)提交表單

93、，或者通過(guò)javascript來(lái)跳轉(zhuǎn)的。這些情況就需要更細(xì)致的考慮，才能獲取。</p><p>　　4.3.2 URL解析</p><p>　　截取出來(lái)的字符串，可能為相對(duì)地址或者絕對(duì)地址。所以需要判斷URL為絕對(duì)地址，還是相對(duì)地址。相對(duì)地址需要先轉(zhuǎn)化為絕對(duì)地址，再進(jìn)行過(guò)濾。因?yàn)榻馕龀鰜?lái)的URL地址可能是一些文件的地址，或者為javascript文件或者css文件。這些格式的URL是無(wú)法獲

94、取HTML代碼的，也就不可能進(jìn)行URL解析。所以我們需要過(guò)濾掉這些URLs。然后再進(jìn)行URL消重處理，最后加入到URL等待隊(duì)列。</p><p>　　為了把爬行限制在同一站點(diǎn)內(nèi)需要截?cái)嘀赶蛘就獾逆溄?保證SPIDER總在站內(nèi)執(zhí)行,即準(zhǔn)確地根據(jù)超鏈URL判斷超鏈?zhǔn)欠裰赶蛘就?由RFC對(duì)URL的定義可知,URL的格式為[protocol://host:port/path?query],一般情況下,同一網(wǎng)站內(nèi)所有頁(yè)面對(duì)

95、應(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)志串.站點(diǎn)類型各異的串].站點(diǎn)類型串只有[ com |edu|gov|net| 國(guó)家域名]幾種類型,所以我們?nèi)≌军c(diǎn)類型各異串前面的串,即站點(diǎn)標(biāo)志串作匹配,超鏈URL的host中是否包含此串,為超鏈?zhǔn)欠裾緝?nèi)

96、的判斷標(biāo)準(zhǔn).</p><p>　　4.3.3 URL保存</p><p>　　因?yàn)榈却齍RLs的數(shù)目非常多，如果全部采用List來(lái)存儲(chǔ)非常的占用內(nèi)存空間。所以將等待URLs存入數(shù)據(jù)庫(kù)中，并設(shè)計(jì)2個(gè)緩存區(qū)，用于向隊(duì)列中加入和取得URLs。URL等待隊(duì)列設(shè)計(jì)成三段式：第一段為一個(gè)List,用來(lái)加入新得到的URL。當(dāng)這個(gè)List中的數(shù)目過(guò)多時(shí)，則將List中的內(nèi)容加入到數(shù)據(jù)庫(kù)，并清空該List，

97、以便加入新的URLs；第二段為數(shù)據(jù)庫(kù)，當(dāng)?shù)谝欢螖?shù)據(jù)過(guò)多時(shí)，將第一段內(nèi)的數(shù)據(jù)存入數(shù)據(jù)庫(kù)；第三段也為一個(gè)List，從這里面分配任務(wù)URL，當(dāng)該List內(nèi)URL不足時(shí)，將數(shù)據(jù)庫(kù)里的數(shù)據(jù)再轉(zhuǎn)存入。</p><p>　　圖4.3.3表示了URL等待隊(duì)列的結(jié)構(gòu)。</p><p><b>　　圖4.3.3</b></p><p><b>　　第五章

98、 系統(tǒng)實(shí)現(xiàn)</b></p><p><b>　　5.1 實(shí)現(xiàn)工具</b></p><p>　　操作系統(tǒng)是winXP;JAVA程序的編寫(xiě)工具是eclipse-SDK-3.2.1-win32；數(shù)據(jù)庫(kù)是MYSQL 5 5.0.51a。</p><p><b>　　5.2 爬蟲(chóng)工作</b></p><

99、;p>　　這個(gè)類繼承自線程類，實(shí)現(xiàn)線程在java中有兩種方法：一種是直接繼承Thread類；一種是實(shí)現(xiàn)Runnable接口。我采用了第二種方法：</p><p>　　public class SpiderWorker implements Runnable {</p><p>　　在這個(gè)類中必須要實(shí)現(xiàn)重寫(xiě)run()這個(gè)方法。我在這個(gè)方法里定義了一個(gè)循環(huán)，這個(gè)線程會(huì)重復(fù)地執(zhí)行爬蟲(chóng)動(dòng)作。

100、</p><p>　　在這個(gè)循環(huán)里，首先會(huì)向URL等待隊(duì)列里請(qǐng)求一個(gè)URL。因?yàn)閁RL隊(duì)列會(huì)出現(xiàn)為空或者被其他線程占用的情況。所以我在這里寫(xiě)了一個(gè)循環(huán)：</p><p><b>　　s = null;</b></p><p>　　while (s == null) {</p><p>　　s = urlQueueMana

101、ger.getWaitQueue();</p><p><b>　　}</b></p><p>　　如果沒(méi)有得到URL就繼續(xù)向URL等待隊(duì)列申請(qǐng)。</p><p>　　當(dāng)?shù)玫饺蝿?wù)URL以后，會(huì)通過(guò)這個(gè)URL得到對(duì)應(yīng)的HTML代碼。具體方法是調(diào)用getHtml(String sourse_url)這個(gè)方法：</p><p>

102、;　　HttpURLConnection connection = null;</p><p>　　InputStreamReader in = null;</p><p>　　BufferedReader br = null;</p><p>　　URL url = null;</p><p>　　url = new URL(sourse_

103、url);</p><p>　　connection = (HttpURLConnection) url.openConnection();</p><p>　　connection.connect();</p><p>　　// 打開(kāi)的連接讀取的輸入流。</p><p>　　in = new InputStreamReader(u

104、rl.openStream());</p><p>　　br = new BufferedReader(in);</p><p><b>　　String c;</b></p><p>　　while ((c = br.readLine()) != null) {</p><p>　　html.append(c);<

105、;/p><p><b>　　}</b></p><p>　　return html.toString();</p><p>　　這個(gè)方法是通過(guò)調(diào)用JAVA里面的URL這個(gè)類，可以用給定的URL構(gòu)造這個(gè)類的一個(gè)實(shí)例，然后通過(guò)openStream()這個(gè)方法得到HTML代碼的數(shù)據(jù)流，然后再一行一行地把數(shù)據(jù)流轉(zhuǎn)換成String字符串，再用StringBu

106、ffer將這些字符串拼接成一個(gè)完整的HTML代碼。</p><p>　　當(dāng)?shù)玫紿TML代碼以后，程序就會(huì)調(diào)用Url_Parse這個(gè)類里面的方法來(lái)解析HTML。</p><p><b>　　5.3 URL解析</b></p><p>　　從HTML代碼中提取URLs，主要是通過(guò)檢索字符串中的href字符串來(lái)實(shí)現(xiàn)的。對(duì)于一個(gè)HTML代碼，我尋找其中

107、的href=字符串，然后記錄它的下表i。然后判斷下表i+1位置上的字符是雙引號(hào)，單引號(hào)或者兩者皆不是，然后選擇對(duì)應(yīng)的字符作為截取URL的終止標(biāo)記。截取過(guò)后的href標(biāo)記就剔除它與它前面的部分，以便而后的操作可以繼續(xù)檢索href標(biāo)記，直到正個(gè)HTML代碼中所有的href標(biāo)記都被解析過(guò)后，操作終止。</p><p>　　<a href="http://www.tom365.com/" cla

108、ss="focu">首頁(yè)</a><a href=’movie_2004/mlist/1_1.html’ target=_self>動(dòng)作片</a><a href=movie_2004/mlist/2_1.html target=_self>恐怖片</a><a href=movie_2004/mlist/3_1.html >愛(ài)情片</a&