【正文】 的兩名博士生， David Filo 和美籍華人楊致遠(yuǎn)（ Gerry Yang）共同創(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ú)斗已無(wú)法適應(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è)意義上說(shuō)，它們是搜索引擎的搜索引擎。 網(wǎng)絡(luò)爬蟲的分類 網(wǎng)絡(luò)爬蟲種類繁多，如果按照部署在哪里分，可以分成： 1，服務(wù)器側(cè)： 一般是一個(gè)多線程程序，同時(shí)下載多個(gè)目標(biāo) HTML，可以用 PHP， 3 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ì)手 廣 告信息的。這類爬蟲可以部署很多，而且可以很有侵略性。可以低成本大量部署，由于客戶端 IP地址是動(dòng)態(tài)的，所以很難被目標(biāo)網(wǎng)站封鎖。 網(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)容形式花樣的不斷翻新，搜索引擎越來(lái)越不能滿足挑剔的網(wǎng)民們的各種信息需求。 搜索引擎的發(fā)展面臨著兩大 難題：一是如何跟上 Inter 的發(fā)展速度，二是如何為用戶提供更精確的查詢結(jié)果。所以，傳統(tǒng)的引擎不能適應(yīng)信息 技術(shù)的高速發(fā)展，新一代智能搜索引擎作為一種高效搜索引擎技術(shù)的在當(dāng)今的網(wǎng)絡(luò)信息時(shí)代日益引起業(yè)界人士的關(guān)注。搜索引擎己成為一個(gè)新的研究、開發(fā)領(lǐng)域。因 為它要用到信息檢索、人工智能、計(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)搜索引擎并不能支持定制搜索和信息處理、挖掘，只能以 形式存在。 可以預(yù)見(jiàn)將來(lái)互聯(lián)網(wǎng)信息抓取、挖掘和再處理，將成為人們?cè)絹?lái)越多的需求，而滿足這種需求的，就是各種各樣的爬蟲與相關(guān)的信息處理工具?，F(xiàn)在網(wǎng)絡(luò)上流 行的信息采集工具、網(wǎng)站聚合工具，都是未來(lái)新一代爬蟲的先驅(qū)，甚至已經(jīng)具備其特點(diǎn)。但是互聯(lián)網(wǎng)本身，不 管 ，還沒(méi)有為爬蟲時(shí)代的到來(lái)做好充分 4 準(zhǔn)備?，F(xiàn)在游行的 SEO，就是強(qiáng)勢(shì)搜索引擎條件下對(duì)網(wǎng)站結(jié)構(gòu)產(chǎn)生的影響。爬蟲時(shí)代到來(lái)之后，互聯(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/行，如何抓取 AJAX 等動(dòng)態(tài)頁(yè)面成了搜索引擎急需解決的問(wèn)題，因?yàn)?AJAX 顛覆了傳統(tǒng)的純 HTTP 請(qǐng)求 /響應(yīng)協(xié)議機(jī)制，如果搜索引擎依舊采用“爬”的機(jī)制，是無(wú)法抓取到 AJAX 頁(yè)面的有效數(shù)據(jù)的。 AJAX 采用了 JavaScript 驅(qū)動(dòng)的異步請(qǐng)求 /響應(yīng)機(jī)制，以往的爬蟲們?nèi)狈avaScript 語(yǔ)義上的理解，基本上無(wú)法模擬觸發(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)容都通過(guò) JavaScript 直接從服務(wù)器端讀取并動(dòng)態(tài)繪制出來(lái)。這對(duì)習(xí)慣了 DOM 結(jié)構(gòu)相對(duì)不變的靜態(tài)頁(yè)面簡(jiǎn)直是無(wú)法理解的。由此可以看出，以往的爬蟲是基于協(xié)議驅(qū)動(dòng)的，而對(duì)于 AJAX 這樣的技術(shù)，所需要的爬蟲引擎必須是基于事件驅(qū)動(dòng)的。 5 第二章 相 關(guān)技術(shù)背景 網(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è)的過(guò)程中，不斷從當(dāng)前頁(yè)面上抽取新的 URL 放入待爬行隊(duì)列，直到滿足系統(tǒng)的停止條件。 定義 2：主題網(wǎng)絡(luò)爬蟲就是根據(jù)一定的網(wǎng)頁(yè)分析算法過(guò)濾與主題無(wú)關(guān)的鏈接，保留主題相關(guān)的鏈接并將其放入待抓取的 URL 隊(duì)列中；然后根據(jù)一定的搜索策略從隊(duì)列中選擇下一步要抓取的網(wǎng)頁(yè) URL，并重復(fù)上述過(guò)程，直到達(dá) 到系統(tǒng)的某一條件時(shí)停止。所有被網(wǎng)絡(luò)爬蟲抓取的網(wǎng)頁(yè)將會(huì)被系統(tǒng)存儲(chǔ)，進(jìn)行一定的分析、過(guò)濾，并建立索引，對(duì)于主題網(wǎng)絡(luò)爬蟲來(lái)說(shuō)，這一過(guò)程所得到的分析結(jié)果還可能對(duì)后續(xù)的抓取過(guò)程進(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è)，盡可能少地下載無(wú)關(guān)網(wǎng)頁(yè)。 網(wǎng)頁(yè)搜索策略介紹 網(wǎng)頁(yè)的抓取策略可以分為深度優(yōu)先、廣度優(yōu)先和最佳優(yōu)先三種。深度優(yōu)先在很多情況下會(huì)導(dǎo)致爬蟲的陷入 (trapped)問(wèn)題，目前常見(jiàn)的是廣度優(yōu)先和最佳優(yōu)先方法。 廣度優(yōu)先搜索策略 廣度優(yōu)先搜索 策略 是指在抓取過(guò)程中，在完成當(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è)過(guò)濾技術(shù)結(jié)合使用，先用 廣度優(yōu)先策略 抓取網(wǎng)頁(yè)，再將其中無(wú)關(guān)的網(wǎng)頁(yè)過(guò)濾掉。這些方法的缺點(diǎn)在于，隨著 6 抓取網(wǎng)頁(yè)的增多，大量的無(wú)關(guān)網(wǎng)頁(yè)將被下載并過(guò)濾，算法的效率將變低。 最佳優(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)行抓取。它只訪問(wèn)經(jīng)過(guò)網(wǎng)頁(yè)分析算法預(yù)測(cè)為“有用”的網(wǎng)頁(yè)。存在的一個(gè)問(wèn)題是，在爬蟲抓取路徑上的很多相關(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)整可以將無(wú)關(guān)網(wǎng)頁(yè)數(shù)量降低 30%~90%。 判斷相關(guān)度算法 主題爬蟲的系統(tǒng)組成最初考慮是對(duì)頁(yè)面的過(guò)濾，不像普通爬蟲對(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è)，與主題無(wú)關(guān)的網(wǎng)頁(yè)將被丟棄，將此類網(wǎng)絡(luò)蜘蛛稱為主題蜘蛛 [68]。主題蜘蛛將網(wǎng)頁(yè)下載到本地后，需要使用基于內(nèi)容的主題 判別方法計(jì)算該網(wǎng)頁(yè)的主題相關(guān)度值，主題相關(guān)度低于某一閾值的網(wǎng)頁(yè)被丟棄。主題相關(guān)度的計(jì)算方法有布爾模型和向量空間模型兩種模型算法 [10]。 。在主題判別時(shí)，布爾模型是很容易實(shí)現(xiàn)的。在布爾模型 [9]中，一個(gè)文檔通過(guò)一個(gè)關(guān)鍵詞集合來(lái)表示。同時(shí)，某個(gè)主題也以關(guān)鍵詞集合的形式來(lái)表示。在判斷文檔與某主題的相關(guān)度的過(guò)程中，相當(dāng)于是計(jì)算兩個(gè)關(guān)鍵詞集合的交集。對(duì)基于布爾模型的主題判別模型來(lái)說(shuō)，交集中含有的元素越多，則認(rèn)為與主題的相關(guān)度就越高。 。向量空間模型 [11]（ Vector Space Model）由 Salton 等人于 20 世紀(jì) 60年代末提出，是一種簡(jiǎn)便、高效的文本表示模型，其理論基礎(chǔ)是代數(shù)學(xué)。與布爾模型不同，向量空間模型把用戶的查詢要求和數(shù)據(jù)庫(kù)文檔信息表示成由檢索項(xiàng)構(gòu)成的向量空間中的點(diǎn)（向量），而通過(guò)計(jì)算向量之間的距離來(lái)判定文檔和查詢之間的相似程度（例如，用它們之間夾角的余弦作為相似性度量）。 7 然后，根據(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ò)頻率比，求出其他關(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ì)算性和可操作性。 通過(guò)對(duì)空間向量模型和布爾模型的介紹，我們知道現(xiàn)在垂直搜索引擎大多采用空間向量模型計(jì)算主題相關(guān)性。這樣極大的提高到主題爬蟲的效率，也極大的提 高了垂直搜索引擎的應(yīng)用效率，給客戶帶來(lái)了高效的查詢效果。與在進(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)的空間模型策略沒(méi)有注意到網(wǎng)頁(yè)標(biāo)題這個(gè)重要的角色。針對(duì)此提出了一種基于網(wǎng)頁(yè)標(biāo)題的空間向量模型主題相關(guān)度計(jì)算方法。 8 第三章 網(wǎng)絡(luò)爬蟲模型的分析和概要設(shè)計(jì) 網(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)行。 網(wǎng)絡(luò)爬蟲的搜索策略 本文的搜索策略為廣度優(yōu)先搜索策略。如下圖 31 所示。 圖 31 廣度優(yōu)先搜索策略示意圖 1） 定義一個(gè)狀態(tài)結(jié)點(diǎn) 采用廣度優(yōu)先搜索算法解答問(wèn)題時(shí)，需要構(gòu)造一個(gè)表明狀態(tài)特征和不同狀態(tài)之間關(guān)系的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié) 構(gòu)稱為結(jié)點(diǎn)。不同的問(wèn)題需要用不同的數(shù)據(jù)結(jié)構(gòu)描述。 2）確定結(jié)點(diǎn)的擴(kuò)展規(guī)則 根據(jù)問(wèn)題所給定的條件，從一個(gè)結(jié)點(diǎn)出發(fā)，可以生成一個(gè)或多個(gè)新的結(jié)點(diǎn)，這個(gè) 9 過(guò)程通常稱為擴(kuò)展。結(jié)點(diǎn)之間的關(guān)系一般可以表示成一棵樹，它被稱為解答樹。搜索算法的搜索過(guò)程實(shí)際上就是根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一棵解答樹并尋找符合目標(biāo)狀態(tài)的結(jié)點(diǎn)的過(guò)程。 廣度優(yōu)先搜索算法中，解答樹上結(jié)點(diǎn)的擴(kuò)展是沿結(jié)點(diǎn)深度的“斷層”進(jìn)行，也就是說(shuō)，結(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)來(lái)說(shuō)，求解問(wèn)題的價(jià)值是相同的，我們可以按任意順序來(lái)擴(kuò)展它們。這里采用的原則是先生成的結(jié)點(diǎn)先擴(kuò)展。 結(jié)點(diǎn)的擴(kuò)展規(guī)則也就是如何從現(xiàn)有的結(jié)點(diǎn)生成新結(jié)點(diǎn)。對(duì)不同的問(wèn)題，結(jié)點(diǎn)的擴(kuò)展規(guī)則也不相同，需要按照問(wèn)題的要求確定。 3）搜索策略 為了便于進(jìn)行搜索