基于廣度優(yōu)先算法的多線(xiàn)程爬蟲(chóng)程序的設(shè)計(jì)與實(shí)現(xiàn)畢業(yè)論文

1、. . . . I / 65摘要網(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)先算法的多線(xiàn)程爬蟲(chóng)程序。本論文闡述了網(wǎng)絡(luò)爬蟲(chóng)實(shí)現(xiàn)中一些主要問(wèn)題：為何使用廣度優(yōu)先的爬行策略，以與如何實(shí)現(xiàn)廣度優(yōu)先爬行；為何要使用多線(xiàn)程，以與如何實(shí)現(xiàn)多線(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ù)。 關(guān)鍵字網(wǎng)絡(luò)爬蟲(chóng)；JAVA；廣度優(yōu)先；多線(xiàn)程。. . . . ABSTRACTS

2、PIDER is a program which can auto collect informations from internet. SPIDER can collect data for search engines, also can be a Directional information collector, collects specifically informations from some web sites, such as HR informations, house rent informations.In this paper, use JAVA implemen

3、ts a breadth-first algorithm multi-thread SPDIER.This paper expatiates some major problems of SPIDER: why to use breadth-first crawling strategy, and how to implement breadth-first crawling; why to use multi-threading, and howto implement multi-thread; data structure; HTML code parse. etc.This SPIDE

4、R can collect URLs from one web site, and store URLs into database. KEY WORDSPIDER; JAVA; Breadth First Search; multi-threads. . . . III / 65目錄第一章引言第一章引言 1 1第二章相關(guān)技術(shù)介紹第二章相關(guān)技術(shù)介紹 2 22.1 JAVA 線(xiàn)程 22.1.1 線(xiàn)程概述 22.1.2 JAVA 線(xiàn)程模型 22.1.3 創(chuàng)建線(xiàn)程 32.1.4 JAVA 中的線(xiàn)程的生命周期 42.1.5 JAVA 線(xiàn)程的結(jié)束方式 42.1.6 多線(xiàn)程同步 52.2 URL 消重 5

5、2.2.1 URL 消重的意義 52.2.2 網(wǎng)絡(luò)爬蟲(chóng) URL 去重儲(chǔ)存庫(kù)設(shè)計(jì) 52.2.3 LRU 算法實(shí)現(xiàn) URL 消重 72.3 URL 類(lèi)訪(fǎng)問(wèn)網(wǎng)絡(luò) 82.4爬行策略淺析 82.4.1 寬度或深度優(yōu)先搜索策略 82.4.2 聚焦搜索策略 92.4.3 基于容評(píng)價(jià)的搜索策略 92.4.4 基于結(jié)構(gòu)評(píng)價(jià)的搜索策略 102.4.5 基于鞏固學(xué)習(xí)的聚焦搜索 112.4.6 基于語(yǔ)境圖的聚焦搜索 11第三章系統(tǒng)需求分析與模塊設(shè)計(jì)第三章系統(tǒng)需求分析與模塊設(shè)計(jì) 13133.1 系統(tǒng)需求分析 133.2 SPIDER 體系結(jié)構(gòu) 133.3 各主要功能模塊（類(lèi)）設(shè)計(jì) 143.4 SPIDER 工作過(guò)程 1

6、4第四章系統(tǒng)分析與設(shè)計(jì)第四章系統(tǒng)分析與設(shè)計(jì) 16164.1 SPIDER 構(gòu)造分析 164.2 爬行策略分析 174.3 URL 抽取，解析和保存 184.3.1 URL 抽取 184.3.2 URL 解析 194.3.3 URL 保存 19第五章系統(tǒng)實(shí)現(xiàn)第五章系統(tǒng)實(shí)現(xiàn) 21215.1 實(shí)現(xiàn)工具 215.2 爬蟲(chóng)工作 215.3 URL 解析 225.4 URL 隊(duì)列管理 24. . . . 5.4.1 URL 消重處理 245.4.2 URL 等待隊(duì)列維護(hù) 265.4.3 數(shù)據(jù)庫(kù)設(shè)計(jì) 27第六章系統(tǒng)測(cè)試第六章系統(tǒng)測(cè)試 2929第七章結(jié)論第七章結(jié)論 3232參考文獻(xiàn)參考文獻(xiàn) 3333致致 34

7、34外文資料原文外文資料原文 3535譯文譯文 5151. . . . 1 / 65第一章 引言隨著互聯(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ù)幕一般都不公開(kāi)。目前幾種比較常用的爬蟲(chóng)實(shí)現(xiàn)策略：廣度優(yōu)先的爬蟲(chóng)程序，Repetitive 爬蟲(chóng)程序，定義爬行爬蟲(chóng)程序

8、，深層次爬行爬蟲(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)有：多線(xiàn)程的實(shí)現(xiàn)；對(duì)臨界資源的分配；遍歷 web圖的遍歷

