網(wǎng)絡爬蟲講解（附java實現(xiàn)的實例）

1、網(wǎng)絡爬蟲講解（附java實現(xiàn)的實例） 網(wǎng)絡蜘蛛即web spider，是一個很形象的名字。把互聯(lián)網(wǎng)比喻成一個蜘蛛網(wǎng)，那么spider就是在網(wǎng)上爬來爬去的蜘蛛。網(wǎng)絡蜘蛛是通過網(wǎng)頁的鏈接地址來尋找網(wǎng)頁，從 網(wǎng)站某一個頁面（通常是首頁）開始，讀取網(wǎng)頁的內(nèi)容，找到在網(wǎng)頁中的其它鏈接地址，然后通過這些鏈接地址尋找下一個網(wǎng)頁，這樣一直循環(huán)下去，直到把這個網(wǎng)站所有的網(wǎng)頁都抓取完為止。如果把整個互聯(lián)網(wǎng)當成一個網(wǎng)站，那么網(wǎng)絡蜘蛛就可以用這個原理把互聯(lián)網(wǎng)上所有的網(wǎng)頁都抓取下來。對于搜索引擎來說，要抓取互聯(lián)網(wǎng)上所有的網(wǎng)頁幾乎是不可能的，從目前公布的數(shù)據(jù)來看，容量最大的搜索引擎也不過是抓取了整個網(wǎng)頁數(shù)量的百分之四十左

2、右。這其中的原因一方面是抓取技術(shù)的瓶頸，無法遍歷所有的網(wǎng)頁，有許多網(wǎng)頁無法從其它網(wǎng)頁的鏈接中找到；另一個原因是存儲技術(shù)和處理技術(shù)的問題，如果按照每個頁面的平均大小為20k計算（包含圖片），100億網(wǎng)頁的容量是100×2000g字節(jié)，即使能夠存儲，下載也存在問題（按照一臺機器每秒下載 20k計算，需要340臺機器不停的下載一年時間，才能把所有網(wǎng)頁下載完畢）。同時，由于數(shù)據(jù)量太大，在提供搜索時也會有效率方面的影響。因此，許多搜索引擎的網(wǎng)絡蜘蛛只是抓取那些重要的網(wǎng)頁，而在抓取的時候評價重要性主要的依據(jù)是某個網(wǎng)頁的鏈接深度。在抓取網(wǎng)頁的時候，網(wǎng)絡蜘蛛一般有兩種策略：廣度優(yōu)先和深度優(yōu)先。廣度優(yōu)

3、先是指網(wǎng)絡蜘蛛會先抓取起始網(wǎng)頁中鏈接的所有網(wǎng)頁，然后再選擇其中的一個鏈接網(wǎng)頁，繼續(xù)抓取在此網(wǎng)頁中鏈接的所有網(wǎng)頁。這是最常用的方式，因為這個方法可以讓網(wǎng)絡蜘蛛并行處理，提高其抓取速度。深度優(yōu)先是指網(wǎng)絡蜘蛛會從起始頁開始，一個鏈接一個鏈接跟蹤下去，處理完這條線路之后再轉(zhuǎn)入下一個起始頁， 繼續(xù)跟蹤鏈接。這個方法有個優(yōu)點是網(wǎng)絡蜘蛛在設計的時候比較容易。兩種策略的區(qū)別，下圖的說明會更加明確。由于不可能抓取所有的網(wǎng)頁，有些網(wǎng)絡蜘蛛對一些不太重要的網(wǎng)站，設置了訪問的層數(shù)。例如，在上圖中，a為起始網(wǎng)頁，屬于0層，b、c、d、 e、f屬于第1層，g、h屬于第2層， i屬于第3層。如果網(wǎng)絡蜘蛛設置的訪問層數(shù)為2的

4、話，網(wǎng)頁i是不會被訪問到的。這也讓有些網(wǎng)站上一部分網(wǎng)頁能夠在搜索引擎上搜索到，另外一部分不能被搜索到。對于網(wǎng)站設計者來說，扁平化的網(wǎng)站結(jié)構(gòu)設計有助于搜索引擎抓取其更多的網(wǎng)頁。網(wǎng)絡蜘蛛在訪問網(wǎng)站網(wǎng)頁的時候，經(jīng)常會遇到加密數(shù)據(jù)和網(wǎng)頁權(quán)限的問題，有些網(wǎng)頁是需要會員權(quán)限才能訪問。當然，網(wǎng)站的所有者可以通過協(xié)議讓網(wǎng) 絡蜘蛛不去抓?。ㄏ滦」?jié)會介紹），但對于一些出售報告的網(wǎng)站，他們希望搜索引擎能搜索到他們的報告，但又不能完全*的讓搜索者查看，這樣就需要給網(wǎng)絡蜘 蛛提供相應的用戶名和密碼。網(wǎng)絡蜘蛛可以通過所給的權(quán)限對這些網(wǎng)頁進行網(wǎng)頁抓取，從而提供搜索。而當搜索者點擊查看該網(wǎng)頁的時候，同樣需要搜索者提供相應的權(quán)

