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

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

2、TSPIDERisaprogramwhichcanautocollectinformationsfrominternet.SPIDERcancollectdataforsearchengines,alsocanbeaDirectionalinformationcollector,collectsspecificallyinformationsfromsomewebsites,suchasHRinformations,houserentinformations.Inthispaper,useJAVAimplementsabreadth-firstalgorithmmulti-threadSPDI

3、ER.ThispaperexpatiatessomemajorproblemsofSPIDER:whytousebreadth-firstcrawlingstrategy,andhowtoimplementbreadth-firstcrawling;whytousemulti-threading,andhowtoimplementmulti-thread;datastructure;HTMLcodeparse.etc.ThisSPIDERcancollectURLsfromonewebsite,andstoreURLsintodatabase.【KEYWORD】SPIDER;JAVA;Brea

4、dthFirstSearch;multi-threads.II目錄第一章引言.1第二章相關(guān)技術(shù)介紹.22.1JAVA線程.22.1.1線程概述.22.1.2JAVA線程模型.2 2.1.3創(chuàng)建線程.32.1.4JAVA中的線程的生命周期.4 2.1.5JAVA線程的結(jié)束方式.4 2.1.6多線程同步.52.2URL消重.52.2.1URL消重的意義.5 2.2.2網(wǎng)絡(luò)爬蟲(chóng)URL去重儲(chǔ)存庫(kù)設(shè)計(jì).52.2.3LRU算法實(shí)現(xiàn)URL消重.72.3URL類(lèi)訪問(wèn)網(wǎng)絡(luò).82.4爬行策略淺析.82.4.1寬度或深度優(yōu)先搜索策略.82.4.2聚焦搜索策略.92.4.3基于內(nèi)容評(píng)價(jià)的搜索策略.92.4.4基于結(jié)構(gòu)

5、評(píng)價(jià)的搜索策略.102.4.5基于鞏固學(xué)習(xí)的聚焦搜索.112.4.6基于語(yǔ)境圖的聚焦搜索.11第三章系統(tǒng)需求分析及模塊設(shè)計(jì).133.1系統(tǒng)需求分析.133.2SPIDER體系結(jié)構(gòu).133.3各主要功能模塊（類(lèi)）設(shè)計(jì).143.4SPIDER工作過(guò)程.14第四章系統(tǒng)分析與設(shè)計(jì).164.1SPIDER構(gòu)造分析.164.2爬行策略分析.174.3URL抽取，解析和保存.184.3.1URL抽取.184.3.2URL解析.194.3.3URL保存.19第五章系統(tǒng)實(shí)現(xiàn).215.1實(shí)現(xiàn)工具.21 5.2爬蟲(chóng)工作.215.3URL解析.22 5.4URL隊(duì)列管理.245.4.1URL消重處理.245.4.2U

6、RL等待隊(duì)列維護(hù).265.4.3數(shù)據(jù)庫(kù)設(shè)計(jì).27第六章系統(tǒng)測(cè)試.29第七章結(jié)論.32參考文獻(xiàn).33致謝.34外文資料原文.35譯文.50第一章引言第一章引言隨著互聯(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ù)以?xún)|計(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)在比較流行的搜索引擎，比如google，百度，它們爬蟲(chóng)程序的技術(shù)內(nèi)幕一般都不公開(kāi)。目前幾種比較常用的爬蟲(chóng)實(shí)現(xiàn)策略：廣度優(yōu)先

7、的爬蟲(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è)的選擇性爬行程序等等。爬蟲(chóng)程序是一個(gè)自動(dòng)獲取網(wǎng)頁(yè)的程序。它為搜索引擎從互聯(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)確的信息。實(shí)現(xiàn)網(wǎng)絡(luò)爬蟲(chóng)的重點(diǎn)和難點(diǎn)有：多線程的實(shí)現(xiàn)；

8、對(duì)臨界資源的分配；遍歷web圖的遍歷策略選擇和實(shí)現(xiàn)；存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的選擇和實(shí)現(xiàn)。本文通過(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)信息。1電子科技大學(xué)XX學(xué)院本科畢業(yè)設(shè)計(jì)論文第二章相關(guān)技術(shù)介紹2.1JAVA線程2.1.1線程概述幾乎每種操作系統(tǒng)都支持線程的概念進(jìn)程就是在某種程度上相互隔離的，獨(dú)立運(yùn)行的程序。一般來(lái)說(shuō)，這些操作系統(tǒng)都支持多進(jìn)程操作。所謂多進(jìn)程，就是讓系統(tǒng)（好像）同時(shí)運(yùn)行多個(gè)程序。比如，我在MicrosoftWord編寫(xiě)本論文的時(shí)候，我還打開(kāi)了一個(gè)mp3播放器