9、策略選擇和實(shí)現(xiàn)；存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的選擇和實(shí)現(xiàn)。本文通過(guò) JAVA 語(yǔ)言實(shí)現(xiàn)一個(gè)基于廣度優(yōu)先偏歷算法的多線(xiàn)程爬蟲(chóng)程序。通過(guò)實(shí)現(xiàn)此爬蟲(chóng)程序可以定點(diǎn)搜集某一站點(diǎn)的 URLs，如果需要搜集其他信息，可以在解析 URLs 的同時(shí)，解析獲取相應(yīng)信息。. . . . 第二章 相關(guān)技術(shù)介紹2.1 JAVA 線(xiàn)程2.1.1 線(xiàn)程概述幾乎每種操作系統(tǒng)都支持線(xiàn)程的概念進(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ì)再編

10、輯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)作。因此，雖然我們看到的都是一些同步的操作，但實(shí)際上，對(duì)

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

12、 JAVA 程序部虛擬了多臺(tái)計(jì)算機(jī)，每臺(tái)計(jì)算機(jī)對(duì)應(yīng)一個(gè)線(xiàn)程，有自己的 CPU，可以獲取所需的代碼和數(shù)據(jù)，因此能獨(dú)立執(zhí)行任務(wù)，相互間還可以共用代碼和數(shù)據(jù)。JAVA 的線(xiàn)程是通過(guò) java.lang.Thread 類(lèi)來(lái)實(shí)現(xiàn)的，它部實(shí). . . . 3 / 65現(xiàn)了虛擬 CPU 的功能，能夠接收和處理傳遞給它的代碼和數(shù)據(jù)，并提供了獨(dú)立的運(yùn)行控制功能。我們知道，每個(gè) JAVA 應(yīng)用程序都至少有一個(gè)線(xiàn)程，這就是所謂的主線(xiàn)程。它由 JVM 創(chuàng)建并調(diào)用 JAVA 應(yīng)用程序的 main（）方法。JVM 還通常會(huì)創(chuàng)建一些其他的線(xiàn)程，不過(guò)，這些線(xiàn)程對(duì)我們而言通常都是不可見(jiàn)的。比如，用于自動(dòng)垃圾收集的線(xiàn)程，對(duì)象終止

13、或者其他的 JVM 處理任務(wù)相關(guān)的線(xiàn)程。2.1.3 創(chuàng)建線(xiàn)程2.1.3.1 創(chuàng)建線(xiàn)程方式一在 JAVA 中創(chuàng)建線(xiàn)程的一種方式是通過(guò) Thread 來(lái)實(shí)現(xiàn)的。Thread 有很多個(gè)構(gòu)造器來(lái)創(chuàng)建一個(gè)線(xiàn)程（Thread）實(shí)例：Thread();創(chuàng)建一個(gè)線(xiàn)程。Thread(Runnable target);創(chuàng)建一個(gè)線(xiàn)程，并指定一個(gè)目標(biāo)。Thread(Runnable target,String name);創(chuàng)建一個(gè)名為 name 的目標(biāo)為target 的線(xiàn)程。Thread(String name);創(chuàng)建一個(gè)名為 name 的線(xiàn)程。Thread(ThreadGroup group,Runnable ta

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

15、方法 run()，可以創(chuàng)建一個(gè)線(xiàn)程。在使用 Runnable 接口時(shí)，不能直接創(chuàng)建所需類(lèi)的對(duì)象并運(yùn)行它，而是必須從 Thread 類(lèi)的一個(gè)實(shí)例部運(yùn)行它。. . . . 從上面兩種創(chuàng)建線(xiàn)程的方法可以看出，如果繼承 Thread 類(lèi)，則這個(gè)類(lèi)本身可以調(diào)用 start 方法，也就是說(shuō)將這個(gè)繼承了 Thread 的類(lèi)當(dāng)作目標(biāo)對(duì)象；而如果實(shí)現(xiàn) Runnable 接口，則這個(gè)類(lèi)必須被當(dāng)作其他線(xiàn)程的目標(biāo)對(duì)象。2.1.4 JAVA 中的線(xiàn)程的生命周期JAVA 的線(xiàn)程從產(chǎn)生到消失,可分為 5 種狀態(tài)：新建（New） ，可運(yùn)行（Runnable） ，運(yùn)行（Running） ，阻塞（Blocked）以與死亡（Dea

16、d） 。其中，Running 狀態(tài)并非屬于 JAVA 規(guī)中定義的線(xiàn)程狀態(tài)，也就是說(shuō)，在 JAVA 規(guī)中，并沒(méi)有將運(yùn)行（Running）狀態(tài)真正的設(shè)置為一個(gè)狀態(tài)，它屬于可運(yùn)行狀態(tài)的一種。當(dāng)使用 new 來(lái)新建一個(gè)線(xiàn)程時(shí)，它處于 New 狀態(tài)，這個(gè)時(shí)候，線(xiàn)程并未進(jìn)行任何操作。然后，調(diào)用線(xiàn)程的 start()方法，來(lái)向線(xiàn)程調(diào)度程序（通常是 JVM 或操作系統(tǒng)）注冊(cè)一個(gè)線(xiàn)程，這個(gè)時(shí)候，這個(gè)線(xiàn)程一切就緒，就等待 CPU 時(shí)間了。線(xiàn)程調(diào)度程序根據(jù)調(diào)度策略來(lái)調(diào)度不同的線(xiàn)程，調(diào)用線(xiàn)程的 run 方法給已經(jīng)注冊(cè)的各個(gè)線(xiàn)程以執(zhí)行的機(jī)會(huì)，被調(diào)度執(zhí)行的線(xiàn)程進(jìn)入運(yùn)行（Running）狀態(tài)。當(dāng)線(xiàn)程的 run 方法運(yùn)行完畢

17、，線(xiàn)程將被拋棄，進(jìn)入死亡狀態(tài)。你不能調(diào)用restart 方法來(lái)重新開(kāi)始一個(gè)處于死亡狀態(tài)的線(xiàn)程，但是，你可以調(diào)用處于死亡狀態(tài)的線(xiàn)程對(duì)象的各個(gè)方法。如果線(xiàn)程在運(yùn)行（Running）狀態(tài)中因?yàn)?I/O 阻塞，等待鍵盤(pán)鍵入，調(diào)用了線(xiàn)程的 sleep 方法，調(diào)用了對(duì)象的 wait()方法等，則線(xiàn)程將進(jìn)入阻塞狀態(tài)，直到這些阻塞原因被解除，如：IO 完成，鍵盤(pán)輸入了數(shù)據(jù)，調(diào)用 sleep 方法后的睡眠時(shí)間到以與其他線(xiàn)程調(diào)用了對(duì)象的 notify 或 notifyAll 方法來(lái)喚醒這個(gè)因?yàn)榈却枞木€(xiàn)程等，線(xiàn)程將返回到 Runnable 狀態(tài)重新等待調(diào)度程序調(diào)度，注意，被阻塞的線(xiàn)程不會(huì)直接返回到 Runni

