網(wǎng)絡(luò)爬蟲的設(shè)計(jì)與實(shí)現(xiàn)畢業(yè)設(shè)計(jì)(論文)

畢業(yè)設(shè)計(jì)（論文）說明書題目：網(wǎng)絡(luò)爬蟲設(shè)計(jì)與實(shí)現(xiàn)畢業(yè)設(shè)計(jì)（論文）任務(wù)書題目：網(wǎng)絡(luò)爬蟲設(shè)計(jì)與實(shí)現(xiàn)

獨(dú)創(chuàng)聲明本人鄭重聲明：所呈交的畢業(yè)設(shè)計(jì)(論文)，是本人在指導(dǎo)老師的指導(dǎo)下，獨(dú)立進(jìn)行研究工作所取得的成果，成果不存在知識(shí)產(chǎn)權(quán)爭(zhēng)議。盡我所知，除文中已經(jīng)注明引用的內(nèi)容外，本設(shè)計(jì)（論文）不含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫過的作品成果。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體均已在文中以明確方式標(biāo)明。本聲明的法律后果由本人承擔(dān)。

作者簽名:二〇一〇年九月二十日

畢業(yè)設(shè)計(jì)（論文）使用授權(quán)聲明本人完全了解濱州學(xué)院關(guān)于收集、保存、使用畢業(yè)設(shè)計(jì)（論文）的規(guī)定。本人愿意按照學(xué)校要求提交學(xué)位論文的印刷本和電子版，同意學(xué)校保存學(xué)位論文的印刷本和電子版，或采用影印、數(shù)字化或其它復(fù)制手段保存設(shè)計(jì)（論文）；同意學(xué)校在不以營(yíng)利為目的的前提下，建立目錄檢索與閱覽服務(wù)系統(tǒng)，公布設(shè)計(jì)（論文）的部分或全部?jī)?nèi)容，允許他人依法合理使用。（保密論文在解密后遵守此規(guī)定）

作者簽名:二〇一〇年九月二十日原始依據(jù)（包括設(shè)計(jì)或論文的工作基礎(chǔ)、研究條件、應(yīng)用環(huán)境、工作目的等。）互聯(lián)網(wǎng)是一個(gè)龐大的非結(jié)構(gòu)化的數(shù)據(jù)庫(kù)，將數(shù)據(jù)有效的檢索并組織呈現(xiàn)出來有著巨大的應(yīng)用前景。搜索引擎作為一個(gè)輔助人們檢索信息的工具成為用戶訪問萬維網(wǎng)的入口和指南。但是，這些通用性搜索引擎也存在著一定的局限性。不同領(lǐng)域、不同背景的用戶往往具有不同的檢索目的和需求，通用搜索引擎所返回的結(jié)果包含大量用戶不關(guān)心的網(wǎng)頁(yè)。所以需要一個(gè)能基于主題搜索的滿足特定需求的網(wǎng)絡(luò)爬蟲。為了解決上述問題，參照成功的網(wǎng)絡(luò)爬蟲模式，對(duì)網(wǎng)絡(luò)爬蟲進(jìn)行研究，從而能夠?yàn)榫W(wǎng)絡(luò)爬蟲實(shí)現(xiàn)更深入的主題相關(guān)性，提供滿足特定搜索需求的網(wǎng)絡(luò)爬蟲。參考文獻(xiàn)[1]Winter．中文搜索引擎技術(shù)解密：網(wǎng)絡(luò)蜘蛛[M]．北京：人民郵電出版社，2004年．[2]Sergey等．TheAnatomyofaLarge-ScaleHypertextualWebSearchEngine[M]．北京：清華大學(xué)出版社，1998年．[3]Wisenut．WiseNutSearchEnginewhitepaper[M]．北京：中國(guó)電力出版社，2001年．[4]GaryR.WrightW.RichardStevens．TCP-IP協(xié)議詳解卷3：TCP事務(wù)協(xié)議，HTTP，NNTP和UNIX域協(xié)議[M]．北京：機(jī)械工業(yè)出版社，2002年1月.[5]羅剛王振東．自己動(dòng)手寫網(wǎng)絡(luò)爬蟲[M]．北京：清華大學(xué)出版社，2010年10月.[6]李曉明，閆宏飛，王繼民．搜索引擎：原理、技術(shù)與系統(tǒng)——華夏英才基金學(xué)術(shù)文庫(kù)[M]．北京：科學(xué)出版社，2005年04月.設(shè)計(jì)（研究）內(nèi)容和要求（包括設(shè)計(jì)或研究?jī)?nèi)容、主要指標(biāo)與技術(shù)參數(shù)，并根據(jù)課題性質(zhì)對(duì)學(xué)生提出具體要求。）本課題的主要目的是設(shè)計(jì)面向主題的網(wǎng)絡(luò)爬蟲程序，同時(shí)需要滿足的是具有一定的性能，要考慮到網(wǎng)絡(luò)爬蟲的各種需求。網(wǎng)絡(luò)爬蟲應(yīng)用寬度搜索技術(shù)。對(duì)url進(jìn)行分析，去重。網(wǎng)絡(luò)爬蟲使用多線程技術(shù)，讓爬蟲具備更強(qiáng)大的抓取能力。網(wǎng)絡(luò)爬蟲要實(shí)現(xiàn)對(duì)特定主題的爬取。網(wǎng)絡(luò)爬蟲還要完成信息提取任務(wù)，對(duì)于抓取回來的網(wǎng)頁(yè)提取出來:新聞、電子圖書、行業(yè)信息等。對(duì)網(wǎng)絡(luò)爬蟲的連接網(wǎng)絡(luò)設(shè)置連接及讀取時(shí)間，避免無限制的等待。研究網(wǎng)絡(luò)爬蟲的原理并實(shí)現(xiàn)爬蟲的相關(guān)功能。最終實(shí)現(xiàn)的網(wǎng)絡(luò)爬蟲應(yīng)該能根據(jù)設(shè)定的主題，從設(shè)定的url進(jìn)行一定深度的搜索，并最終得到需要的數(shù)據(jù)。指導(dǎo)教師（簽字）年月日審題小組組長(zhǎng)（簽字）年月日天津大學(xué)本科生畢業(yè)設(shè)計(jì)（論文）開題報(bào)告課題名稱網(wǎng)絡(luò)爬蟲設(shè)計(jì)與實(shí)現(xiàn)學(xué)院名稱軟件學(xué)院專業(yè)名稱軟件工程學(xué)生姓名張鳳龍指導(dǎo)教師陳錦言（內(nèi)容包括：課題的來源及意義，國(guó)內(nèi)外發(fā)展?fàn)顩r，本課題的研究目標(biāo)、研究?jī)?nèi)容、研究方法、研究手段和進(jìn)度安排，實(shí)驗(yàn)方案的可行性分析和已具備的實(shí)驗(yàn)條件以及主要參考文獻(xiàn)等。）課題的來源及意義互聯(lián)網(wǎng)是一個(gè)龐大的非結(jié)構(gòu)化的數(shù)據(jù)庫(kù)，將數(shù)據(jù)有效的檢索并組織呈現(xiàn)出來有著巨大的應(yīng)用前景。搜索引擎作為一個(gè)輔助人們檢索信息的工具成為用戶訪問萬維網(wǎng)的入口和指南。但是，這些通用性搜索引擎也存在著一定的局限性。不同領(lǐng)域、不同背景的用戶往往具有不同的檢索目的和需求，通用搜索引擎所返回的結(jié)果包含大量用戶不關(guān)心的網(wǎng)頁(yè)。為了解決這個(gè)問題，一個(gè)靈活的爬蟲有著無可替代的重要意義。國(guó)內(nèi)外發(fā)展?fàn)顩r對(duì)于網(wǎng)絡(luò)爬蟲的研究從上世紀(jì)九十年代就開始了，目前爬蟲技術(shù)已經(jīng)趨見成熟，網(wǎng)絡(luò)爬蟲是搜索引擎的重要組成部分。網(wǎng)絡(luò)上比較著名的開源爬蟲包括Nutch，Larbin，Heritrix。網(wǎng)絡(luò)爬蟲最重要的是網(wǎng)頁(yè)搜索策略（廣度優(yōu)先和最佳度優(yōu)先）和網(wǎng)頁(yè)分析策略（基于網(wǎng)絡(luò)拓?fù)涞姆治鏊惴ê突诰W(wǎng)頁(yè)內(nèi)容的網(wǎng)頁(yè)分析算法）。研究目標(biāo)本論文主要研究搜索引擎的搜索器（網(wǎng)絡(luò)爬蟲程序）的設(shè)計(jì)與實(shí)現(xiàn),實(shí)現(xiàn)簡(jiǎn)單的可在后臺(tái)自動(dòng)運(yùn)行的爬蟲程序?？梢远嗑€程進(jìn)行抓取?？梢赃M(jìn)行面向主題的抓取。四．研究?jī)?nèi)容本課題研究的內(nèi)容是如何使網(wǎng)絡(luò)爬蟲靈活高效。如何具備更強(qiáng)的抓取能力。如何分辨重復(fù)的網(wǎng)頁(yè)內(nèi)容。如何確定主題相關(guān)性。對(duì)于網(wǎng)絡(luò)時(shí)延等的處理。五．研究方法網(wǎng)絡(luò)爬蟲應(yīng)用寬度搜索技術(shù)。對(duì)url進(jìn)行分析，去重。網(wǎng)絡(luò)爬蟲使用多線程技術(shù)，讓爬蟲具備更強(qiáng)大的抓取能力。網(wǎng)絡(luò)爬蟲還要完成信息提取任務(wù)，對(duì)于抓取回來的網(wǎng)頁(yè)提取出來新聞等信息。對(duì)網(wǎng)絡(luò)爬蟲的連接網(wǎng)絡(luò)設(shè)置連接及讀取時(shí)間，避免無限制的等待。研究網(wǎng)絡(luò)爬蟲的原理并實(shí)現(xiàn)爬蟲的相關(guān)功能。研究手段參考網(wǎng)上開源的網(wǎng)絡(luò)爬蟲和各種網(wǎng)絡(luò)爬蟲相關(guān)的書籍，在windows系統(tǒng)環(huán)境下開發(fā)。本課題進(jìn)度安排：2010.12.20—2011.03.10查閱資料完成任務(wù)書，完成開題報(bào)告2011.03.11—2011.03.12開題報(bào)告會(huì)2011.03.13—2011.04.24查閱資料，進(jìn)行論文基本章節(jié)的寫作，完成初稿，并完成進(jìn)行代碼編寫2011.04.25—2011.04.30畢業(yè)設(shè)計(jì)中期報(bào)告會(huì)2011.05.01—2011.05.22系統(tǒng)設(shè)計(jì)結(jié)束并再次檢查系統(tǒng)的可靠性。2011.05.23—2011.06.22完成論文及答辯本課題可行性分析網(wǎng)絡(luò)爬蟲目前已經(jīng)比較普遍，國(guó)內(nèi)外有眾多對(duì)網(wǎng)絡(luò)爬蟲的研究成果，大部分的技術(shù)難題已經(jīng)有解決方案。所以本課題的可行性較高。實(shí)驗(yàn)條件Windows操作系統(tǒng)；互聯(lián)網(wǎng)主要參考文獻(xiàn)[1]Winter．中文搜索引擎技術(shù)解密：網(wǎng)絡(luò)蜘蛛[M]．北京：人民郵電出版社，2004年．[2]Sergey等．TheAnatomyofaLarge-ScaleHypertextualWebSearchEngine[M]．北京：清華大學(xué)出版社，1998年．[3]Wisenut．WiseNutSearchEnginewhitepaper[M]．北京：中國(guó)電力出版社，2001年．[4]GaryR.WrightW.RichardStevens．TCP-IP協(xié)議詳解卷3：TCP事務(wù)協(xié)議，HTTP，NNTP和UNIX域協(xié)議[M]．北京：機(jī)械工業(yè)出版社，2002年1月.[5]羅剛王振東．自己動(dòng)手寫網(wǎng)絡(luò)爬蟲[M]．北京：清華大學(xué)出版社，2010年10月.[6]李曉明，閆宏飛，王繼民．搜索引擎：原理、技術(shù)與系統(tǒng)——華夏英才基金學(xué)術(shù)文庫(kù)[M]．北京：科學(xué)出版社，2005年04月.選題是否合適：是□否□課題能否實(shí)現(xiàn)：能□不能□指導(dǎo)教師（簽字）年月日選題是否合適：是□否□課題能否實(shí)現(xiàn)：能□不能□審題小組組長(zhǎng)（簽字）年月日摘要本課題的主要目的是設(shè)計(jì)面向主題的網(wǎng)絡(luò)爬蟲程序，同時(shí)需要滿足的是具有一定的性能，考慮到網(wǎng)絡(luò)爬蟲的各種需求。網(wǎng)絡(luò)爬蟲應(yīng)用寬度搜索技術(shù)。對(duì)url進(jìn)行分析，去重。網(wǎng)絡(luò)爬蟲使用多線程技術(shù)，讓爬蟲具備更強(qiáng)大的抓取能力。對(duì)網(wǎng)絡(luò)爬蟲的連接網(wǎng)絡(luò)設(shè)置連接及讀取時(shí)間，避免無限制的等待。為了適應(yīng)不同需求，使網(wǎng)絡(luò)爬蟲可以根據(jù)預(yù)先設(shè)定的主題實(shí)現(xiàn)對(duì)特定主題的爬取。研究網(wǎng)絡(luò)爬蟲的原理并實(shí)現(xiàn)爬蟲的相關(guān)功能。關(guān)鍵詞：網(wǎng)絡(luò)爬蟲；面向主題；多線程