9、來(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)行的，我不需要等一首歌曲放完了再來(lái)編輯我的論文?？雌饋?lái)，它們都同時(shí)在我的機(jī)器上給我工作。事實(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ù)的動(dòng)作。因此，雖然我們看到的都是一些同步的操作，但

10、實(shí)際上，對(duì)于計(jì)算機(jī)而言，它在某個(gè)時(shí)間點(diǎn)上只能執(zhí)行一個(gè)程序，除非你的計(jì)算機(jī)是多CPU的。多線程（Multi-Thread）擴(kuò)展了多進(jìn)程（multi-Process）操作的概念，將任務(wù)的劃分下降到了程序級(jí)別，使得各個(gè)程序似乎可以在同一個(gè)時(shí)間內(nèi)執(zhí)行多個(gè)任務(wù)。每個(gè)任務(wù)稱(chēng)為一個(gè)線程，能夠同時(shí)運(yùn)行多個(gè)線程的程序稱(chēng)為多線程程序。多線程和多進(jìn)程有什么區(qū)別呢？對(duì)于進(jìn)程來(lái)說(shuō)，每個(gè)進(jìn)程都有自己的一組完整的變量，而線程則共享相同的數(shù)據(jù)。2.1.2JAVA線程模型我們知道，計(jì)算機(jī)程序得以執(zhí)行的三個(gè)要素是：CPU，程序代碼，可存取的數(shù)據(jù)。在JAVA語(yǔ)言中，多線程的機(jī)制是通過(guò)虛擬CPU來(lái)實(shí)現(xiàn)的?？梢孕蜗蟮睦斫鉃?在一個(gè)JA

11、VA程序內(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)來(lái)實(shí)現(xiàn)的，它內(nèi)部實(shí)現(xiàn)了虛擬CPU的功能，能夠接收和處理傳遞給它的代碼和數(shù)據(jù)，并提供了2第二章相關(guān)技術(shù)介紹獨(dú)立的運(yùn)行控制功能。我們知道，每個(gè)JAVA應(yīng)用程序都至少有一個(gè)線程，這就是所謂的主線程。它由JVM創(chuàng)建并調(diào)用JAVA應(yīng)用程序的main（）方法。JVM還通常會(huì)創(chuàng)建一些其他的線程，不過(guò)，這些線程對(duì)我們而言通常都是不可見(jiàn)的。比如，用于自動(dòng)垃圾收集的線程，對(duì)象終止或者其他的JVM處理任務(wù)相關(guān)的線程。2.

12、1.3創(chuàng)建線程創(chuàng)建線程方式一在JAVA中創(chuàng)建線程的一種方式是通過(guò)Thread來(lái)實(shí)現(xiàn)的。Thread有很多個(gè)構(gòu)造器來(lái)創(chuàng)建一個(gè)線程（Thread）實(shí)例：Thread();創(chuàng)建一個(gè)線程。Thread(Runnabletarget)創(chuàng);建一個(gè)線程，并指定一個(gè)目標(biāo)。Thread(Runnabletarget,Stringname)創(chuàng);建一個(gè)名為name的目標(biāo)為target的線程。Thread(Stringname)創(chuàng);建一個(gè)名為name的線程。Thread(ThreadGroupgroup,Runnabletarget);創(chuàng)建一個(gè)隸屬于group線程組，目標(biāo)為target的線程。通常，我們

13、可以將一個(gè)類(lèi)繼承Thread，然后，覆蓋Thread中的run()方法，這樣讓這個(gè)類(lèi)本身也就成了線程。每個(gè)線程都是通過(guò)某個(gè)特定Thread對(duì)象所對(duì)應(yīng)的方法run()來(lái)完成其操作的，方法run()稱(chēng)為線程體。使用start()方法，線程進(jìn)入Runnable狀態(tài)，它將線程調(diào)度器注冊(cè)這個(gè)線程。調(diào)用start()方法并不一定馬上會(huì)執(zhí)行這個(gè)線程，正如上面所說(shuō)，它只是進(jìn)入Runnble而不是Running。創(chuàng)建線程方式二通過(guò)實(shí)現(xiàn)Runnable接口并實(shí)現(xiàn)接口中定義的唯一方法run()，可以創(chuàng)建一個(gè)線程。在使用Runnable接口時(shí)，不能直接創(chuàng)建所需類(lèi)的對(duì)象并運(yùn)行它，而是必須從Thread類(lèi)的