5、限驗證。網(wǎng)站與網(wǎng)絡蜘蛛網(wǎng)絡蜘蛛需要抓取網(wǎng)頁，不同于一般的訪問，如果控制不好，則會引起網(wǎng)站服務器負擔過重。去年4月，淘寶 ）就因為雅虎搜索引擎的網(wǎng)絡蜘蛛抓取其數(shù)據(jù)引起淘寶網(wǎng)服務器的不穩(wěn)定。網(wǎng)站是否就無法和網(wǎng)絡蜘蛛交流呢？其實不然，有多種方法可以讓網(wǎng)站和網(wǎng)絡蜘蛛進行交流。一方面讓網(wǎng)站管理員了解網(wǎng)絡蜘蛛都來自哪兒，做了些什么，另一方面也告訴網(wǎng)絡蜘蛛哪些網(wǎng)頁不應該抓取，哪 些網(wǎng)頁應該更新。每個網(wǎng)絡蜘蛛都有自己的名字，在抓取網(wǎng)頁的時候，都會向網(wǎng)站標明自己的身份。網(wǎng)絡蜘蛛在抓取網(wǎng)頁的時候會發(fā)送一個請求，這個請求中就有一個字段為useragent，用于標識此網(wǎng)絡蜘蛛的身份。例如google網(wǎng)絡蜘蛛的標識為g

6、ooglebot，baidu網(wǎng)絡蜘蛛的標識為baiduspider， yahoo網(wǎng)絡蜘蛛的標識為inktomi slurp。如果在網(wǎng)站上有訪問日志記錄，網(wǎng)站管理員就能知道，哪些搜索引擎的網(wǎng)絡蜘蛛過來過，什么時候過來的，以及讀了多少數(shù)據(jù)等等。如果網(wǎng)站管理員發(fā)現(xiàn)某個蜘蛛有問題，就通過其標識來和其所有者聯(lián)系。下面是博客中）2004年5月15日的搜索引擎訪問日志：網(wǎng)絡蜘蛛進入一個網(wǎng)站，一般會訪問一個特殊的文本文件robots.txt，這個文件一般放在網(wǎng)站服務器的根目錄下，user-agent: * disallow:當然，robots.txt只是一個協(xié)議，如果網(wǎng)絡蜘蛛的設計者不遵循這個協(xié)議，網(wǎng)站管理員

7、也無法阻止網(wǎng)絡蜘蛛對于某些頁面的訪問，但一般的網(wǎng)絡蜘蛛都會遵循這些協(xié)議，而且網(wǎng)站管理員還可以通過其它方式來拒絕網(wǎng)絡蜘蛛對某些網(wǎng)頁的抓取。網(wǎng)絡蜘蛛在下載網(wǎng)頁的時候，會去識別網(wǎng)頁的html代碼，在其代碼的部分，會有meta標識。通過這些標識，可以告訴網(wǎng)絡蜘蛛本網(wǎng)頁是否需要被抓取，還可以告訴網(wǎng)絡蜘蛛本網(wǎng)頁中的鏈接是否需要被繼續(xù)跟蹤。例如：表示本網(wǎng)頁不需要被抓取，但是網(wǎng)頁內(nèi)的鏈接需要被跟蹤?，F(xiàn)在一般的網(wǎng)站都希望搜索引擎能更全面的抓取自己網(wǎng)站的網(wǎng)頁，因為這樣可以讓更多的訪問者能通過搜索引擎找到此網(wǎng)站。為了讓本網(wǎng)站的網(wǎng)頁更全面被抓取到，網(wǎng)站管理員可以建立一個網(wǎng)站地圖，即sitemap。許多網(wǎng)絡蜘蛛會把si

8、temap.htm文件作為一個網(wǎng)站網(wǎng)頁爬取的入口，網(wǎng)站管理員可以把網(wǎng)站內(nèi)部所有網(wǎng)頁的鏈接放在這個文件里面，那么網(wǎng)絡蜘蛛可以很方便的把整個網(wǎng)站抓取下來，避免遺漏某些網(wǎng)頁，也會減小對網(wǎng)站服務器的負擔。內(nèi)容提取搜索引擎建立網(wǎng)頁索引，處理的對象是文本文件。對于網(wǎng)絡蜘蛛來說，抓取下來網(wǎng)頁包括各種格式，包括html、圖片、doc、pdf、多媒體、 動態(tài)網(wǎng)頁及其它格式等。這些文件抓取下來后，需要把這些文件中的文本信息提取出來。準確提取這些文檔的信息，一方面對搜索引擎的搜索準確性有重要作用，另一方面對于網(wǎng)絡蜘蛛正確跟蹤其它鏈接有一定影響。對于doc、pdf等文檔，這種由專業(yè)廠商提供的軟件生成的文檔，廠商都會提