ABSTRACTThemainpurposeofthisprojectistodesignsubject-orientedwebcrawlerprocesswhichisalsorequiredtomeetcertainperformance,takingintoaccountthediverseneedsofwebcrawlers.

WebCrawlerusesthetechnology.ofBreadth-firstsearch.Webcrawlerusesmulti-threadedtechnology,sothatspiderscrawlcanhavemorepowerfulcapabilities.SetconnectiontimeandreadtimeofthewebconnectionoftheWebcrawler,toavoidunlimitedwaiting.Inordertomeetdifferentneeds,sothatcrawlerscanachievepre-setthemecrawlingaspecifictopic.Researchtheprinciplewebcrawlerandandrealizetherelatedfunctions.Keywords：Webcrawler;subject-oriented;multi-threading天津大學(xué)2007屆本科生畢業(yè)設(shè)計(jì)（論文）目錄TOC\o"1-3"\h\u11746第一章概述 152981.1課題背景 125861.2網(wǎng)絡(luò)爬蟲的歷史和分類 2178681.2.1網(wǎng)絡(luò)爬蟲的歷史 2129701.2.2網(wǎng)絡(luò)爬蟲的分類 3289621.3網(wǎng)絡(luò)爬蟲的發(fā)展趨勢(shì) 414258第二章相關(guān)技術(shù)背景 6272722.1網(wǎng)絡(luò)爬蟲的定義 6228172.2網(wǎng)頁(yè)搜索策略介紹 6266132.2.1廣度優(yōu)先搜索策略 671172.2.2最佳優(yōu)先搜索策略 7201512.3判斷相關(guān)度算法 715448第三章網(wǎng)絡(luò)爬蟲模型的分析和概要設(shè)計(jì) 9192753.1網(wǎng)絡(luò)爬蟲的模型分析 956643.2網(wǎng)絡(luò)爬蟲的搜索策略 943593.3網(wǎng)絡(luò)爬蟲的主題相關(guān)度判斷 1017413.4網(wǎng)絡(luò)爬蟲的概要設(shè)計(jì) 1218421第四章網(wǎng)絡(luò)爬蟲模型的設(shè)計(jì)和實(shí)現(xiàn) 15233594.1網(wǎng)絡(luò)爬蟲總體設(shè)計(jì) 1588424.2網(wǎng)絡(luò)爬蟲具體設(shè)計(jì) 15309464.2.1爬取網(wǎng)頁(yè) 1587384.2.2分析網(wǎng)頁(yè) 16201504.2.3判斷相關(guān)度 1721614.2.4保存網(wǎng)頁(yè)信息 18131984.2.5數(shù)據(jù)庫(kù)設(shè)計(jì)和存儲(chǔ) 1895314.2.6多線程的實(shí)現(xiàn) 18172374.2.7附加功能 19274154.2.8整體流程 196995第五章測(cè)試 2119211第六章總結(jié)和展望 24天津大學(xué)2007屆本科生畢業(yè)設(shè)計(jì)（論文）PAGE56第一章概述1.1課題背景網(wǎng)絡(luò)爬蟲，是一種按照一定的規(guī)則，自動(dòng)的抓取萬維網(wǎng)信息的程序或者腳本。另外一些不常使用的名字還有螞蟻，自動(dòng)索引，模擬程序或者蠕蟲。網(wǎng)絡(luò)檢索功能起于互聯(lián)網(wǎng)內(nèi)容爆炸性發(fā)展所帶來的對(duì)內(nèi)容檢索的需求。搜索引擎不斷的發(fā)展,人們的需求也在不斷的提高,網(wǎng)絡(luò)信息搜索已經(jīng)成為人們每天都要進(jìn)行的內(nèi)容.如何使搜索引擎能時(shí)刻滿足人們的需求。最初的檢索功能通過索引站的方式實(shí)現(xiàn)，而有了網(wǎng)絡(luò)機(jī)器人，即網(wǎng)絡(luò)爬蟲這個(gè)技術(shù)之后，搜索引擎的時(shí)代便開始一發(fā)不可收拾了。1.2網(wǎng)絡(luò)爬蟲的歷史和分類1.2.1網(wǎng)絡(luò)爬蟲的歷史在互聯(lián)網(wǎng)發(fā)展初期，網(wǎng)站相對(duì)較少，信息查找比較容易。然而伴隨互聯(lián)網(wǎng)爆炸性的發(fā)展，普通網(wǎng)絡(luò)用戶想找到所需的資料簡(jiǎn)直如同大海撈針，這時(shí)為滿足大眾信息檢索需求的專業(yè)搜索網(wǎng)站便應(yīng)運(yùn)而生了?，F(xiàn)代意義上的搜索引擎的祖先，是1990年由蒙特利爾大學(xué)學(xué)生AlanEmtage發(fā)明的Archie。雖然當(dāng)時(shí)WorldWideWeb還未出現(xiàn)，但網(wǎng)絡(luò)中文件傳輸還是相當(dāng)頻繁的，而且由于大量的文件散布在各個(gè)分散的FTP主機(jī)中，查詢起來非常不便，因此AlanArchie工作原理與現(xiàn)在的搜索引擎已經(jīng)很接近，它依靠腳本程序自動(dòng)搜索網(wǎng)上的文件，然后對(duì)有關(guān)信息進(jìn)行索引，供使用者以一定的表達(dá)式查詢。由于Archie深受用戶歡迎，受其啟發(fā)，美國(guó)內(nèi)華達(dá)SystemComputingServices大學(xué)于1993年開發(fā)了另一個(gè)與之非常相似的搜索工具，不過此時(shí)的搜索工具除了索引文件外，已能檢索網(wǎng)頁(yè)。當(dāng)時(shí)，“機(jī)器人”一詞在編程者中十分流行。電腦“機(jī)器人”（ComputerRobot）是指某個(gè)能以人類無法達(dá)到的速度不間斷地執(zhí)行某項(xiàng)任務(wù)的軟件程序。由于專門用于檢索信息的“機(jī)器人”程序象蜘蛛一樣在網(wǎng)絡(luò)間爬來爬去，因此，搜索引擎的“機(jī)器人”程序就被稱為“蜘蛛”程序。世界上第一個(gè)用于監(jiān)測(cè)互聯(lián)網(wǎng)發(fā)展規(guī)模的“機(jī)器人”程序是MatthewGray開發(fā)的WorldwideWebWanderer。剛開始它只用來統(tǒng)計(jì)互聯(lián)網(wǎng)上的服務(wù)器數(shù)量，后來則發(fā)展為能夠檢索網(wǎng)站域名。與Wanderer相對(duì)應(yīng)，MartinKoster于1993年10月創(chuàng)建了ALIWEB，它是Archie的HTTP版本。ALIWEB不使用“機(jī)器人”程序，而是靠網(wǎng)站主動(dòng)提交信息來建立自己的鏈接索引，類似于現(xiàn)在我們熟知的Yahoo。隨著互聯(lián)網(wǎng)的迅速發(fā)展，使得檢索所有新出現(xiàn)的網(wǎng)頁(yè)變得越來越困難，因此，在MatthewGray的Wanderer基礎(chǔ)上，一些編程者將傳統(tǒng)的“蜘蛛”程序工作原理作了些改進(jìn)。其設(shè)想是，既然所有網(wǎng)頁(yè)都可能有連向其他網(wǎng)站的鏈接，那么從跟蹤一個(gè)網(wǎng)站的鏈接開始，就有可能檢索整個(gè)互聯(lián)網(wǎng)。到1993年底，一些基于此原理的搜索引擎開始紛紛涌現(xiàn)，其中以JumpStation、TheWorldWideWebWorm（Goto的前身，也就是今天Overture），和Repository-BasedSoftwareEngineering(RBSE)spider最負(fù)盛名。然而JumpStation和WWWWorm只是以搜索工具在數(shù)據(jù)庫(kù)中找到匹配信息的先后次序排列搜索結(jié)果，因此毫無信息關(guān)聯(lián)度可言。而RBSE是第一個(gè)在搜索結(jié)果排列中引入關(guān)鍵字串匹配程度概念的引擎最早現(xiàn)代意義上的搜索引擎出現(xiàn)于1994年7月。當(dāng)時(shí)MichaelMauldin將JohnLeavitt的蜘蛛程序接入到其索引程序中，創(chuàng)建了大家現(xiàn)在熟知的Lycos。同年4月，斯坦福（Stanford）大學(xué)的兩名博士生，DavidFilo和美籍華人楊致遠(yuǎn)（GerryYang）共同創(chuàng)辦了超級(jí)目錄索引Yahoo，并成功地使搜索引擎的概念深入人心。從此搜索引擎進(jìn)入了高速發(fā)展時(shí)期。目前，互聯(lián)網(wǎng)上有名有姓的搜索引擎已達(dá)數(shù)百家，其檢索的信息量也與從前不可同日而語(yǔ)。比如最近風(fēng)頭正勁的Google，其數(shù)據(jù)庫(kù)中存放的網(wǎng)頁(yè)已達(dá)30億之巨。隨著互聯(lián)網(wǎng)規(guī)模的急劇膨脹，一家搜索引擎光靠自己?jiǎn)未颡?dú)斗已無法適應(yīng)目前的市場(chǎng)狀況，因此現(xiàn)在搜索引擎之間開始出現(xiàn)了分工協(xié)作，并有了專業(yè)的搜索引擎技術(shù)和搜索數(shù)據(jù)庫(kù)服務(wù)提供商。象國(guó)外的Inktomi，它本身并不是直接面向用戶的搜索引擎，但向包括Overture（原GoTo）、LookSmart、MSN、HotBot等在內(nèi)的其他搜索引擎提供全文網(wǎng)頁(yè)搜索服務(wù)。國(guó)內(nèi)的百度也屬于這一類（注），搜狐和新浪用的就是它的技術(shù)。因此從這個(gè)意義上說，它們是搜索引擎的搜索引擎。1.2.2網(wǎng)絡(luò)爬蟲的分類網(wǎng)絡(luò)爬蟲種類繁多，如果按照部署在哪里分，可以分成：