14、一個(gè)實(shí)例內(nèi)部運(yùn)行它。從上面兩種創(chuàng)建線程的方法可以看出，如果繼承Thread類(lèi)，則這個(gè)類(lèi)本身3電子科技大學(xué)XX學(xué)院本科畢業(yè)設(shè)計(jì)論文可以調(diào)用start方法，也就是說(shuō)將這個(gè)繼承了Thread的類(lèi)當(dāng)作目標(biāo)對(duì)象；而如果實(shí)現(xiàn)Runnable接口，則這個(gè)類(lèi)必須被當(dāng)作其他線程的目標(biāo)對(duì)象。2.1.4JAVA中的線程的生命周期JAVA的線程從產(chǎn)生到消失,可分為5種狀態(tài)：新建（New），可運(yùn)行（Runnable），運(yùn)行（Running），阻塞（Blocked）以及死亡（Dead）。其中，Running狀態(tài)并非屬于JAVA規(guī)X中定義的線程狀態(tài)，也就是說(shuō)，在JAVA規(guī)X中，并沒(méi)有將運(yùn)行（Running）狀態(tài)真正的設(shè)置為

15、一個(gè)狀態(tài)，它屬于可運(yùn)行狀態(tài)的一種。當(dāng)使用new來(lái)新建一個(gè)線程時(shí)，它處于New狀態(tài)，這個(gè)時(shí)候，線程并未進(jìn)行任何操作。然后，調(diào)用線程的start()方法，來(lái)向線程調(diào)度程序（通常是JVM或操作系統(tǒng)）注冊(cè)一個(gè)線程，這個(gè)時(shí)候，這個(gè)線程一切就緒，就等待CPU時(shí)間了。線程調(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è)方法。如果線程在運(yùn)行（Running）狀

16、態(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)，而是重新回到Runnable狀態(tài)等待線程調(diào)度程序的調(diào)用。線程調(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

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

18、步。多數(shù)JAVA同步是以對(duì)象鎖定為中心的。JAVA中從Object對(duì)象繼承來(lái)的每個(gè)對(duì)象都有一個(gè)單獨(dú)的鎖。由于JAVA中的每個(gè)對(duì)象都是從Object繼承來(lái)的。所以JAVA中的每個(gè)對(duì)象都有自己的鎖。這樣使它在共享的線程之間可以相互協(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í)行。2.2URL消重2.2.1URL消重的意義在SPIDER系統(tǒng)實(shí)際運(yùn)行的過(guò)程中，每秒下載的1

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

20、00個(gè)URL，如果每秒下載10個(gè)頁(yè)面，就會(huì)產(chǎn)生9001000次的URL排重操作，每次排重操作都要在幾百萬(wàn)至幾千萬(wàn)的URL庫(kù)中去查詢(xún)。這種操作對(duì)數(shù)據(jù)庫(kù)系統(tǒng)是一個(gè)災(zāi)難，理論上任何需要產(chǎn)生磁盤(pán)I/O動(dòng)作的存儲(chǔ)系統(tǒng)都無(wú)法滿(mǎn)足這種查詢(xún)的需求。2.2.2網(wǎng)絡(luò)爬蟲(chóng)URL去重儲(chǔ)存庫(kù)設(shè)計(jì)5電子科技大學(xué)XX學(xué)院本科畢業(yè)設(shè)計(jì)論文在爬蟲(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)題，就要考慮下載所依據(jù)的超，只要能夠控制待下載的URL不重復(fù)，基本可以解決同一個(gè)網(wǎng)頁(yè)重復(fù)下載的問(wèn)題。非常容易想到，在搜索引擎系統(tǒng)中建立一個(gè)全局的專(zhuān)門(mén)

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

22、有出現(xiàn)過(guò)，則將這個(gè)新的URL寫(xiě)入記事本的最后一行，否則就放棄該URL的下載。這種方式幾乎沒(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í)低下，這種方案肯定放棄。基于Hash算法的存儲(chǔ)對(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ò)，放棄下載，否則，將該

23、URL及其Hash地址作為鍵值對(duì)存放到Hash表中。這樣，URL去重存儲(chǔ)庫(kù)就是要維護(hù)一個(gè)Hash表，如果Hash函數(shù)設(shè)計(jì)的不好，在進(jìn)行映射的時(shí)候，發(fā)生碰撞的幾率很大，則再進(jìn)行碰撞的處理也非常復(fù)雜。而且，這里使用的是URL作為鍵，URL字符串也占用了很大的存儲(chǔ)空間?；贛D5壓縮映射的存儲(chǔ)MD5算法是一種加密算法，同時(shí)它也是基于Hash的算法。這樣就可以對(duì)URL字符串進(jìn)行壓縮，得到一個(gè)壓縮字符串，同時(shí)可以直接得到一個(gè)Hash地址。另外，MD5算法能夠?qū)⑷魏巫址畨嚎s為128位整數(shù)，并映射為物理地址，6第二章相關(guān)技術(shù)介紹而且MD5進(jìn)行Hash映射碰撞的幾率非常小，這點(diǎn)非常好。從另一個(gè)