9、供相應的文本提取接口。網(wǎng)絡蜘蛛只需要調(diào)用這些插件的接口，就可以輕松的提取文檔中的文本信息和文件其它相關的信息。html等文檔不一樣，html有一套自己的語法，通過不同的命令標識符來表示不同的字體、顏色、位置等版式，如：、等，提取文本信息時需要把這些標識符都過濾掉。過濾標識符并非難事，因為這些標識符都有一定的規(guī)則，只要按照不同的標識符取得相應的信息即可。但在識別這些信息的時候，需要同步記錄許多版式信息，例如文字的字體大小、是否是標題、是否是加粗顯示、是否是頁面的關鍵詞等，這些信息有助于計算單詞在網(wǎng)頁中的重要程度。同時，對于 html網(wǎng)頁來說，除了標題和正文以外，會有許多廣告鏈接以及公共的頻道鏈接

10、，這些鏈接和文本正文一點關系也沒有，在提取網(wǎng)頁內(nèi)容的時候，也需要過濾這些 無用的鏈接。例如某個網(wǎng)站有“產(chǎn)品介紹”頻道，因為導航條在網(wǎng)站內(nèi)每個網(wǎng)頁都有，若不過濾導航條鏈接，在搜索“產(chǎn)品介紹”的時候，則網(wǎng)站內(nèi)每個網(wǎng)頁都會搜索到，無疑會帶來大量垃圾信息。過濾這些無效鏈接需要統(tǒng)計大量的網(wǎng)頁結(jié)構(gòu)規(guī)律，抽取一些共性，統(tǒng)一過濾；對于一些重要而結(jié)果特殊的網(wǎng)站，還需要個別處理。這就需要網(wǎng)絡蜘蛛的設計有一定的擴展性。對于多媒體、圖片等文件，一般是通過鏈接的錨文本（即，鏈接文本）和相關的文件注釋來判斷這些文件的內(nèi)容。例如有一個鏈接文字為“張曼玉照片 ”，其鏈接指向一張bmp格式的圖片，那么網(wǎng)絡蜘蛛就知道這張圖片的內(nèi)

11、容是“張曼玉的照片”。這樣，在搜索“張曼玉”和“照片”的時候都能讓搜索引擎找到這張圖片。另外，許多多媒體文件中有文件屬性，考慮這些屬性也可以更好的了解文件的內(nèi)容。動態(tài)網(wǎng)頁一直是網(wǎng)絡蜘蛛面臨的難題。所謂動態(tài)網(wǎng)頁，是相對于靜態(tài)網(wǎng)頁而言，是由程序自動生成的頁面，這樣的好處是可以快速統(tǒng)一更改網(wǎng)頁風格，也可以減少網(wǎng)頁所占服務器的空間，但同樣給網(wǎng)絡蜘蛛的抓取帶來一些麻煩。由于開發(fā)語言不斷的增多，動態(tài)網(wǎng)頁的類型也越來越多，如：asp、jsp、php 等。這些類型的網(wǎng)頁對于網(wǎng)絡蜘蛛來說，可能還稍微容易一些。網(wǎng)絡蜘蛛比較難于處理的是一些腳本語言（如vbscript和javascript）生成的網(wǎng)頁，如果要完善的

12、處理好這些網(wǎng)頁，網(wǎng)絡蜘蛛需要有自己的腳本解釋程序。對于許多數(shù)據(jù)是放在數(shù)據(jù)庫的網(wǎng)站，需要通過本網(wǎng)站的數(shù)據(jù)庫搜索才能獲得信息，這些給網(wǎng)絡蜘蛛的抓取帶來很大的困難。對于這類網(wǎng)站，如果網(wǎng)站設計者希望這些數(shù)據(jù)能被搜索引擎搜索，則需要提供一種可以遍歷整個數(shù)據(jù)庫內(nèi)容的方法。對于網(wǎng)頁內(nèi)容的提取，一直是網(wǎng)絡蜘蛛中重要的技術(shù)。整個系統(tǒng)一般采用插件的形式，通過一個插件管理服務程序，遇到不同格式的網(wǎng)頁采用不同的插件處理。這種方式的好處在于擴充性好，以后每發(fā)現(xiàn)一種新的類型，就可以把其處理方式做成一個插件補充到插件管理服務程序之中。更新周期由于網(wǎng)站的內(nèi)容經(jīng)常在變化，因此網(wǎng)絡蜘蛛也需不斷的更新其抓取網(wǎng)頁的內(nèi)容，這就需要網(wǎng)絡

