【正文】 分析設(shè)計(jì)一些比較復(fù)雜的爬行策略，優(yōu)化爬蟲(chóng)程序。在這個(gè) 3 個(gè)月里，我不斷學(xué)習(xí)，探索，從對(duì)網(wǎng)絡(luò)爬蟲(chóng)一無(wú)所知，到能成功編寫(xiě)出網(wǎng)絡(luò)爬蟲(chóng)程序。對(duì)應(yīng)圖 的爬蟲(chóng)結(jié)果，可以看到這段 URL 的確被過(guò)濾了。最先檢索出來(lái) href 如下：這是一個(gè)相對(duì)地址，對(duì)應(yīng)圖 的爬蟲(chóng)結(jié)果。} catch (Exception ex) {(Error : + ())。middlequeue 表和 databasequeue 表都只有一個(gè)字段 URL，同時(shí)它作為主鍵，因?yàn)榇嫒氲?URL 不可能重復(fù)。Statement stmt = null。)。(0).remove(0)。具體的實(shí)現(xiàn)方法是，當(dāng)存入緩存超過(guò)一定數(shù)目的時(shí)候。((url), true)。} finally {()。public LRULinkedHashMap(int maxCapacity) {super(maxCapacity, DEFAULT_LOAD_FACTOR, true)。而且產(chǎn)生碰撞的幾率非常小，可以忽略不計(jì)。if ((((39。代碼通過(guò)檢索 URL 字符串中是否包含.css， .rar，.zip這些后綴來(lái)進(jìn)行判斷。a href=../mlist/ target=_self 動(dòng)作片/aa href= 例如上面的 HTML 代碼，如果截取出來(lái)的 URL 為../mlist/ 這種形式，即為相對(duì)地址。\39。這個(gè)地方 href=沒(méi)有接續(xù)任何符號(hào)，所以當(dāng)我們沒(méi)有發(fā)現(xiàn)單引號(hào)或雙引號(hào)的時(shí)候，可以判斷為這種情況。然后判斷下表 i+1 位置上的字符是雙引號(hào)，單引號(hào)或者兩者皆不是，然后選擇對(duì)應(yīng)的字符作為截取 URL 的終止標(biāo)記。br = new BufferedReader(in)。InputStreamReader in = null。我在這個(gè)方法里定義了一個(gè)循環(huán)，這個(gè)線程會(huì)重復(fù)地執(zhí)行爬蟲(chóng)動(dòng)作。所以將等待 URLs 存入數(shù)據(jù)庫(kù)中，并設(shè)計(jì) 2 個(gè)緩存區(qū)，用于向隊(duì)列中加入和取得 URLs。 URL 解析截取出來(lái)的字符串，可能為相對(duì)地址或者絕對(duì)地址。HTML 代碼中，頁(yè)面之間的跳轉(zhuǎn)，關(guān)聯(lián)是通過(guò) href 標(biāo)簽來(lái)實(shí)現(xiàn)的。廣度優(yōu)先算法的等待隊(duì)列設(shè)計(jì)如圖 所示。廣度優(yōu)先算法的實(shí)行理論是覆蓋更多的節(jié)點(diǎn)，所以此爬蟲(chóng)程序選擇了廣度優(yōu)先算法。這就意味著遞歸的 SPIDER 程序不能使用多線程。如果獲取到的 URL 為相對(duì)地址，需要轉(zhuǎn)換為絕對(duì)地址，然后淘汰站外 URLs，錯(cuò)誤 URLs 或者不能解析的 URL 地址。而采用直接持久化到數(shù)據(jù)庫(kù), 則需要大量的數(shù)據(jù)庫(kù)連接、查詢等操作, 系統(tǒng)效率會(huì)明顯下降. 如果采用 URL 壓縮的辦法,盡管在一定程度上可以平衡空間和時(shí)間的矛盾, 但仍然不適用于大規(guī)模數(shù)據(jù)采集的 SPIDER.圖 SPIDER 體系結(jié) 各主要功能模塊（類）設(shè)計(jì)SPIDERWorker 類：該類繼承自線程類，請(qǐng)求任務(wù) URL，根據(jù)得到的 URL下載相應(yīng)的 HTML 代碼，利用 HTML 代碼調(diào)用其他模塊完成相關(guān)處理。但網(wǎng)頁(yè)數(shù)目是如此之大，如果任 SPIDER 程序無(wú)窮地搜索下去，那么程序幾乎不能終止。當(dāng)目標(biāo)網(wǎng)頁(yè)存在時(shí) 2 調(diào)用 URLConnection 類 getInputStream()函數(shù)明確打開(kāi)到 URL 的連接，獲取輸入流，再用 包中的 InputStreamReader 類讀取該輸入流，將網(wǎng)頁(yè)下載下來(lái)。這樣，在進(jìn)行過(guò)多次查找操作后，最近被命中過(guò)的內(nèi)容就像鏈表的頭移動(dòng)，而沒(méi)有命中過(guò)的內(nèi)容就向鏈表的后面移動(dòng)。 基于嵌入式 Berkeley DB 的存儲(chǔ)Berkeley DB 的特點(diǎn)就是只存儲(chǔ)鍵值對(duì)類型數(shù)據(jù)，這和 URL 去重有很大關(guān)系。這樣，URL 去重存儲(chǔ)庫(kù)就是要維護(hù)一個(gè) Hash 表，如果 Hash 函數(shù)設(shè)計(jì)的不好，在進(jìn)行映射的時(shí)候，發(fā)生碰撞的幾率很大，則再進(jìn)行碰撞的處理也非常復(fù)雜。我們先從最簡(jiǎn)單的情況說(shuō)起，然后逐步優(yōu)化，最終得到一個(gè)非常不錯(cuò)的解決方案。URL 消重工作量是非常巨大的。在 JAVA 中實(shí)現(xiàn)線程同步的另一個(gè)方法是通過(guò)使用 synchronized 關(guān)鍵字。注意，因?yàn)檫@個(gè)方法會(huì)引起線程的安全問(wèn)題，已經(jīng)被不推薦使用了，所以，不要再程序調(diào)用這個(gè)方法。當(dāng)使用 new 來(lái)新建一個(gè)線程時(shí)，它處于 New 狀態(tài)，這個(gè)時(shí)候，線程并未進(jìn)行任何操作。每個(gè)線程都是通過(guò)某個(gè)特定 Thread 對(duì)象所對(duì)應(yīng)的方法 run()來(lái)完成其操作的，方法 run()稱為線程體。創(chuàng)建一個(gè)線程，并指定一個(gè)目標(biāo)。我們知道，每個(gè) JAVA 應(yīng)用程序都至少有一個(gè)線程，這就是所謂的主線程。因此，雖然我們看到的都是一些同步的操作，但實(shí)際上，對(duì)于計(jì)算機(jī)而言，它在某個(gè)時(shí)間點(diǎn)上只能執(zhí)行一個(gè)程序，除非你的計(jì)算機(jī)是多 CPU 的。比如，我在 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à)。不同的搜索引擎，會(huì)根據(jù)對(duì)搜索結(jié)果的不同需求，選擇最合適的爬行策略來(lái)搜集互聯(lián)網(wǎng)上的信息。以何種策略偏歷互聯(lián)網(wǎng)上的網(wǎng)頁(yè)，也成了爬蟲(chóng)程序主要的研究方向。 HTML code parse. etc. This SPIDER can collect URLs from one web site, and store URLs into database. 【KEY WORD】SPIDER。通過(guò)網(wǎng)絡(luò)爬蟲(chóng)不僅能夠?yàn)樗阉饕娌杉W(wǎng)絡(luò)信息，而且可以作為定向信息采集器，定向采集某些網(wǎng)站下的特定信息，如招聘信息，租房信息等。ABSTRACT SPIDER is a program which can auto collect informations from inter. 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 implements a breadthfirst algorithm multithread SPDIER. This paper expatiates some major problems of SPIDER: why to use breadthfirst crawling strategy, and how to implement breadthfirst crawling。搜索引擎搜集互聯(lián)網(wǎng)上數(shù)以億計(jì)的網(wǎng)頁(yè)，并為每個(gè)詞建立索引。爬蟲(chóng)程序是一個(gè)自動(dòng)獲取網(wǎng)頁(yè)的程序。第二章 相關(guān)技術(shù)介紹 JAVA 線程 線程概述幾乎每種操作系統(tǒng)都支持線程的概念—進(jìn)程就是在某種程度上相互隔離的，獨(dú)立運(yùn)行的程序。那么，為什么我們看不出任何的中斷現(xiàn)象呢？這是因?yàn)?，相?duì)于我們的感覺(jué)，它的速度實(shí)在太快了。在 JAVA 語(yǔ)言中，多線程的機(jī)制是通過(guò)虛擬 CPU 來(lái)實(shí)現(xiàn)的。Thread 有很多個(gè)構(gòu)造器來(lái)創(chuàng)建一個(gè)線程（Thread）實(shí)例：Thread()。Thread(ThreadGroup group,Runnable target)。從上面兩種創(chuàng)建線程的方法可以看出，如果繼承 Thread 類，則這個(gè)類本身可以調(diào)用 start 方法，也就是說(shuō)將這個(gè)繼承了 Thread 的類當(dāng)作目標(biāo)對(duì)象；而如果實(shí)現(xiàn) Runnable 接口，則這個(gè)類必須被當(dāng)作其他線程的目標(biāo)對(duì)象。如果線程在運(yùn)行（Running）狀態(tài)中因?yàn)?I/O 阻塞，等待鍵盤鍵入，調(diào)用了線程的 sleep 方法，調(diào)用了對(duì)象的 wait()方法等，則線程將進(jìn)入阻塞狀態(tài)，直到這些阻塞原因被解除，如：IO 完成，鍵盤輸入了數(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)用。由于 JAVA 中的每個(gè)對(duì)象都是從 Object 繼承來(lái)的。這種情況非常類似于操作系統(tǒng)中虛擬儲(chǔ)存器管理。非常容易想到，在搜索引擎系統(tǒng)中建立一個(gè)全局的專門用來(lái)檢測(cè)，是否某一個(gè) URL 對(duì)應(yīng)的網(wǎng)頁(yè)文件曾經(jīng)被下載過(guò)的 URL 存儲(chǔ)庫(kù)，這就是方案。試想，如果已經(jīng)下載了 100 億網(wǎng)頁(yè)，那么對(duì)應(yīng)著 100 億個(gè)鏈接，也就是這個(gè)檢查 URL是否重復(fù)的記事本文件就要存儲(chǔ)這 100 億 URL，況且，很多 URL 字符串的長(zhǎng)度也不小，占用存儲(chǔ)空間不說(shuō)，查找效率超級(jí)低下，這種方案肯定放棄。從另一個(gè)方面來(lái)說(shuō)，非常少的碰撞，對(duì)于搜索引擎的爬蟲(chóng)是可以容忍的。不過(guò)，我沒(méi)有用過(guò)這種方式，有機(jī)會(huì)可以嘗試一下。當(dāng)成功創(chuàng)建一個(gè) URL 對(duì)象后，我們調(diào)用 openConnection 函數(shù)建立與URL 的通信，此時(shí)，我們就獲得了一個(gè) URLConnection 對(duì)象的引用，URLConnection 類包含了許多與網(wǎng)絡(luò)上的 URL 通信的函數(shù)。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 S 中加入被 S 引用的網(wǎng)頁(yè)和引用 S 的網(wǎng)頁(yè)將 S 擴(kuò)展成一個(gè)更大的集合 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è)二分有向圖 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 指向, 則其權(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 ]. 基于鞏固學(xué)習(xí)的聚焦搜索近年來(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)的地方往往能獲得較好的回報(bào), 而前兩種策略在這種, 把網(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). 基于語(yǔ)境圖的聚焦搜索基于鞏固學(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é)構(gòu), 因而這種方式也具有局限性.第三章 系統(tǒng)需求分析及模塊設(shè)計(jì) 系統(tǒng)需求分析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）。每一個(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ù)傳.SPIDER 客戶端線程間的協(xié)調(diào)通信采用 Java 的線程同步技術(shù) synchronized,在數(shù)據(jù)服務(wù)端中對(duì) URL 進(jìn)行緩存提高了系統(tǒng)處理速度. SPIDER 的任務(wù)執(zhí)行和任務(wù)調(diào)度端都需要維持一個(gè) URL 隊(duì)列: 任務(wù)執(zhí)行端的 URL 隊(duì)列中存儲(chǔ)了站內(nèi)URL。 SPIDER 工作過(guò)程