24、方面來(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)行處理也是可行的。在Java中有一個(gè)Map類(lèi)非常好，你可以將壓縮后的URL串作為Key，而將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è)?；谇度胧紹erkeleyDB的存儲(chǔ)BerkeleyDB的特點(diǎn)就是只存儲(chǔ)鍵值對(duì)類(lèi)型數(shù)據(jù)，這和URL去重有很大關(guān)系。去重，可以考慮對(duì)某個(gè)鍵，存在一個(gè)值，

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

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

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

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

29、.io包中的InputStreamReader類(lèi)讀取該輸入流，將網(wǎng)頁(yè)下載下來(lái)。2.4爬行策略淺析2.4.1寬度或深度優(yōu)先搜索策略搜索引擎所用的第一代網(wǎng)絡(luò)爬蟲(chóng)主要是基于傳統(tǒng)的圖算法,如寬度優(yōu)先或深度優(yōu)先算法來(lái)索引整個(gè)Web,一個(gè)核心的URL集被用來(lái)作為一個(gè)種子集合,這種算法遞歸的跟蹤超到其它頁(yè)面,而通常不管頁(yè)面的內(nèi)容,因?yàn)樽罱K的目標(biāo)是這種跟蹤能覆蓋整個(gè)Web.這種策略通常用在通用搜索引擎中,因?yàn)橥ㄓ盟阉饕娅@得的網(wǎng)頁(yè)越多越好,沒(méi)有特定的要求.寬度優(yōu)先搜索算法寬度優(yōu)先搜索算法(又稱(chēng)廣度優(yōu)先搜索)是最簡(jiǎn)便的圖的搜索算法之一,這一算法也是很多重要的圖的算法的原型.Dijkstra單源最短

30、路徑算法和Prim最小生成樹(shù)算法都采用了和寬度優(yōu)先搜索類(lèi)似的思想.寬度優(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)先搜8第二章相關(guān)技術(shù)介紹索方法.也有很多研究將寬度優(yōu)先搜索策略應(yīng)用于聚焦爬蟲(chóng)中.其基本思想是認(rèn)為與初始URL在一定距離內(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ò)濾,算法的效率將變低.深度優(yōu)先搜索深度優(yōu)先搜

31、索所遵循的搜索策略是盡可能“深”地搜索圖.在深度優(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)的陷入(trapped)問(wèn)題,所以它既不是完備的,也不是最優(yōu)的.2.4.2聚焦搜索策略基于第一代網(wǎng)絡(luò)爬蟲(chóng)的搜索引擎抓取的網(wǎng)頁(yè)一般少于1000000個(gè)網(wǎng)頁(yè),極少重新搜集網(wǎng)頁(yè)并去刷新索引.而且其檢索速度非常慢

32、,一般都要等待10s甚至更長(zhǎng)的時(shí)間.隨著網(wǎng)頁(yè)頁(yè)信息的指數(shù)級(jí)增長(zhǎng)及動(dòng)態(tài)變化,這些通用搜索引擎的局限性越來(lái)越大,隨著科學(xué)技術(shù)的發(fā)展,定向抓取相關(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.聚焦爬蟲(chóng)會(huì)給它所下載下來(lái)的頁(yè)面分配一個(gè)評(píng)價(jià)分,然后根據(jù)得分排序,最后插入到一個(gè)隊(duì)列中.最好的下一個(gè)搜索將通過(guò)對(duì)彈出隊(duì)列中的第一個(gè)頁(yè)面進(jìn)行分析而執(zhí)行,這種策略保證爬蟲(chóng)能優(yōu)先跟蹤那些最有可能到目標(biāo)頁(yè)面的頁(yè)面.決定網(wǎng)絡(luò)爬蟲(chóng)搜索策略的關(guān)鍵是如何評(píng)價(jià)價(jià)值,即價(jià)值的計(jì)算方法

33、,不同的價(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)用在專(zhuān)業(yè)搜索引擎中,因?yàn)檫@種搜索引擎只關(guān)心某一特定主題的頁(yè)面.2.4.3基于內(nèi)容評(píng)價(jià)的搜索策略3,4,主要是根據(jù)主題(如關(guān)鍵詞、主題相關(guān)文檔) 基于內(nèi)容評(píng)價(jià)的搜索策略9電子科技大學(xué)XX學(xué)院本科畢業(yè)設(shè)計(jì)論文與文本的相似度來(lái)評(píng)價(jià)價(jià)值的高低,并以此決定其搜索策略:文本是指周?chē)恼f(shuō)明文字和URL上的文字信息,相似度的評(píng)價(jià)通常采用以下公式:sim(di,dj)=mk=1wikwjk(

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

35、是Google(:/Google),它獨(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ì)查詢(xún)結(jié)果的排序過(guò)程5,近年來(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ì)算:PR(p)=C1T+(1-C)Cin(p)PR(p)?out(C)?其中T為計(jì)算中的頁(yè)面總量,C1是阻尼常數(shù)因子,in(p)為所有指向p的頁(yè)面的集

36、合,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).HITS算法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)威性的10