18、ng 狀態(tài)，而是重新回到 Runnable 狀態(tài)等待線(xiàn)程調(diào)度程序的調(diào)用。線(xiàn)程調(diào)度程序會(huì)根據(jù)調(diào)度情況，將正在運(yùn)行中的線(xiàn)程設(shè)置為 Runnable 狀態(tài)，例如，有一個(gè)比當(dāng)前運(yùn)行狀態(tài)線(xiàn)程更高運(yùn)行等級(jí)的線(xiàn)程進(jìn)入 Runnable 狀態(tài)，就可能將當(dāng)前運(yùn)行的線(xiàn)程從 Running 狀態(tài)“踢出”,讓它回到 Runnable 狀態(tài)。2.1.5 JAVA 線(xiàn)程的結(jié)束方式線(xiàn)程會(huì)以以下三種方式之一結(jié)束：線(xiàn)程到達(dá)其 run()方法的末尾；. . . . 5 / 65線(xiàn)程拋出一個(gè)未捕獲到的 Exception 或 Error；另一個(gè)線(xiàn)程調(diào)用一個(gè) Deprecated 的 stop()方法。注意，因?yàn)檫@個(gè)方法會(huì)引起線(xiàn)程的

19、安全問(wèn)題，已經(jīng)被不推薦使用了，所以，不要再程序調(diào)用這個(gè)方法。2.1.6 多線(xiàn)程同步當(dāng)同時(shí)運(yùn)行的相互獨(dú)立的線(xiàn)程需要共享數(shù)據(jù)并且需要考慮其他線(xiàn)程的狀態(tài)時(shí)，就需要使用一套機(jī)制使得這些線(xiàn)程同步，避免在爭(zhēng)用資源時(shí)發(fā)生沖突，甚至發(fā)生死鎖。JAVA 提供了多種機(jī)制以實(shí)現(xiàn)線(xiàn)程同步。多數(shù) JAVA 同步是以對(duì)象鎖定為中心的。JAVA 中從 Object 對(duì)象繼承來(lái)的每個(gè)對(duì)象都有一個(gè)單獨(dú)的鎖。由于 JAVA 中的每個(gè)對(duì)象都是從 Object 繼承來(lái)的。所以 JAVA 中的每個(gè)對(duì)象都有自己的鎖。這樣使它在共享的線(xiàn)程之間可以相互協(xié)調(diào)。在 JAVA 中實(shí)現(xiàn)線(xiàn)程同步的另一個(gè)方法是通過(guò)使用 synchronized 關(guān)鍵字

20、。JAVA 使用 synchronized 關(guān)鍵字來(lái)定義程序中要求線(xiàn)程同步的部分。synchronized 關(guān)鍵字實(shí)現(xiàn)的基本操作是把每個(gè)需要線(xiàn)程同步的部分定義為一個(gè)臨界區(qū)，在臨界區(qū)中同一時(shí)刻只有一個(gè)線(xiàn)程被執(zhí)行。2.2 URL 消重2.2.1 URL 消重的意義在 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 左右。這種情況非常類(lèi)似于操作系統(tǒng)中虛擬儲(chǔ)存器管理。所謂的虛擬儲(chǔ)存器，是指具有請(qǐng)求調(diào)入和置換