1，服務(wù)器側(cè)：一般是一個(gè)多線程程序，同時(shí)下載多個(gè)目標(biāo)HTML，可以用PHP，Java,Python等做，一般綜合搜索引擎的爬蟲這樣做。但是，如果對(duì)方討厭爬蟲，很可能封掉服務(wù)器的IP，服務(wù)器IP又不容易改，另外耗用的帶寬也是較貴。2，客戶端：很適合部署定題爬蟲，或者叫聚焦爬蟲。做一個(gè)與Google，百度等競(jìng)爭(zhēng)的綜合搜索引擎成功的機(jī)會(huì)微乎其微，而垂直搜訴或者比價(jià)服務(wù)或者推薦引擎，機(jī)會(huì)要多得多，這類爬蟲不是什么頁(yè)面都取的，而是只取關(guān)心的頁(yè)面，而且只取頁(yè)面上關(guān)心的內(nèi)容，例如提取黃頁(yè)信息，商品價(jià)格信息，還有提取競(jìng)爭(zhēng)對(duì)手廣告信息的。這類爬蟲可以部署很多，而且可以很有侵略性?？梢缘统杀敬罅坎渴穑捎诳蛻舳薎P地址是動(dòng)態(tài)的，所以很難被目標(biāo)網(wǎng)站封鎖。1.3網(wǎng)絡(luò)爬蟲的發(fā)展趨勢(shì)目前，大多數(shù)的搜索引擎都是基于關(guān)鍵詞的搜索引擎?；陉P(guān)鍵字匹配的搜索技術(shù)有較大的局限性：首先，它不能區(qū)分同形異義。其次，不能聯(lián)想到關(guān)鍵字的同義詞。Web商業(yè)化至今，搜索引擎始終保持著網(wǎng)絡(luò)上被使用最多的服務(wù)項(xiàng)目的地位，然而，隨著網(wǎng)上內(nèi)容的爆炸式增長(zhǎng)和內(nèi)容形式花樣的不斷翻新，搜索引擎越來越不能滿足挑剔的網(wǎng)民們的各種信息需求。搜索引擎的發(fā)展面臨著兩大難題：一是如何跟上Internet的發(fā)展速度，二是如何為用戶提供更精確的查詢結(jié)果。所以，傳統(tǒng)的引擎不能適應(yīng)信息技術(shù)的高速發(fā)展，新一代智能搜索引擎作為一種高效搜索引擎技術(shù)的在當(dāng)今的網(wǎng)絡(luò)信息時(shí)代日益引起業(yè)界人士的關(guān)注。搜索引擎己成為一個(gè)新的研究、開發(fā)領(lǐng)域。因?yàn)樗玫叫畔z索、人工智能、計(jì)算機(jī)網(wǎng)絡(luò)、分布式處理、數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘、數(shù)字圖書館、自然語(yǔ)言處理等多領(lǐng)域的理論和技術(shù)，所以具有綜合性和挑戰(zhàn)性。又由于搜索引擎有大量的用戶，有很好的經(jīng)濟(jì)價(jià)值，所以引起了世界各國(guó)計(jì)算機(jī)科學(xué)界和信息產(chǎn)業(yè)界的高度關(guān)注，目前的研究、開發(fā)十分活躍，并出現(xiàn)了很多值得注意的動(dòng)向。目前傳統(tǒng)搜索引擎下，百度、谷歌等大廠商壟斷了網(wǎng)絡(luò)索引市場(chǎng)，因?yàn)樗鼈兊拇嬖冢找纨嫶蟮幕ヂ?lián)網(wǎng)內(nèi)容才能突破網(wǎng)絡(luò)黑暗狀態(tài)，變成可知的一個(gè)世界。然而，傳統(tǒng)搜索引擎并不能支持定制搜索和信息處理、挖掘，只能以WEB1.0的形式存在?？梢灶A(yù)見將來互聯(lián)網(wǎng)信息抓取、挖掘和再處理，將成為人們?cè)絹碓蕉嗟男枨?，而滿足這種需求的，就是各種各樣的爬蟲與相關(guān)的信息處理工具?，F(xiàn)在網(wǎng)絡(luò)上流行的信息采集工具、網(wǎng)站聚合工具，都是未來新一代爬蟲的先驅(qū)，甚至已經(jīng)具備其特點(diǎn)。但是互聯(lián)網(wǎng)本身，不管1.0還是2.0，還沒有為爬蟲時(shí)代的到來做好充分準(zhǔn)備?，F(xiàn)在游行的SEO，就是強(qiáng)勢(shì)搜索引擎條件下對(duì)網(wǎng)站結(jié)構(gòu)產(chǎn)生的影響。爬蟲時(shí)代到來之后，互聯(lián)網(wǎng)上會(huì)出現(xiàn)專門的信息站點(diǎn)，就是提供給爬蟲看的站點(diǎn)。傳統(tǒng)的網(wǎng)絡(luò)爬蟲技術(shù)主要應(yīng)用于抓取靜態(tài)Web網(wǎng)頁(yè)，隨著AJAX/Web2.0的流行，如何抓取AJAX等動(dòng)態(tài)頁(yè)面成了搜索引擎急需解決的問題，因?yàn)锳JAX顛覆了傳統(tǒng)的純HTTP請(qǐng)求/響應(yīng)協(xié)議機(jī)制，如果搜索引擎依舊采用“爬”的機(jī)制，是無法抓取到AJAX頁(yè)面的有效數(shù)據(jù)的。AJAX采用了JavaScript驅(qū)動(dòng)的異步請(qǐng)求/響應(yīng)機(jī)制，以往的爬蟲們?nèi)狈avaScript語(yǔ)義上的理解，基本上無法模擬觸發(fā)JavaScript的異步調(diào)用并解析返回的異步回調(diào)邏輯和內(nèi)容。另外，在AJAX的應(yīng)用中，JavaScript會(huì)對(duì)DOM結(jié)構(gòu)進(jìn)行大量變動(dòng)，甚至頁(yè)面所有內(nèi)容都通過JavaScript直接從服務(wù)器端讀取并動(dòng)態(tài)繪制出來。這對(duì)習(xí)慣了DOM結(jié)構(gòu)相對(duì)不變的靜態(tài)頁(yè)面簡(jiǎn)直是無法理解的。由此可以看出，以往的爬蟲是基于協(xié)議驅(qū)動(dòng)的，而對(duì)于AJAX這樣的技術(shù)，所需要的爬蟲引擎必須是基于事件驅(qū)動(dòng)的。

