【正文】 首先生成第一層結(jié)點，同時檢查目標(biāo)結(jié)點是否在所生成的結(jié)點中，如果不在，則將所有 的第一層結(jié)點逐一擴展，得到第二層結(jié)點，并檢查第二層結(jié)點是否包含目標(biāo)結(jié)點， ...對長度為 n+1 的任一結(jié)點進(jìn)行擴展之前，必須先考慮長度為 n的結(jié)點的每種可能的狀態(tài)。搜索算法的搜索過程實際上就是根據(jù)初始條件和擴展規(guī)則構(gòu)造一棵解答樹并尋找符合目標(biāo)狀態(tài)的結(jié)點的過程。 2）確定結(jié)點的擴展規(guī)則 根據(jù)問題所給定的條件，從一個結(jié)點出發(fā)，可以生成一個或多個新的結(jié)點，這個 9 過程通常稱為擴展。 圖 31 廣度優(yōu)先搜索策略示意圖 1） 定義一個狀態(tài)結(jié)點 采用廣度優(yōu)先搜索算法解答問題時，需要構(gòu)造一個表明狀態(tài)特征和不同狀態(tài)之間關(guān)系的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié) 構(gòu)稱為結(jié)點。 網(wǎng)絡(luò)爬蟲的搜索策略 本文的搜索策略為廣度優(yōu)先搜索策略。由 URL任務(wù)列表開始，根據(jù)預(yù)先設(shè)定的深度爬取網(wǎng)頁，同時判斷 URL 是否重復(fù)， 按照一定算法和排序方式搜索頁面，然后對頁面按照一定算法進(jìn)行分析，并提取相關(guān) URL，最后將所得 URL返回任務(wù)列表。針對此提出了一種基于網(wǎng)頁標(biāo)題的空間向量模型主題相關(guān)度計算方法。這樣極大的提高到主題爬蟲的效率，也極大的提 高了垂直搜索引擎的應(yīng)用效率，給客戶帶來了高效的查詢效果。也正是因為把文檔以向量的形式定義到實數(shù)域中，才使得模式識別和其他領(lǐng)域中各種成熟的算法和計算方法得以采用，極大地提高了自然語言文檔的可計算性和可操作性。 向量空間模型最大優(yōu)點在于它在知識表示方法上的巨大優(yōu)勢。指定一個閾值 r，當(dāng) cosα，β =r 時就可以認(rèn)為該頁面和主題是比較相關(guān)的， r 的取值需要根據(jù)經(jīng)驗和實際要求確定，如果想獲得較多的頁面，可以把 r設(shè)小一點，要獲得較少的頁面可以把 r 設(shè)的大一點。 7 然后，根據(jù)相似程度排列查詢結(jié)果。向量空間模型 [11]（ Vector Space Model）由 Salton 等人于 20 世紀(jì) 60年代末提出，是一種簡便、高效的文本表示模型，其理論基礎(chǔ)是代數(shù)學(xué)。對基于布爾模型的主題判別模型來說，交集中含有的元素越多，則認(rèn)為與主題的相關(guān)度就越高。同時，某個主題也以關(guān)鍵詞集合的形式來表示。在主題判別時，布爾模型是很容易實現(xiàn)的。主題相關(guān)度的計算方法有布爾模型和向量空間模型兩種模型算法 [10]。 （一）主題相關(guān)度計算模型 垂直搜索引擎與通用搜索引擎最大的區(qū)別在于垂直搜索引擎是面向某個領(lǐng)域的，因而垂直搜索引擎的網(wǎng)絡(luò)蜘蛛只采集與主題相關(guān)的網(wǎng)頁，與主題無關(guān)的網(wǎng)頁將被丟棄，將此類網(wǎng)絡(luò)蜘蛛稱為主題蜘蛛 [68]。 判斷相關(guān)度算法 主題爬蟲的系統(tǒng)組成最初考慮是對頁面的過濾，不像普通爬蟲對所有頁面的鏈接進(jìn)行處理，先對頁面與受限領(lǐng)域的主題相 關(guān)度進(jìn)行分析，只有當(dāng)其主題相關(guān)度符合要求時才處理該頁面中的鏈接，因為如果該頁面和本領(lǐng)域比較相關(guān)，它所包含的鏈接和領(lǐng)域相關(guān)的幾率也較大，這樣提高了爬行精度，雖然會遺漏少數(shù)頁面，但綜合效果是令人滿意的。將在第 4節(jié)中結(jié)合網(wǎng)頁分析算法作具體的討論。存在的一個問題是，在爬蟲抓取路徑上的很多相關(guān)網(wǎng)頁可能被忽略，因為最佳優(yōu)先策略是一種局部最優(yōu)搜索算法。 最佳優(yōu)先搜索策略 最佳優(yōu)先搜索策略按照一定的網(wǎng)頁分析算法，預(yù)測候選 URL與目標(biāo)網(wǎng)頁 的相似度，或與主題的相關(guān)性，并選取評價最好的一個或幾個 URL 進(jìn)行抓取。另外一種方法是將廣度優(yōu)先搜索與網(wǎng)頁過濾技術(shù)結(jié)合使用，先用 廣度優(yōu)先策略 抓取網(wǎng)頁，再將其中無關(guān)的網(wǎng)頁過濾掉。也有很多研究將 廣度優(yōu)先搜索策略應(yīng)用于聚焦爬蟲中。該算法的設(shè)計和實現(xiàn)相對簡單。深度優(yōu)先在很多情況下會導(dǎo)致爬蟲的陷入 (trapped)問題，目前常見的是廣度優(yōu)先和最佳優(yōu)先方法。 主題網(wǎng)絡(luò)爬蟲的基本思路就是按照事先給出的主題，分超鏈接和已經(jīng)下載的網(wǎng)頁內(nèi)容，預(yù)測下一個待抓取的 URL及當(dāng)前網(wǎng)頁的主題相關(guān)度，保證盡可能多地爬行、下載與主相關(guān)的網(wǎng)頁，盡可能少地下載無關(guān)網(wǎng)頁。 定義 3：如果網(wǎng)頁 p中包含超鏈接 l，則 p稱為鏈接 l的父網(wǎng)頁。 定義 2：主題網(wǎng)絡(luò)爬蟲就是根據(jù)一定的網(wǎng)頁分析算法過濾與主題無關(guān)的鏈接，保留主題相關(guān)的鏈接并將其放入待抓取的 URL 隊列中；然后根據(jù)一定的搜索策略從隊列中選擇下一步要抓取的網(wǎng)頁 URL，并重復(fù)上述過程，直到達(dá) 到系統(tǒng)的某一條件時停止。 5 第二章 相 關(guān)技術(shù)背景 網(wǎng)絡(luò)爬蟲的定義 定義 1：網(wǎng)絡(luò)爬蟲是一個自動提取網(wǎng)頁的程序，它為搜索引擎從 Web上下載網(wǎng)頁，是搜索引擎的重要組成部分。這對習(xí)慣了 DOM 結(jié)構(gòu)相對不變的靜態(tài)頁面簡直是無法理解的。 AJAX 采用了 JavaScript 驅(qū)動的異步請求 /響應(yīng)機制，以往的爬蟲們?nèi)狈avaScript 語義上的理解，基本上無法模擬觸發(fā) JavaScript 的異步調(diào)用并解析返回的異步回調(diào)邏輯和內(nèi)容。爬蟲時代到來之后，互聯(lián)網(wǎng)上會出現(xiàn)專門的信息站點，就是提供給爬蟲看的站點。但是互聯(lián)網(wǎng)本身，不 管 ，還沒有為爬蟲時代的到來做好充分 4 準(zhǔn)備。 可以預(yù)見將來互聯(lián)網(wǎng)信息抓取、挖掘和再處理，將成為人們越來越多的需求，而滿足這種需求的，就是各種各樣的爬蟲與相關(guān)的信息處理工具。 目前傳統(tǒng)搜索引擎下，百度、谷歌等大廠商壟斷了網(wǎng)絡(luò)索引市場，因為它們的存在，日益龐大的互聯(lián)網(wǎng)內(nèi)容才能突破網(wǎng)絡(luò)黑暗狀態(tài)，變成可知的一個世界。因 為它要用到信息檢索、人工智能、計算機網(wǎng)絡(luò)、分布式處理、數(shù)據(jù)庫、數(shù)據(jù)挖掘、數(shù)字圖書館、自然語言處理等多領(lǐng)域的理論和技術(shù)，所以具有綜合性和挑戰(zhàn)性。所以，傳統(tǒng)的引擎不能適應(yīng)信息 技術(shù)的高速發(fā)展，新一代智能搜索引擎作為一種高效搜索引擎技術(shù)的在當(dāng)今的網(wǎng)絡(luò)信息時代日益引起業(yè)界人士的關(guān)注。 Web 商業(yè)化至今，搜索引擎始終保持著網(wǎng)絡(luò)上被使用最多的服務(wù)項目的地位，然而，隨著網(wǎng)上內(nèi)容的爆炸式增長和內(nèi)容形式花樣的不斷翻新，搜索引擎越來越不能滿足挑剔的網(wǎng)民們的各種信息需求。基于關(guān)鍵字匹配的搜索技術(shù)有較大的局限性：首先，它不能區(qū)分同形異義?？梢缘统杀敬罅坎渴?，由于客戶端 IP地址是動態(tài)的，所以很難被目標(biāo)網(wǎng)站封鎖。做一個與 Google，百度等競爭的綜合搜索引擎成功的機會微乎其微，而垂直搜訴或者比價服務(wù)或者推 薦引擎，機會要多得多，這類爬蟲不是什么頁面都取的，而是只取關(guān)心的頁面，而且只取頁面上關(guān)心的內(nèi)容，例如提取黃頁信息，商品價格信息，還有提取競爭對手 廣 告信息的。但是，如果對方討厭爬蟲，很可能封掉服務(wù)器的 IP，服務(wù)器 IP又不容易改，另外耗用的帶寬也是較貴。因此 從這個意義上說，它們是搜索引擎的搜索引擎。象國外的 Inktomi，它本身并不是直接面向用戶的搜索引擎，但向包括 Overture（原 GoTo）、 LookSmart、 MSN、 HotBot等在內(nèi)的其他搜索引擎提供全文網(wǎng)頁搜索服務(wù)。比如最近風(fēng)頭正勁的 Google，其數(shù)據(jù)庫中存放的網(wǎng)頁已達(dá) 30億之巨。從此搜索引擎進(jìn)入了高速發(fā)展時期。當(dāng)時 Michael Mauldin 將 John Leavitt 的蜘蛛程序接入到其索引程序中，創(chuàng)建了大家現(xiàn)在熟知的 Lycos。 然而 JumpStation 和 WWW Worm 只是以搜索工具在數(shù)據(jù)庫中找到匹配信息的先后次序排列搜索結(jié)果，因此毫無信息關(guān)聯(lián)度可言。其設(shè)想是，既然所有網(wǎng)頁都可能有連向其他網(wǎng)站的鏈接，那么從跟蹤 一個網(wǎng)站的鏈接開始，就有可能檢索整個互聯(lián)網(wǎng)。 ALIWEB 不使用“機器人”程序，而是靠網(wǎng)站主動提交信息來建立 自己的鏈接索引，類似于現(xiàn)在我們熟知的 Yahoo。剛 2 開始它只用來統(tǒng)計互聯(lián)網(wǎng)上的服務(wù)器數(shù)量，后來則發(fā)展為能夠檢索網(wǎng)站域名。由于專門用于檢索信息的“機器人”程序象蜘蛛一樣在網(wǎng)絡(luò)間爬來爬去，因此， 搜索引擎的“機器人”程序就被稱為“蜘蛛”程序。 當(dāng) 時，“機器人”一詞在編程者中十分流行。雖然當(dāng)時 World Wide Web 還未出現(xiàn)，但網(wǎng)絡(luò)中文件傳輸還是相當(dāng)頻繁的，而且由于大量的文件散布在各個分散的 FTP 主機中，查詢起來非常不便，因此 Alan Archie 工作原理與現(xiàn)在的搜索引擎已經(jīng)很接近，它依靠腳本程序自動搜索網(wǎng)上的文件，然后對有關(guān)信息進(jìn)行索引，供使用者以一定的表達(dá)式查詢。然而伴隨互聯(lián)網(wǎng)爆炸性的發(fā)展，普通網(wǎng)絡(luò)用戶想找到所需的資料簡直如同大海撈針，這時為滿足大眾信息檢索需求的專業(yè)搜索網(wǎng)站便應(yīng)運而生了。最初的檢索功能通過索引站的方式實現(xiàn)，而有了網(wǎng)絡(luò)機器人，即網(wǎng)絡(luò)爬蟲這個技術(shù)之后，搜索引擎的時代便開始一發(fā)不可收拾了。 網(wǎng)絡(luò)檢索功能起于互聯(lián)網(wǎng)內(nèi)容爆炸性發(fā)展所帶來的對內(nèi)容檢索的需求。 multithreading 目 錄 第一章 概述 .................................. 1 課題背景 ...................................... 1 網(wǎng)絡(luò)爬蟲的歷史和分類 .......................... 1 網(wǎng)絡(luò)爬蟲的歷史 .............................. 1 網(wǎng)絡(luò)爬蟲的分類 .............................. 2 網(wǎng)絡(luò)爬蟲的發(fā)展趨勢 ............................ 3 第二章 相關(guān)技術(shù)背景 ........................... 5 網(wǎng)絡(luò)爬蟲的定義 ................................ 5 網(wǎng)頁搜索策略介紹 .............................. 5 廣度優(yōu)先搜索策略 ............................ 5 最佳優(yōu)先搜索策略 ............................ 6 判斷相關(guān)度算法 ................................ 6 第三章 網(wǎng)絡(luò)爬蟲模型的分析和概要設(shè)計 ............ 8 網(wǎng)絡(luò)爬蟲的模型分析 ............................ 8 網(wǎng)絡(luò)爬蟲的搜索策略 ............................ 8 網(wǎng)絡(luò)爬蟲的主題相關(guān)度判斷 ...................... 9 網(wǎng)絡(luò)爬蟲的概要設(shè)計 ........................... 11 第四章 網(wǎng)絡(luò)爬蟲模型的設(shè)計和實現(xiàn) ............... 14 網(wǎng)絡(luò)爬蟲總體設(shè)計 ............................. 14 網(wǎng)絡(luò)爬蟲具體設(shè)計 ............................. 14 爬取網(wǎng)頁 ................................... 14 分析網(wǎng)頁 ................................... 15 判斷相關(guān)度 ................................. 16 保存網(wǎng)頁信息 ............................... 17 數(shù)據(jù)庫設(shè)計和存儲 ........................... 17 多線程的實現(xiàn) ............................... 17 附加功能 ................................... 18 整體流程 ................................... 18 第五章 測試 .................................. 20 第六章 總結(jié)和展望 ............................ 24 1 第一章 概述 課題背景 網(wǎng)絡(luò)爬蟲，是一種按照一定的規(guī)則，自動的抓取萬維網(wǎng)信息的程序或者 腳本 。 關(guān)鍵詞： 網(wǎng)絡(luò)爬蟲；面向主題；多線程 ABSTRACT The main purpose of this project is to design subjectoriented web crawler process which is also required to meet certain performance, taking into account the diverse needs of web crawlers. Web Crawler uses the technology. of Breadthfirst crawler uses multithreaded technology, so that spiders crawl can have more powerful connection time and read time of the web connection of the Web crawler , to avoid unlimited order to meet different needs, so that crawlers can achieve pres