13、蜘蛛按照一定的周期去掃描網(wǎng)站，查看哪些頁面是需要更新的頁面，哪些頁面是新增頁面，哪些頁面是已經(jīng)過期的死鏈接。搜索引擎的更新周期對搜索引擎搜索的查全率有很大影響。如果更新周期太長，則總會有一部分新生成的網(wǎng)頁搜索不到；周期過短，技術(shù)實現(xiàn)會有一定難度，而且會對帶寬、服務器的資源都有浪費。搜索引擎的網(wǎng)絡蜘蛛并不是所有的網(wǎng)站都采用同一個周期進行更新，對于一些重要的更新量大的網(wǎng)站，更新的周期短，如有些新聞網(wǎng)站，幾個小時就更新一次；相反對于一些不重要的網(wǎng)站，更新的周期就長，可能一兩個月才更新一次。一般來說，網(wǎng)絡蜘蛛在更新網(wǎng)站內(nèi)容的時候，不用把網(wǎng)站網(wǎng)頁重新抓取一遍，對于大部分的網(wǎng)頁，只需要判斷網(wǎng)頁的屬性（主要

14、是日期），把得到的屬性和上次抓取的屬性相比較，如果一樣則不用更新。spider的實現(xiàn)細節(jié)a. url 的組織和管理考慮到系統(tǒng)自身的資源和時間有限，spider程序應盡可能的對鏈接進行篩選，以保證獲取信息的質(zhì)量和效率。spider程序?qū)π聈rl 的選擇往往與搜索引擎的類型、目標集合、能夠處理信息的類型、資源的限制和是否支持robots限制協(xié)議有關。概括為以下幾點: 訪問過的和重復的url排除 文件類型必須被系統(tǒng)處理，不能處理的url排除 不在目標集合中的排除，被rohots.txt限制的排除url排序也是減輕系統(tǒng)負擔的重要手段之一。這就要求計算url的重要性，如果評估新uri的重要性較高，則會沖

15、掉舊的url。無論任何情況下，對 spider而言，首先訪問目標集合中的重要站點都是意義和重要的。但是一個頁面的重要性的準確評估只能在分析其內(nèi)容之后進行?？梢愿鶕?jù)一個頁面鏈接數(shù)量的多少來評估此頁面是否重要;或者對url 地址進行解析其中的內(nèi)容例如以".com", ".edu"，".cn"就較為重要一些，或者可以根據(jù)頁而標題與當前的熱點問題是否相近或相關來評定其頁面的重要性。決定網(wǎng)站或頁面的重要性的因素很多，也根據(jù)各個搜索引擎的側(cè)重點不同而各異，最終的評估方法都依賴于該搜索引擎對于資源獲取的要求來決定。影響spider速度的一種重要因素

16、是dns查詢，為此每個 spider都要維護一個自己的dns緩沖。這樣每個鏈接都處于不同的狀態(tài)，包括:dns 查詢、連接到主機、發(fā)送請求、得到響應。這些因素綜合起來使得spider變成一個非常復雜的系統(tǒng)。b. spider的遍歷規(guī)則：頁面的遍歷主要有兩種方式:深度遍歷和廣度遍歷。深度遍歷算法可以獲得的信息較為集中，信息比較完整，但覆蓋面就比較有限，廣度遍歷算法則剛好相反。c. spider實現(xiàn)中的主要問題：雖然spider的功能很強，但也存在不少的問題:(1)如果一組url地址沒有被組外url所鏈接到，那么spider就找不到它們。由于spider不能更新過快(因為網(wǎng)絡帶寬是有限的，更新過快就

17、會影響其他用戶的正常使用)，難免有不能及時加入的新網(wǎng)站或新頁面。(2)spider程序在遍歷web時也存在危險，很可能遇到一個環(huán)鏈接而陷入死循環(huán)中。簡單的避免方法就是忽略已訪問過的url,或限制網(wǎng)站的遍歷深度。(3) spider程序時大型搜索引擎中很脆弱的部分，因為它與很多的web報務器、不同的域名服務器打交道，而這些服務完全在系統(tǒng)的控制之外。由于網(wǎng)絡上包含了大量的垃圾信息，spider很可能會收取這些垃圾信息。一個頁面出現(xiàn)問題也很可能引起spider程序中止、崩潰或其他不可預料的行為。因此訪問 internet的spider程序應該設計得非常強壯，充分考慮各種可能遇到的情況，讓spider

