【正文】 ，是搜索引擎的重要組成部分。不同的搜索引擎，會(huì)根據(jù)對(duì)搜索結(jié)果的不同需求，選擇最合適的爬行策略來搜集互聯(lián)網(wǎng)上的信息。實(shí)現(xiàn)網(wǎng)絡(luò)爬蟲的重點(diǎn)和難點(diǎn)有：多線程的實(shí)現(xiàn)；對(duì)臨界資源的分配；遍歷 web圖的遍歷策略選擇和實(shí)現(xiàn)；存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的選擇和實(shí)現(xiàn)。通過實(shí)現(xiàn)此爬蟲程序可以定點(diǎn)搜集某一站點(diǎn)的 URLs，如果需要搜集其他信息，可以在解析 URLs 的同時(shí)，解析獲取相應(yīng)信息。一般來說，這些操作系統(tǒng)都支持多進(jìn)程操作。比如，我在 Microsoft Word 編寫本論文的時(shí)候，我還打開了一個(gè) mp3 播放器來播放音樂，偶爾的，我還會(huì)再編輯Word 的同時(shí)讓我的機(jī)器執(zhí)行一個(gè)打印任務(wù)，而且我還喜歡通過 IE 從網(wǎng)上下載一個(gè) Flash 動(dòng)畫。看起來，它們都同時(shí)在我的機(jī)器上給我工作。CPU 不斷的在這些程序之間“跳躍”執(zhí)行。我們?nèi)说母兄獣r(shí)間可能以秒來計(jì)算。因此，雖然我們看到的都是一些同步的操作，但實(shí)際上，對(duì)于計(jì)算機(jī)而言，它在某個(gè)時(shí)間點(diǎn)上只能執(zhí)行一個(gè)程序，除非你的計(jì)算機(jī)是多 CPU 的。每個(gè)任務(wù)稱為一個(gè)線程，能夠同時(shí)運(yùn)行多個(gè)線程的程序稱為多線程程序。 JAVA 線程模型我們知道，計(jì)算機(jī)程序得以執(zhí)行的三個(gè)要素是：CPU，程序代碼，可存取的數(shù)據(jù)?？梢孕蜗蟮睦斫鉃?在一個(gè) JAVA 程序內(nèi)部虛擬了多臺(tái)計(jì)算機(jī)，每臺(tái)計(jì)算機(jī)對(duì)應(yīng)一個(gè)線程，有自己的 CPU，可以獲取所需的代碼和數(shù)據(jù)，因此能獨(dú)立執(zhí)行任務(wù)，相互間還可以共用代碼和數(shù)據(jù)。我們知道，每個(gè) JAVA 應(yīng)用程序都至少有一個(gè)線程，這就是所謂的主線程。JVM 還通常會(huì)創(chuàng)建一些其他的線程，不過，這些線程對(duì)我們而言通常都是不可見的。 創(chuàng)建線程 創(chuàng)建線程方式一在 JAVA 中創(chuàng)建線程的一種方式是通過 Thread 來實(shí)現(xiàn)的。創(chuàng)建一個(gè)線程。創(chuàng)建一個(gè)線程，并指定一個(gè)目標(biāo)。創(chuàng)建一個(gè)名為 name 的目標(biāo)為 target 的線程。創(chuàng)建一個(gè)名為 name 的線程。創(chuàng)建一個(gè)隸屬于 group 線程組，目標(biāo)為 target 的線程。每個(gè)線程都是通過某個(gè)特定 Thread 對(duì)象所對(duì)應(yīng)的方法 run()來完成其操作的，方法 run()稱為線程體。調(diào)用 start()方法并不一定馬上會(huì)執(zhí)行這個(gè)線程，正如上面所說，它只是進(jìn)入Runnble 而不是 Running。在使用 Runnable 接口時(shí)，不能直接創(chuàng)建所需類的對(duì)象并運(yùn)行它，而是必須從 Thread 類的一個(gè)實(shí)例內(nèi)部運(yùn)行它。 JAVA 中的線程的生命周期JAVA 的線程從產(chǎn)生到消失,可分為 5 種狀態(tài)：新建（New），可運(yùn)行（Runnable），運(yùn)行（ Running），阻塞（Blocked）以及死亡（Dead）。當(dāng)使用 new 來新建一個(gè)線程時(shí)，它處于 New 狀態(tài)，這個(gè)時(shí)候，線程并未進(jìn)行任何操作。線程調(diào)度程序根據(jù)調(diào)度策略來調(diào)度不同的線程，調(diào)用線程的 run 方法給已經(jīng)注冊(cè)的各個(gè)線程以執(zhí)行的機(jī)會(huì)，被調(diào)度執(zhí)行的線程進(jìn)入運(yùn)行（Running）狀態(tài)。你不能調(diào)用 restart方法來重新開始一個(gè)處于死亡狀態(tài)的線程，但是，你可以調(diào)用處于死亡狀態(tài)的線程對(duì)象的各個(gè)方法。線程調(diào)度程序會(huì)根據(jù)調(diào)度情況，將正在運(yùn)行中的線程設(shè)置為 Runnable 狀態(tài)，例如，有一個(gè)比當(dāng)前運(yùn)行狀態(tài)線程更高運(yùn)行等級(jí)的線程進(jìn)入 Runnable 狀態(tài)，就可能將當(dāng)前運(yùn)行的線程從 Running 狀態(tài)“踢出”,讓它回到 Runnable 狀態(tài)。注意，因?yàn)檫@個(gè)方法會(huì)引起線程的安全問題，已經(jīng)被不推薦使用了，所以，不要再程序調(diào)用這個(gè)方法。JAVA 提供了多種機(jī)制以實(shí)現(xiàn)線程同步。JAVA 中從 Object 對(duì)象繼承來的每個(gè)對(duì)象都有一個(gè)單獨(dú)的鎖。所以 JAVA 中的每個(gè)對(duì)象都有自己的鎖。在 JAVA 中實(shí)現(xiàn)線程同步的另一個(gè)方法是通過使用 synchronized 關(guān)鍵字。synchronized 關(guān)鍵字實(shí)現(xiàn)的基本操作是把每個(gè)需要線程同步的部分定義為一個(gè)臨界區(qū)，在臨界區(qū)中同一時(shí)刻只有一個(gè)線程被執(zhí)行。在持續(xù)下載的過程中，新的 URL非常少，還是以新浪網(wǎng)舉例，1 天 24 小時(shí)中總共出現(xiàn)的新 URL 也就是 10000左右。所謂的虛擬儲(chǔ)存器，是指具有請(qǐng)求調(diào)入和置換功能，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種儲(chǔ)存器系統(tǒng)。URL 消重工作量是非常巨大的。這種操作對(duì)數(shù)據(jù)庫系統(tǒng)是一個(gè)災(zāi)難，理論上任何需要產(chǎn)生磁盤 I/O 動(dòng)作的存儲(chǔ)系統(tǒng)都無法滿足這種查詢的需求。而想要控制這種重復(fù)性下載問題，就要考慮下載所依據(jù)的超鏈接，只要能夠控制待下載的 URL 不重復(fù)，基本可以解決同一個(gè)網(wǎng)頁重復(fù)下載的問題。接著要考慮的就是如何能夠更加高效地讓爬蟲工作，確切地說，讓去重工作更加高效。我們先從最簡單的情況說起，然后逐步優(yōu)化，最終得到一個(gè)非常不錯(cuò)的解決方案。你可以把全部已經(jīng)下載完成的 URL 存放到磁盤記事本文件中。這種方式幾乎沒有人考慮使用了，但是這種檢查的思想是非常直觀的。 基于 Hash 算法的存儲(chǔ)對(duì)每一個(gè)給定的 URL，都是用一個(gè)已經(jīng)建立好的 Hash 函數(shù)，映射到某個(gè)物理地址上。這樣，URL 去重存儲(chǔ)庫就是要維護(hù)一個(gè) Hash 表，如果 Hash 函數(shù)設(shè)計(jì)的不好，在進(jìn)行映射的時(shí)候，發(fā)生碰撞的幾率很大，則再進(jìn)行碰撞的處理也非常復(fù)雜。 基于 MD5 壓縮映射的存儲(chǔ)MD5 算法是一種加密算法，同時(shí)它也是基于 Hash 的算法。另外，MD5 算法能夠?qū)⑷魏巫址畨嚎s為 128 位整數(shù)，并映射為物理地址，而且 MD5 進(jìn)行 Hash 映射碰撞的幾率非常小，這點(diǎn)非常好。況且，在爬蟲進(jìn)行檢測的過程中，可以通過記錄日志來保存在進(jìn)行 MD5 時(shí)發(fā)生碰撞的 URL，通過單獨(dú)對(duì)該 URL 進(jìn)行處理也是可行的。 基于嵌入式 Berkeley DB 的存儲(chǔ)Berkeley DB 的特點(diǎn)就是只存儲(chǔ)鍵值對(duì)類型數(shù)據(jù)，這和 URL 去重有很大關(guān)系。使用了 Berkeley DB，你就不需要考慮進(jìn)行磁盤 IO 操作的性能損失了，這個(gè)數(shù)據(jù)庫在設(shè)計(jì)的時(shí)候很好地考慮了這些問題，并且該數(shù)據(jù)庫支持高并發(fā)，支持記錄的順序存儲(chǔ)和隨機(jī)存儲(chǔ)，是一個(gè)不錯(cuò)的選擇。 基于布隆過濾器（Bloom Filter）的存儲(chǔ)使用布隆過濾器，設(shè)計(jì)多個(gè) Hash 函數(shù)，也就是對(duì)每個(gè)字符串進(jìn)行映射是經(jīng)過多個(gè) Hash 函數(shù)進(jìn)行映射，映射到一個(gè)二進(jìn)制向量上，這種方式充分利用了比特位?？梢詤⒖?Google的 LRU 算法實(shí)現(xiàn) URL 消重用雙向鏈表來實(shí)現(xiàn)大容量 cache 的 LRU 算法。這樣，在進(jìn)行過多次查找操作后，最近被命中過的內(nèi)容就像鏈表的頭移動(dòng)，而沒有命中過的內(nèi)容就向鏈表的后面移動(dòng)。 URL 類訪問網(wǎng)絡(luò)JAVA 提供了許多支 Inter 連接的類，URL 類就是其中之一。如：URL url=new URL（ ）；如果傳遞無效的 URL 給 URL 對(duì)象，該對(duì)象會(huì)拋出 MalformedURLException異常。在下載網(wǎng)頁前，我們需要判斷目標(biāo)網(wǎng)頁是否存在，這時(shí)調(diào)用 URLConnection 類的 getHeaderField()方法，獲得服務(wù)器返回給 SPIDER 程序的響應(yīng)碼，如果響應(yīng)碼包含”20*”字樣，表示目標(biāo)網(wǎng)頁存在，下一步就下載網(wǎng)頁，否則就不下載。當(dāng)目標(biāo)網(wǎng)頁存在時(shí) 2 調(diào)用 URLConnection 類 getInputStream()函數(shù)明確打開到 URL 的連接，獲取輸入流，再用 包中的 InputStreamReader 類讀取該輸入流，將網(wǎng)頁下載下來。ou t (C) Hub 表示一個(gè) Web 頁面指向其它頁面的數(shù)量, 即該頁面的出度值. 網(wǎng)頁的出度值越大 , 其 Hub 值越高. 由于 Hub 值高的頁面通常都提供了指向權(quán)威頁面的鏈接, 因而起到了隱含說明某主題頁面權(quán)威性的作用.HITS (Hyperlink Induced Top ic Search) 算法是利用 Hub246。我們可以把網(wǎng)絡(luò)看做一個(gè)圖 M(V,E)，網(wǎng)絡(luò)中的網(wǎng)頁構(gòu)成節(jié)點(diǎn)集 V，他們之間的鏈接構(gòu)成邊集 E，SPIDER 正是從某一節(jié)點(diǎn)開始，沿著邊，遍歷圖M，每訪問到圖中一個(gè)節(jié)點(diǎn) Vi，就進(jìn)行一定的處理。但網(wǎng)頁數(shù)目是如此之大，如果任 SPIDER 程序無窮地搜索下去，那么程序幾乎不能終止。一個(gè)再大型的站點(diǎn)，其中的網(wǎng)頁數(shù)目也是有限的，因此 SPIDER 程序能在有限的時(shí)間內(nèi)結(jié)束。 SPIDER 體系結(jié)構(gòu)此爬蟲程序主要分為三個(gè)部分：任務(wù)執(zhí)行端，任務(wù)調(diào)度端，數(shù)據(jù)服務(wù)端。 任務(wù)調(diào)度端則是站點(diǎn)的 URL. 在這些 URL 隊(duì)列上有大量的操作, 包括URL 查找、 URL 插入、URL 狀態(tài)更新等. 如果 SPIDER 以 300 頁 246。而采用直接持久化到數(shù)據(jù)庫, 則需要大量的數(shù)據(jù)庫連接、查詢等操作, 系統(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)處理。UrlQueueManager 類：該類用于維護(hù) URL 等待隊(duì)列，分配任務(wù) URL，URL消重模塊。DateBaseConnect 類：用于提供數(shù)據(jù)庫連接。②創(chuàng)建爬蟲線程，啟動(dòng)爬蟲線程③每個(gè)爬蟲線程從 URL 等待隊(duì)列中取得任務(wù) URL。如果獲取到的 URL 為相對(duì)地址，需要轉(zhuǎn)換為絕對(duì)地址，然后淘汰站外 URLs，錯(cuò)誤 URLs 或者不能解析的 URL 地址。④繼續(xù)執(zhí)行步驟③，直到結(jié)束條件停止。考慮使用哪一種方式的前提是，構(gòu)造的 SPIDER 程序必須能夠訪問非常大的 Web 站點(diǎn)。這是因?yàn)?，?dāng)一個(gè)遞歸程序運(yùn)行時(shí)要把每次遞歸壓入堆棧，但在本系統(tǒng)設(shè)計(jì)中使用的是多線程，它允許一次運(yùn)行多個(gè)任務(wù)，但是，多線程與遞歸是不兼容的。這就意味著遞歸的 SPIDER 程序不能使用多線程。圖 圖 表示了該系統(tǒng)爬蟲線程的實(shí)現(xiàn)策略。然后線程 1 會(huì)再從 URL 隊(duì)列中獲取新的 URL，下載 HTML 代碼，并解析出 URLs，再加入到 URL 隊(duì)列中去。以此類推，多個(gè)線程并發(fā)地去完成爬蟲工作。廣度優(yōu)先算法的實(shí)行理論是覆蓋更多的節(jié)點(diǎn)，所以此爬蟲程序選擇了廣度優(yōu)先算法。然后依次獲取這些 URLs 對(duì)應(yīng)的 HTML 里的 URLs，當(dāng)這一層所有的 URLs 都下載解析完后，在獲取下一層的信息。如圖 ，假如 a 代表初始 URL，bcd 為以 a 獲取的 3 個(gè) URLs，efg 為以b 獲取的 URLs，以此類推。當(dāng)獲取到 b 的 URLs 之后，并不會(huì)馬上去解析這些 URLs，而是先解析同 b 在同一層中的 cd 對(duì)應(yīng)的 URLs。廣度優(yōu)先算法的等待隊(duì)列設(shè)計(jì)如圖 所示。第一個(gè)方框是將初始 URL：a 加入到等待隊(duì)列。第三個(gè)方框?yàn)?，解?b 對(duì)應(yīng) HTML 獲取URLs：efg ，同時(shí)刪除 URL：b。通過這樣的存儲(chǔ)方法實(shí)現(xiàn)如圖 的廣度爬行算法。HTML 代碼中，頁面之間的跳轉(zhuǎn)，關(guān)聯(lián)是通過 href 標(biāo)簽來實(shí)現(xiàn)的。lia href=movie_2022/html/ target=_blank我猜[20220531]/aem531/em/lilia href=movie_2022/html/? target=_blank火影忍者[331 ，頁面上 303 既是]/a/li通過觀察得知，一般 href 標(biāo)簽是以 href=這樣的形式出現(xiàn)的。比如 href=”url”這樣情況，我們就可以通過截取雙引號(hào)之間的內(nèi)容來獲取 URL；如果是 href=’url’這種情況，我們就需要截取單引號(hào)之間的內(nèi)容來獲取 URL；或者有些是 href=url，我們需要以等號(hào)為開始標(biāo)記，而這種情況通常結(jié)尾是空格或者符號(hào)。但是有些 URLs 是通過提交表單，或者通過 javascript 來跳轉(zhuǎn)的。 URL 解析截取出來的字符串，可能為相對(duì)地址或者絕對(duì)地址。相對(duì)地址需要先轉(zhuǎn)化為絕對(duì)地址，再進(jìn)行過濾。這些格式的 URL 是無法獲取 HTML 代碼的，也就不可能進(jìn)行 URL 解析。然后再進(jìn)行 URL 消重處理，最后加入到 URL等待隊(duì)列。所以將等待 URLs 存入數(shù)據(jù)庫中，并設(shè)計(jì) 2 個(gè)緩存區(qū)，用于向隊(duì)列中加入和取得 URLs。當(dāng)這個(gè) List 中的數(shù)目過多時(shí)，則將 List 中的內(nèi)容加入到數(shù)據(jù)庫，并清空該 List，以便加入新的 URLs；第二段為數(shù)據(jù)庫，當(dāng)?shù)谝欢螖?shù)據(jù)過多時(shí)，將第一段內(nèi)的數(shù)據(jù)存入數(shù)據(jù)庫；第三段也為一個(gè) List，從這里面分配任務(wù)URL，當(dāng)該 List 內(nèi) URL 不足時(shí)，將數(shù)據(jù)庫里的數(shù)據(jù)再轉(zhuǎn)存入。圖 第五章 系統(tǒng)實(shí)現(xiàn) 實(shí)現(xiàn)工具操作系統(tǒng)是 winXP。 爬蟲工作這個(gè)類繼承自線程類，實(shí)現(xiàn)線程在 java 中有兩種方法：一種是直接繼承Thread 類；一種是實(shí)現(xiàn) Runnable 接口。我在這個(gè)方法里定義了一個(gè)循環(huán)，這個(gè)線程會(huì)重復(fù)地執(zhí)行爬蟲動(dòng)作。因?yàn)?URL 隊(duì)列會(huì)出現(xiàn)為空或者被其他線程占用的情況。while (s == null) {s = ()。當(dāng)?shù)玫饺蝿?wù) URL 以后，會(huì)通過這個(gè) URL 得到對(duì)應(yīng)的 HTML 代碼。InputStreamReader in = null。URL url = null。connection = (HttpURLConnection) ()。// 打開的連接讀取的輸入流。br = new BufferedReader(in)。while ((c = ()) != null) {(c)。這個(gè)方法是通過調(diào)用 JAVA 里面的 URL 這個(gè)類，可以用給定的 URL 構(gòu)造這個(gè)類的一個(gè)實(shí)例，然后通過 openStream()這