37、第二章相關(guān)技術(shù)介紹作用.HITS(Hyperlink-InducedTopicSearch)算法是利用Hub?Authority方法的搜索方法,Authority表示一個(gè)頁(yè)面被其它頁(yè)面引用的數(shù)量,即該頁(yè)面的入度值.Hub表示一個(gè)Web頁(yè)面指向其它頁(yè)面的數(shù)量,即該頁(yè)面的出度值.算法如下:將查詢(xún)q提交給傳統(tǒng)的基于關(guān)鍵字匹配的搜索引擎.搜索引擎返回很多網(wǎng)頁(yè),從中取前n個(gè)網(wǎng)頁(yè)作為根集,用S表示.通過(guò)向S中加入被S引用的網(wǎng)頁(yè)和引用S的網(wǎng)頁(yè)將S擴(kuò)展成一個(gè)更大的集合T.以T中的Hub網(wǎng)頁(yè)為頂點(diǎn)集Vl,以權(quán)威網(wǎng)頁(yè)為頂點(diǎn)集V2,V1中的網(wǎng)頁(yè)到V2中的網(wǎng)頁(yè)的超為邊集E,形成一個(gè)二分有向圖SG=(V1,V2,E).

38、對(duì)V1中的任一個(gè)頂點(diǎn)v,用H(v)表示網(wǎng)頁(yè)v的Hub值,對(duì)V2中的頂點(diǎn)u,用A(u)表示網(wǎng)頁(yè)的Authority值.開(kāi)始時(shí)H(v)=A(u)=1,對(duì)u執(zhí)行公式(1)來(lái)修改它的A(u),對(duì)v執(zhí)行公式(2)來(lái)修改它的H(v),然后規(guī)X化A(u),H(v),如此不斷的重復(fù)計(jì)算上述運(yùn)算,直到A(u),H(v)收斂.A(u)=v:(v,u)EH(v)(1)H(v)=v:(v,u)EA(v)(2)式(1)反映了若一個(gè)網(wǎng)頁(yè)由很多好的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è)的