18、在遇到各種情況時可以采取相應的處理行為，而不至于獲得一些垃圾信息或者直接就對程序本身造成危害。spider構(gòu)架發(fā)現(xiàn)、搜集網(wǎng)頁信息需要有高性能的“網(wǎng)絡蜘蛛”程序spider去自動地在互聯(lián)網(wǎng)中搜索信息。一個典型的網(wǎng)絡蜘蛛工作的方式:查看一個頁面，并從中找到相關信息，然后它再從該頁面的所有鏈接中出發(fā)，繼續(xù)尋找相關的信息，以此類推。網(wǎng)絡蜘蛛在搜索引擎整體結(jié)構(gòu)中的位置如下圖所示: 初始化時，網(wǎng)絡蜘蛛一般指向一個url ( uniform resourcelocator)池。在遍歷internet的過程中，按照深度優(yōu)先或廣度優(yōu)先或其他啟發(fā)式算法從url池中取出若干url進行處理，同時將未訪問的 url放入

19、url池中，這樣處理直到url池空為止。對web文檔的索引則根據(jù)文檔的標題、首段落甚至整個頁面內(nèi)容進行，這取決于搜索服務的數(shù)據(jù)收集策略。網(wǎng)絡蜘蛛在漫游的過程中，根據(jù)頁面的標題、頭、鏈接等生成摘要放在索引數(shù)據(jù)庫中。如果是全文搜索，還需要將整個頁面的內(nèi)容保存到本地數(shù)據(jù)庫。網(wǎng)絡蜘蛛為實現(xiàn)其快速地瀏覽整個互聯(lián)網(wǎng)，通常在技術(shù)上采用搶先式多線程技術(shù)實現(xiàn)在網(wǎng)上搜索信息。通過搶先式多線程的使用，你能索引一個基于url鏈接的 web頁面，啟動一個新的線程跟隨每個新的url鏈接，索引一個新的url起點。當然在服務器上所開的線程也不能無限膨脹，需要在服務器的正常運轉(zhuǎn)和快速 收集網(wǎng)頁之間找一個平衡點。在整個搜索引擎工

20、作過程中，整個蜘蛛的數(shù)據(jù)入口是url地址，數(shù)據(jù)出口是web頁倉庫。spider程序發(fā)現(xiàn)url鏈接以后，經(jīng)過stor處理模塊，將我們所需要的網(wǎng)頁數(shù)據(jù)存儲在web頁倉庫中，為以后的形成網(wǎng)頁快照、網(wǎng)頁分析提供基礎數(shù)據(jù)。在spider程序工作的過程中，發(fā)現(xiàn)新的鏈接，對該鏈接進行分析，形成新的搜索地址，作為下一次spider程序的數(shù)據(jù)輸入。這個過程的實現(xiàn)就是spider程序的隊列管理。spider程序的工作過程，簡單來講，就是不斷發(fā)現(xiàn)新的鏈接，并對該鏈接對應的頁面分析存儲的工程。如下圖所示，一、索引器： 索引器的功能是理解搜索器所搜集的信息，從中抽取出索引項，用于表示文檔以及生成文檔庫的索引表。索引項有

21、客觀索引項和內(nèi)容索引項兩種: 客觀項：與文檔的語意內(nèi)容無關，如作者名、url、更新時間、編碼、長度、鏈接流行度(link popularity)等等; 內(nèi)容索引項：是用來反映文檔內(nèi)容的，如關鍵詞及其權(quán)重、短語、詞、字等等。內(nèi)容索引項可以分為單索引項和多索引項(或稱短語索引項)兩種。單索引項對于英文來講是英語單詞，比較容易提取，因為單詞之間有天然的分隔符(空格);對于中文等連續(xù)書寫的語言，必須采用多索引項，進行詞語的切分。索引器可以使用集中式索引算法或分布式索引算法。當數(shù)據(jù)量很大時，必須實現(xiàn)實時索引(real-time indexing),否則不能夠跟上信息量急劇增加的速度。索引算法對索引器的性

22、能(如大規(guī)模峰值查詢時的響應速度)有很大的影響。一個搜索引擎的有效性 在很大程度取決于索引的質(zhì)量。 由于漢文字符多，處理復雜，中文詞的處理不容易。索引器中的中文分詞技術(shù)： 一個分詞系統(tǒng)=分詞程序+分詞詞典(1)最大匹配法mm (2)反向最大匹配法rmm (1)最佳匹配法om (1)雙向掃描法百度的分詞就采用了雙向掃描法 系統(tǒng)關鍵是：分詞精度和分詞速度二、建立索引的方法： 為了加快檢索速度，搜索引擎要對snider程序搜集到的信,建立倒排索引。 （1）全文索引和部分索引有些搜索引擎對于信息庫中的頁面建立全文索引，有些只建立摘要部分索引或者每個段落前面部分的索引。還有些搜索引擎在建立索引時，要同時