21、功能，能從邏輯上對(duì)存容量加以擴(kuò)充的一種儲(chǔ)存器系統(tǒng)。其關(guān)鍵在于允許一個(gè)作業(yè)只裝入部分的頁(yè)或段就可以啟動(dòng)運(yùn)行，當(dāng)作業(yè)運(yùn)行的時(shí)候在存中找不到所需要的頁(yè)或段的時(shí)候，就會(huì)發(fā)生請(qǐng)求調(diào)入，而從外存中找到的頁(yè)或段將會(huì)置換存中暫時(shí)不運(yùn)行的頁(yè)面到外存。URL 消重工作量是非常巨大的。以下在新浪新聞頁(yè)面為例，新浪一個(gè)新聞頁(yè)面大小為 5060k，每個(gè)頁(yè)面有 90100 個(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.

22、2.2 網(wǎng)絡(luò)爬蟲(chóng) URL 去重儲(chǔ)存庫(kù)設(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)用來(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)行檢

23、測(cè)時(shí)候，要加載到存中，在存中進(jìn)行檢測(cè)一定會(huì)比直接從磁盤(pán)上讀取速度快很多。我們先從最簡(jiǎn)單的情況說(shuō)起，然后逐步優(yōu)化，最終得到一個(gè)非常不錯(cuò)的解決方案。2.2.2.1 基于磁盤(pán)的順序存儲(chǔ)這里，就是指把每個(gè)已經(jīng)下載過(guò)的 URL 進(jìn)行順序存儲(chǔ)。你可以把全部已經(jīng)下載完成的 URL 存放到磁盤(pán)記事本文件中。每次有一個(gè)爬蟲(chóng)線(xiàn)程得到一個(gè)任務(wù) URL開(kāi)始下載之前，通過(guò)到磁盤(pán)上的該文件中檢索，如果沒(méi)有出現(xiàn)過(guò)，則將這個(gè)新的 URL 寫(xiě)入記事本的最后一行，否則就放棄該 URL 的下載。這種方式幾乎沒(méi)有人考慮使用了，但是這種檢查的思想是非常直觀(guān)的。試想，如果已經(jīng)下載了 100 億網(wǎng)頁(yè)，那么對(duì)應(yīng)著 100 億個(gè)，也就是這個(gè)檢

24、查 URL 是否重復(fù)的記事本文件就要存儲(chǔ)這 100 億 URL，況且，很多 URL 字符串的長(zhǎng)度也不小，占用存儲(chǔ)空間不說(shuō)，查找效率超級(jí)低下，這種方案肯定放棄。2.2.2.2 基于 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ò)，放棄下載，否則，將該 URL 與其 Hash 地址作為鍵值對(duì)存放到 Hash 表中。這樣，URL 去重存儲(chǔ)庫(kù)就是要維護(hù)一個(gè) Hash 表，如果 Hash 函數(shù)設(shè)計(jì)的不好，在進(jìn)行映射的時(shí)候，

25、發(fā)生碰撞的幾率很大，則再進(jìn)行碰撞的處理也非常復(fù)雜。而且，這里使用的是 URL 作為鍵，URL 字符串也占用了很大的存儲(chǔ)空間。2.2.2.3 基于 MD5 壓縮映射的存儲(chǔ)MD5 算法是一種加密算法，同時(shí)它也是基于 Hash 的算法。這樣就可以對(duì) URL 字符串進(jìn)行壓縮，得到一個(gè)壓縮字符串，同時(shí)可以直接得到一個(gè) Hash 地址。另外，MD5 算法能夠?qū)⑷魏巫址畨嚎s為 128 位整數(shù)，并映射為物理地址，而且 MD5. . . . 7 / 65進(jìn)行 Hash 映射碰撞的幾率非常小，這點(diǎn)非常好。從另一個(gè)方面來(lái)說(shuō)，非常少的碰撞，對(duì)于搜索引擎的爬蟲(chóng)是可以容忍的。況且，在爬蟲(chóng)進(jìn)行檢測(cè)的過(guò)程中，可以通過(guò)記錄日

26、志來(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 反序列化到存中，供爬蟲(chóng)進(jìn)行 URL 去重檢測(cè)。2.2.2.4 基于嵌入式 Berkeley DB 的存儲(chǔ)Berkeley DB 的特點(diǎn)就是只存儲(chǔ)鍵值對(duì)類(lèi)型數(shù)據(jù)，這和 URL 去重有很大關(guān)系。去重，可以考慮對(duì)某個(gè)鍵，存在一個(gè)值，這個(gè)值就是那個(gè)鍵的狀態(tài)。使用了Berkele

27、y DB，你就不需要考慮進(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ù)使用 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ǔ)空間。2.2.2.5 基于布隆過(guò)濾器（Bloom Filter）的存儲(chǔ)使用布隆過(guò)濾器，設(shè)計(jì)多個(gè) Hash 函數(shù)，也就是對(duì)每個(gè)字符串進(jìn)行映射是經(jīng)過(guò)多個(gè)

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