39、所有網(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以及Hub權(quán)重,計(jì)算復(fù)雜度隨頁(yè)面和數(shù)量的增長(zhǎng)呈指數(shù)級(jí)增長(zhǎng)基于鞏固學(xué)習(xí)的聚焦搜索近年來(lái)對(duì)Web信息資源分布的研究表明很多類(lèi)型相同的在構(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)的地方往往能獲得較好的回報(bào),而前兩種策略在這種情況下容易迷失方向.在

40、鞏固學(xué)習(xí)模型中,把網(wǎng)絡(luò)爬蟲(chóng)經(jīng)過(guò)若干無(wú)關(guān)頁(yè)面的訪問(wèn)之后才能獲得的主題相關(guān)頁(yè)面稱(chēng)為未來(lái)回報(bào),對(duì)未來(lái)回報(bào)的預(yù)測(cè)值稱(chēng)為未來(lái)回報(bào)價(jià)值,用Q價(jià)值表示.這種方法的核心就是學(xué)習(xí)如何計(jì)算的Q價(jià)值,根據(jù)未來(lái)回報(bào)價(jià)值確定正確的搜索方向.目前這類(lèi)搜索策略不足之處在于學(xué)習(xí)效率低的問(wèn)題,而且在訓(xùn)練過(guò)程中增加了用戶(hù)的負(fù)擔(dān).2.4.6基于語(yǔ)境圖的聚焦搜索11電子科技大學(xué)XX學(xué)院本科畢業(yè)設(shè)計(jì)論文基于鞏固學(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.

41、基于“語(yǔ)境圖”的搜索策略需要借助已有的通用搜索引擎構(gòu)建“語(yǔ)境圖”,而搜索引擎的檢索結(jié)果并非一定代表真實(shí)的web結(jié)構(gòu),因而這種方式也具有局限性.12第三章系統(tǒng)需求分析及模塊設(shè)計(jì)第三章系統(tǒng)需求分析及模塊設(shè)計(jì)3.1系統(tǒng)需求分析SPIDER要獲取的對(duì)象是存在于網(wǎng)絡(luò)上數(shù)以?xún)|計(jì)的網(wǎng)頁(yè)，這些網(wǎng)頁(yè)以超形式互相聯(lián)系在一起，每一網(wǎng)頁(yè)對(duì)應(yīng)一個(gè)超，也稱(chēng)統(tǒng)一資源定位符（URL）。我們可以把網(wǎng)絡(luò)看做一個(gè)圖M(V,E)，網(wǎng)絡(luò)中的網(wǎng)頁(yè)構(gòu)成節(jié)點(diǎn)集V，他們之間的構(gòu)成邊集E，SPIDER正是從某一節(jié)點(diǎn)開(kāi)始，沿著邊，遍歷圖M，每訪問(wèn)到圖中一個(gè)節(jié)點(diǎn)Vi，就進(jìn)行一定的處理。為了達(dá)到上述目的，一個(gè)SPIDER必須被設(shè)計(jì)成多線程的，A個(gè)線程

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

43、Web頁(yè)面解析,得到站內(nèi)URL和發(fā)現(xiàn)新站點(diǎn)URL另外,將URL隊(duì)列持久化到數(shù)據(jù)庫(kù),因此在SPIDER任務(wù)執(zhí)行端以外Down掉后,能夠斷點(diǎn)續(xù)傳.SPIDER客戶(hù)端線程間的協(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)更新等.如果SPIDER以300頁(yè)?秒的速度下載Web頁(yè)面,平均將會(huì)產(chǎn)生2000多個(gè)URL12,因此簡(jiǎn)單的采用內(nèi)存數(shù)據(jù)結(jié)構(gòu)

44、存儲(chǔ)這些URL隊(duì)列有一定的問(wèn)題,系統(tǒng)沒(méi)有足夠的內(nèi)存空間;而采用直接持久化到數(shù)據(jù)庫(kù),則需要大量的數(shù)據(jù)庫(kù)連接、查詢(xún)等操作,系統(tǒng)效率會(huì)明顯下降.如果采用URL壓縮的辦法,盡管在一定程度上可以平衡空間和時(shí)間的矛盾,但仍然不適用于大規(guī)模數(shù)據(jù)采集的SPIDER.13電子科技大學(xué)XX學(xué)院本科畢業(yè)設(shè)計(jì)論文圖3.2SPIDER體系結(jié)3.3各主要功能模塊（類(lèi)）設(shè)計(jì)SPIDERWorker類(lèi)：該類(lèi)繼承自線程類(lèi)，請(qǐng)求任務(wù)URL，根據(jù)得到的URL下載相應(yīng)的HTML代碼，利用HTML代碼調(diào)用其他模塊完成相關(guān)處理。SPIDERManager類(lèi)：該類(lèi)用于控制SPIDERWorker線程。UrlQueueManager類(lèi)：該類(lèi)

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

46、初始URLs加入到等待隊(duì)列創(chuàng)建啟動(dòng)爬蟲(chóng)線程從URL等待隊(duì)列獲取任務(wù)URL下載URL對(duì)應(yīng)的HTML代碼解析HTML，獲取URLs將相對(duì)地址轉(zhuǎn)換是否為絕對(duì)地址為絕對(duì)地址是否為非法URL是否為重復(fù)URL將URLs加入到URL等待隊(duì)列15電子科技大學(xué)XX學(xué)院本科畢業(yè)設(shè)計(jì)論文第四章系統(tǒng)分析與設(shè)計(jì)4.1SPIDER構(gòu)造分析構(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í)要把每次

47、遞歸壓入堆棧，但在本系統(tǒng)設(shè)計(jì)中使用的是多線程，它允許一次運(yùn)行多個(gè)任務(wù)，但是，多線程與遞歸是不兼容的。因?yàn)樵谶@一過(guò)程中每一個(gè)線程都有自己的堆棧，而當(dāng)一個(gè)方法調(diào)用它自身時(shí)，它們需要使用同一個(gè)堆棧。這就意味著遞歸的SPIDER程序不能使用多線程。每個(gè)SPIDER線程都會(huì)獨(dú)立的去完成獲取URLs的任務(wù)，并將獲取到的URLs加入一個(gè)公共的URL等待隊(duì)列中。圖4.1圖4.1表示了該系統(tǒng)爬蟲(chóng)線程的實(shí)現(xiàn)策略。假設(shè)線程1從URL隊(duì)列中獲取一條任務(wù)URL1，然后它會(huì)下載對(duì)應(yīng)的HTML，解析出里面包含URLs，然后16第四章系統(tǒng)實(shí)現(xiàn)再將這些URLs加入到URL隊(duì)列中去。然后線程1會(huì)再?gòu)腢RL隊(duì)列中獲取新的URL，下

48、載HTML代碼，并解析出URLs，再加入到URL隊(duì)列中去。而線程2同時(shí)也會(huì)下載它獲取到的URL2對(duì)應(yīng)的HTML代碼，解析出URLs加入到等待隊(duì)列中。以此類(lèi)推，多個(gè)線程并發(fā)地去完成爬蟲(chóng)工作。4.2爬行策略分析圖4.2.1因?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。然后依次獲取這些URLs對(duì)應(yīng)的HTML里的URLs，當(dāng)這一層所有的URLs都下載解析完后，在獲取下一層的信息。通過(guò)這種循環(huán)的獲取方式實(shí)現(xiàn)廣度優(yōu)先爬行。如圖4.2.1，假如a代表初始U