23、考慮超文本的不同標記所表示的含義，如粗體、大字體顯示的東西往往比較重要。有些搜索引擎還在建立索引的過程中收集頁面中的超鏈接。這些超鏈接反映了收集到的信息之間的空間結(jié)構(gòu)。利用這些結(jié)果信息可以提高頁面相關度判別時的準確度。（2）是否過濾無用詞由于網(wǎng)頁中存在這許多無用(無實際意義)單詞，例如“啊”、“的”等。這此詞往往不能明確表達該網(wǎng)頁信息，所以有些搜索引擎保存一個無用詞匯表，在建立索引時將不對這些詞匯建立索引。 （3）是否使用meta標記中的信息網(wǎng)頁中的meta標記用來標注一些非常顯示性的信息。有些網(wǎng)頁將頁面的關鍵詞等信息放在其中。便于在建立索引的過程中提高這些詞匯的相關度。（4）是否對圖像標記中

24、的替換文本(alt text)或頁面中的注解建立索引由于現(xiàn)有的搜索引擎對圖像的檢索技術(shù)還不太成熟，大多數(shù)搜索引擎不支持圖像的檢索。在超文木的結(jié)構(gòu)頁面中，圖像標記中往往存放著圖像的替換信息。這些信息說明了該圖像對應的圖像的基本信息。（5）是否支持詞干提取技術(shù)三、建立索引的過程： 分析過程對文檔進行索引并存儲到存儲桶中排序過程spider處理流程當一個url被加入到等待隊列中時spider程序就會開始運行。只要等待隊列中有一個網(wǎng)頁或spider程序正在處理一個網(wǎng)頁，spider程序就會繼續(xù)它的工作。當?shù)却犃袨榭詹⑶耶斍皼]有處理任何網(wǎng)頁，spider程序就會停止它的工作。spider程序?qū)崿F(xiàn)初探s

25、pider 程序是從網(wǎng)上下載web頁面再對其進行處理，為了提高效率，很顯然要采用多線程的方法，幾個spider線程同時并行工作，訪問不同的鏈接。構(gòu)造 spider程序有兩種方式。第一種是將它設計為遞歸程序，第二種是將它編寫成非遞歸的程序。遞歸是在一個方法中調(diào)用它本身的程序設計技術(shù)。當需要重復做同樣的基本仟務或在處理先前任務時可展現(xiàn)將來的任務信息時，遞歸是相當實用的。例如下面的代碼:void recursivespider(string url) download urlparse urlwhile found each urlcall recursivespider(found url) pr

26、ocess the page just downloaded 這段代碼查看單獨的一個web頁的任務放在一個recursivespider方法中。在此，調(diào)用recursivesipder方法來訪問url。當它發(fā)現(xiàn)鏈接時，該方法調(diào)用它自己。遞歸方法在訪問很少的網(wǎng)頁時，可以使用。因為當一個遞歸程序運行時要把每次遞歸壓入堆棧(堆棧是個程序結(jié)構(gòu)，每次調(diào)用一個方法時，將返回地址存入其中)。如果遞歸程序要運行很多次，堆棧會變得非常大，它可能會耗盡整個堆棧內(nèi)存而導致程序中止。遞歸還有個問題是多線程和遞歸是不兼容的，因為在這一過程中每一個線程都是自己的堆棧。當一個方法調(diào)用它自身時，它們需要使用同一個堆棧。這就是

27、說遞歸的spider程序不能使用多線程。 非遞歸程序不調(diào)用自身，而是采用隊列的方法。隊列就是排隊，要得到程序的處理就必須在隊列中排隊等待。我們在構(gòu)造造spider時就采用該方式。使用非遞歸的方法時，給定spider程序一個要訪問的頁面，它會將其加入到要訪問的站點的隊列中去。當spider發(fā)現(xiàn)新的鏈接時，也會將它們加入到該隊列中。 spider程序會順序處理隊列中的每一個網(wǎng)頁。實際在spider程序中使用了四個隊列;在spider程序的構(gòu)造過程中，有兩種方法用于訪問隊列的管理。一種方法就是基于內(nèi)存的隊列管理。第二種方法就是基于sql的隊列管理?；趕ql的隊列和基于內(nèi)存的隊列都是有效的，在校園網(wǎng)

