【正文】 ible that the membership question can only be answered by a peer node, not locally. A crucial way to speed up the membership test is to cache a (dynamic) subset of the “seen” URLs in main memory. The main goal of this paper is to investigate in depth several URL caching techniques for web crawling. We examined four practical techniques: random replacement, static cache, LRU, and CLOCK, and pared them against two theoretical limits: clairvoyant caching and infinite cache when run against a trace of a web crawl that issued over one billion HTTP requests. We found that simple caching techniques are extremely effective even at relatively small cache sizes such as 50,000 entries and show how these caches can be implemented very efficiently. The paper is anized as follows: Section 2 discusses the various crawling solutions proposed in the literature and how caching fits in their model. Section 3 presents an introduction to caching techniques and describes several theoretical and practical algorithms for caching. We implemented these algorithms under the experimental setup described in Section 4. The results of our simulations are depicted and discussed in Section 5, and our remendations for practical algorithms and data structures for URL caching are presented in Section 6. Section 7 contains our conclusions and directions for further research. 2. CRAWLING Web crawlers are almost as old as the web itself, and numerous crawling systems have been described in the literature. In this section, we present a brief survey of these 30 crawlers (in historical order) and then discuss why most of these crawlers could benefit from URL caching. The crawler used by the Inter Archive [10] employs multiple crawling processes, each of which performs an exhaustive crawl of 64 hosts at a time. The crawling processes save nonlocal URLs to disk。在我的學(xué)業(yè)和論文的研究工作中無不傾注著老師們辛勤的汗水和心 血。 腳踏實(shí)地，認(rèn)真嚴(yán)謹(jǐn)，實(shí)事求是的學(xué)習(xí)態(tài)度，不怕困難、堅(jiān)持不懈、吃苦耐勞的精神是我在這次設(shè)計(jì)中最大的收益。在設(shè)計(jì)平臺(tái)中，要注意平臺(tái)的可行性和有效性，選擇既重要又適合以學(xué)習(xí)軟件 形式出現(xiàn)的知識(shí)點(diǎn)作為材料，參考優(yōu)秀的國內(nèi)外學(xué)習(xí)輔助平臺(tái)，又考慮到數(shù)據(jù)庫課程的特殊性。 5 月開始相關(guān)代碼編寫工作。 4月初，資料已經(jīng)查找完畢了，我開始著手論文的寫作。我將這一困難告訴了導(dǎo)師，在導(dǎo)師細(xì)心的指導(dǎo)下，終于使我對(duì)自己現(xiàn)在的工作方向和方法有了掌握。歷經(jīng)了幾個(gè)月的奮戰(zhàn)，緊張而又充實(shí)的畢業(yè)設(shè)計(jì)終于落下了帷幕。 第四步：調(diào)用 ， 得到每個(gè) URL對(duì)應(yīng)的網(wǎng)頁內(nèi)容與給定主題的閾值，大于給定值則相關(guān)，小于給定值則不相關(guān)，丟棄該 URL。 整體流程 爬蟲代碼文件構(gòu)成如圖 41： 圖 41 代碼結(jié)構(gòu)構(gòu)成截圖 這個(gè)類是改寫 getParser()方法為public 是根據(jù)輸入 URL獲取網(wǎng)頁文檔 是 繼承 ParserCallback 獲得網(wǎng)頁內(nèi)容 是判斷主題與網(wǎng)頁內(nèi)容的相關(guān)性 是對(duì)網(wǎng)頁主題和正文進(jìn)行分詞 19 是下載網(wǎng)頁所用， 是為 生成存儲(chǔ)對(duì)象。 2. 對(duì)每個(gè) URL 進(jìn)行分析，判斷相關(guān)度。 。 private int ContentLength。 PagePro類。 ，設(shè)定相關(guān)度閾值為 2，網(wǎng)頁與主題的相關(guān)度 A2，則認(rèn)為該網(wǎng)頁與主題相關(guān)的。 判斷相關(guān)度 算法實(shí)現(xiàn)步驟和算法描述： 題集合匹配，并通過詞頻計(jì)算來得到與主題向量維數(shù)相等的標(biāo)題向量和正文向量。 } public String getEncode() { return encode。 // 得到網(wǎng)頁上的正文文本 protected String paragraphText = new String()。 ， BufferedReader 讀取，并且將網(wǎng)頁內(nèi)容存儲(chǔ)為字符串。 URLConnection url_C = ()。 ，從網(wǎng)頁中某個(gè)鏈接出發(fā)，訪問該鏈接網(wǎng)頁上的所有鏈接，訪問完成后，再通過遞歸算法實(shí)現(xiàn)下一層的訪問，重復(fù)以上步驟。 URL配置文件 URL配置文件列表 臨 界 區(qū) 互聯(lián)網(wǎng) 線程 1 搜索元URL 如 線程 2 搜索元URL 如 線程 N 13 圖 33 網(wǎng)絡(luò)爬蟲工作流程圖 開始從配置文件中讀取初始URL 作為源 URL獲取網(wǎng)頁以正則表達(dá)式過濾網(wǎng)頁標(biāo)簽提取目標(biāo) URL滿足條件停止結(jié)束根據(jù)寬度有限算法搜索目標(biāo)URL 網(wǎng)絡(luò)蜘蛛循環(huán)爬行 14 第四章 網(wǎng)絡(luò)爬蟲模型的設(shè)計(jì)和實(shí)現(xiàn) 網(wǎng)絡(luò)爬蟲總體設(shè)計(jì) 根據(jù)本網(wǎng)絡(luò)爬蟲的概要設(shè)計(jì)本網(wǎng)絡(luò)爬蟲是一個(gè)自動(dòng)提取網(wǎng)頁的程序，根據(jù)設(shè)定的主題判斷是否與主題相關(guān)，再根據(jù)已 下載的網(wǎng)頁上繼續(xù)訪問其它的網(wǎng)頁，并將其下載直到滿足用戶的需求。 信息。 網(wǎng)絡(luò)爬蟲的概要設(shè)計(jì) 本網(wǎng)絡(luò)爬蟲的開發(fā)目的，通過網(wǎng)絡(luò)爬蟲技術(shù)一個(gè)自動(dòng)提取網(wǎng) 頁的程序，實(shí)現(xiàn)搜索引擎從自己想要訪問的網(wǎng)上下載網(wǎng)頁，再根據(jù)已下載的網(wǎng)頁上繼續(xù)訪問其它的網(wǎng)頁，并將其下載直到滿足用戶的需求。 B。戴爾的首頁標(biāo)題中不但涵蓋了最重要的公司信息，而且還包括 公司的主要產(chǎn)品，這就是核心關(guān)鍵詞，當(dāng)用“筆記本電腦”、“臺(tái)式電腦”這些關(guān)鍵詞在谷歌中進(jìn)行搜索時(shí)，戴爾公司的網(wǎng)頁都排在第一屏的前幾條位置。在實(shí)際操作中 ，網(wǎng)頁標(biāo)題不宜過短或過長。因?yàn)橐话愕墓久Q（或者品牌名稱）中可能不包含核心業(yè)務(wù)的關(guān)鍵詞，在搜索結(jié)果排名中將處于不利地位。 在網(wǎng)頁 HTML 代碼中，網(wǎng)頁標(biāo)題位于標(biāo)簽之間。 網(wǎng)絡(luò)爬蟲的主題相關(guān)度判斷 主題爬蟲的系統(tǒng)組成最初考慮是對(duì)頁面的過濾，不像普通爬蟲對(duì)所有頁面的鏈接進(jìn)行處理，先對(duì)頁面與受限領(lǐng)域的主題相關(guān)度進(jìn)行分析，只有當(dāng)其主題相關(guān)度符合要求時(shí)才處理該頁面中的鏈接，因?yàn)槿绻擁撁婧捅绢I(lǐng)域比較相關(guān)，它所包含的鏈接和領(lǐng)域相關(guān)的幾率也較大，這樣提高了爬行精度，雖然會(huì)遺漏少數(shù)頁面，但綜合效果是令人滿意的。否則，如果新結(jié)點(diǎn)未曾在隊(duì)列中出現(xiàn)過，則將它加入到隊(duì)列尾。 3）搜索策略 為了便于進(jìn)行搜索，要設(shè)置一個(gè)表存儲(chǔ)所有的結(jié)點(diǎn)。因此，對(duì)于同一層結(jié)點(diǎn)來說，求解問題的價(jià)值是相同的，我們可以按任意順序來擴(kuò)展它們。結(jié)點(diǎn)之間的關(guān)系一般可以表示成一棵樹，它被稱為解答樹。如下圖 31 所示。 8 第三章 網(wǎng)絡(luò)爬蟲模型的分析和概要設(shè)計(jì) 網(wǎng)絡(luò)爬蟲的模型分析 首先建立 URL 任務(wù)列表，即開始要爬取 的 URL。 通過對(duì)空間向量模型和布爾模型的介紹，我們知道現(xiàn)在垂直搜索引擎大多采用空間向量模型計(jì)算主題相關(guān)性。 （二）布爾模型與空間向量模型分析 布爾模型的主要缺陷在于每個(gè)關(guān)鍵詞的權(quán)重都是 一樣的，它不支持設(shè)定關(guān)鍵詞的相對(duì)重要性，但是其優(yōu)點(diǎn)也較為明顯，它易于實(shí)現(xiàn)，計(jì)算代價(jià)較小。與布爾模型不同，向量空間模型把用戶的查詢要求和數(shù)據(jù)庫文檔信息表示成由檢索項(xiàng)構(gòu)成的向量空間中的點(diǎn)（向量），而通過計(jì)算向量之間的距離來判定文檔和查詢之間的相似程度（例如，用它們之間夾角的余弦作為相似性度量）。在判斷文檔與某主題的相關(guān)度的過程中，相當(dāng)于是計(jì)算兩個(gè)關(guān)鍵詞集合的交集。 。因此，主題相關(guān)度的分析是主題爬蟲設(shè)計(jì)的關(guān)鍵。因此需要將最佳優(yōu)先結(jié)合具體的應(yīng)用進(jìn)行改進(jìn)，以跳出局部最優(yōu)點(diǎn)。這些方法的缺點(diǎn)在于，隨著 6 抓取網(wǎng)頁的增多，大量的無關(guān)網(wǎng)頁將被下載并過濾，算法的效率將變低。在目前為覆蓋盡可能多的網(wǎng)頁，一般使用廣度優(yōu)先搜索方法。 網(wǎng)頁搜索策略介紹 網(wǎng)頁的抓取策略可以分為深度優(yōu)先、廣度優(yōu)先和最佳優(yōu)先三種。所有被網(wǎng)絡(luò)爬蟲抓取的網(wǎng)頁將會(huì)被系統(tǒng)存儲(chǔ)，進(jìn)行一定的分析、過濾，并建立索引，對(duì)于主題網(wǎng)絡(luò)爬蟲來說，這一過程所得到的分析結(jié)果還可能對(duì)后續(xù)的抓取過程進(jìn)行反饋和指導(dǎo)。由此可以看出，以往的爬蟲是基于協(xié)議驅(qū)動(dòng)的，而對(duì)于 AJAX 這樣的技術(shù)，所需要的爬蟲引擎必須是基于事件驅(qū)動(dòng)的。 傳統(tǒng)的網(wǎng)絡(luò)爬蟲技術(shù)主要應(yīng)用于抓取靜態(tài) Web 網(wǎng)頁，隨著 AJAX/行，如何抓取 AJAX 等動(dòng)態(tài)頁面成了搜索引擎急需解決的問題，因?yàn)?AJAX 顛覆了傳統(tǒng)的純 HTTP 請(qǐng)求 /響應(yīng)協(xié)議機(jī)制，如果搜索引擎依舊采用“爬”的機(jī)制，是無法抓取到 AJAX 頁面的有效數(shù)據(jù)的?，F(xiàn)在網(wǎng)絡(luò)上流 行的信息采集工具、網(wǎng)站聚合工具，都是未來新一代爬蟲的先驅(qū)，甚至已經(jīng)具備其特點(diǎn)。又 由于搜索引擎有大量的用戶，有很好的經(jīng)濟(jì)價(jià)值，所以引起了世界各國計(jì)算機(jī)科學(xué)界和信息產(chǎn)業(yè)界的高度關(guān)注，目前的研究 、開發(fā)十分活躍，并出現(xiàn)了很多值得注意的動(dòng)向。 搜索引擎的發(fā)展面臨著兩大 難題：一是如何跟上 Inter 的發(fā)展速度，二是如何為用戶提供更精確的查詢結(jié)果。 網(wǎng)絡(luò)爬蟲的發(fā)展趨勢(shì) 目前，大多數(shù)的搜索引擎都是基于關(guān)鍵詞的搜索引擎。 2，客戶端：很適合部署定題爬蟲，或者叫聚焦爬蟲。國內(nèi)的百度也屬于這一類（注），搜狐和新浪用的就是它的技術(shù)。目前，互聯(lián)網(wǎng)上有名有姓的搜索引擎已 達(dá)數(shù)百家，其檢索的信息量也與從前不可同日而語。而 RBSE 是第一個(gè)在搜索結(jié)果排列中引入關(guān)鍵字串匹配程 度概念的引擎 最早現(xiàn)代意義上的搜索引擎出現(xiàn)于 1994年 7月。 隨著互聯(lián)網(wǎng)的迅速發(fā)展，使得檢索所有新出現(xiàn)的網(wǎng)頁變得越來越困難，因此，在 Matthew Gray 的 Wanderer 基礎(chǔ)上，一些編程者將傳統(tǒng)的“蜘蛛”程序工作原理作了些改進(jìn)。世界上第一個(gè)用于監(jiān)測互聯(lián)網(wǎng)發(fā)展規(guī)模的“機(jī)器人”程序是 Matthew Gray 開發(fā)的 World wide Web Wanderer。由于 Archie 深受用戶歡迎，受其啟發(fā)，美國內(nèi)華達(dá) System Computing Services大學(xué)于 1993年開發(fā)了另一個(gè)與之非常相似的搜索工具，不過此時(shí)的搜索工具除了索引文件外，已能檢索網(wǎng)頁。 網(wǎng)絡(luò)爬蟲的歷史和分類 網(wǎng)絡(luò)爬蟲的歷史 在互聯(lián)網(wǎng)發(fā)展初期，網(wǎng)站相對(duì)較少，信息查找比較容易。另外一些不常使用的名字還有螞蟻，自動(dòng)索引，模擬程序或者 蠕蟲 。研究網(wǎng)絡(luò)爬蟲的原理并實(shí)現(xiàn)爬蟲的相關(guān)功能。對(duì) url 進(jìn)行分析，去重。 — 完成論文及答辯 六． 本課題可行性分析 網(wǎng)絡(luò)爬蟲目前已經(jīng)比較普遍，國內(nèi)外有眾多對(duì)網(wǎng)絡(luò)爬蟲的研究成果，大部分的技術(shù)難題已經(jīng)有解決方案。對(duì)網(wǎng)絡(luò)爬蟲的連接網(wǎng)絡(luò)設(shè)置連 接及讀取時(shí)間，避免無限制的等待。 五．研究方法 網(wǎng)絡(luò)爬蟲