49、RL，bcd為以a獲取的3個(gè)URLs，efg為以b獲取的URLs，以此類(lèi)推。那么這些URLs獲取的順序就是abcdefghijklmnop這樣一個(gè)順序。當(dāng)獲取到b的URLs之后，并不會(huì)馬上去解析這些URLs，而是先解析同b在同一層中的cd對(duì)應(yīng)的URLs。當(dāng)這一層URLs全部解析完后，再開(kāi)始下一層URLs。廣度優(yōu)先算法的等待隊(duì)列設(shè)計(jì)如圖4.2.2所示。17電子科技大學(xué)XX學(xué)院本科畢業(yè)設(shè)計(jì)論文圖4.2.2圖4.2.2列舉了不同時(shí)間段時(shí)，URL等待隊(duì)列的存儲(chǔ)狀態(tài)。第一個(gè)方框是將初始URL：a加入到等待隊(duì)列。第二個(gè)方框?yàn)?，解析a對(duì)應(yīng)HTML獲取URLs：bcd，同時(shí)刪除a。第三個(gè)方框?yàn)椋馕鯾對(duì)應(yīng)HT

50、ML獲取URLs：efg，同時(shí)刪除URL：b。第四個(gè)方框?yàn)?，解析e對(duì)應(yīng)HTML獲取URLs：nop，并刪除e。通過(guò)這樣的存儲(chǔ)方法實(shí)現(xiàn)如圖4.2.1的廣度爬行算法。4.3URL抽取，解析和保存4.3.1URL抽取通過(guò)觀察研究HTML代碼，我們可以知道。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á)到目的。我猜200905315-31火影忍者331，頁(yè)面上303既是18第四章系統(tǒng)實(shí)現(xiàn)通過(guò)觀察得知，一般href標(biāo)簽是以href=這樣的形式出現(xiàn)的。但是不同的網(wǎng)站href=后面的內(nèi)容有所不同。比如href=url這樣情

51、況，我們就可以通過(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)。通過(guò)這種方法，我們獲取網(wǎng)頁(yè)中大部分的URLs。但是有些URLs是通過(guò)提交表單，或者通過(guò)javascript來(lái)跳轉(zhuǎn)的。這些情況就需要更細(xì)致的考慮，才能獲取。4.3.2URL解析截取出來(lái)的字符串，可能為相對(duì)地址或者絕對(duì)地址。所以需要判斷URL為絕對(duì)地址，還是相對(duì)地址。相對(duì)地址需要先轉(zhuǎn)化為絕對(duì)地址，再進(jìn)行過(guò)濾。因?yàn)榻馕龀鰜?lái)的URL地址可能是一些文件的地址，或者為javascript文件或

52、者css文件。這些格式的URL是無(wú)法獲取HTML代碼的，也就不可能進(jìn)行URL解析。所以我們需要過(guò)濾掉這些URLs。然后再進(jìn)行URL消重處理，最后加入到URL等待隊(duì)列。為了把爬行限制在同一站點(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,一般情況下,同一內(nèi)所有頁(yè)面對(duì)應(yīng)URL的host是相同的,所以可以使用host匹配作為判斷超鏈?zhǔn)欠裰赶蛘就獾臉?biāo)準(zhǔn).進(jìn)一步研究發(fā)現(xiàn),很多大型中一個(gè)分類(lèi)目錄對(duì)應(yīng)一個(gè)主機(jī),所以前面的判斷標(biāo)準(zhǔn)必須改進(jìn).研究host的組成

53、可知,host的格式一般為站內(nèi)分類(lèi).站點(diǎn)標(biāo)志串.站點(diǎn)類(lèi)型各異的串.站點(diǎn)類(lèi)型串只有com|edu|gov|net|國(guó)家域名幾種類(lèi)型,所以我們?nèi)≌军c(diǎn)類(lèi)型各異串前面的串,即站點(diǎn)標(biāo)志串作匹配,超鏈URL的host中是否包含此串,為超鏈?zhǔn)欠裾緝?nèi)的判斷標(biāo)準(zhǔn).4.3.3URL保存因?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，以便加入新的URLs

54、；第二段為數(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)存入。19電子科技大學(xué)XX學(xué)院本科畢業(yè)設(shè)計(jì)論文圖4.3.3表示了URL等待隊(duì)列的結(jié)構(gòu)。圖4.3.320第五章系統(tǒng)實(shí)現(xiàn)第五章系統(tǒng)實(shí)現(xiàn)5.1實(shí)現(xiàn)工具操作系統(tǒng)是winXP;JAVA程序的編寫(xiě)工具是eclipse-SDK-3.2.1-win32；數(shù)據(jù)庫(kù)是MYSQL55.0.51a。5.2爬蟲(chóng)工作這個(gè)類(lèi)繼承自線程類(lèi)，實(shí)現(xiàn)線程在java中有兩種方法：一種是直接繼承Thread類(lèi)；一種是實(shí)現(xiàn)Runnable接口。我采用了第二種方法：publiccl