29、最后的位置就是最近最少被命中位置，我們只需要將新的容放在鏈表前面，淘汰鏈表最后的位置就實(shí)現(xiàn)了 LRU 算法。2.3 URL 類(lèi)訪(fǎng)問(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)。如：URL url=newURL（） ；如果傳遞無(wú)效的 URL 給 URL 對(duì)象，該對(duì)象會(huì)拋出 MalformedURLException異常。當(dāng)成功創(chuàng)建一個(gè) URL 對(duì)象后，我們調(diào)用 openConnection 函數(shù)建立與 URL的通信，此時(shí)

30、，我們就獲得了一個(gè) URLConnection 對(duì)象的引用，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) getI

31、nputStream()函數(shù)明確打開(kāi)到 URL 的連接，獲取輸入流，再用 java.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è)核心的 U RL 集被用來(lái)作為一個(gè)種子集合, 這種算法遞歸的跟蹤超到其它頁(yè)面, 而通常不管頁(yè)面的容, 因?yàn)樽罱K的目標(biāo)是這種跟蹤能覆蓋整個(gè) Web. 這種策略通常用在通用搜索引擎中,因?yàn)橥ㄓ盟阉饕娅@得的網(wǎng)頁(yè)越多越好, 沒(méi)有特定的要求.2.4.1.1寬度優(yōu)先搜索算法寬度優(yōu)先搜索算

32、法(又稱(chēng)廣度優(yōu)先搜索) 是最簡(jiǎn)便的圖的搜索算法之一, 這一算法也是很多重要的圖的算法的原型. Dijkstra 單源最短路徑算法和 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)先搜索方法. 也有很多研究將寬度優(yōu)先搜索策略應(yīng)用于聚焦爬蟲(chóng)中. 其基本思想是認(rèn)為與初始 U RL 在一定距離的網(wǎng)頁(yè)具有主題相關(guān)性的概率很大. 另外一種方法是將寬度優(yōu)先搜索與網(wǎng)頁(yè)過(guò)濾技術(shù)結(jié)合使用, 先用廣度優(yōu)先策略抓取網(wǎng)頁(yè), . . . . 9

33、/ 65再將其中無(wú)關(guān)的網(wǎng)頁(yè)過(guò)濾掉. 這些方法的缺點(diǎn)在于, 隨著抓取網(wǎng)頁(yè)的增多, 大量的無(wú)關(guān)網(wǎng)頁(yè)將被下載并過(guò)濾, 算法的效率將變低.2.4.1.2深度優(yōu)先搜索深度優(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)的陷入(

34、 trapped) 問(wèn)題, 所以它既不是完備的, 也不是最優(yōu)的.2.4.2 聚焦搜索策略基于第一代網(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ā)展, 定向抓取相關(guān)網(wǎng)頁(yè)資源的聚焦爬蟲(chóng)便應(yīng)運(yùn)而生.聚焦爬蟲(chóng)的爬行策略只挑出某一個(gè)特定主題的頁(yè)面, 根據(jù)“最好優(yōu)先原則”進(jìn)行訪(fǎng)問(wèn), 快速、有效地獲得更多的與主題相關(guān)的頁(yè)面, 主要通過(guò)容和 Web 的結(jié)構(gòu)來(lái)指導(dǎo)進(jìn)一步的頁(yè)面抓取 2 . 聚焦爬蟲(chóng)會(huì)給它所

35、下載下來(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ì)算方法, 不同的價(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 基于容評(píng)價(jià)的搜索策略基于容評(píng)價(jià)

36、的搜索策略 3, 4 , 主要是根據(jù)主題(如關(guān)鍵詞、主題相關(guān)文檔) 與文本的相似度來(lái)評(píng)價(jià)價(jià)值的高低, 并以此決定其搜索策略: 文本是指周?chē)恼f(shuō)明文字和 U RL 上的文字信息, 相似度的評(píng)價(jià)通常采用以下公式:. . . . sim (d i, d j ) =mk= 1w ik w jk(mk= 1w 2ik ) (mk= 1w 2jk )其中, di 為新文本的特征向量, d j 為第 j 類(lèi)的中心向量,m 為特征向量的維數(shù),wk 為向量的第 K 維.由于 Web 頁(yè)面不同于傳統(tǒng)的文本, 它是一種半結(jié)構(gòu)化的文檔, 包含許多結(jié)構(gòu)信息 Web 頁(yè)面不是單獨(dú)存在的, 頁(yè)面中的指示了頁(yè)面之間的相互關(guān)系

37、, 因而有些學(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)而決定訪(fǎng)問(wèn)順序的方法. 通常認(rèn)為有較多入鏈或出鏈的頁(yè)面具有較高的價(jià)值. PageRank 和 Hits 是其中具有代表性的算法.2.4.4.1PageRank 算法基于評(píng)價(jià)的搜索引擎的優(yōu)秀代表是 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 算法最初用于 Goo