第二章相關(guān)技術(shù)背景2.1網(wǎng)絡(luò)爬蟲的定義定義1：網(wǎng)絡(luò)爬蟲是一個(gè)自動(dòng)提取網(wǎng)頁(yè)的程序，它為搜索引擎從Web上下載網(wǎng)頁(yè)，是搜索引擎的重要組成部分。通用網(wǎng)絡(luò)爬蟲從一個(gè)或若干初始網(wǎng)頁(yè)的URL開始，獲得初始網(wǎng)頁(yè)上的URL列表；在抓取網(wǎng)頁(yè)的過程中，不斷從當(dāng)前頁(yè)面上抽取新的URL放入待爬行隊(duì)列，直到滿足系統(tǒng)的停止條件。

定義2：主題網(wǎng)絡(luò)爬蟲就是根據(jù)一定的網(wǎng)頁(yè)分析算法過濾與主題無關(guān)的鏈接，保留主題相關(guān)的鏈接并將其放入待抓取的URL隊(duì)列中；然后根據(jù)一定的搜索策略從隊(duì)列中選擇下一步要抓取的網(wǎng)頁(yè)URL，并重復(fù)上述過程，直到達(dá)到系統(tǒng)的某一條件時(shí)停止。所有被網(wǎng)絡(luò)爬蟲抓取的網(wǎng)頁(yè)將會(huì)被系統(tǒng)存儲(chǔ)，進(jìn)行一定的分析、過濾，并建立索引，對(duì)于主題網(wǎng)絡(luò)爬蟲來說，這一過程所得到的分析結(jié)果還可能對(duì)后續(xù)的抓取過程進(jìn)行反饋和指導(dǎo)。

定義3：如果網(wǎng)頁(yè)p中包含超鏈接l，則p稱為鏈接l的父網(wǎng)頁(yè)。

定義4：如果超鏈接l指向網(wǎng)頁(yè)t，則網(wǎng)頁(yè)t稱為子網(wǎng)頁(yè)，又稱為目標(biāo)網(wǎng)頁(yè)。主題網(wǎng)絡(luò)爬蟲的基本思路就是按照事先給出的主題，分超鏈接和已經(jīng)下載的網(wǎng)頁(yè)內(nèi)容，預(yù)測(cè)下一個(gè)待抓取的URL及當(dāng)前網(wǎng)頁(yè)的主題相關(guān)度，保證盡可能多地爬行、下載與主相關(guān)的網(wǎng)頁(yè)，盡可能少地下載無關(guān)網(wǎng)頁(yè)。2.2網(wǎng)頁(yè)搜索策略介紹網(wǎng)頁(yè)的抓取策略可以分為深度優(yōu)先、廣度優(yōu)先和最佳優(yōu)先三種。深度優(yōu)先在很多情況下會(huì)導(dǎo)致爬蟲的陷入(trapped)問題，目前常見的是廣度優(yōu)先和最佳優(yōu)先方法。2.2.1廣度優(yōu)先搜索策略廣度優(yōu)先搜索策略是指在抓取過程中，在完成當(dāng)前層次的搜索后，才進(jìn)行下一層次的搜索。該算法的設(shè)計(jì)和實(shí)現(xiàn)相對(duì)簡(jiǎn)單。在目前為覆蓋盡可能多的網(wǎng)頁(yè)，一般使用廣度優(yōu)先搜索方法。也有很多研究將廣度優(yōu)先搜索策略應(yīng)用于聚焦爬蟲中。其基本思想是認(rèn)為與初始URL在一定鏈接距離內(nèi)的網(wǎng)頁(yè)具有主題相關(guān)性的概率很大。另外一種方法是將廣度優(yōu)先搜索與網(wǎng)頁(yè)過濾技術(shù)結(jié)合使用，先用廣度優(yōu)先策略抓取網(wǎng)頁(yè)，再將其中無關(guān)的網(wǎng)頁(yè)過濾掉。這些方法的缺點(diǎn)在于，隨著抓取網(wǎng)頁(yè)的增多，大量的無關(guān)網(wǎng)頁(yè)將被下載并過濾，算法的效率將變低。2.2.2最佳優(yōu)先搜索策略最佳優(yōu)先搜索策略按照一定的網(wǎng)頁(yè)分析算法，預(yù)測(cè)候選URL與目標(biāo)網(wǎng)頁(yè)的相似度，或與主題的相關(guān)性，并選取評(píng)價(jià)最好的一個(gè)或幾個(gè)URL進(jìn)行抓取。它只訪問經(jīng)過網(wǎng)頁(yè)分析算法預(yù)測(cè)為“有用”的網(wǎng)頁(yè)。存在的一個(gè)問題是，在爬蟲抓取路徑上的很多相關(guān)網(wǎng)頁(yè)可能被忽略，因?yàn)樽罴褍?yōu)先策略是一種局部最優(yōu)搜索算法。因此需要將最佳優(yōu)先結(jié)合具體的應(yīng)用進(jìn)行改進(jìn)，以跳出局部最優(yōu)點(diǎn)。將在第4節(jié)中結(jié)合網(wǎng)頁(yè)分析算法作具體的討論。研究表明，這樣的閉環(huán)調(diào)整可以將無關(guān)網(wǎng)頁(yè)數(shù)量降低30%~90%。2.3判斷相關(guān)度算法主題爬蟲的系統(tǒng)組成最初考慮是對(duì)頁(yè)面的過濾，不像普通爬蟲對(duì)所有頁(yè)面的鏈接進(jìn)行處理，先對(duì)頁(yè)面與受限領(lǐng)域的主題相關(guān)度進(jìn)行分析，只有當(dāng)其主題相關(guān)度符合要求時(shí)才處理該頁(yè)面中的鏈接，因?yàn)槿绻擁?yè)面和本領(lǐng)域比較相關(guān)，它所包含的鏈接和領(lǐng)域相關(guān)的幾率也較大，這樣提高了爬行精度，雖然會(huì)遺漏少數(shù)頁(yè)面，但綜合效果是令人滿意的。因此，主題相關(guān)度的分析是主題爬蟲設(shè)計(jì)的關(guān)鍵。（一）主題相關(guān)度計(jì)算模型

垂直搜索引擎與通用搜索引擎最大的區(qū)別在于垂直搜索引擎是面向某個(gè)領(lǐng)域的，因而垂直搜索引擎的網(wǎng)絡(luò)蜘蛛只采集與主題相關(guān)的網(wǎng)頁(yè)，與主題無關(guān)的網(wǎng)頁(yè)將被丟棄，將此類網(wǎng)絡(luò)蜘蛛稱為主題蜘蛛[6-8]。主題蜘蛛將網(wǎng)頁(yè)下載到本地后，需要使用基于內(nèi)容的主題判別方法計(jì)算該網(wǎng)頁(yè)的主題相關(guān)度值，主題相關(guān)度低于某一閾值的網(wǎng)頁(yè)被丟棄。主題相關(guān)度的計(jì)算方法有布爾模型和向量空間模型兩種模型算法[10]。

1.布爾模型。在主題判別時(shí)，布爾模型是很容易實(shí)現(xiàn)的。在布爾模型[9]中，一個(gè)文檔通過一個(gè)關(guān)鍵詞集合來表示。同時(shí)，某個(gè)主題也以關(guān)鍵詞集合的形式來表示。在判斷文檔與某主題的相關(guān)度的過程中，相當(dāng)于是計(jì)算兩個(gè)關(guān)鍵詞集合的交集。對(duì)基于布爾模型的主題判別模型來說，交集中含有的元素越多，則認(rèn)為與主題的相關(guān)度就越高。2.空間向量模型。向量空間模型[11]（VectorSpaceModel）由Salton等人于20世紀(jì)60年代末提出，是一種簡(jiǎn)便、高效的文本表示模型，其理論基礎(chǔ)是代數(shù)學(xué)。與布爾模型不同，向量空間模型把用戶的查詢要求和數(shù)據(jù)庫(kù)文檔信息表示成由檢索項(xiàng)構(gòu)成的向量空間中的點(diǎn)（向量），而通過計(jì)算向量之間的距離來判定文檔和查詢之間的相似程度（例如，用它們之間夾角的余弦作為相似性度量）。然后，根據(jù)相似程度排列查詢結(jié)果。在向量空間模型中，文檔被形式化為n維空間中的向量，把關(guān)鍵詞的個(gè)數(shù)n作為空間向量的維數(shù)，每個(gè)關(guān)鍵詞的權(quán)值作為每一維分量的大小，則主題用向量表示為：

A=(a1,a2,…,an),i=1,2,…,n,ai=wi

對(duì)于頁(yè)面進(jìn)行分析，統(tǒng)計(jì)關(guān)鍵詞出現(xiàn)的頻率，并求出頻率之比，以出現(xiàn)的頻率最高的關(guān)鍵詞作為基準(zhǔn)，其頻率用xi=1表示，通過頻率比，求出其他關(guān)鍵詞的頻率，則該頁(yè)面對(duì)應(yīng)向量的每一維分量為xiwi。指定一個(gè)閾值r，當(dāng)cos<α，β>=r時(shí)就可以認(rèn)為該頁(yè)面和主題是比較相關(guān)的，r的取值需要根據(jù)經(jīng)驗(yàn)和實(shí)際要求確定，如果想獲得較多的頁(yè)面，可以把r設(shè)小一點(diǎn)，要獲得較少的頁(yè)面可以把r設(shè)的大一點(diǎn)。

（二）布爾模型與空間向量模型分析

布爾模型的主要缺陷在于每個(gè)關(guān)鍵詞的權(quán)重都是一樣的，它不支持設(shè)定關(guān)鍵詞的相對(duì)重要性，但是其優(yōu)點(diǎn)也較為明顯，它易于實(shí)現(xiàn)，計(jì)算代價(jià)較小。

向量空間模型最大優(yōu)點(diǎn)在于它在知識(shí)表示方法上的巨大優(yōu)勢(shì)。在該模型中，文檔的內(nèi)容被形式化為多維空間中的一個(gè)點(diǎn)，以向量的形式給出。也正是因?yàn)榘盐臋n以向量的形式定義到實(shí)數(shù)域中，才使得模式識(shí)別和其他領(lǐng)域中各種成熟的算法和計(jì)算方法得以采用，極大地提高了自然語(yǔ)言文檔的可計(jì)算性和可操作性。