55、assSpiderWorkerimplementsRunnable在這個(gè)類(lèi)中必須要實(shí)現(xiàn)重寫(xiě)run()這個(gè)方法。我在這個(gè)方法里定義了一個(gè)循環(huán)，這個(gè)線程會(huì)重復(fù)地執(zhí)行爬蟲(chóng)動(dòng)作。在這個(gè)循環(huán)里，首先會(huì)向URL等待隊(duì)列里請(qǐng)求一個(gè)URL。因?yàn)閁RL隊(duì)列會(huì)出現(xiàn)為空或者被其他線程占用的情況。所以我在這里寫(xiě)了一個(gè)循環(huán)：s=null;while(s=null)s=urlQueueManager.getWaitQueue();如果沒(méi)有得到URL就繼續(xù)向URL等待隊(duì)列申請(qǐng)。當(dāng)?shù)玫饺蝿?wù)URL以后，會(huì)通過(guò)這個(gè)URL得到對(duì)應(yīng)的HTML代碼。具體方法是調(diào)用getHtml(Stringsourse_url)這個(gè)方法：URLCon

56、nectionconnection=null;InputStreamReaderin=null;BufferedReaderbr=null;URLurl=null;url=newURL(sourse_url);connection=(URLConnection)url.openConnection();connection.connect();/打開(kāi)的連接讀取的輸入流。in=newInputStreamReader(url.openStream();br=newBufferedReader(in);Stringc;21電子科技大學(xué)XX學(xué)院本科畢業(yè)設(shè)計(jì)論文while(c=br.readLine(

57、)!=null)html.append(c);returnhtml.toString();這個(gè)方法是通過(guò)調(diào)用JAVA里面的URL這個(gè)類(lèi)，可以用給定的URL構(gòu)造這個(gè)類(lèi)的一個(gè)實(shí)例，然后通過(guò)openStream(這)個(gè)方法得到HTML代碼的數(shù)據(jù)流，然后再一行一行地把數(shù)據(jù)流轉(zhuǎn)換成String字符串，再用StringBuffer將這些字符串拼接成一個(gè)完整的HTML代碼。當(dāng)?shù)玫紿TML代碼以后，程序就會(huì)調(diào)用Url_Parse這個(gè)類(lèi)里面的方法來(lái)解析HTML。5.3URL解析從HTML代碼中提取URLs，主要是通過(guò)檢索字符串中的href字符串來(lái)實(shí)現(xiàn)的。對(duì)于一個(gè)HTML代碼，我尋找其中的href=字符串，然后記

58、錄它的下表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ò)后，操作終止。首頁(yè)動(dòng)作片恐怖片愛(ài)情片例如上面那段HTML代碼。我們先檢索href=標(biāo)記，然后判斷出第i+1位為一個(gè)雙引號(hào)，所以我們可以截取i+1位到第2個(gè)雙引號(hào)的位置。之間的這段字符串即為URL。當(dāng)完成這一步操作后，原字符串被截取從“class=開(kāi)始。我們繼續(xù)檢索href=標(biāo)簽，判斷它的第i+1位為一個(gè)單引號(hào)，所以我們又截取i+1位到第2個(gè)單

59、引號(hào)的位置。這步以后原字符串又被截取為“target=”開(kāi)始，我們可以繼續(xù)檢索href=標(biāo)簽。這個(gè)地方href=沒(méi)有接續(xù)任何符號(hào)，所以當(dāng)我們沒(méi)有發(fā)現(xiàn)單引號(hào)或雙引號(hào)的時(shí)候，可以判斷為這種情況。我們就去檢索空格和標(biāo)簽，以下標(biāo)較小的字符作為截取URL的結(jié)束標(biāo)記。下面是href=后面接續(xù)雙引號(hào)情況的JAVA代碼，其他情況的代碼方式相同。publicvoidgetHref_UrlsList(Stringhtml_text,StringfromURL,UrlQueueManagerurlQueueManager,intbiaoji)22第五章系統(tǒng)實(shí)現(xiàn)/站內(nèi)URL隊(duì)列ListsiteInsideUrls=n

60、ewArrayList();Stringurl=;/HTML中是否還含有href標(biāo)簽booleanhaveHref=html_text.contains(href);while(haveHref)html_text=html_text.substring(html_text.indexOf(href=)+5);/當(dāng)href=后以開(kāi)頭的情況if(=html_text.charAt(0)html_text=html_text.substring(1);url=html_text.substring(0,html_text.indexOf();url=addURLhost(fromURL,url);