38、gle 搜索引擎信息檢索中對(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 ) = C 1T+ (1 - C) Cin (p )PR (p )ou t (C) 其中T 為計(jì)算中的頁(yè)面總量, C 1 是阻尼常數(shù)因子, in (p )為所有指向p 的頁(yè)面的集合,out (C) 為頁(yè)面 C 出鏈的集合. 基于 PageRank 算法的網(wǎng)絡(luò)爬蟲(chóng)在搜索過(guò)程中, 通過(guò)計(jì)算每個(gè)已訪(fǎng)問(wèn)頁(yè)面的 PageRank

39、 值來(lái)確定頁(yè)面的價(jià)值, 并優(yōu)先選擇 PageRank 值大的頁(yè)面中的進(jìn)行訪(fǎng)問(wèn).2.4.4.2H ITS 算法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 (Hyperlink- Induced Top ic

40、Search)算法是利用 HubAuthority 方法的搜索方法,Authority 表示一個(gè)頁(yè)面被其它頁(yè)面引用的數(shù)量, 即該頁(yè)面的入度值. Hub 表示一個(gè) Web 頁(yè)面指向其它頁(yè)面的數(shù)量, 即該頁(yè)面的出度值. 算法如下: 將查詢(xún). . . . 11 / 65q 提交給傳統(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)集 V l,以權(quán)威網(wǎng)頁(yè)為頂點(diǎn)集V 2,V1 中的網(wǎng)頁(yè)到V 2 中的網(wǎng)頁(yè)的超為邊集E , 形成一個(gè)二分有向

41、圖S G = (V 1,V 2, E ).對(duì)V 1 中的任一個(gè)頂點(diǎn)v ,用H (v )表示網(wǎng)頁(yè)v 的 Hub值, 對(duì)V 2 中的頂點(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ī)化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 指

42、向, 則其權(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 以與 Hub 權(quán)重, 計(jì)算復(fù)雜度隨頁(yè)面和數(shù)量的增長(zhǎng)呈指數(shù)級(jí)增長(zhǎng) 6 .2.4.5 基于鞏固學(xué)習(xí)的聚焦搜索近年來(lái)對(duì) Web 信息資源分布的研究表明很多類(lèi)型一樣的在構(gòu)建方式上, 主題一

43、樣的網(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), 而前兩種策略在這種情況下容易迷失方向.在鞏固學(xué)習(xí)模型中, 把網(wǎng)絡(luò)爬蟲(chóng)經(jīng)過(guò)若干無(wú)關(guān)頁(yè)面的訪(fǎng)問(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ǔ)境圖的聚焦搜索基于鞏固學(xué)習(xí)的網(wǎng)絡(luò)

44、爬蟲(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è)面較早得到訪(fǎng)問(wèn) 7 .基于“語(yǔ)境圖”的搜索策略需要借助已有的通用搜索引擎構(gòu)建“語(yǔ)境圖”, 而搜索引擎的檢索結(jié)果并非一定代表真實(shí)的 web 結(jié)構(gòu), 因而這種方式也具有局限性. . . . 13 / 65第三章 系統(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)一

45、資源定位符（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，每訪(fǎng)問(wèn)到圖中一個(gè)節(jié)點(diǎn) Vi，就進(jìn)行一定的處理。為了達(dá)到上述目的，一個(gè) SPIDER 必須被設(shè)計(jì)成多線(xiàn)程的，A 個(gè)線(xiàn)程并發(fā)地在網(wǎng)絡(luò)上協(xié)同工作，才有可能在盡可能短的時(shí)間遍歷完網(wǎng)絡(luò)中的網(wǎng)頁(yè)。但網(wǎng)頁(yè)數(shù)目是如此之大，如果任 SPIDER 程序無(wú)窮地搜索下去，那么程序幾乎不能終止。所以我們限制 SPIDER 每次工作只訪(fǎng)問(wèn)一個(gè)站點(diǎn)。一個(gè)再大型的站點(diǎn)，其中的網(wǎng)頁(yè)數(shù)目也是有限的，因此 SPIDER 程序能在有限的時(shí)間結(jié)束。當(dāng) SPIDER 程

46、序訪(fǎng)問(wèn)到一個(gè)網(wǎng)頁(yè)，必須進(jìn)行以下幾項(xiàng)基本處理：抽取網(wǎng)頁(yè)中包含的文本；抽取網(wǎng)頁(yè)中包含的 URL，并將其區(qū)分為 URL 或外 URL。3.2 SPIDER 體系結(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è)線(xiàn)程下載一個(gè)基于 URL 的頁(yè)面, 并進(jìn)行 Web 頁(yè)面解析, 得到站 URL 和發(fā)現(xiàn)新站點(diǎn) URL 另外,將 URL 隊(duì)列持久化到數(shù)據(jù)庫(kù), 因此在 SPIDER 任務(wù)執(zhí)行端以外 Down 掉后, 能夠斷點(diǎn)續(xù)傳.SPIDER 客戶(hù)端線(xiàn)程間的協(xié)調(diào)通信采用 Java 的線(xiàn)程同步技術(shù) synchronized,在數(shù)據(jù)服務(wù)端中對(duì) UR

47、L 進(jìn)行緩存提高了系統(tǒng)處理速度. SPIDER 的任務(wù)執(zhí)行和任務(wù)調(diào)度端都需要維持一個(gè) URL 隊(duì)列: 任務(wù)執(zhí)行端的 URL 隊(duì)列中存儲(chǔ)了站 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)單的采用存數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)這些 URL 隊(duì)列有一定的問(wèn)題, 系統(tǒng)沒(méi)有足夠的存空間;而采用直接持久化到數(shù)據(jù)庫(kù), 則需要大量的數(shù)據(jù)庫(kù)連接、查詢(xún)等操作, 系統(tǒng)效率會(huì)明顯下降. 如果采用 URL 壓縮的辦法,盡管在一定