通過對(duì)空間向量模型和布爾模型的介紹，我們知道現(xiàn)在垂直搜索引擎大多采用空間向量模型計(jì)算主題相關(guān)性。這樣極大的提高到主題爬蟲的效率，也極大的提高了垂直搜索引擎的應(yīng)用效率，給客戶帶來了高效的查詢效果。與在進(jìn)行頁(yè)面的主題相關(guān)度分析后，當(dāng)其主題相關(guān)度符合要求時(shí)將處理該頁(yè)面中的所有鏈接，但其中的鏈接指向的頁(yè)面也可能有許多偏離了主題，這一點(diǎn)在網(wǎng)頁(yè)的標(biāo)題上就可以看出，現(xiàn)在大多數(shù)網(wǎng)頁(yè)的標(biāo)題已經(jīng)很明顯的給出了文本的主要描述對(duì)象，所以傳統(tǒng)的空間模型策略沒有注意到網(wǎng)頁(yè)標(biāo)題這個(gè)重要的角色。針對(duì)此提出了一種基于網(wǎng)頁(yè)標(biāo)題的空間向量模型主題相關(guān)度計(jì)算方法。

第三章網(wǎng)絡(luò)爬蟲模型的分析和概要設(shè)計(jì)3.1網(wǎng)絡(luò)爬蟲的模型分析首先建立URL任務(wù)列表，即開始要爬取的URL。由URL任務(wù)列表開始，根據(jù)預(yù)先設(shè)定的深度爬取網(wǎng)頁(yè)，同時(shí)判斷URL是否重復(fù)，按照一定算法和排序方式搜索頁(yè)面，然后對(duì)頁(yè)面按照一定算法進(jìn)行分析，并提取相關(guān)URL，最后將所得URL返回任務(wù)列表。之后將任務(wù)列表中URL重新開始爬取，從而使網(wǎng)絡(luò)爬蟲進(jìn)行循環(huán)運(yùn)行。3.2網(wǎng)絡(luò)爬蟲的搜索策略本文的搜索策略為廣度優(yōu)先搜索策略。如下圖3-1所示。圖3-1廣度優(yōu)先搜索策略示意圖定義一個(gè)狀態(tài)結(jié)點(diǎn)

采用廣度優(yōu)先搜索算法解答問題時(shí)，需要構(gòu)造一個(gè)表明狀態(tài)特征和不同狀態(tài)之間關(guān)系的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)稱為結(jié)點(diǎn)。不同的問題需要用不同的數(shù)據(jù)結(jié)構(gòu)描述。

2）確定結(jié)點(diǎn)的擴(kuò)展規(guī)則

根據(jù)問題所給定的條件，從一個(gè)結(jié)點(diǎn)出發(fā)，可以生成一個(gè)或多個(gè)新的結(jié)點(diǎn)，這個(gè)過程通常稱為擴(kuò)展。結(jié)點(diǎn)之間的關(guān)系一般可以表示成一棵樹，它被稱為解答樹。搜索算法的搜索過程實(shí)際上就是根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一棵解答樹并尋找符合目標(biāo)狀態(tài)的結(jié)點(diǎn)的過程。

廣度優(yōu)先搜索算法中，解答樹上結(jié)點(diǎn)的擴(kuò)展是沿結(jié)點(diǎn)深度的“斷層”進(jìn)行，也就是說，結(jié)點(diǎn)的擴(kuò)展是按它們接近起始結(jié)點(diǎn)的程度依次進(jìn)行的。首先生成第一層結(jié)點(diǎn)，同時(shí)檢查目標(biāo)結(jié)點(diǎn)是否在所生成的結(jié)點(diǎn)中，如果不在，則將所有的第一層結(jié)點(diǎn)逐一擴(kuò)展，得到第二層結(jié)點(diǎn)，并檢查第二層結(jié)點(diǎn)是否包含目標(biāo)結(jié)點(diǎn)，...對(duì)長(zhǎng)度為n+1的任一結(jié)點(diǎn)進(jìn)行擴(kuò)展之前，必須先考慮長(zhǎng)度為n的結(jié)點(diǎn)的每種可能的狀態(tài)。因此，對(duì)于同一層結(jié)點(diǎn)來說，求解問題的價(jià)值是相同的，我們可以按任意順序來擴(kuò)展它們。這里采用的原則是先生成的結(jié)點(diǎn)先擴(kuò)展。

結(jié)點(diǎn)的擴(kuò)展規(guī)則也就是如何從現(xiàn)有的結(jié)點(diǎn)生成新結(jié)點(diǎn)。對(duì)不同的問題，結(jié)點(diǎn)的擴(kuò)展規(guī)則也不相同，需要按照問題的要求確定。

3）搜索策略

為了便于進(jìn)行搜索，要設(shè)置一個(gè)表存儲(chǔ)所有的結(jié)點(diǎn)。因?yàn)樵趶V度優(yōu)先搜索算法中，要滿足先生成的結(jié)點(diǎn)先擴(kuò)展的原則，所以存儲(chǔ)結(jié)點(diǎn)的表一般設(shè)計(jì)成隊(duì)列的數(shù)據(jù)結(jié)構(gòu)。

搜索的步驟一般是：

（1）從隊(duì)列頭取出一個(gè)結(jié)點(diǎn)，檢查它按照擴(kuò)展規(guī)則是否能夠擴(kuò)展，如果能則產(chǎn)生一個(gè)新結(jié)點(diǎn)。

（2）檢查新生成的結(jié)點(diǎn)，看它是否已在隊(duì)列中存在，如果新結(jié)點(diǎn)已經(jīng)在隊(duì)列中出現(xiàn)過，就放棄這個(gè)結(jié)點(diǎn)，然后回到第（1）步。否則，如果新結(jié)點(diǎn)未曾在隊(duì)列中出現(xiàn)過，則將它加入到隊(duì)列尾。

（3）檢查新結(jié)點(diǎn)是否目標(biāo)結(jié)點(diǎn)。如果新結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)，則搜索成功，程序結(jié)束；若新結(jié)點(diǎn)不是目標(biāo)結(jié)點(diǎn)，則回到第（1）步，再?gòu)年?duì)列頭取出結(jié)點(diǎn)進(jìn)行擴(kuò)展。

最終可能產(chǎn)生兩種結(jié)果：找到目標(biāo)結(jié)點(diǎn)，或擴(kuò)展完所有結(jié)點(diǎn)而沒有找到目標(biāo)結(jié)點(diǎn)。3.3網(wǎng)絡(luò)爬蟲的主題相關(guān)度判斷主題爬蟲的系統(tǒng)組成最初考慮是對(duì)頁(yè)面的過濾，不像普通爬蟲對(duì)所有頁(yè)面的鏈接進(jìn)行處理，先對(duì)頁(yè)面與受限領(lǐng)域的主題相關(guān)度進(jìn)行分析，只有當(dāng)其主題相關(guān)度符合要求時(shí)才處理該頁(yè)面中的鏈接，因?yàn)槿绻擁?yè)面和本領(lǐng)域比較相關(guān)，它所包含的鏈接和領(lǐng)域相關(guān)的幾率也較大，這樣提高了爬行精度，雖然會(huì)遺漏少數(shù)頁(yè)面，但綜合效果是令人滿意的。因此，主題相關(guān)度的分析是主題爬蟲設(shè)計(jì)的關(guān)鍵。主題蜘蛛將網(wǎng)頁(yè)下載到本地后，需要使用基于內(nèi)容的主題判別方法計(jì)算該網(wǎng)頁(yè)的主題相關(guān)度值，主題相關(guān)度低于某一閾值的網(wǎng)頁(yè)被丟棄。什么是網(wǎng)頁(yè)標(biāo)題

通常瀏覽一個(gè)網(wǎng)頁(yè)時(shí)，通過瀏覽器頂端的藍(lán)色顯示條出現(xiàn)的信息就是“網(wǎng)頁(yè)標(biāo)題”。

在網(wǎng)頁(yè)HTML代碼中，網(wǎng)頁(yè)標(biāo)題位于標(biāo)簽之間。

網(wǎng)頁(yè)標(biāo)題是對(duì)于一個(gè)網(wǎng)頁(yè)的高度概括，一般來說，網(wǎng)站首頁(yè)的標(biāo)題就是網(wǎng)站的正式名稱，而網(wǎng)站中文章內(nèi)容頁(yè)面的標(biāo)題就是這文章的題目，欄目首頁(yè)的標(biāo)題通常是欄目名稱。當(dāng)然這種一般原則并不是固定不變的，在實(shí)際工作中可能會(huì)有一定的變化，但是無論如何變化，總體上仍然會(huì)遵照這種規(guī)律[12]。

例如，現(xiàn)在會(huì)看到很多網(wǎng)站的首頁(yè)標(biāo)題較長(zhǎng)，除了網(wǎng)站名稱之外，還有網(wǎng)站相關(guān)業(yè)務(wù)之類的關(guān)鍵詞，這主要是為了在搜索引擎搜索結(jié)果中獲得排名優(yōu)勢(shì)而考慮的，也屬于正常的搜索引擎優(yōu)化方法。因?yàn)橐话愕墓久Q（或者品牌名稱）中可能不包含核心業(yè)務(wù)的關(guān)鍵詞，在搜索結(jié)果排名中將處于不利地位。

（二）網(wǎng)頁(yè)標(biāo)題的重要性