28、上做實驗的結(jié)果表明，在系統(tǒng)運行過程中間，如果 spider 的訪問任務隨著網(wǎng)頁數(shù)量增加，基于內(nèi)存的spider程序效率會下降。因而，選擇基于sql的隊列管理方案來構(gòu)造本spider程序。等待隊列: 在這個隊列中，url等待被spider程序處理。新發(fā)現(xiàn)的url被加入到該處理隊列:當spider開始處理url時，它們被傳送到這一隊列。當一個 url被處理后它被移送到錯誤隊列或完成隊列: 錯誤隊列: 如果下載某一頁面時出現(xiàn)錯誤，它的url將被加入該隊列。該隊列的url不會再移動到其他隊列。被列入該隊列的url將不再會被spider程序處理。完成隊列: 如果頁面的下載沒有出現(xiàn)任何錯誤，則該頁面將會被

29、加入完成隊列。加入該隊列的url不會再移動到其他隊列。同一時刻一個url只能在一個隊列中。其實通俗的講就是該url處于什么狀態(tài)，url 狀態(tài)的變化過程就是程序處理url的過程。下圖說明的一個url狀態(tài)的變化過程。 spider程序會遇到三種連接：內(nèi)部連接外部連接其他連接,一個示例spider類：java代碼 import java.awt.*; import .*; import java.io.*; import java.lang.*; import java.util.*; class node private object data; private node next; privat

30、e node prev; public node(object o) data = o; prev = next = null; public string tostring() if(next!=null)return data.tostring() + "n"+ next.tostring(); return data.tostring(); public node getnext()return next; public void setnext(node n)next = n; public node getprev()return prev; public voi