48、程度上可以平衡空間和時(shí)間的矛盾, 但仍然不適用于大規(guī)模數(shù)據(jù)采集的 SPIDER. . . . 圖 3.2 SPIDER 體系結(jié)3.3 各主要功能模塊（類(lèi)）設(shè)計(jì)SPIDERWorker 類(lèi)：該類(lèi)繼承自線(xiàn)程類(lèi)，請(qǐng)求任務(wù) URL，根據(jù)得到的 URL 下載相應(yīng)的 HTML 代碼，利用 HTML 代碼調(diào)用其他模塊完成相關(guān)處理。SPIDERManager 類(lèi)：該類(lèi)用于控制 SPIDERWorker 線(xiàn)程。UrlQueueManager 類(lèi)：該類(lèi)用于維護(hù) URL 等待隊(duì)列，分配任務(wù) URL，URL 消重模塊。UrlParse 類(lèi)：用于解析 HTML，獲取并過(guò)濾 URL。DateBaseConnect 類(lèi)：用

49、于提供數(shù)據(jù)庫(kù)連接。3.4 SPIDER 工作過(guò)程將給定的初始 URL 加入到 URL 等待隊(duì)列。創(chuàng)建爬蟲(chóng)線(xiàn)程，啟動(dòng)爬蟲(chóng)線(xiàn)程每個(gè)爬蟲(chóng)線(xiàn)程從 URL 等待隊(duì)列中取得任務(wù) URL。然后根據(jù) URL 下載網(wǎng)頁(yè)，然. . . . 15 / 65后解析網(wǎng)頁(yè)，獲取超 URLs。如果獲取到的 URL 為相對(duì)地址，需要轉(zhuǎn)換為絕對(duì)地址，然后淘汰站外 URLs，錯(cuò)誤 URLs 或者不能解析的 URL 地址。再判斷這些 URL是否已經(jīng)被下載到，如果沒(méi)有則加入到 URL 等待隊(duì)列。繼續(xù)執(zhí)行步驟，直到結(jié)束條件停止。將初始 URLs 加入到等待隊(duì)列是否為非法 URL創(chuàng)建啟動(dòng)爬蟲(chóng)線(xiàn)程從 URL 等待隊(duì)列獲取任務(wù)URL下載 U

50、RL 對(duì)應(yīng)的 HTML 代碼將相對(duì)地址轉(zhuǎn)換為絕對(duì)地址解析 HTML，獲取 URLs將 URLs 加入到URL 等待隊(duì)列是否為絕對(duì)地址是否為重復(fù) URL. . . . 第四章 系統(tǒng)分析與設(shè)計(jì)4.1 SPIDER 構(gòu)造分析構(gòu)造 SPIDER 程序有兩種方式：（1）把 SPIDER 程序設(shè)計(jì)為遞歸的程序；（2）編寫(xiě)一個(gè)非遞歸的程序，它要維護(hù)一個(gè)要訪(fǎng)問(wèn)的網(wǎng)頁(yè)列表?？紤]使用哪一種方式的前提是，構(gòu)造的 SPIDER 程序必須能夠訪(fǎng)問(wèn)非常大的 Web 站點(diǎn)。本系統(tǒng)中使用了非遞歸的程序設(shè)計(jì)方法。這是因?yàn)?，?dāng)一個(gè)遞歸程序運(yùn)行時(shí)要把每次遞歸壓入堆棧，但在本系統(tǒng)設(shè)計(jì)中使用的是多線(xiàn)程，它允許一次運(yùn)行多個(gè)任務(wù)，但是，多

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

52、ML 代碼，并解析出 URLs，再加入到 URL 隊(duì)列中去。而線(xiàn)程 2 同時(shí)也會(huì)下載它獲取到的 URL 2 對(duì)應(yīng)的 HTML 代碼，解析出 URLs 加入到等待隊(duì)列中。以此類(lèi)推，多個(gè)線(xiàn)程并發(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í)

53、現(xiàn)廣度優(yōu)先爬行。如圖 4.2.1，假如 a 代表初始 URL，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 所示。. . . . 圖 4.2.2圖 4.2.2 列舉了不同時(shí)間段時(shí)，URL 等待隊(duì)列的存儲(chǔ)狀態(tài)。第一個(gè)方框是將初始 URL：a 加入到等待隊(duì)