以Google為例，Google會(huì)對(duì)其標(biāo)題標(biāo)簽（metatitle）中出現(xiàn)的關(guān)鍵字給予較高的權(quán)值。所以應(yīng)當(dāng)確保在網(wǎng)站的標(biāo)題標(biāo)簽中包含了最重要的關(guān)鍵詞，即應(yīng)圍繞最重要的關(guān)鍵詞來決定網(wǎng)頁(yè)標(biāo)題的內(nèi)容。不過網(wǎng)頁(yè)的標(biāo)題不可過長(zhǎng)，一般最好在35到40個(gè)字符之間。在實(shí)際操作中，網(wǎng)頁(yè)標(biāo)題不宜過短或過長(zhǎng)。太短無法完整的表達(dá)網(wǎng)頁(yè)信息，太長(zhǎng)不僅不利于用戶識(shí)別，而且對(duì)搜索引擎來說也加大了識(shí)別核心關(guān)鍵詞的難度；網(wǎng)頁(yè)標(biāo)題應(yīng)概括網(wǎng)頁(yè)的核心內(nèi)容。搜索引擎在進(jìn)行搜索的時(shí)候，搜索結(jié)果的內(nèi)容一般是網(wǎng)頁(yè)標(biāo)題、網(wǎng)頁(yè)摘要信息和鏈接，要引起用戶的關(guān)注，高度總結(jié)了網(wǎng)頁(yè)內(nèi)容的標(biāo)題至關(guān)重要。比如戴爾中國(guó)的網(wǎng)站首頁(yè)標(biāo)題為“戴爾中國(guó)（DellChina）—計(jì)算機(jī)，筆記本電腦，臺(tái)式機(jī)，打印機(jī)，工作站，服務(wù)器，存儲(chǔ)器，電子產(chǎn)品及附件等”。戴爾的首頁(yè)標(biāo)題中不但涵蓋了最重要的公司信息，而且還包括公司的主要產(chǎn)品，這就是核心關(guān)鍵詞，當(dāng)用“筆記本電腦”、“臺(tái)式電腦”這些關(guān)鍵詞在谷歌中進(jìn)行搜索時(shí)，戴爾公司的網(wǎng)頁(yè)都排在第一屏的前幾條位置。但是與此同時(shí)需要注意的還有網(wǎng)頁(yè)正文的重要性，因?yàn)榫W(wǎng)頁(yè)的標(biāo)題和關(guān)鍵字很可能與正文無關(guān)，虛假關(guān)鍵詞是通過在META中設(shè)置與網(wǎng)站內(nèi)容無關(guān)的關(guān)鍵詞，如在Title中設(shè)置熱門關(guān)鍵詞，以達(dá)到誤導(dǎo)用戶進(jìn)入網(wǎng)站的目的。同樣的情況也包括鏈接關(guān)鍵詞與實(shí)際內(nèi)容不符的情況。

具體判斷主題相關(guān)度的步驟1.對(duì)標(biāo)題及正文的特征項(xiàng)的選取是通過分詞后與主題集合匹配，并通過詞頻計(jì)算來得到與主題向量維數(shù)相等的標(biāo)題向量和正文向量。

2.通過向量空間模型計(jì)算出主題和標(biāo)題的相關(guān)度B。

3.通過空間向量向量模型計(jì)算主題與正文的相關(guān)度C。

4.主題與整個(gè)網(wǎng)頁(yè)的相關(guān)度：A=4×B+C。

5.通過詳細(xì)計(jì)算，設(shè)定相關(guān)度閾值為2，網(wǎng)頁(yè)與主題的相關(guān)度A>2，則認(rèn)為該網(wǎng)頁(yè)與主題相關(guān)的。

3.4網(wǎng)絡(luò)爬蟲的概要設(shè)計(jì)本網(wǎng)絡(luò)爬蟲的開發(fā)目的，通過網(wǎng)絡(luò)爬蟲技術(shù)一個(gè)自動(dòng)提取網(wǎng)頁(yè)的程序，實(shí)現(xiàn)搜索引擎從自己想要訪問的網(wǎng)上下載網(wǎng)頁(yè)，再根據(jù)已下載的網(wǎng)頁(yè)上繼續(xù)訪問其它的網(wǎng)頁(yè)，并將其下載直到滿足用戶的需求。根據(jù)現(xiàn)實(shí)中不同用戶的實(shí)際上的各種需求，本項(xiàng)目簡(jiǎn)單實(shí)現(xiàn)主題爬蟲，本網(wǎng)絡(luò)爬蟲需要達(dá)到如下幾個(gè)目標(biāo)：1.設(shè)計(jì)基于多線程的網(wǎng)絡(luò)爬蟲，客戶端向服務(wù)器發(fā)送自己設(shè)定好請(qǐng)求。如圖3-7所示。URL配置文件URL配置文件URL配置文件列表臨界區(qū)互聯(lián)網(wǎng)線程1搜索元URL如線程2搜索元URL如線程N(yùn)圖3-2多線程網(wǎng)絡(luò)爬蟲概要設(shè)計(jì)圖模型2.通過http將Web服務(wù)器上協(xié)議站點(diǎn)的網(wǎng)頁(yè)代碼提取出來。3.根據(jù)一定的正則表達(dá)式提取出客戶端所需要的信息。4.廣度優(yōu)先搜索可從網(wǎng)頁(yè)中某個(gè)鏈接出發(fā)，訪問該鏈接網(wǎng)頁(yè)上的所有鏈接，訪問完成后，再通過遞歸算法實(shí)現(xiàn)下一層的訪問。本網(wǎng)絡(luò)爬蟲最終將設(shè)計(jì)成一個(gè)能夠自動(dòng)讀寫配置文件并且在后臺(tái)自動(dòng)執(zhí)行的網(wǎng)絡(luò)爬蟲程序。網(wǎng)絡(luò)爬蟲工作流程圖如圖3-3所示。圖3-3網(wǎng)絡(luò)爬蟲工作流程圖

第四章網(wǎng)絡(luò)爬蟲模型的設(shè)計(jì)和實(shí)現(xiàn)4.1網(wǎng)絡(luò)爬蟲總體設(shè)計(jì)根據(jù)本網(wǎng)絡(luò)爬蟲的概要設(shè)計(jì)本網(wǎng)絡(luò)爬蟲是一個(gè)自動(dòng)提取網(wǎng)頁(yè)的程序，根據(jù)設(shè)定的主題判斷是否與主題相關(guān)，再根據(jù)已下載的網(wǎng)頁(yè)上繼續(xù)訪問其它的網(wǎng)頁(yè)，并將其下載直到滿足用戶的需求。1.設(shè)計(jì)基于多線程的網(wǎng)絡(luò)爬蟲。2.通過http將待爬取URL列表對(duì)應(yīng)的URL的網(wǎng)頁(yè)代碼提取出來。3.提取出所需要的信息并且通過算法判斷網(wǎng)頁(yè)是否和設(shè)定的主題相關(guān)。4.廣度優(yōu)先搜索，從網(wǎng)頁(yè)中某個(gè)鏈接出發(fā)，訪問該鏈接網(wǎng)頁(yè)上的所有鏈接，訪問完成后，再通過遞歸算法實(shí)現(xiàn)下一層的訪問，重復(fù)以上步驟?？偟膩碚f爬蟲程序根據(jù)輸入獲得URL任務(wù)列表，即初始URL種子，把初始種子保存在臨界區(qū)中，按照廣度搜索運(yùn)算法搜索抓取網(wǎng)頁(yè)并提取URL返回到臨屆區(qū)中，通過判斷主題相關(guān)度算法判斷相關(guān)度，取出不相關(guān)網(wǎng)頁(yè)，，從而使整個(gè)爬蟲程序循環(huán)運(yùn)行下去。4.2網(wǎng)絡(luò)爬蟲具體設(shè)計(jì)4.2.1爬取網(wǎng)頁(yè)主要用到的技術(shù)如下：繼承HTMLEditorKit類，改寫其中的HTMLEditorKit.ParsergetParser()屬性protect為public，用下列函數(shù)爬取網(wǎng)頁(yè)：publicclassXXXXXextendsHTMLEditorKit{

publicHTMLEditorKit.ParsergetParser()

{

returnsuper.getParser();

}

}步驟如下：

1首先建立URL連接。URLConnectionurl_C=url_test.openConnection();2設(shè)置連接超時(shí)時(shí)間和讀取超時(shí)時(shí)間。url_C.setConnectTimeout(10000);url_C.setReadTimeout(10000);用輸入流，BufferedReader讀取，并且將網(wǎng)頁(yè)內(nèi)容存儲(chǔ)為字符串。4.2.2分析網(wǎng)頁(yè)繼承ParserCallback獲得網(wǎng)頁(yè)內(nèi)容//得到標(biāo)題文本 protectedStringurlTitle=newString(); //得到某一網(wǎng)頁(yè)上的所有鏈接 protectedVector<String>links=newVector<String>(); protectedVector<String>linkname=newVector<String>(); //得到網(wǎng)頁(yè)上的正文文本 protectedStringparagraphText=newString(); protectedStringlinkandparagraph=newString(); protectedStringencode=newString(); publicParser(Stringbaseurl){ base=baseurl; } publicStringgetEncode(){ returnencode; } //獲得該網(wǎng)頁(yè)標(biāo)題 publicStringgetURLtitle(){ returnurlTitle; } //獲得該網(wǎng)頁(yè)的所有鏈接 publicVectorgetLinks(){ returnlinks; } //獲得所有該網(wǎng)頁(yè)的鏈接名 publicVectorgetLinkName() //獲得網(wǎng)頁(yè)正文 publicStringgetParagraphText() publicvoidhandleEndTag(HTML.Tagt,intpos) //處理簡(jiǎn)單標(biāo)簽 publicvoidhandleSimpleTag(HTML.Tagt,MutableAttributeSeta,intpos) //處理結(jié)束標(biāo)簽 publicvoidhandleStartTag(HTML.Tagt,MutableAttributeSeta,intpos) //處理文本標(biāo)簽 publicvoidhandleText(char[]data,intpos)之后通過調(diào)用HTMLEditorKit.Parser類，生成對(duì)象就可以直接得到分析后的網(wǎng)頁(yè)文件。4.2.3判斷相關(guān)度算法實(shí)現(xiàn)步驟和算法描述：對(duì)標(biāo)題及正文的特征項(xiàng)的選取是通過分詞后與主題集合匹配，并通過詞頻計(jì)算來得到與主題向量維數(shù)相等的標(biāo)題向量和正文向量。

2.通過向量空間模型計(jì)算出主題和標(biāo)題的相關(guān)度B。

3.通過空間向量向量模型計(jì)算主題與正文的相關(guān)度C。

4.主題與整個(gè)網(wǎng)頁(yè)的相關(guān)度：A=4×B+C。

5.通過詳細(xì)計(jì)算，設(shè)定相關(guān)度閾值為2，網(wǎng)頁(yè)與主題的相關(guān)度A>2，則認(rèn)為該網(wǎng)頁(yè)與主題相關(guān)的。

