網(wǎng)絡(luò)爬蟲的設(shè)計與實現(xiàn)-畢業(yè)(完整版)資料

網(wǎng)絡(luò)爬蟲的設(shè)計與實現(xiàn)畢業(yè)（完整版）資料(可以直接使用，可編輯優(yōu)秀版資料，歡迎下載）

網(wǎng)絡(luò)爬蟲的設(shè)計與實現(xiàn)畢業(yè)（完整版）資料(可以直接使用，可編輯優(yōu)秀版資料，歡迎下載）摘要 網(wǎng)絡(luò)爬蟲是一種自動搜集互聯(lián)網(wǎng)信息的程序。通過網(wǎng)絡(luò)爬蟲不僅能夠為搜索引擎采集網(wǎng)絡(luò)信息，而且可以作為定向信息采集器，定向采集某些網(wǎng)站下的特定信息，如招聘信息，租房信息等。 本文通過JAVA實現(xiàn)了一個基于廣度優(yōu)先算法的多線程爬蟲程序。本論文闡述了網(wǎng)絡(luò)爬蟲實現(xiàn)中一些主要問題：為何使用廣度優(yōu)先的爬行策略，以及如何實現(xiàn)廣度優(yōu)先爬行；為何要使用多線程，以及如何實現(xiàn)多線程；系統(tǒng)實現(xiàn)過程中的數(shù)據(jù)存儲；網(wǎng)頁信息解析等。 通過實現(xiàn)這一爬蟲程序，可以搜集某一站點的URLs，并將搜集到的URLs存入數(shù)據(jù)庫。【關(guān)鍵字】網(wǎng)絡(luò)爬蟲；JAVA；廣度優(yōu)先；多線程。ABSTRACTSPIDERisaprogramwhichcanautocollectinformationsfrominternet.SPIDERcancollectdataforsearchengines,alsocanbeaDirectionalinformationcollector,collectsspecificallyinformationsfromsomewebsites,suchasHRinformations,houserentinformations. Inthispaper,useJAVAimplementsabreadth-firstalgorithmmulti-threadSPDIER.ThispaperexpatiatessomemajorproblemsofSPIDER:whytousebreadth-firstcrawlingstrategy,andhowtoimplementbreadth-firstcrawling;whytousemulti-threading,andhowtoimplementmulti-thread;datastructure;HTMLcodeparse.etc.

ThisSPIDERcancollectURLsfromonewebsite,andstoreURLsintodatabase.【KEYWORD】SPIDER;JAVA;BreadthFirstSearch;multi-threads.目錄第一章引言 1第二章相關(guān)技術(shù)介紹 22.1JAVA線程 22.1.1線程概述 22.1.2JAVA線程模型 22.1.3創(chuàng)建線程 32.1.4JAVA中的線程的生命周期 42.1.5JAVA線程的結(jié)束方式 42.1.6多線程同步 52.2URL消重 52.2.1URL消重的意義 52.2.2網(wǎng)絡(luò)爬蟲URL去重儲存庫設(shè)計 52.2.3LRU算法實現(xiàn)URL消重 72.3URL類訪問網(wǎng)絡(luò) 82.4爬行策略淺析 82.4.1寬度或深度優(yōu)先搜索策略 82.4.2聚焦搜索策略 92.4.3基于內(nèi)容評價的搜索策略 92.4.4基于鏈接結(jié)構(gòu)評價的搜索策略 102.4.5基于鞏固學(xué)習(xí)的聚焦搜索 112.4.6基于語境圖的聚焦搜索 11第三章系統(tǒng)需求分析及模塊設(shè)計 133.1系統(tǒng)需求分析 133.2SPIDER體系結(jié)構(gòu) 133.3各主要功能模塊（類）設(shè)計 143.4SPIDER工作過程 14第四章系統(tǒng)分析與設(shè)計 164.1SPIDER構(gòu)造分析 164.2爬行策略分析 174.3URL抽取，解析和保存 184.3.1URL抽取 184.3.2URL解析 194.3.3URL保存 19第五章系統(tǒng)實現(xiàn) 215.1實現(xiàn)工具 215.2爬蟲工作 215.3URL解析 225.4URL隊列管理 245.4.1URL消重處理 245.4.2URL等待隊列維護 265.4.3數(shù)據(jù)庫設(shè)計 27第六章系統(tǒng)測試 29第七章結(jié)論 32參考文獻 33致謝 34外文資料原文 35譯文 51第一章引言 隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)上的信息呈爆炸式增長。這使得人們在網(wǎng)上找到所需的信息越來越困難，這種情況下搜索引擎應(yīng)運而生。搜索引擎搜集互聯(lián)網(wǎng)上數(shù)以億計的網(wǎng)頁，并為每個詞建立索引。在建立搜索引擎的過程中，搜集網(wǎng)頁是非常重要的一個環(huán)節(jié)。爬蟲程序就是用來搜集網(wǎng)頁的程序。以何種策略偏歷互聯(lián)網(wǎng)上的網(wǎng)頁，也成了爬蟲程序主要的研究方向。現(xiàn)在比較流行的搜索引擎，比如google，百度，它們爬蟲程序的技術(shù)內(nèi)幕一般都不公開。目前幾種比較常用的爬蟲實現(xiàn)策略：廣度優(yōu)先的爬蟲程序，Repetitive爬蟲程序，定義爬行爬蟲程序，深層次爬行爬蟲程序。此外,還有根據(jù)概率論進行可用Web頁的數(shù)量估算,用于評估互聯(lián)網(wǎng)Web規(guī)模的抽樣爬蟲程序;采用爬行深度、頁面導(dǎo)入鏈接量分析等方法,限制從程序下載不相關(guān)的Web頁的選擇性爬行程序等等。 爬蟲程序是一個自動獲取網(wǎng)頁的程序。它為搜索引擎從互聯(lián)網(wǎng)上下載網(wǎng)頁，是搜索引擎的重要組成部分。爬蟲程序的實現(xiàn)策略，運行效率直接影響搜索引擎的搜索結(jié)果。不同的搜索引擎，會根據(jù)對搜索結(jié)果的不同需求，選擇最合適的爬行策略來搜集互聯(lián)網(wǎng)上的信息。高效，優(yōu)秀的爬蟲程序可以使人們在互聯(lián)網(wǎng)上尋找到更及時，更準確的信息。實現(xiàn)網(wǎng)絡(luò)爬蟲的重點和難點有：多線程的實現(xiàn)；對臨界資源的分配；遍歷web圖的遍歷策略選擇和實現(xiàn)；存儲數(shù)據(jù)結(jié)構(gòu)的選擇和實現(xiàn)。 本文通過JAVA語言實現(xiàn)一個基于廣度優(yōu)先偏歷算法的多線程爬蟲程序。通過實現(xiàn)此爬蟲程序可以定點搜集某一站點的URLs，如果需要搜集其他信息，可以在解析URLs的同時，解析獲取相應(yīng)信息。第二章相關(guān)技術(shù)介紹2.1JAVA線程2.1.1線程概述 幾乎每種操作系統(tǒng)都支持線程的概念—進程就是在某種程度上相互隔離的，獨立運行的程序。一般來說，這些操作系統(tǒng)都支持多進程操作。所謂多進程，就是讓系統(tǒng)（好像）同時運行多個程序。比如，我在MicrosoftWord編寫本論文的時候，我還打開了一個mp3播放器來播放音樂，偶爾的，我還會再編輯Word的同時讓我的機器執(zhí)行一個打印任務(wù)，而且我還喜歡通過IE從網(wǎng)上下載一個Flash動畫。對于我來說，這些操作都是同步進行的，我不需要等一首歌曲放完了再來編輯我的論文。看起來，它們都同時在我的機器上給我工作。 事實的真相是，對于一個CPU而言，它在某一個時間點上，只能執(zhí)行一個程序。CPU不斷的在這些程序之間“跳躍”執(zhí)行。那么，為什么我們看不出任何的中斷現(xiàn)象呢？這是因為，相對于我們的感覺，它的速度實在太快了。我們?nèi)说母兄獣r間可能以秒來計算。而對于CPU而言，它的時間是以毫秒來計算的，從我們?nèi)庋劭磥?，它們就是一個連續(xù)的動作。 因此，雖然我們看到的都是一些同步的操作，但實際上，對于計算機而言，它在某個時間點上只能執(zhí)行一個程序，除非你的計算機是多CPU的。 多線程（Multi-Thread）擴展了多進程（multi-Process）操作的概念，將任務(wù)的劃分下降到了程序級別，使得各個程序似乎可以在同一個時間內(nèi)執(zhí)行多個任務(wù)。每個任務(wù)稱為一個線程，能夠同時運行多個線程的程序稱為多線程程序。 多線程和多進程有什么區(qū)別呢？對于進程來說，每個進程都有自己的一組完整的變量，而線程則共享相同的數(shù)據(jù)。2.1.2JAVA線程模型 我們知道，計算機程序得以執(zhí)行的三個要素是：CPU，程序代碼，可存取的數(shù)據(jù)。在JAVA語言中，多線程的機制是通過虛擬CPU來實現(xiàn)的?？梢孕蜗蟮睦斫鉃?在一個JAVA程序內(nèi)部虛擬了多臺計算機，每臺計算機對應(yīng)一個線程，有自己的CPU，可以獲取所需的代碼和數(shù)據(jù)，因此能獨立執(zhí)行任務(wù)，相互間還可以共用代碼和數(shù)據(jù)。JAVA的線程是通過java.lang.Thread類來實現(xiàn)的，它內(nèi)部實現(xiàn)了虛擬CPU的功能，能夠接收和處理傳遞給它的代碼和數(shù)據(jù)，并提供了獨立的運行控制功能。 我們知道，每個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來實現(xiàn)的。Thread有很多個構(gòu)造器來創(chuàng)建一個線程（Thread）實例： Thread();創(chuàng)建一個線程。 Thread(Runnabletarget);創(chuàng)建一個線程，并指定一個目標。 Thread(Runnabletarget,Stringname);創(chuàng)建一個名為name的目標為target的線程。 Thread(Stringname);創(chuàng)建一個名為name的線程。 Thread(ThreadGroupgroup,Runnabletarget);創(chuàng)建一個隸屬于group線程組，目標為target的線程。 通常，我們可以將一個類繼承Thread，然后，覆蓋Thread中的run()方法，這樣讓這個類本身也就成了線程。 每個線程都是通過某個特定Thread對象所對應(yīng)的方法run()來完成其操作的，方法run()稱為線程體。 使用start()方法，線程進入Runnable狀態(tài)，它將線程調(diào)度器注冊這個線程。調(diào)用start()方法并不一定馬上會執(zhí)行這個線程，正如上面所說，它只是進入Runnble而不是Running。創(chuàng)建線程方式二 通過實現(xiàn)Runnable接口并實現(xiàn)接口中定義的唯一方法run()，可以創(chuàng)建一個線程。在使用Runnable接口時，不能直接創(chuàng)建所需類的對象并運行它，而是必須從Thread類的一個實例內(nèi)部運行它。 從上面兩種創(chuàng)建線程的方法可以看出，如果繼承Thread類，則這個類本身可以調(diào)用start方法，也就是說將這個繼承了Thread的類當作目標對象；而如果實現(xiàn)Runnable接口，則這個類必須被當作其他線程的目標對象。2.1.4JAVA中的線程的生命周期 JAVA的線程從產(chǎn)生到消失,可分為5種狀態(tài)：新建（New），可運行（Runnable），運行（Running），阻塞（Blocked）以及死亡（Dead）。其中，Running狀態(tài)并非屬于JAVA規(guī)范中定義的線程狀態(tài)，也就是說，在JAVA規(guī)范中，并沒有將運行（Running）狀態(tài)真正的設(shè)置為一個狀態(tài)，它屬于可運行狀態(tài)的一種。 當使用new來新建一個線程時，它處于New狀態(tài)，這個時候，線程并未進行任何操作。 然后，調(diào)用線程的start()方法，來向線程調(diào)度程序（通常是JVM或操作系統(tǒng)）注冊一個線程，這個時候，這個線程一切就緒，就等待CPU時間了。 線程調(diào)度程序根據(jù)調(diào)度策略來調(diào)度不同的線程，調(diào)用線程的run方法給已經(jīng)注冊的各個線程以執(zhí)行的機會，被調(diào)度執(zhí)行的線程進入運行（Running）狀態(tài)。當線程的run方法運行完畢，線程將被拋棄，進入死亡狀態(tài)。你不能調(diào)用restart方法來重新開始一個處于死亡狀態(tài)的線程，但是，你可以調(diào)用處于死亡狀態(tài)的線程對象的各個方法。 如果線程在運行（Running）狀態(tài)中因為I/O阻塞，等待鍵盤鍵入，調(diào)用了線程的sleep方法，調(diào)用了對象的wait()方法等，則線程將進入阻塞狀態(tài)，直到這些阻塞原因被解除，如：IO完成，鍵盤輸入了數(shù)據(jù)，調(diào)用sleep方法后的睡眠時間到以及其他線程調(diào)用了對象的notify或notifyAll方法來喚醒這個因為等待而阻塞的線程等，線程將返回到Runnable狀態(tài)重新等待調(diào)度程序調(diào)度，注意，被阻塞的線程不會直接返回到Running狀態(tài)，而是重新回到Runnable狀態(tài)等待線程調(diào)度程序的調(diào)用。 線程調(diào)度程序會根據(jù)調(diào)度情況，將正在運行中的線程設(shè)置為Runnable狀態(tài)，例如，有一個比當前運行狀態(tài)線程更高運行等級的線程進入Runnable狀態(tài)，就可能將當前運行的線程從Running狀態(tài)“踢出”,讓它回到Runnable狀態(tài)。2.1.5JAVA線程的結(jié)束方式 線程會以以下三種方式之一結(jié)束： 線程到達其run()方法的末尾； 線程拋出一個未捕獲到的Exception或Error； 另一個線程調(diào)用一個Deprecated的stop()方法。注意，因為這個方法會引起線程的安全問題，已經(jīng)被不推薦使用了，所以，不要再程序調(diào)用這個方法。2.1.6多線程同步 當同時運行的相互獨立的線程需要共享數(shù)據(jù)并且需要考慮其他線程的狀態(tài)時，就需要使用一套機制使得這些線程同步，避免在爭用資源時發(fā)生沖突，甚至發(fā)生死鎖。JAVA提供了多種機制以實現(xiàn)線程同步。多數(shù)JAVA同步是以對象鎖定為中心的。JAVA中從Object對象繼承來的每個對象都有一個單獨的鎖。由于JAVA中的每個對象都是從Object繼承來的。所以JAVA中的每個對象都有自己的鎖。這樣使它在共享的線程之間可以相互協(xié)調(diào)。在JAVA中實現(xiàn)線程同步的另一個方法是通過使用synchronized關(guān)鍵字。JAVA使用synchronized關(guān)鍵字來定義程序中要求線程同步的部分。synchronized關(guān)鍵字實現(xiàn)的基本操作是把每個需要線程同步的部分定義為一個臨界區(qū)，在臨界區(qū)中同一時刻只有一個線程被執(zhí)行。2.2URL消重2.2.1URL消重的意義 在SPIDER系統(tǒng)實際運行的過程中，每秒下載的10個頁面中，分析的URL大多數(shù)是重復(fù)的，實際上新的URL才幾個。在持續(xù)下載的過程中，新的URL非常少，還是以新浪網(wǎng)舉例，1天24小時中總共出現(xiàn)的新URL也就是10000左右。這種情況非常類似于操作系統(tǒng)中虛擬儲存器管理。所謂的虛擬儲存器，是指具有請求調(diào)入和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種儲存器系統(tǒng)。其關(guān)鍵在于允許一個作業(yè)只裝入部分的頁或段就可以啟動運行，當作業(yè)運行的時候在內(nèi)存中找不到所需要的頁或段的時候，就會發(fā)生請求調(diào)入，而從外存中找到的頁或段將會置換內(nèi)存中暫時不運行的頁面到外存。 URL消重工作量是非常巨大的。以下在新浪新聞頁面為例，新浪一個新聞頁面大小為50～60k，每個頁面有90～100個URL，如果每秒下載10個頁面，就會產(chǎn)生900～1000次的URL排重操作，每次排重操作都要在幾百萬至幾千萬的URL庫中去查詢。這種操作對數(shù)據(jù)庫系統(tǒng)是一個災(zāi)難，理論上任何需要產(chǎn)生磁盤I/O動作的存儲系統(tǒng)都無法滿足這種查詢的需求。2.2.2網(wǎng)絡(luò)爬蟲URL去重儲存庫設(shè)計 在爬蟲啟動工作的過程中，我們不希望同一個網(wǎng)頁被多次下載，因為重復(fù)下載不僅會浪費CPU機時，還會為搜索引擎系統(tǒng)增加負荷。而想要控制這種重復(fù)性下載問題，就要考慮下載所依據(jù)的超鏈接，只要能夠控制待下載的URL不重復(fù)，基本可以解決同一個網(wǎng)頁重復(fù)下載的問題。 非常容易想到，在搜索引擎系統(tǒng)中建立一個全局的專門用來檢測，是否某一個URL對應(yīng)的網(wǎng)頁文件曾經(jīng)被下載過的URL存儲庫，這就是方案。接著要考慮的就是如何能夠更加高效地讓爬蟲工作，確切地說，讓去重工作更加高效。如果實現(xiàn)去重，一定是建立一個URL存儲庫，并且已經(jīng)下載完成的URL在進行檢測時候，要加載到內(nèi)存中，在內(nèi)存中進行檢測一定會比直接從磁盤上讀取速度快很多。我們先從最簡單的情況說起，然后逐步優(yōu)化，最終得到一個非常不錯的解決方案?；诖疟P的順序存儲 這里，就是指把每個已經(jīng)下載過的URL進行順序存儲。你可以把全部已經(jīng)下載完成的URL存放到磁盤記事本文件中。每次有一個爬蟲線程得到一個任務(wù)URL開始下載之前，通過到磁盤上的該文件中檢索，如果沒有出現(xiàn)過，則將這個新的URL寫入記事本的最后一行，否則就放棄該URL的下載。這種方式幾乎沒有人考慮使用了，但是這種檢查的思想是非常直觀的。試想，如果已經(jīng)下載了100億網(wǎng)頁，那么對應(yīng)著100億個鏈接，也就是這個檢查URL是否重復(fù)的記事本文件就要存儲這100億URL，況且，很多URL字符串的長度也不小，占用存儲空間不說，查找效率超級低下，這種方案肯定放棄?；贖ash算法的存儲 對每一個給定的URL，都是用一個已經(jīng)建立好的Hash函數(shù)，映射到某個物理地址上。當需要進行檢測URL是否重復(fù)的時候，只需要將這個URL進行Hash映射，如果得到的地址已經(jīng)存在，說明已經(jīng)被下載過，放棄下載，否則，將該URL及其Hash地址作為鍵值對存放到Hash表中。這樣，URL去重存儲庫就是要維護一個Hash表，如果Hash函數(shù)設(shè)計的不好，在進行映射的時候，發(fā)生碰撞的幾率很大，則再進行碰撞的處理也非常復(fù)雜。而且，這里使用的是URL作為鍵，URL字符串也占用了很大的存儲空間?；贛D5壓縮映射的存儲 MD5算法是一種加密算法，同時它也是基于Hash的算法。這樣就可以對URL字符串進行壓縮，得到一個壓縮字符串，同時可以直接得到一個Hash地址。另外，MD5算法能夠?qū)⑷魏巫址畨嚎s為128位整數(shù)，并映射為物理地址，而且MD5進行Hash映射碰撞的幾率非常小，這點非常好。從另一個方面來說，非常少的碰撞，對于搜索引擎的爬蟲是可以容忍的。況且，在爬蟲進行檢測的過程中，可以通過記錄日志來保存在進行MD5時發(fā)生碰撞的URL，通過單獨對該URL進行處理也是可行的。 在Java中有一個Map類非常好，你可以將壓縮后的URL串作為Key，而將Boolean作為Value進行存儲，然后將工作中的Map在爬蟲停止工作后序列化到本地磁盤上；當下一次啟動新的爬蟲任務(wù)的時候，再將這個Map反序列化到內(nèi)存中，供爬蟲進行URL去重檢測。基于嵌入式BerkeleyDB的存儲 BerkeleyDB的特點就是只存儲鍵值對類型數(shù)據(jù)，這和URL去重有很大關(guān)系。去重，可以考慮對某個鍵，存在一個值，這個值就是那個鍵的狀態(tài)。使用了BerkeleyDB，你就不需要考慮進行磁盤IO操作的性能損失了，這個數(shù)據(jù)庫在設(shè)計的時候很好地考慮了這些問題，并且該數(shù)據(jù)庫支持高并發(fā)，支持記錄的順序存儲和隨機存儲，是一個不錯的選擇。 URL去重存儲庫使用BerkeleyDB，壓縮后的URL字符串作為Key，或者直接使用壓縮后的URL字節(jié)數(shù)組作為Key，對于Value可以使用Boolean，一個字節(jié)，或者使用字節(jié)數(shù)組，實際Value只是一個狀態(tài)標識，減少Value存儲占用存儲空間?；诓悸∵^濾器（BloomFilter）的存儲 使用布隆過濾器，設(shè)計多個Hash函數(shù)，也就是對每個字符串進行映射是經(jīng)過多個Hash函數(shù)進行映射，映射到一個二進制向量上，這種方式充分利用了比特位。不過，我沒有用過這種方式，有機會可以嘗試一下?？梢詤⒖糋oogle的://googlechinablog/2007/07/bloom-filter.html。2.2.3LRU算法實現(xiàn)URL消重 用雙向鏈表來實現(xiàn)大容量cache的LRU算法。原理是：cache的所有位置都用雙向鏈表連接起來，當一個位置被命中后，就將通過調(diào)整鏈表的指向?qū)⒃撐恢谜{(diào)整到鏈表的頭位置，新加入的內(nèi)容直接放在鏈表的頭上。這樣，在進行過多次查找操作后，最近被命中過的內(nèi)容就像鏈表的頭移動，而沒有命中過的內(nèi)容就向鏈表的后面移動。當需要替換時，鏈表最后的位置就是最近最少被命中位置，我們只需要將新的內(nèi)容放在鏈表前面，淘汰鏈表最后的位置就實現(xiàn)了LRU算法。2.3URL類訪問網(wǎng)絡(luò) JAVA提供了許多支Internet連接的類，URL類就是其中之一。在使用URL類之前，必須創(chuàng)建一個URL對象，創(chuàng)建的方法是使用其構(gòu)造函數(shù)，通過向其指定一個URL地址，就能實例化該類。如：URLurl=newURL（://sina）； 如果傳遞無效的URL給URL對象，該對象會拋出MalformedURLException異常。當成功創(chuàng)建一個URL對象后，我們調(diào)用openConnection函數(shù)建立與URL的通信，此時，我們就獲得了一個URLConnection對象的引用，URLConnection類包含了許多與網(wǎng)絡(luò)上的URL通信的函數(shù)。在下載網(wǎng)頁前，我們需要判斷目標網(wǎng)頁是否存在，這時調(diào)用URLConnection類的getHeaderField()方法，獲得服務(wù)器返回給SPIDER程序的響應(yīng)碼，如果響應(yīng)碼包含”20*”字樣，表示目標網(wǎng)頁存在，下一步就下載網(wǎng)頁，否則就不下載。getHeaderField()方法僅僅獲得服務(wù)器返回的頭標志，其通信開銷是最小的，因此在下載網(wǎng)頁前進行此測試，不僅能減小網(wǎng)絡(luò)流量，而且能提高程序效率。當目標網(wǎng)頁存在時2調(diào)用URLConnection類getInputStream()函數(shù)明確打開到URL的連接，獲取輸入流，再用java.io包中的InputStreamReader類讀取該輸入流，將網(wǎng)頁下載下來。2.4爬行策略淺析2.4.1寬度或深度優(yōu)先搜索策略 搜索引擎所用的第一代網(wǎng)絡(luò)爬蟲主要是基于傳統(tǒng)的圖算法,如寬度優(yōu)先或深度優(yōu)先算法來索引整個Web,一個核心的URL集被用來作為一個種子集合,這種算法遞歸的跟蹤超鏈接到其它頁面,而通常不管頁面的內(nèi)容,因為最終的目標是這種跟蹤能覆蓋整個Web.這種策略通常用在通用搜索引擎中,因為通用搜索引擎獲得的網(wǎng)頁越多越好,沒有特定的要求. 寬度優(yōu)先搜索算法 寬度優(yōu)先搜索算法(又稱廣度優(yōu)先搜索)是最簡便的圖的搜索算法之一,這一算法也是很多重要的圖的算法的原型.Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想.寬度優(yōu)先搜索算法是沿著樹的寬度遍歷樹的節(jié)點,如果發(fā)現(xiàn)目標,則算法中止.該算法的設(shè)計和實現(xiàn)相對簡單,屬于盲目搜索.在目前為覆蓋盡可能多的網(wǎng)頁,一般使用寬度優(yōu)先搜索方法.也有很多研究將寬度優(yōu)先搜索策略應(yīng)用于聚焦爬蟲中.其基本思想是認為與初始URL在一定鏈接距離內(nèi)的網(wǎng)頁具有主題相關(guān)性的概率很大.另外一種方法是將寬度優(yōu)先搜索與網(wǎng)頁過濾技術(shù)結(jié)合使用,先用廣度優(yōu)先策略抓取網(wǎng)頁,再將其中無關(guān)的網(wǎng)頁過濾掉.這些方法的缺點在于,隨著抓取網(wǎng)頁的增多,大量的無關(guān)網(wǎng)頁將被下載并過濾,算法的效率將變低.深度優(yōu)先搜索 深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索圖.在深度優(yōu)先搜索中,對于最新發(fā)現(xiàn)的頂點,如果它還有以此為起點而未探測到的邊,就沿此邊繼續(xù)漢下去.當結(jié)點v的所有邊都己被探尋過,搜索將回溯到發(fā)現(xiàn)結(jié)點v有那條邊的始結(jié)點.這一過程一直進行到已發(fā)現(xiàn)從源結(jié)點可達的所有結(jié)點為止.如果還存在未被發(fā)現(xiàn)的結(jié)點,則選擇其中一個作為源結(jié)點并重復(fù)以上過程,整個進程反復(fù)進行直到所有結(jié)點都被發(fā)現(xiàn)為止.深度優(yōu)先在很多情況下會導(dǎo)致爬蟲的陷入(trapped)問題,所以它既不是完備的,也不是最優(yōu)的.2.4.2聚焦搜索策略 基于第一代網(wǎng)絡(luò)爬蟲的搜索引擎抓取的網(wǎng)頁一般少于1000000個網(wǎng)頁,極少重新搜集網(wǎng)頁并去刷新索引.而且其檢索速度非常慢,一般都要等待10s甚至更長的時間.隨著網(wǎng)頁頁信息的指數(shù)級增長及動態(tài)變化,這些通用搜索引擎的局限性越來越大,隨著科學(xué)技術(shù)的發(fā)展,定向抓取相關(guān)網(wǎng)頁資源的聚焦爬蟲便應(yīng)運而生.聚焦爬蟲的爬行策略只挑出某一個特定主題的頁面,根據(jù)“最好優(yōu)先原則”進行訪問,快速、有效地獲得更多的與主題相關(guān)的頁面,主要通過內(nèi)容和Web的鏈接結(jié)構(gòu)來指導(dǎo)進一步的頁面抓取[2]. 聚焦爬蟲會給它所下載下來的頁面分配一個評價分,然后根據(jù)得分排序,最后插入到一個隊列中.最好的下一個搜索將通過對彈出隊列中的第一個頁面進行分析而執(zhí)行,這種策略保證爬蟲能優(yōu)先跟蹤那些最有可能鏈接到目標頁面的頁面.決定網(wǎng)絡(luò)爬蟲搜索策略的關(guān)鍵是如何評價鏈接價值,即鏈接價值的計算方法,不同的價值評價方法計算出的鏈接的價值不同,表現(xiàn)出的鏈接的“重要程度”也不同,從而決定了不同的搜索策略.由于鏈接包含于頁面之中,而通常具有較高價值的頁面包含的鏈接也具有較高的價值,因而對鏈接價值的評價有時也轉(zhuǎn)換為對頁面價值的評價.這種策略通常運用在專業(yè)搜索引擎中,因為這種搜索引擎只關(guān)心某一特定主題的頁面.2.4.3基于內(nèi)容評價的搜索策略 基于內(nèi)容評價的搜索策略[3,4],主要是根據(jù)主題(如關(guān)鍵詞、主題相關(guān)文檔)與鏈接文本的相似度來評價鏈接價值的高低,并以此決定其搜索策略:鏈接文本是指鏈接周圍的說明文字和鏈接URL上的文字信息,相似度的評價通常采用以下公式: sim(di,dj)=Σmk=1wik×wjk(Σmk=1w2ik)(Σmk=1w2jk) 其中,di為新文本的特征向量,dj為第j類的中心向量,m為特征向量的維數(shù),wk為向量的第K維.由于Web頁面不同于傳統(tǒng)的文本,它是一種半結(jié)構(gòu)化的文檔,包含許多結(jié)構(gòu)信息Web頁面不是單獨存在的,頁面中的鏈接指示了頁面之間的相互關(guān)系,因而有些學(xué)者提出了基于鏈接結(jié)構(gòu)評價鏈接價值的方法.2.4.4基于鏈接結(jié)構(gòu)評價的搜索策略 基于鏈接結(jié)構(gòu)評價的搜索策略,是通過對Web頁面之間相互引用關(guān)系的分析來確定鏈接的重要性,進而決定鏈接訪問順序的方法.通常認為有較多入鏈或出鏈的頁面具有較高的價值.PageRank和Hits是其中具有代表性的算法.PageRank算法 基于鏈接評價的搜索引擎的優(yōu)秀代表是Google(://Google),它獨創(chuàng)的“鏈接評價體系”(PageRank算法)是基于這樣一種認識,一個網(wǎng)頁的重要性取決于它被其它網(wǎng)頁鏈接的數(shù)量,特別是一些已經(jīng)被認定是“重要”的網(wǎng)頁的鏈接數(shù)量.PageRank算法最初用于Google搜索引擎信息檢索中對查詢結(jié)果的排序過程[5],近年來被應(yīng)用于網(wǎng)絡(luò)爬蟲對鏈接重要性的評價,PageRank算法中,頁面的價值通常用頁面的PageRank值表示,若設(shè)頁面p的PageRank值為PR(p),則PR(p)采用如下迭代公式計算: PR(p)=C1T+(1-C)ΣC∈in(p)PR(p)?out(C)?其中T為計算中的頁面總量,C<1是阻尼常數(shù)因子,in(p)為所有指向p的頁面的集合,out(C)為頁面C出鏈的集合.基于PageRank算法的網(wǎng)絡(luò)爬蟲在搜索過程中,通過計算每個已訪問頁面的PageRank值來確定頁面的價值,并優(yōu)先選擇PageRank值大的頁面中的鏈接進行訪問.HITS算法 HITS方法定義了兩個重要概念:Authority和Hub.Authority表示一個權(quán)威頁面被其它頁面引用的數(shù)量,即該權(quán)威頁面的入度值.網(wǎng)頁被引用的數(shù)量越大,則該網(wǎng)頁的Authority值越大;Hub表示一個Web頁面指向其它頁面的數(shù)量,即該頁面的出度值.網(wǎng)頁的出度值越大,其Hub值越高.由于Hub值高的頁面通常都提供了指向權(quán)威頁面的鏈接,因而起到了隱含說明某主題頁面權(quán)威性的作用.HITS(Hyperlink-InducedTopicSearch)算法是利用Hub?Authority方法的搜索方法,Authority表示一個頁面被其它頁面引用的數(shù)量,即該頁面的入度值.Hub表示一個Web頁面指向其它頁面的數(shù)量,即該頁面的出度值.算法如下:將查詢q提交給傳統(tǒng)的基于關(guān)鍵字匹配的搜索引擎.搜索引擎返回很多網(wǎng)頁,從中取前n個網(wǎng)頁作為根集,用S表示.通過向S中加入被S引用的網(wǎng)頁和引用S的網(wǎng)頁將S擴展成一個更大的集合T.以T中的Hub網(wǎng)頁為頂點集Vl,以權(quán)威網(wǎng)頁為頂點集V2,V1中的網(wǎng)頁到V2中的網(wǎng)頁的超鏈接為邊集E,形成一個二分有向圖SG=(V1,V2,E).對V1中的任一個頂點v,用H(v)表示網(wǎng)頁v的Hub值,對V2中的頂點u,用A(u)表示網(wǎng)頁的Authority值.開始時H(v)=A(u)=1,對u執(zhí)行公式(1)來修改它的A(u),對v執(zhí)行公式(2)來修改它的H(v),然后規(guī)范化A(u),H(v),如此不斷的重復(fù)計算上述運算,直到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值增加為該網(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)驗”,而這些經(jīng)驗信息在搜索距相關(guān)頁面集較遠的地方往往能獲得較好的回報,而前兩種策略在這種情況下容易迷失方向.在鞏固學(xué)習(xí)模型中,把網(wǎng)絡(luò)爬蟲經(jīng)過若干無關(guān)頁面的訪問之后才能獲得的主題相關(guān)頁面稱為未來回報,對未來回報的預(yù)測值稱為未來回報價值,用Q價值表示.這種方法的核心就是學(xué)習(xí)如何計算鏈接的Q價值,根據(jù)未來回報價值確定正確的搜索方向.目前這類搜索策略不足之處在于學(xué)習(xí)效率低的問題,而且在訓(xùn)練過程中增加了用戶的負擔(dān).2.4.6基于語境圖的聚焦搜索 基于鞏固學(xué)習(xí)的網(wǎng)絡(luò)爬蟲通過計算鏈接的Q價值可以確定搜索方向,但它卻無法估計距離目標頁面的遠近.為此,Diligent等提出了基于“語境圖”的搜索策略,它通過構(gòu)建典型頁面的web“語境圖”來估計離目標頁面的距離,距離較近的頁面較早得到訪問[7].基于“語境圖”的搜索策略需要借助已有的通用搜索引擎構(gòu)建“語境圖”,而搜索引擎的檢索結(jié)果并非一定代表真實的web結(jié)構(gòu),因而這種方式也具有局限性.第三章系統(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,E)，網(wǎng)絡(luò)中的網(wǎng)頁構(gòu)成節(jié)點集V，他們之間的鏈接構(gòu)成邊集E，SPIDER正是從某一節(jié)點開始，沿著邊，遍歷圖M，每訪問到圖中一個節(jié)點Vi，就進行一定的處理。 為了達到上述目的，一個SPIDER必須被設(shè)計成多線程的，A個線程并發(fā)地在網(wǎng)絡(luò)上協(xié)同工作，才有可能在盡可能短的時間內(nèi)遍歷完網(wǎng)絡(luò)中的網(wǎng)頁。但網(wǎng)頁數(shù)目是如此之大，如果任SPIDER程序無窮地搜索下去，那么程序幾乎不能終止。所以我們限制SPIDER每次工作只訪問一個站點。一個再大型的站點，其中的網(wǎng)頁數(shù)目也是有限的，因此SPIDER程序能在有限的時間內(nèi)結(jié)束。當SPIDER程序訪問到一個網(wǎng)頁，必須進行以下幾項基本處理：抽取網(wǎng)頁中包含的文本；抽取網(wǎng)頁中包含的URL，并將其區(qū)分為網(wǎng)站內(nèi)URL或網(wǎng)站外URL。3.2SPIDER體系結(jié)構(gòu) 此爬蟲程序主要分為三個部分：任務(wù)執(zhí)行端，任務(wù)調(diào)度端，數(shù)據(jù)服務(wù)端。 每一個SPIDER任務(wù)執(zhí)行端關(guān)聯(lián)一個站點,一個線程下載一個基于URL鏈接的頁面,并進行Web頁面解析,得到站內(nèi)URL和發(fā)現(xiàn)新站點URL另外,將URL隊列持久化到數(shù)據(jù)庫,因此在SPIDER任務(wù)執(zhí)行端以外Down掉后,能夠斷點續(xù)傳. SPIDER客戶端線程間的協(xié)調(diào)通信采用Java的線程同步技術(shù)synchronized,在數(shù)據(jù)服務(wù)端中對URL進行緩存提高了系統(tǒng)處理速度.SPIDER的任務(wù)執(zhí)行和任務(wù)調(diào)度端都需要維持一個URL隊列:任務(wù)執(zhí)行端的URL隊列中存儲了站內(nèi)URL;任務(wù)調(diào)度端則是站點的URL.在這些URL隊列上有大量的操作,包括URL查找、URL插入、URL狀態(tài)更新等.如果SPIDER以300頁?秒的速度下載Web頁面,平均將會產(chǎn)生2000多個URL[12],因此簡單的采用內(nèi)存數(shù)據(jù)結(jié)構(gòu)存儲這些URL隊列有一定的問題,系統(tǒng)沒有足夠的內(nèi)存空間;而采用直接持久化到數(shù)據(jù)庫,則需要大量的數(shù)據(jù)庫連接、查詢等操作,系統(tǒng)效率會明顯下降.如果采用URL壓縮的辦法,盡管在一定程度上可以平衡空間和時間的矛盾,但仍然不適用于大規(guī)模數(shù)據(jù)采集的SPIDER.圖3.2SPIDER體系結(jié)3.3各主要功能模塊（類）設(shè)計 SPIDERWorker類：該類繼承自線程類，請求任務(wù)URL，根據(jù)得到的URL下載相應(yīng)的HTML代碼，利用HTML代碼調(diào)用其他模塊完成相關(guān)處理。 SPIDERManager類：該類用于控制SPIDERWorker線程。 UrlQueueManager類：該類用于維護URL等待隊列，分配任務(wù)URL，URL消重模塊。 UrlParse類：用于解析HTML，獲取并過濾URL。 DateBaseConnect類：用于提供數(shù)據(jù)庫連接。3.4SPIDER工作過程 ①將給定的初始URL加入到URL等待隊列。 ②創(chuàng)建爬蟲線程，啟動爬蟲線程 ③每個爬蟲線程從URL等待隊列中取得任務(wù)URL。然后根據(jù)URL下載網(wǎng)頁，然后解析網(wǎng)頁，獲取超鏈接URLs。如果獲取到的URL為相對地址，需要轉(zhuǎn)換為絕對地址，然后淘汰站外URLs，錯誤URLs或者不能解析的URL地址。再判斷這些URL是否已經(jīng)被下載到，如果沒有則加入到URL等待隊列。 ④繼續(xù)執(zhí)行步驟③，直到結(jié)束條件停止。將初始URLs加入到等待隊列 將初始URLs加入到等待隊列創(chuàng)建啟動爬蟲線程創(chuàng)建啟動爬蟲線程從URL等待隊列獲取任務(wù)URL從URL等待隊列獲取任務(wù)URL下載URL對應(yīng)的HTML代碼下載URL對應(yīng)的HTML代碼將相對地址轉(zhuǎn)換為絕對地址是否為絕對地址解析HTML，獲取URLs將相對地址轉(zhuǎn)換為絕對地址是否為絕對地址解析HTML，獲取URLs將URLs加入到URL等待隊列是否為非法URL是否為重復(fù)URL將URLs加入到URL等待隊列是否為非法URL是否為重復(fù)URL第四章系統(tǒng)分析與設(shè)計4.1SPIDER構(gòu)造分析 構(gòu)造SPIDER程序有兩種方式：（1）把SPIDER程序設(shè)計為遞歸的程序；（2）編寫一個非遞歸的程序，它要維護一個要訪問的網(wǎng)頁列表?？紤]使用哪一種方式的前提是，構(gòu)造的SPIDER程序必須能夠訪問非常大的Web站點。本系統(tǒng)中使用了非遞歸的程序設(shè)計方法。這是因為，當一個遞歸程序運行時要把每次遞歸壓入堆棧，但在本系統(tǒng)設(shè)計中使用的是多線程，它允許一次運行多個任務(wù)，但是，多線程與遞歸是不兼容的。因為在這一過程中每一個線程都有自己的堆棧，而當一個方法調(diào)用它自身時，它們需要使用同一個堆棧。這就意味著遞歸的SPIDER程序不能使用多線程。 每個SPIDER線程都會獨立的去完成獲取URLs的任務(wù)，并將獲取到的URLs加入一個公共的URL等待隊列中。圖4.1 圖4.1表示了該系統(tǒng)爬蟲線程的實現(xiàn)策略。假設(shè)線程1從URL隊列中獲取一條任務(wù)URL1，然后它會下載對應(yīng)的HTML，解析出里面包含URLs，然后再將這些URLs加入到URL隊列中去。然后線程1會再從URL隊列中獲取新的URL，下載HTML代碼，并解析出URLs，再加入到URL隊列中去。而線程2同時也會下載它獲取到的URL2對應(yīng)的HTML代碼，解析出URLs加入到等待隊列中。以此類推，多個線程并發(fā)地去完成爬蟲工作。4.2爬行策略分析 圖4.2.1 因為本論文實現(xiàn)的爬蟲程序的初衷是盡可能遍歷某一站點所有的頁面。廣度優(yōu)先算法的實行理論是覆蓋更多的節(jié)點，所以此爬蟲程序選擇了廣度優(yōu)先算法。實現(xiàn)的策略是：先獲取初始URL對應(yīng)HTML代碼里所有的URLs。然后依次獲取這些URLs對應(yīng)的HTML里的URLs，當這一層所有的URLs都下載解析完后，在獲取下一層的信息。通過這種循環(huán)的獲取方式實現(xiàn)廣度優(yōu)先爬行。 如圖4.2.1，假如a代表初始URL，bcd為以a獲取的3個URLs，efg為以b獲取的URLs，以此類推。那么這些URLs獲取的順序就是abcdefghijklmnop這樣一個順序。當獲取到b的URLs之后，并不會馬上去解析這些URLs，而是先解析同b在同一層中的cd對應(yīng)的URLs。當這一層URLs全部解析完后，再開始下一層URLs。 廣度優(yōu)先算法的等待隊列設(shè)計如圖4.2.2所示。圖4.2.2 圖4.2.2列舉了不同時間段時，URL等待隊列的存儲狀態(tài)。第一個方框是將初始URL：a加入到等待隊列。第二個方框為，解析a對應(yīng)HTML獲取URLs：bcd，同時刪除a。第三個方框為，解析b對應(yīng)HTML獲取URLs：efg，同時刪除URL：b。第四個方框為，解析e對應(yīng)HTML獲取URLs：nop，并刪除e。通過這樣的存儲方法實現(xiàn)如圖4.2.1的廣度爬行算法。4.3URL抽取，解析和保存4.3.1URL抽取 通過觀察研究HTML代碼，我們可以知道。HTML代碼中，頁面之間的跳轉(zhuǎn)，關(guān)聯(lián)是通過href標簽來實現(xiàn)的。我們需要獲取HTML代碼中的URLs，就可以通過尋找href標簽來達到目的。<li><ahref=movie_2004/html/6664.htmltarget=_blank>我猜[20210531]</a><em>5-31</em></li><li><ahref="movie_2004/html/2088.html?29.html"target="_blank">火影忍者[331，頁面上303既是]</a></li> 通過觀察得知，一般href標簽是以href=這樣的形式出現(xiàn)的。但是不同的網(wǎng)站href=后面的內(nèi)容有所不同。比如href=”url”這樣情況，我們就可以通過截取雙引號之間的內(nèi)容來獲取URL；如果是href=’url’這種情況，我們就需要截取單引號之間的內(nèi)容來獲取URL；或者有些是href=url，我們需要以等號為開始標記，而這種情況通常結(jié)尾是空格或者>符號。 通過這種方法，我們獲取網(wǎng)頁中大部分的URLs。但是有些URLs是通過提交表單，或者通過javascript來跳轉(zhuǎn)的。這些情況就需要更細致的考慮，才能獲取。4.3.2URL解析 截取出來的字符串，可能為相對地址或者絕對地址。所以需要判斷URL為絕對地址，還是相對地址。相對地址需要先轉(zhuǎn)化為絕對地址，再進行過濾。因為解析出來的URL地址可能是一些文件的地址，或者為javascript文件或者css文件。這些格式的URL是無法獲取HTML代碼的，也就不可能進行URL解析。所以我們需要過濾掉這些URLs。然后再進行URL消重處理，最后加入到URL等待隊列。 為了把爬行限制在同一站點內(nèi)需要截斷指向站外的鏈接,保證SPIDER總在站內(nèi)執(zhí)行,即準確地根據(jù)超鏈URL判斷超鏈是否指向站外.由RFC對URL的定義可知,URL的格式為[protocol://host:port/path?query],一般情況下,同一網(wǎng)站內(nèi)所有頁面對應(yīng)URL的host是相同的,所以可以使用host匹配作為判斷超鏈是否指向站外的標準.進一步研究發(fā)現(xiàn),很多大型網(wǎng)站中一個分類目錄對應(yīng)一個主機,所以前面的判斷標準必須改進.研究host的組成可知,host的格式一般為[站內(nèi)分類.站點標志串.站點類型各異的串].站點類型串只有[com|edu|gov|net|國家域名]幾種類型,所以我們?nèi)≌军c類型各異串前面的串,即站點標志串作匹配,超鏈URL的host中是否包含此串,為超鏈是否站內(nèi)的判斷標準.4.3.3URL保存 因為等待URLs的數(shù)目非常多，如果全部采用List來存儲非常的占用內(nèi)存空間。所以將等待URLs存入數(shù)據(jù)庫中，并設(shè)計2個緩存區(qū)，用于向隊列中加入和取得URLs。URL等待隊列設(shè)計成三段式：第一段為一個List,用來加入新得到的URL。當這個List中的數(shù)目過多時，則將List中的內(nèi)容加入到數(shù)據(jù)庫，并清空該List，以便加入新的URLs；第二段為數(shù)據(jù)庫，當?shù)谝欢螖?shù)據(jù)過多時，將第一段內(nèi)的數(shù)據(jù)存入數(shù)據(jù)庫；第三段也為一個List，從這里面分配任務(wù)URL，當該List內(nèi)URL不足時，將數(shù)據(jù)庫里的數(shù)據(jù)再轉(zhuǎn)存入。圖4.3.3表示了URL等待隊列的結(jié)構(gòu)。圖4.3.3第五章系統(tǒng)實現(xiàn)5.1實現(xiàn)工具 操作系統(tǒng)是winXP;JAVA程序的編寫工具是eclipse-SDK-3.2.1-win32；數(shù)據(jù)庫是MYSQL55.0.51a。5.2爬蟲工作 這個類繼承自線程類，實現(xiàn)線程在java中有兩種方法：一種是直接繼承Thread類；一種是實現(xiàn)Runnable接口。我采用了第二種方法： publicclassSpiderWorkerimplementsRunnable{ 在這個類中必須要實現(xiàn)重寫run()這個方法。我在這個方法里定義了一個循環(huán)，這個線程會重復(fù)地執(zhí)行爬蟲動作。 在這個循環(huán)里，首先會向URL等待隊列里請求一個URL。因為URL隊列會出現(xiàn)為空或者被其他線程占用的情況。所以我在這里寫了一個循環(huán)： s=null; while(s==null){ s=urlQueueManager.getWaitQueue(); }如果沒有得到URL就繼續(xù)向URL等待隊列申請。 當?shù)玫饺蝿?wù)URL以后，會通過這個URL得到對應(yīng)的HTML代碼。具體方法是調(diào)用getHtml(Stringsourse_url)這個方法： URLConnectionconnection=null; InputStreamReaderin=null; BufferedReaderbr=null; URLurl=null; url=newURL(sourse_url); connection=(URLConnection) url.openConnection(); connection.connect(); //打開的連接讀取的輸入流。 in=newInputStreamReader(url.openStream()); br=newBufferedReader(in); Stringc; while((c=br.readLine())!=null){ html.append(c); } returnhtml.toString(); 這個方法是通過調(diào)用JAVA里面的URL這個類，可以用給定的URL構(gòu)造這個類的一個實例，然后通過openStream()這個方法得到HTML代碼的數(shù)據(jù)流，然后再一行一行地把數(shù)據(jù)流轉(zhuǎn)換成String字符串，再用StringBuffer將這些字符串拼接成一個完整的HTML代碼。 當?shù)玫紿TML代碼以后，程序就會調(diào)用Url_Parse這個類里面的方法來解析HTML。5.3URL解析 從HTML代碼中提取URLs，主要是通過檢索字符串中的href字符串來實現(xiàn)的。對于一個HTML代碼，我尋找其中的href=字符串，然后記錄它的下表i。然后判斷下表i+1位置上的字符是雙引號，單引號或者兩者皆不是，然后選擇對應(yīng)的字符作為截取URL的終止標記。截取過后的href標記就剔除它與它前面的部分，以便而后的操作可以繼續(xù)檢索href標記，直到正個HTML代碼中所有的href標記都被解析過后，操作終止。<ahref="://tom365/"class="focu">首頁</a><ahref=’movie_2004/mlist/1_1.html’target=_self>動作片</a><ahref=movie_2004/mlist/2_1.htmltarget=_self>恐怖片</a><ahref=movie_2004/mlist/3_1.html>愛情片</a> 例如上面那段HTML代碼。我們先檢索href=標記，然后判斷出第i+1位為一個雙引號，所以我們可以截取i+1位到第2個雙引號的位置。之間的這段字符串即為URL。當完成這一步操作后，原字符串被截取從“class=”開始。我們繼續(xù)檢索href=標簽，判斷它的第i+1位為一個單引號，所以我們又截取i+1位到第2個單引號的位置。這步以后原字符串又被截取為“target=”開始，我們可以繼續(xù)檢索href=標簽。這個地方href=沒有接續(xù)任何符號，所以當我們沒有發(fā)現(xiàn)單引號或雙引號的時候，可以判斷為這種情況。我們就去檢索空格和<標簽，以下標較小的字符作為截取URL的結(jié)束標記。 下面是href=后面接續(xù)雙引號情況的JAVA代碼，其他情況的代碼方式相同。publicvoidgetHref_UrlsList(Stringhtml_text,StringfromURL, UrlQueueManagerurlQueueManager,intbiaoji){ //站內(nèi)URL隊列 List<String>siteInsideUrls=newArrayList<String>(); Stringurl=""; //HTML中是否還含有href標簽 booleanhaveHref=html_text.contains("href"); while(haveHref){ html_text=html_text.substring(html_text.indexOf("href=")+5); //當href=后以"開頭的情況 if('\"'==html_text.charAt(0)){ html_text=html_text.substring(1); url=html_text.substring(0,html_text.indexOf("\"")); url=addURLhost(fromURL,url); if(isSiteInsideUrl(url,urlQueueManager)){ if(!urlQueueManager.isContainUrl(url)){ siteInsideUrls.add(url); } } haveHref=html_text.contains("href"); } urlQueueManager.waitQueueAdd(siteInsideUrls); } 在每個URL被截取出來之后，需要判斷這些URL是相對地址，還是絕對地址。 <ahref=../mlist/1_1.htmltarget=_self>動作片</a> <ahref="://so.tom365/search.asp">TOM365</a> 例如上面的HTML代碼，如果截取出來的URL為../mlist/1_1.html這種形式，即為相對地址。我們需要將其轉(zhuǎn)化為絕對地址。假如這個相對地址的父URL為://tom365/movie_2004/html/6664.html。根據(jù)相對地址的概念，../為返回上一層，所以可以得到這個相對地址的絕對地址為://tom365/mlist/1_1.html。比如像上面的第2種URL，它包含完整的協(xié)議信息，域名地址?？梢耘袛嗨鼮榻^對地址。 當?shù)玫竭@些完整的URL地址以后，我們需要對其進行過濾。很多URL它們指向的文件不是HTML文件，而是一些CSS文件，或者RAR包文件，或者只是接續(xù)“#”符號，代表只是調(diào)用一段javascript代碼。像這種情況我們就直接拋棄這些URLs。 下面是一段實行代碼。代碼通過檢索URL字符串中是否包含".css"，".rar"，".zip"這些后綴來進行判斷。 //如果url中包含以下字符串，則不加入隊列 if(url.toLowerCase().contains(".css") ||url.toLowerCase().contains(".rar")||url.contains("#") ||url.contains(".zip")||url.contains("javascript")) { returnfalse; } 過濾完后的URLs，再判斷它為站內(nèi)URL或者為站外URL。一般情況下同一網(wǎng)站內(nèi)的URL的host名因該是一致的。所以我們可以通過判斷URLs中是否包含站點host就可以了。 下面的代碼是host為的情況。其他情況的代碼可以類推。 //host域名為 if(urlQueueManager.initURL.contains("")){ Stringstr=urlQueueManager.initURL.substring(0, urlQueueManager.initURL.indexOf("")); if(url.contains(str.substring(str.lastIndexOf('.'))+"")){ returntrue; } } 如果為站內(nèi)URL則加入到緩存隊列。5.4URL隊列管理5.4.1URL消重處理 URL消重處理，我是用LRU算法加上MD5壓縮算法來實現(xiàn)的。因為URLs的數(shù)量非常巨大，為了節(jié)省內(nèi)存空間。我先通過MD5壓縮來得到每個URL對于的一個hash碼。這個hash碼的長度相對較小，可以節(jié)省內(nèi)存開銷。而且產(chǎn)生碰撞的幾率非常小，可以忽略不計。 然后這個URL消重隊列的維護是同時LRULinkedHashMap來實現(xiàn)的。這個Map非常好，它總是淘汰重復(fù)次數(shù)最少的URL。這樣就算URL數(shù)過大，也可以盡量避免重復(fù)下載URL。它的具體構(gòu)造如下：publicclassLRULinkedHashMap<K,V>extendsLinkedHashMap<K,V>{ privatestaticfinallongserialVersionUID=1L; privatefinalintmaxCapacity; privatestaticfinalfloatDEFAULT_LOAD_FACTOR=0.75f; privatefinalLocklock=newReentrantLock(); publicLRULinkedHashMap(intmaxCapacity){ super(maxCapacity,DEFAULT_LOAD_FACTOR,true); this.maxCapacity=maxCapacity; } @Override protectedbooleanremoveEldestEntry(java.util.Map.Entry<K,V>eldest){ returnsize()>maxCapacity; } @Override publicVget(Objectkey){ try{ lock.lock(); returnsuper.get(key); }finally{ lock.unlock(); } } @Override publicVput(Kkey,Vvalue){ try{ lock.lock(); returnsuper.put(key,value); }finally{ lock.unlock(); } }} 有了這個map以后，我就會用URL到里面去碰撞。因為有些網(wǎng)站的URL寫法不固定。也許是同一個URL，但是有些在最后一位接續(xù)"/"符號，而有些則沒有接續(xù)。這樣當進行URL去重處理時，會認為它們不是一個URL。所以我們必須先除去后面的"/"符號，再進行URL去重判斷。 publicsynchronizedbooleanisContainUrl(Stringurl){ if(url.endsWith("/")){ url=url.substring(0,url.length()-1); } booleanb=lRULinkedHashMap.containsKey(Url_Md5.MD5Encode(url)); lRULinkedHashMap.put(Url_Md5.MD5Encode(url),true); returnb; }5.4.2URL等待隊列維護 對URL等待隊列的操作主要有2個：從里面取出URLs;往里面加入URLs。 但是因為URL等待隊列會非常巨大，所以我將URL等待隊列設(shè)計成3段式。2段基于內(nèi)存的URL緩存區(qū)，和一個基于數(shù)據(jù)庫的儲存區(qū)。 所以這里就會有2個方法來完成數(shù)據(jù)直接的交接。當加入URL緩存太長時，調(diào)用下面的方法，將緩存區(qū)的內(nèi)容加入到數(shù)據(jù)庫。具體的實現(xiàn)方法是，當存入緩存超過一定數(shù)目的時候。調(diào)用waitQueueDecrease()這個函數(shù)，將存入緩存里的數(shù)據(jù)轉(zhuǎn)移到數(shù)據(jù)庫。方法是取出下標為0的元素，將其加入到數(shù)據(jù)庫，然后刪除下標為0的元素。不斷重復(fù)這個操作，直到存入緩存被清空。 下面是具體實現(xiàn)的JAVA代碼。publicsynchronizedvoidwaitQueueDecrease(){ try{ Statementstmt=null; while(waitQueueFron.size()>0){ try{ stmt=DateBaseConnect.conn().createStatement(); while(waitQueueFron.get(0).size()>0){ Stringurl=(String)waitQueueFron.get(0).get(0); waitQueueFron.get(0).remove(0); stmt.execute("insertintomiddlequeue(url)values('" +url+"');"); stmt.execute("insertintodatabasequeue(url)values('" +url+"');"); } 當取出緩存區(qū)空以后，需要將數(shù)據(jù)庫的內(nèi)容加入到緩存區(qū)。通過調(diào)用waitQueueAdd()這個函數(shù)來實現(xiàn)。具體的實現(xiàn)方法是：從數(shù)據(jù)庫里搜索前25條數(shù)據(jù)，因為數(shù)據(jù)庫添加數(shù)據(jù)時是順序往下壓入的。對于MYSQL數(shù)據(jù)庫，可以使用LIMIT這個關(guān)鍵字。檢索存入數(shù)據(jù)庫最上端的25條數(shù)據(jù)，然后依次將其加入到取出緩存區(qū)。然后刪除數(shù)據(jù)庫中這25條數(shù)據(jù)。 下面是具體實現(xiàn)的JAVA代碼：publicsynchronizedvoidwaitQueueAdd(){ Stringsql="SELECT*FROMmiddlequeueLIMIT25;"; Statementstmt=null; ResultSetres=null; try{ stmt=DateBaseConnect.conn().createStatement(); res=stmt.executeQuery(sql); while(res.next()){ waitQueueBack.add(res.getString("url")); } stmt.execute("deletefrommiddlequeuelimit25");5.4.3數(shù)據(jù)庫設(shè)計 對于MYSQL數(shù)據(jù)庫的設(shè)計。我建立了2個表，分別為middlequeue和databasequeue。middlequeue表和databasequeue表都只有一個字段URL，同時它作為主鍵，因為存入的URL不可能重復(fù)。Middlequeue用于URL等待隊列的主存儲部分。而databasequeue表記錄爬蟲程序運行得到的所有URLs。 JAVA程序和數(shù)據(jù)之間的通信是通過JDBC實現(xiàn)的。下面是JAVA程序連接MYSQL數(shù)據(jù)庫的代碼。 publicstaticConnectionconn(){ Connectionconn=null; try{ //加載Connector/J驅(qū)動 Class.forName("com.mysql.jdbc.Driver").newInstance(); //建立到MySQL的連接 conn=DriverManager.getConnection( "jdbc:mysql://localhost:3306/mysql","root","root"); }catch(Exceptionex){ System.out.println("Error:"+ex.toString()); } returnconn; }第六章系統(tǒng)測試 我以:///為初始U