54、列。第二個(gè)方框?yàn)?，解?a 對(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。通過(guò)這樣的存儲(chǔ)方法實(shí)現(xiàn)如圖 4.2.1 的廣度爬行算法。4.3 URL 抽取，解析和保存4.3.1 URL 抽取通過(guò)觀(guān)察研究 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è)

55、面上 303 既是. . . . 19 / 65通過(guò)觀(guān)察得知，一般 href 標(biāo)簽是以 href=這樣的形式出現(xiàn)的。但是不同的href=后面的容有所不同。比如 href=”url”這樣情況，我們就可以通過(guò)截取雙引號(hào)之間的容來(lái)獲取 URL；如果是 href=url這種情況，我們就需要截取單引號(hào)之間的容來(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.2 URL 解析截取出來(lái)的

56、字符串，可能為相對(duì)地址或者絕對(duì)地址。所以需要判斷 URL 為絕對(duì)地址，還是相對(duì)地址。相對(duì)地址需要先轉(zhuǎn)化為絕對(duì)地址，再進(jìn)行過(guò)濾。因?yàn)榻馕龀鰜?lái)的 URL 地址可能是一些文件的地址，或者為 javascript 文件或者css 文件。這些格式的 URL 是無(wú)法獲取 HTML 代碼的，也就不可能進(jìn)行 URL 解析。所以我們需要過(guò)濾掉這些 URLs。然后再進(jìn)行 URL 消重處理，最后加入到 URL 等待隊(duì)列。為了把爬行限制在同一站點(diǎn)需要截?cái)嘀赶蛘就獾?保證 SPIDER 總在站執(zhí)行,即準(zhǔn)確地根據(jù)超鏈 URL 判斷超鏈?zhǔn)欠裰赶蛘就?由 RFC 對(duì) URL 的定義可知,URL 的格式為protocol:/h

57、ost:port/path?query,一般情況下,同一所有頁(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 的組成可知, host 的格式一般為站分類(lèi).站點(diǎn)標(biāo)志串.站點(diǎn)類(lèi)型各異的串.站點(diǎn)類(lèi)型串只有 |edu|gov|net|國(guó)家域名幾種類(lèi)型,所以我們?nèi)≌军c(diǎn)類(lèi)型各異串前面的串,即站點(diǎn)標(biāo)志串作匹配,超鏈 URL 的 host 中是否包含此串,為超鏈?zhǔn)欠裾镜呐袛鄻?biāo)準(zhǔn).4.3.3 URL 保存因?yàn)榈却?URLs 的數(shù)目非常多，如果全部采用 List 來(lái)

58、存儲(chǔ)非常的占用存空間。所以將等待 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 中的容加入到數(shù)據(jù)庫(kù)，并清空該 List，以便加入新的 URLs；第二段為數(shù)據(jù)庫(kù)，當(dāng)?shù)谝欢螖?shù)據(jù)過(guò)多時(shí)，將第一段的數(shù)據(jù)存入數(shù)據(jù)庫(kù)；第三段也為一個(gè) List，從這里面分配任務(wù) URL，當(dāng)該ListURL 不足時(shí)，將數(shù)據(jù)庫(kù)里的數(shù)據(jù)再轉(zhuǎn)存入。圖 4.3.3 表示了 URL 等待隊(duì)列的結(jié)構(gòu)。. . . . 圖 4.3.3. . . . 21 / 65第五章 系統(tǒng)實(shí)現(xiàn)

59、5.1 實(shí)現(xiàn)工具操作系統(tǒng)是 winXP;JAVA 程序的編寫(xiě)工具是 eclipse-SDK-3.2.1-win32；數(shù)據(jù)庫(kù)是 MYSQL 5 5.0.51a。5.2 爬蟲(chóng)工作這個(gè)類(lèi)繼承自線(xiàn)程類(lèi)，實(shí)現(xiàn)線(xiàn)程在 java 中有兩種方法：一種是直接繼承Thread 類(lèi)；一種是實(shí)現(xiàn) Runnable 接口。我采用了第二種方法：public class SpiderWorker implements Runnable 在這個(gè)類(lèi)中必須要實(shí)現(xiàn)重寫(xiě) run()這個(gè)方法。我在這個(gè)方法里定義了一個(gè)循環(huán)，這個(gè)線(xiàn)程會(huì)重復(fù)地執(zhí)行爬蟲(chóng)動(dòng)作。在這個(gè)循環(huán)里，首先會(huì)向 URL 等待隊(duì)列里請(qǐng)求一個(gè) URL。因?yàn)?URL 隊(duì)列會(huì)出現(xiàn)

60、為空或者被其他線(xiàn)程占用的情況。所以我在這里寫(xiě)了一個(gè)循環(huán)：s = nullnull;whilewhile (s = nullnull) 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(String sourse_url)這個(gè)方法： URLConnection connection = nullnull;InputStreamReader in = nullnull;BufferedReader br = nullnu