輸入：主題集合文本a.txt，網(wǎng)頁(yè)url

輸出：主題相關(guān)度

（1）Gettopic（Stringpath）//根據(jù)路徑獲取主題文本集合

（2）Compulatetopicweight（Stringtopic）//求主題結(jié)合權(quán)重（3）sortAndDelRepeat(int[]count)//刪除重復(fù)元素并排序（4）delRepeat(String[]segment)//刪除分詞后的重復(fù)元素（5）delRepeat(Vectorurl)//刪除得到的URL中的重復(fù)元素（6）getParser(Stringurl)//獲得Parser實(shí)例

（7）StringtitleStr=p.getURLtitle（）//獲取網(wǎng)頁(yè)標(biāo)題

（8）StringbodyStr=p.getParagraphText（）//獲取網(wǎng)頁(yè)文本

（9）StringtitleStrSeg=segment.segment（titleStr）//網(wǎng)頁(yè)標(biāo)題分詞

（10）StringbodyStrSeg=segment.segment（bodyStr）//網(wǎng)頁(yè)文本分詞

（11）Compulatetitle.length，body.length//計(jì)算標(biāo)題向量長(zhǎng)度和網(wǎng)頁(yè)文本向量長(zhǎng)度

（12）settopicweight1，titleweight1，bodyweight1；//設(shè)置權(quán)重

（13）LastcompulateRelative//計(jì)算主題相關(guān)性

（14）Returnrelative；//返回結(jié)果

根據(jù)系統(tǒng)設(shè)置首先是下載所有網(wǎng)頁(yè)，而后判定主題相關(guān)性，與主題相關(guān)則放置在相關(guān)URL庫(kù)中，不相關(guān)的網(wǎng)頁(yè)則丟棄。4.2.4保存網(wǎng)頁(yè)信息1.首先建立URL連接。URLConnectionurl_C=url_test.openConnection();2.新建PagePro類。如下：privateStringHost;privateintprivateStringContentType;privateintContentLength;privateStringDate;privateStringUrl;3.將數(shù)據(jù)存入新建的PagePro類中。4.將數(shù)據(jù)保存到預(yù)先輸入的地址。4.2.5數(shù)據(jù)庫(kù)設(shè)計(jì)和存儲(chǔ)使用JDBC訪問數(shù)據(jù)庫(kù)，儲(chǔ)存下載的網(wǎng)頁(yè)URL和下載時(shí)間信息。4.2.6多線程的實(shí)現(xiàn)設(shè)計(jì)為4個(gè)線程同時(shí)進(jìn)行工作。1.從用戶輸入的起始URL開始，遞歸獲得指定深度的URL。2.對(duì)每個(gè)URL進(jìn)行分析，判斷相關(guān)度。3.下載與主題相關(guān)的網(wǎng)頁(yè)，并存儲(chǔ)在數(shù)據(jù)庫(kù)中。第i個(gè)線程對(duì)所有URL列表中序列為第0+4iURL的進(jìn)行同步操作，其中對(duì)儲(chǔ)存所有URL的列表執(zhí)行synchronized(all_URL)操作。4.2.7附加功能為了檢測(cè)網(wǎng)絡(luò)環(huán)境，防止因?yàn)椴涣嫉木W(wǎng)絡(luò)環(huán)境影響網(wǎng)絡(luò)爬蟲的爬取效率和正確略，額外添加了實(shí)時(shí)的ping功能，調(diào)用windows的命令解釋器的ping功能，測(cè)試用戶輸入網(wǎng)址與當(dāng)前主機(jī)的連接狀況，測(cè)試當(dāng)前網(wǎng)絡(luò)狀況是否良好。4.2.8整體流程爬蟲代碼文件構(gòu)成如圖4-1：圖4-1代碼結(jié)構(gòu)構(gòu)成截圖HtmlParser.java這個(gè)類是改寫HTMLEditorKit.ParsergetParser()方法為publicHTTP.java是根據(jù)輸入U(xiǎn)RL獲取網(wǎng)頁(yè)文檔Parser.java是繼承ParserCallback獲得網(wǎng)頁(yè)內(nèi)容Relative.java是判斷主題與網(wǎng)頁(yè)內(nèi)容的相關(guān)性Segment.java是對(duì)網(wǎng)頁(yè)主題和正文進(jìn)行分詞Download.java是下載網(wǎng)頁(yè)所用，Pagepro.java是為Download.java生成存儲(chǔ)對(duì)象。JDBCTest.java對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作mainF.java整合了網(wǎng)絡(luò)爬蟲的功能Ui.java是界面Ping.java是調(diào)用Ping程序的類具體流程：第一步：調(diào)用HtmlParser.java，Parser.java，獲得起始URL的內(nèi)容，并存儲(chǔ)到String中。第二步：調(diào)用Parser.java獲得網(wǎng)頁(yè)下面所有的URL，同時(shí)去除重復(fù)的部分。第三步：對(duì)以上兩步進(jìn)行遞歸循環(huán)，獲得指定深度的所有URL列表。第四步：調(diào)用Relative.java，Segment.java得到每個(gè)URL對(duì)應(yīng)的網(wǎng)頁(yè)內(nèi)容與給定主題的閾值，大于給定值則相關(guān)，小于給定值則不相關(guān)，丟棄該URL。第五步：調(diào)用Download.java和JDBCTest.java將與主題相關(guān)的網(wǎng)頁(yè)下載并存儲(chǔ)入數(shù)據(jù)庫(kù)。

第五章測(cè)試設(shè)定只爬取前5個(gè)網(wǎng)頁(yè)，程序運(yùn)行后的界面如圖5-1圖5-1測(cè)試圖1預(yù)設(shè)目錄為，D：test按下START后，查看目錄，可見如圖5-2：圖5-2測(cè)試圖2查看數(shù)據(jù)庫(kù)可見，如圖5-3：圖5-3測(cè)試圖3測(cè)試Ping功能，分別對(duì)正確網(wǎng)址ping和不正確網(wǎng)址ping，如圖5-4圖5-4測(cè)試圖4圖5-5測(cè)試圖5圖5-6測(cè)試圖6

第六章總結(jié)和展望2011年3月，我開始了我的畢業(yè)論文工作，時(shí)至今日，論文基本完成。從最初的茫然，到慢慢的進(jìn)入狀態(tài)，再到對(duì)思路逐漸的清晰，整個(gè)寫作過程難以用語(yǔ)言來表達(dá)。歷經(jīng)了幾個(gè)月的奮戰(zhàn)，緊張而又充實(shí)的畢業(yè)設(shè)計(jì)終于落下了帷幕?；叵脒@段日子的經(jīng)歷和感受，我感慨萬千，在這次畢業(yè)設(shè)計(jì)的過程中，我擁有了無數(shù)難忘的回憶和收獲。

3月初，在與導(dǎo)師的交流討論中我的題目定了下來，是面向主題的網(wǎng)絡(luò)爬蟲。當(dāng)選題報(bào)告，開題報(bào)告定下來的時(shí)候，我當(dāng)時(shí)便立刻著手資料的收集工作中，當(dāng)時(shí)面對(duì)浩瀚的書海真是有些茫然，不知如何下手。我將這一困難告訴了導(dǎo)師，在導(dǎo)師細(xì)心的指導(dǎo)下，終于使我對(duì)自己現(xiàn)在的工作方向和方法有了掌握。

在搜集資料的過程中，我認(rèn)真準(zhǔn)備了一個(gè)筆記本。我在學(xué)校圖書館，大工圖書館搜集資料，還在網(wǎng)上查找各類相關(guān)資料，將這些寶貴的資料全部記在筆記本上，盡量使我的資料完整、精確、數(shù)量多，這有利于論文的撰寫。然后我將收集到的資料仔細(xì)整理分類，及時(shí)拿給導(dǎo)師進(jìn)行溝通。

4月初，資料已經(jīng)查找完畢了，我開始著手論文的寫作。在寫作過程中遇到困難我就及時(shí)和導(dǎo)師聯(lián)系，并和同學(xué)互相交流，請(qǐng)教專業(yè)課老師。在大家的幫助下，困難一個(gè)一個(gè)解決掉，論文也慢慢成型。

4月底，平臺(tái)設(shè)計(jì)已經(jīng)完成。5月開始相關(guān)代碼編寫工作。為了完成滿意的平臺(tái)設(shè)計(jì)，我仔細(xì)溫習(xí)了數(shù)據(jù)庫(kù)原理相關(guān)知識(shí)。深入了解并掌握數(shù)據(jù)庫(kù)基礎(chǔ)知識(shí)，挖掘出數(shù)據(jù)庫(kù)課程中的難點(diǎn)和重點(diǎn)，對(duì)于其中的難點(diǎn)，要充分考慮學(xué)生的學(xué)習(xí)能力，幫助學(xué)生以一種最容易接受的方式掌握知識(shí)。對(duì)于課程中的重點(diǎn)，要強(qiáng)調(diào)突出，有規(guī)律反復(fù)出現(xiàn)，幫助學(xué)生更高效消化知識(shí)。在設(shè)計(jì)平臺(tái)中，要注意平臺(tái)的可行性和有效性，選擇既重要又適合以學(xué)習(xí)軟件形式出現(xiàn)的知識(shí)點(diǎn)作為材料，參考優(yōu)秀的國(guó)內(nèi)外學(xué)習(xí)輔助平臺(tái)，又考慮到數(shù)據(jù)庫(kù)課程的特殊性。在設(shè)計(jì)初期，由于沒有設(shè)計(jì)經(jīng)驗(yàn)，覺得無從下手，空有很多設(shè)計(jì)思想，卻不知道應(yīng)該選哪個(gè)，經(jīng)過導(dǎo)師的指導(dǎo)，我的設(shè)計(jì)漸漸有了頭緒，通過查閱資料，逐漸確立系統(tǒng)方案。在整個(gè)過程中，我學(xué)到了新知識(shí)，增長(zhǎng)了見識(shí)。在今后的日子里，我仍然要不斷地充實(shí)自己，爭(zhēng)取在所學(xué)領(lǐng)域有所作為。