31、d setprev(node n)prev = n; public object getdata()return data; class linkedlist node head; node tail; public linkedlist() tail = head = null; public string tostring() if(head=null)return "empty list" return head.tostring(); public void insert(object o) if(tail=null) head = tail = new node(

32、o); else node nn = new node(o); tail.setnext(nn); tail=nn; public boolean contains(object o) for(node n = head;n!=null;n=n.getnext() if(o.equals(n.getdata()return true; return false; public object pop() if(head=null)return null; object ret = head.getdata(); head = head.getnext(); if(head=null)tail =

33、 null; return ret; public boolean isempty() return head=null; class list protected node tail; protected node ptr; private boolean stop; public list() ptr=tail=null; stop=false; public boolean isempty()return tail=null; public void reset() stop=false; ptr=tail; public string tostring() if(tail=null)r

34、eturn "empty list" string ret="" for(node n =tail.getnext();n!=tail;n=n.getnext()ret+=n.getdata().tostring()+"n"ret+=tail.getdata().tostring(); return ret; public object get() if(ptr=null)return null; ptr = ptr.getnext(); if(ptr=tail.getnext() if(stop)return null; stop=

35、true; return tail.getnext().getdata(); return ptr.getdata(); public void insert(object o, boolean attail) node nn = new node(o); if(tail=null) nn.setnext(nn); nn.setprev(nn); ptr=tail=nn; return; if(attail) tail.getnext().setprev(nn); nn.setnext(tail.getnext(); tail.setnext(nn); nn.setprev(tail); ta

36、il=nn; else nn.setnext(tail.getnext(); nn.setprev(tail); tail.setnext(nn); nn.getnext().setprev(nn); public void insert(object o) class stack extends list public stack()super(); public void insert(object o)insert(o, false); class queue extends list public queue()super(); public void insert(object o)

37、insert(o, true); public string peek() if(tail=null)return "" return tail.getnext().getdata().tostring(); public object pop() if(tail=null)return null; object ret = tail.getnext().getdata(); if(tail.getnext()=tail) tail=ptr=null; else if(tail.getnext()=ptr)ptr=ptr.getnext(); tail.setnext(ta

38、il.getnext().getnext(); return ret; class hashtable private vector table; private int size; public hashtable() size = 991; table = new vector(); for(int i=0;i<size;i+) table.add(new linkedlist(); public void insert(object o) int index = o.hashcode(); index = index % size; if(index<0)index+=siz

39、e; linkedlist ol = (linkedlist)table.get(index); ol.insert(o); public boolean contains(object o) int index = o.hashcode(); index = index % size; if(index<0)index+=size; return (linkedlist)(table.get(index).contains(o); public string tostring() string ret ="" for(int i=0;i<size;i+) if

40、(!(linkedlist)(table.get(i).isempty() ret+="n" ret+=table.get(i).tostring(); return ret; class spider implements runnable public queue todo; public stack done; public stack errors; public stack omittions; private hashtable allsites; private string last="" int maxsites; int visite

41、dsites; int timeout; string base; string badendings2 = "ps", "gz" string badendings3 = "pdf", "txt","zip", "jpg", "mpg", "gif","mov", "tut", "req", "abs","swf", "tex

42、", "dvi", "bin","exe", "rpm"string badendings4 = "jpeg", "mpeg" public spider(string starturl, int max, string b) timeout = 5000; base = b; allsites = new hashtable(); todo = new queue(); done = new stack(); errors = new stack(); omitt

43、ions = new stack(); try url u = new url(starturl); todo.insert(u); catch(exception e) system.out.println(e); errors.insert("bad starting url "+starturl+","+e.tostring(); maxsites = max; visitedsites = 0; /* * how many millisec to wait for each page */ public void settimer(int amo

44、unt) timeout = amount; /* * strips the '#' anchor off a url */ private url stripref(url u) try return new url(u.getprotocol(), u.gethost(), u.getport(),u.getfile(); catch(exception e)return u; /* * adds a url for future processing */ public void addsite(url toadd) if(null!=toadd.getref()toad

45、d = stripref(toadd); if(!allsites.contains(toadd) allsites.insert(toadd); if(!toadd.tostring().startswith(base) omittions.insert("foreign url: "+toadd.tostring(); return; if(!toadd.tostring().startswith("http") &&!toadd.tostring().startswith("http")omittions.ins

46、ert("ignoring url: "+toadd.tostring(); return; string s = toadd.getfile(); string last="" string comp=; if(s.charat(s.length()-3)='.') last = s.substring(s.length()-2); comp = badendings2; else if(s.charat(s.length()-4)='.') last = s.substring(s.length()-3); comp

47、= badendings3; else if(s.charat(s.length()-5)='.') last = s.substring(s.length()-4); comp = badendings4; for(int i=0;i<comp.length;i+) if(last.equalsignorecase(compi)/loop through all bad extensions omittions.insert("ignoring url:"+toadd.tostring(); return; todo.insert(toadd); /

48、* * true if there are pending urls and the maximum hasn't beenreached */ public boolean hasmore() return !todo.isempty() && visitedsites<maxsites; /* * returns the next site, works like enumeration, will return newvalues each time*/ private url getnextsite() last = todo.peek(); visite

49、dsites+; return (url)todo.pop(); /* * just to see what we are doing now. */ public string getcurrent() return last; /* * process the next site */ public void donextsite() url current = getnextsite(); if(current=null)return; try /system.err.println("processing #"+visitedsites+":"+

50、current); parse(current); done.insert(current); catch(exception e) errors.insert("bad site: "+current.tostring()+","+e.tostring(); public void run() while(hasmore()donextsite(); /* * to print out the internal data structures */ public string tostring()return getcompleted()+geterr

51、ors(); private string geterrors() if(errors.isempty()return "no errorsn" else return "errors:n"+errors.tostring()+"nend oferrorsn" private string getcompleted() return "completed sites:n"+done.tostring()+"nend of completedsitesn" /* * parses a web pa

52、ge at (site) and adds all the urls it sees */ private void parse(url site) throws exception string source=gettext(site); string title=gettitle(source); if(title.indexof("404")!=-1 | title.indexof("error")!=-1 | title.indexof("not found")!=-1) throw new exception ("

53、404, not found: "+site); int loc, beg; boolean haslt=false; boolean hassp=false; boolean hasf=false; boolean hasr=false; boolean hasa=false; boolean hasm=false; boolean hase=false; for(loc=0;loc<source.length();loc+) char c = source.charat(loc); if(!haslt) haslt = (c='<'); /search

54、 for "<a " else if(haslt && !hasa && !hasf) if(c='a' | c='a')hasa=true; else if(c='f' | c='f')hasf=true; else haslt=false; else if(haslt && hasa && !hasf &&!hassp) if(c=' ' | c='t' | c='n')ha

55、ssp=true; else haslt = hasa = false; /search for "<frame " else if(haslt && hasf && !hasa && !hasr) if(c='r' | c='r')hasr=true; else haslt = hasf = false; else if(haslt && hasf && hasr && !hasa) if(c='a' | c='a&

56、#39;)hasa=true; else haslt = hasf = hasr = false; else if(haslt && hasf && hasr && hasa&& !hasm) if(c='m' | c='m')hasm=true; else haslt = hasf = hasr = hasa = false; else if(haslt && hasf && hasr && hasa&& hasm &&

57、; !hase) if(c='e' | c='e')hase=true; else haslt = hasf = hasr = hasa = hasm = false; else if(haslt && hasf && hasr && hasa&& hasm && hase && !hassp) if(c=' ' | c='t' | c='n')hassp=true; else haslt = hasf = hasr =

58、 hasa = hasm = hase = false; /found "<frame " else if(haslt && hasf && hasr && hasa&& hasm && hase && hassp) haslt = hasf = hasr = hasa = hasm = hase = hassp = false; beg = loc; loc = source.indexof(">", loc); if(loc=-1) errors.insert("malformed frame at"+site.tostring(); loc = beg; else try parseframe(site, source.substring(beg, loc); catch(exception e) errors.insert("while parsing "+site.tostring()+",error parsing frame: "+e.tostring(); /found "<a " else if(hasl