腳踏實(shí)地，認(rèn)真嚴(yán)謹(jǐn)，實(shí)事求是的學(xué)習(xí)態(tài)度，不怕困難、堅(jiān)持不懈、吃苦耐勞的精神是我在這次設(shè)計(jì)中最大的收益。我想這是一次意志的磨練，是對(duì)我實(shí)際能力的一次提升，也會(huì)對(duì)我未來的學(xué)習(xí)和工作有很大的幫助。

在這次畢業(yè)設(shè)計(jì)中也使我們的同學(xué)關(guān)系更進(jìn)一步了，同學(xué)之間互相幫助，有什么不懂的大家在一起商量，聽聽不同的看法對(duì)我們更好的理解知識(shí)，所以在這里非常感謝幫助我的同學(xué)。

在此更要感謝我的導(dǎo)師和專業(yè)老師，是你們的細(xì)心指導(dǎo)和關(guān)懷，使我能夠順利的完成畢業(yè)論文。在我的學(xué)業(yè)和論文的研究工作中無不傾注著老師們辛勤的汗水和心血。老師的嚴(yán)謹(jǐn)治學(xué)態(tài)度、淵博的知識(shí)、無私的奉獻(xiàn)精神使我深受啟迪。從尊敬的導(dǎo)師身上，我不僅學(xué)到了扎實(shí)、寬廣的專業(yè)知識(shí)，也學(xué)到了做人的道理。在此我要向我的導(dǎo)師致以最衷心的感謝和深深的敬意。參考文獻(xiàn)[1]Winter．中文搜索引擎技術(shù)解密：網(wǎng)絡(luò)蜘蛛[M]．北京：人民郵電出版社，2004年．[2]Sergey等．TheAnatomyofaLarge-ScaleHypertextualWebSearchEngine[M]．北京：清華大學(xué)出版社，1998年．[3]Wisenut．WiseNutSearchEnginewhitepaper[M]．北京：中國(guó)電力出版社，2001年．[4]GaryR.WrightW.RichardStevens．TCP-IP協(xié)議詳解卷3：TCP事務(wù)協(xié)議，HTTP，NNTP和UNIX域協(xié)議[M]．北京：機(jī)械工業(yè)出版社，2002年1月.[5]羅剛王振東．自己動(dòng)手寫網(wǎng)絡(luò)爬蟲[M]．北京：清華大學(xué)出版社，2010年10月.[6]李曉明，閆宏飛，王繼民．搜索引擎：原理、技術(shù)與系統(tǒng)——華夏英才基金學(xué)術(shù)文庫(kù)[M]．北京：科學(xué)出版社，2005年04月.外文資料ABSTRACT

Crawlingthewebisdeceptivelysimple:thebasicalgorithmis(a)Fetchapage(b)ParseittoextractalllinkedURLs(c)ForalltheURLsnotseenbefore,repeat(a)–(c).However,thesizeoftheweb(estimatedatover4billionpages)anditsrateofchange(estimatedat7%perweek)movethisplanfromatrivialprogrammingexercisetoaseriousalgorithmicandsystemdesignchallenge.Indeed,thesetwofactorsaloneimplythatforareasonablyfreshandcompletecrawloftheweb,step(a)mustbeexecutedaboutathousandtimespersecond,andthusthemembershiptest(c)mustbedonewellovertenthousandtimespersecondagainstasettoolargetostoreinmainmemory.Thisrequiresadistributedarchitecture,whichfurthercomplicatesthemembershiptest.

Acrucialwaytospeedupthetestistocache,thatis,tostoreinmainmemorya(dynamic)subsetofthe“seen”URLs.ThemaingoalofthispaperistocarefullyinvestigateseveralURLcachingtechniquesforwebcrawling.Weconsiderbothpracticalalgorithms:randomreplacement,staticcache,LRU,andCLOCK,andtheoreticallimits:clairvoyantcachingandinfinitecache.Weperformedabout1,800simulationsusingthesealgorithmswithvariouscachesizes,usingactuallogdataextractedfromamassive33daywebcrawlthatissuedoveronebillionHTTPrequests.Ourmainconclusionisthatcachingisveryeffective–inoursetup,acacheofroughly50,000entriescanachieveahitrateofalmost80%.Interestingly,thiscachesizefallsatacriticalpoint:asubstantiallysmallercacheismuchlesseffectivewhileasubstantiallylargercachebringslittleadditionalbenefit.Weconjecturethatsuchcriticalpointsareinherenttoourproblemandventureanexplanationforthisphenomenon.

1.INTRODUCTION

ArecentPewFoundationstudy[31]statesthat“SearchengineshavebecomeanindispensableutilityforInternetusers”andestimatesthatasofmid-2002,slightlyover50%ofallAmericanshaveusedwebsearchtofindinformation.Hence,thetechnologythatpowerswebsearchisofenormouspracticalinterest.Inthispaper,weconcentrateononeaspectofthesearchtechnology,namelytheprocessofcollectingwebpagesthateventuallyconstitutethesearchenginecorpus.

Searchenginescollectpagesinmanyways,amongthemdirectURLsubmission,paidinclusion,andURLextractionfromnonwebsources,butthebulkofthecorpusisobtainedbyrecursivelyexploringtheweb,aprocessknownascrawlingorSPIDERing.Thebasicalgorithmis

(a)Fetchapage

(b)ParseittoextractalllinkedURLs

(c)ForalltheURLsnotseenbefore,repeat(a)–(c)

CrawlingtypicallystartsfromasetofseedURLs,madeupofURLsobtainedbyothermeansasdescribedaboveand/ormadeupofURLscollectedduringpreviouscrawls.Sometimescrawlsarestartedfromasinglewellconnectedpage,oradirectorysuchas,butinthiscasearelativelylargeportionoftheweb(estimatedatover20%)isneverreached.See[9]foradiscussionofthegraphstructureofthewebthatleadstothisphenomenon.

Ifweviewwebpagesasnodesinagraph,andhyperlinksasdirectededgesamongthesenodes,thencrawlingbecomesaprocessknowninmathematicalcirclesasgraphtraversal.Variousstrategiesforgraphtraversaldifferintheirchoiceofwhichnodeamongthenodesnotyetexploredtoexplorenext.TwostandardstrategiesforgraphtraversalareDepthFirstSearch(DFS)andBreadthFirstSearch(BFS)–theyareeasytoimplementandtaughtinmanyintroductoryalgorithmsclasses.(Seeforinstance[34]).

However,crawlingthewebisnotatrivialprogrammingexercisebutaseriousalgorithmicandsystemdesignchallengebecauseofthefollowingtwofactors.

1.Thewebisverylarge.Currently,Google[20]claimstohaveindexedover3billionpages.Variousstudies[3,27,28]haveindicatedthat,historically,thewebhasdoubledevery9-12months.

2.Webpagesarechangingrapidly.If“change”means“anychange”,thenabout40%ofallwebpageschangeweekly[12].Evenifweconsideronlypagesthatchangebyathirdormore,about7%ofallwebpageschangeweekly[17].

Thesetwofactorsimplythattoobtainareasonablyfreshand679completesnapshotoftheweb,asearchenginemustcrawlatleast100millionpagesperday.Therefore,step(a)mustbeexecutedabout1,000timespersecond,andthemembershiptestinstep(c)mustbedonewellovertenthousandtimespersecond,againstasetofURLsthatistoolargetostoreinmainmemory.Inaddition,crawlerstypicallyuseadistributedarchitecturetocrawlmorepagesinparallel,whichfurthercomplicatesthemembershiptest:itispossiblethatthemembershipquestioncanonlybeansweredbyapeernode,notlocally.

Acrucialwaytospeedupthemembershiptestistocachea(dynamic)subsetofthe“seen”URLsinmainmemory.ThemaingoalofthispaperistoinvestigateindepthseveralURLcachingtechniquesforwebcrawling.Weexaminedfourpracticaltechniques:randomreplacement,staticcache,LRU,andCLOCK,andcomparedthemagainsttwotheoreticallimits:clairvoyantcachingandinfinitecachewhenrunagainstatraceofawebcrawlthatissuedoveronebillionHTTPrequests.Wefoundthatsimplecachingtechniquesareextremelyeffectiveevenatrelativelysmallcachesizessuchas50,000entriesandshowhowthesecachescanbeimplementedveryefficiently.

Thepaperisorganizedasfollows:Section2discussesthevariouscrawlingsolutionsproposedintheliteratureandhowcachingfitsintheirmodel.Section3presentsanintroductiontocachingtechniquesanddescribesseveraltheoreticalandpracticalalgorithmsforcaching.WeimplementedthesealgorithmsundertheexperimentalsetupdescribedinSection4.TheresultsofoursimulationsaredepictedanddiscussedinSection5,andourrecommendationsforpracticalalgorithmsanddatastructuresforURLcachingarepresentedinSection6.Section7containsourconclusionsanddirectionsforfurtherresearch.

2.CRAWLING

Webcrawlersarealmostasoldasthewebitself,andnumerouscrawlingsystemshavebeendescribedintheliterature.Inthissection,wepresentabriefsurveyofthesecrawlers(inhistoricalorder)andthendiscusswhymostofthesecrawlerscouldbenefitfromURLcaching.

ThecrawlerusedbytheInternetArchive[10]employsmultiplecrawlingprocesses,eachofwhichperformsanexhaustivecrawlof64hostsatatime.Thecrawlingprocessessavenon-localURLstodisk;attheendofacrawl,abatchjobaddstheseURLstotheper-hostseedsetsofthenextcrawl.

TheoriginalGooglecrawler,describedin[7],implementsthedifferentcrawlercomponentsasdifferentprocesses.AsingleURLserverprocessmaintainsthesetofURLstodownload;crawlingprocessesfetchpages;indexingprocessesextractwordsandlinks;andURLresolverprocessesconvertrelativeintoabsoluteURLs,whicharethenfedtotheURLServer.Thevariousprocessescommunicateviathefilesystem.

Fortheexperimentsdescribedinthispaper,weusedtheMercatorwebcrawler[22,29].Mercatorusesasetofindependent,communicatingwebcrawlerprocesses.Eachcrawlerprocessisresponsibleforasubs