【正文】 的兩名博士生， David Filo 和美籍華人楊致遠(yuǎn)（ Gerry Yang）共同創(chuàng)辦了超級目錄索引 Yahoo，并成功地使搜索引擎的概念深入人心。從此搜索引擎進(jìn)入了高速發(fā)展時期。目前，互聯(lián)網(wǎng)上有名有姓的搜索引擎已 達(dá)數(shù)百家，其檢索的信息量也與從前不可同日而語。比如最近風(fēng)頭正勁的 Google，其數(shù)據(jù)庫中存放的網(wǎng)頁已達(dá) 30億之巨。 隨著互聯(lián)網(wǎng)規(guī)模的急劇膨脹，一家搜索引擎光靠自己單 打獨斗已無法適應(yīng)目前的市場狀況，因此現(xiàn)在搜索引擎之間開始出現(xiàn)了分工協(xié)作，并有了專業(yè)的搜索引 擎技術(shù)和搜索數(shù)據(jù)庫服務(wù)提供商。象國外的 Inktomi，它本身并不是直接面向用戶的搜索引擎，但向包括 Overture（原 GoTo）、 LookSmart、 MSN、 HotBot等在內(nèi)的其他搜索引擎提供全文網(wǎng)頁搜索服務(wù)。國內(nèi)的百度也屬于這一類（注），搜狐和新浪用的就是它的技術(shù)。因此 從這個意義上說，它們是搜索引擎的搜索引擎。 網(wǎng)絡(luò)爬蟲的分類 網(wǎng)絡(luò)爬蟲種類繁多，如果按照部署在哪里分，可以分成： 1，服務(wù)器側(cè)： 一般是一個多線程程序，同時下載多個目標(biāo) HTML，可以用 PHP， 3 Java, Python 等做，一般綜合搜索引擎的爬蟲這樣做。但是，如果對方討厭爬蟲，很可能封掉服務(wù)器的 IP，服務(wù)器 IP又不容易改，另外耗用的帶寬也是較貴。 2，客戶端：很適合部署定題爬蟲，或者叫聚焦爬蟲。做一個與 Google，百度等競爭的綜合搜索引擎成功的機會微乎其微，而垂直搜訴或者比價服務(wù)或者推 薦引擎，機會要多得多，這類爬蟲不是什么頁面都取的，而是只取關(guān)心的頁面，而且只取頁面上關(guān)心的內(nèi)容，例如提取黃頁信息，商品價格信息，還有提取競爭對手 廣 告信息的。這類爬蟲可以部署很多，而且可以很有侵略性?？梢缘统杀敬罅坎渴?，由于客戶端 IP地址是動態(tài)的，所以很難被目標(biāo)網(wǎng)站封鎖。 網(wǎng)絡(luò)爬蟲的發(fā)展趨勢 目前，大多數(shù)的搜索引擎都是基于關(guān)鍵詞的搜索引擎?；陉P(guān)鍵字匹配的搜索技術(shù)有較大的局限性：首先，它不能區(qū)分同形異義。其次，不能聯(lián)想到關(guān)鍵字的同義詞。 Web 商業(yè)化至今，搜索引擎始終保持著網(wǎng)絡(luò)上被使用最多的服務(wù)項目的地位，然而，隨著網(wǎng)上內(nèi)容的爆炸式增長和內(nèi)容形式花樣的不斷翻新，搜索引擎越來越不能滿足挑剔的網(wǎng)民們的各種信息需求。 搜索引擎的發(fā)展面臨著兩大 難題：一是如何跟上 Inter 的發(fā)展速度，二是如何為用戶提供更精確的查詢結(jié)果。所以，傳統(tǒng)的引擎不能適應(yīng)信息 技術(shù)的高速發(fā)展，新一代智能搜索引擎作為一種高效搜索引擎技術(shù)的在當(dāng)今的網(wǎng)絡(luò)信息時代日益引起業(yè)界人士的關(guān)注。搜索引擎己成為一個新的研究、開發(fā)領(lǐng)域。因 為它要用到信息檢索、人工智能、計算機網(wǎng)絡(luò)、分布式處理、數(shù)據(jù)庫、數(shù)據(jù)挖掘、數(shù)字圖書館、自然語言處理等多領(lǐng)域的理論和技術(shù)，所以具有綜合性和挑戰(zhàn)性。又 由于搜索引擎有大量的用戶，有很好的經(jīng)濟價值，所以引起了世界各國計算機科學(xué)界和信息產(chǎn)業(yè)界的高度關(guān)注，目前的研究 、開發(fā)十分活躍，并出現(xiàn)了很多值得注意的動向。 目前傳統(tǒng)搜索引擎下，百度、谷歌等大廠商壟斷了網(wǎng)絡(luò)索引市場，因為它們的存在，日益龐大的互聯(lián)網(wǎng)內(nèi)容才能突破網(wǎng)絡(luò)黑暗狀態(tài)，變成可知的一個世界。然而，傳統(tǒng)搜索引擎并不能支持定制搜索和信息處理、挖掘，只能以 形式存在。 可以預(yù)見將來互聯(lián)網(wǎng)信息抓取、挖掘和再處理，將成為人們越來越多的需求，而滿足這種需求的，就是各種各樣的爬蟲與相關(guān)的信息處理工具?，F(xiàn)在網(wǎng)絡(luò)上流 行的信息采集工具、網(wǎng)站聚合工具，都是未來新一代爬蟲的先驅(qū)，甚至已經(jīng)具備其特點。但是互聯(lián)網(wǎng)本身，不 管 ，還沒有為爬蟲時代的到來做好充分 4 準(zhǔn)備。現(xiàn)在游行的 SEO，就是強勢搜索引擎條件下對網(wǎng)站結(jié)構(gòu)產(chǎn)生的影響。爬蟲時代到來之后，互聯(lián)網(wǎng)上會出現(xiàn)專門的信息站點，就是提供給爬蟲看的站點。 傳統(tǒng)的網(wǎng)絡(luò)爬蟲技術(shù)主要應(yīng)用于抓取靜態(tài) Web 網(wǎng)頁，隨著 AJAX/行，如何抓取 AJAX 等動態(tài)頁面成了搜索引擎急需解決的問題，因為 AJAX 顛覆了傳統(tǒng)的純 HTTP 請求 /響應(yīng)協(xié)議機制，如果搜索引擎依舊采用“爬”的機制，是無法抓取到 AJAX 頁面的有效數(shù)據(jù)的。 AJAX 采用了 JavaScript 驅(qū)動的異步請求 /響應(yīng)機制，以往的爬蟲們?nèi)狈avaScript 語義上的理解，基本上無法模擬觸發(fā) JavaScript 的異步調(diào)用并解析返回的異步回調(diào)邏輯和內(nèi)容。 另外，在 AJAX 的應(yīng)用中， JavaScript 會對 DOM 結(jié)構(gòu)進(jìn)行大量變動，甚至頁面所有內(nèi)容都通過 JavaScript 直接從服務(wù)器端讀取并動態(tài)繪制出來。這對習(xí)慣了 DOM 結(jié)構(gòu)相對不變的靜態(tài)頁面簡直是無法理解的。由此可以看出，以往的爬蟲是基于協(xié)議驅(qū)動的，而對于 AJAX 這樣的技術(shù)，所需要的爬蟲引擎必須是基于事件驅(qū)動的。 5 第二章 相 關(guān)技術(shù)背景 網(wǎng)絡(luò)爬蟲的定義 定義 1：網(wǎng)絡(luò)爬蟲是一個自動提取網(wǎng)頁的程序，它為搜索引擎從 Web上下載網(wǎng)頁，是搜索引擎的重要組成部分。通用網(wǎng)絡(luò)爬蟲從一個或若干初始網(wǎng)頁的 URL開始，獲得初始網(wǎng)頁上的 URL 列表；在抓取網(wǎng)頁的過程中，不斷從當(dāng)前頁面上抽取新的 URL 放入待爬行隊列，直到滿足系統(tǒng)的停止條件。 定義 2：主題網(wǎng)絡(luò)爬蟲就是根據(jù)一定的網(wǎng)頁分析算法過濾與主題無關(guān)的鏈接，保留主題相關(guān)的鏈接并將其放入待抓取的 URL 隊列中；然后根據(jù)一定的搜索策略從隊列中選擇下一步要抓取的網(wǎng)頁 URL，并重復(fù)上述過程，直到達(dá) 到系統(tǒng)的某一條件時停止。所有被網(wǎng)絡(luò)爬蟲抓取的網(wǎng)頁將會被系統(tǒng)存儲，進(jìn)行一定的分析、過濾，并建立索引，對于主題網(wǎng)絡(luò)爬蟲來說，這一過程所得到的分析結(jié)果還可能對后續(xù)的抓取過程進(jìn)行反饋和指導(dǎo)。 定義 3：如果網(wǎng)頁 p中包含超鏈接 l，則 p稱為鏈接 l的父網(wǎng)頁。 定義 4：如果超鏈接 l指向網(wǎng)頁 t，則網(wǎng)頁 t稱為子網(wǎng)頁，又稱為目標(biāo)網(wǎng)頁。 主題網(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)頁。 網(wǎng)頁搜索策略介紹 網(wǎng)頁的抓取策略可以分為深度優(yōu)先、廣度優(yōu)先和最佳優(yōu)先三種。深度優(yōu)先在很多情況下會導(dǎo)致爬蟲的陷入 (trapped)問題，目前常見的是廣度優(yōu)先和最佳優(yōu)先方法。 廣度優(yōu)先搜索策略 廣度優(yōu)先搜索 策略 是指在抓取過程中，在完成當(dāng)前層次的搜索后，才進(jìn)行下一層次的搜索。該算法的設(shè)計和實現(xiàn)相對簡單。在目前為覆蓋盡可能多的網(wǎng)頁，一般使用廣度優(yōu)先搜索方法。也有很多研究將 廣度優(yōu)先搜索策略應(yīng)用于聚焦爬蟲中。其基本思想是認(rèn)為與初始 URL 在一定鏈接距離內(nèi)的網(wǎng)頁具有主題相關(guān)性的概率很大。另外一種方法是將廣度優(yōu)先搜索與網(wǎng)頁過濾技術(shù)結(jié)合使用，先用 廣度優(yōu)先策略 抓取網(wǎng)頁，再將其中無關(guān)的網(wǎng)頁過濾掉。這些方法的缺點在于，隨著 6 抓取網(wǎng)頁的增多，大量的無關(guān)網(wǎng)頁將被下載并過濾，算法的效率將變低。 最佳優(yōu)先搜索策略 最佳優(yōu)先搜索策略按照一定的網(wǎng)頁分析算法，預(yù)測候選 URL與目標(biāo)網(wǎng)頁 的相似度，或與主題的相關(guān)性，并選取評價最好的一個或幾個 URL 進(jìn)行抓取。它只訪問經(jīng)過網(wǎng)頁分析算法預(yù)測為“有用”的網(wǎng)頁。存在的一個問題是，在爬蟲抓取路徑上的很多相關(guān)網(wǎng)頁可能被忽略，因為最佳優(yōu)先策略是一種局部最優(yōu)搜索算法。因此需要將最佳優(yōu)先結(jié)合具體的應(yīng)用進(jìn)行改進(jìn)，以跳出局部最優(yōu)點。將在第 4節(jié)中結(jié)合網(wǎng)頁分析算法作具體的討論。研究表明，這樣的閉環(huán)調(diào)整可以將無關(guān)網(wǎng)頁數(shù)量降低 30%~90%。 判斷相關(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ù)頁面，但綜合效果是令人滿意的。因此，主題相關(guān)度的分析是主題爬蟲設(shè)計的關(guān)鍵。 （一）主題相關(guān)度計算模型 垂直搜索引擎與通用搜索引擎最大的區(qū)別在于垂直搜索引擎是面向某個領(lǐng)域的，因而垂直搜索引擎的網(wǎng)絡(luò)蜘蛛只采集與主題相關(guān)的網(wǎng)頁，與主題無關(guān)的網(wǎng)頁將被丟棄，將此類網(wǎng)絡(luò)蜘蛛稱為主題蜘蛛 [68]。主題蜘蛛將網(wǎng)頁下載到本地后，需要使用基于內(nèi)容的主題 判別方法計算該網(wǎng)頁的主題相關(guān)度值，主題相關(guān)度低于某一閾值的網(wǎng)頁被丟棄。主題相關(guān)度的計算方法有布爾模型和向量空間模型兩種模型算法 [10]。 。在主題判別時，布爾模型是很容易實現(xiàn)的。在布爾模型 [9]中，一個文檔通過一個關(guān)鍵詞集合來表示。同時，某個主題也以關(guān)鍵詞集合的形式來表示。在判斷文檔與某主題的相關(guān)度的過程中，相當(dāng)于是計算兩個關(guān)鍵詞集合的交集。對基于布爾模型的主題判別模型來說，交集中含有的元素越多，則認(rèn)為與主題的相關(guān)度就越高。 。向量空間模型 [11]（ Vector Space Model）由 Salton 等人于 20 世紀(jì) 60年代末提出，是一種簡便、高效的文本表示模型，其理論基礎(chǔ)是代數(shù)學(xué)。與布爾模型不同，向量空間模型把用戶的查詢要求和數(shù)據(jù)庫文檔信息表示成由檢索項構(gòu)成的向量空間中的點（向量），而通過計算向量之間的距離來判定文檔和查詢之間的相似程度（例如，用它們之間夾角的余弦作為相似性度量）。 7 然后，根據(jù)相似程度排列查詢結(jié)果。在向量空間模型中，文檔被形式化為 n 維空間中的向量，把關(guān)鍵詞的個數(shù) n 作為空間向量的維數(shù)，每個關(guān)鍵詞的權(quán)值 作為每一維分量的大小，則主題用向量表示為： A=(a1,a2,? ,an),i=1,2,? ,n,ai=wi 對于頁面進(jìn)行分析，統(tǒng)計關(guān)鍵詞出現(xiàn)的頻率，并求出頻率之比，以出現(xiàn)的頻率最高的關(guān)鍵詞作為基準(zhǔn)，其頻率用 xi=1 表示，通過頻率比，求出其他關(guān)鍵詞的頻率 ，則該頁面對應(yīng)向量的每一維分量為 xiwi。指定一個閾值 r，當(dāng) cosα，β =r 時就可以認(rèn)為該頁面和主題是比較相關(guān)的， r 的取值需要根據(jù)經(jīng)驗和實際要求確定，如果想獲得較多的頁面，可以把 r設(shè)小一點，要獲得較少的頁面可以把 r 設(shè)的大一點。 （二）布爾模型與空間向量模型分析 布爾模型的主要缺陷在于每個關(guān)鍵詞的權(quán)重都是 一樣的，它不支持設(shè)定關(guān)鍵詞的相對重要性，但是其優(yōu)點也較為明顯，它易于實現(xiàn)，計算代價較小。 向量空間模型最大優(yōu)點在于它在知識表示方法上的巨大優(yōu)勢。在該模型中，文檔的內(nèi)容被形式化為多維空間中的一個點，以向量的形式給出。也正是因為把文檔以向量的形式定義到實數(shù)域中，才使得模式識別和其他領(lǐng)域中各種成熟的算法和計算方法得以采用，極大地提高了自然語言文檔的可計算性和可操作性。 通過對空間向量模型和布爾模型的介紹，我們知道現(xiàn)在垂直搜索引擎大多采用空間向量模型計算主題相關(guān)性。這樣極大的提高到主題爬蟲的效率，也極大的提 高了垂直搜索引擎的應(yīng)用效率，給客戶帶來了高效的查詢效果。與在進(jìn)行頁面的主題相關(guān)度分析后，當(dāng)其主題相關(guān)度符合要求時將處理該頁面中的所有鏈接，但其中的鏈接指向的頁面也可能有許多偏離了主題，這一點在網(wǎng)頁的標(biāo)題上就可以看出，現(xiàn)在大多數(shù)網(wǎng)頁的標(biāo)題已經(jīng)很明顯的給出了文本的主要描述對象，所以傳統(tǒng)的空間模型策略沒有注意到網(wǎng)頁標(biāo)題這個重要的角色。針對此提出了一種基于網(wǎng)頁標(biāo)題的空間向量模型主題相關(guān)度計算方法。 8 第三章 網(wǎng)絡(luò)爬蟲模型的分析和概要設(shè)計 網(wǎng)絡(luò)爬蟲的模型分析 首先建立 URL 任務(wù)列表，即開始要爬取 的 URL。由 URL任務(wù)列表開始，根據(jù)預(yù)先設(shè)定的深度爬取網(wǎng)頁，同時判斷 URL 是否重復(fù)， 按照一定算法和排序方式搜索頁面，然后對頁面按照一定算法進(jìn)行分析，并提取相關(guān) URL，最后將所得 URL返回任務(wù)列表。之后將任務(wù)列表中 URL 重新開始爬取，從而使網(wǎng)絡(luò)爬蟲進(jìn)行循環(huán)運行。 網(wǎng)絡(luò)爬蟲的搜索策略 本文的搜索策略為廣度優(yōu)先搜索策略。如下圖 31 所示。 圖 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é)點。不同的問題需要用不同的數(shù)據(jù)結(jié)構(gòu)描述。 2）確定結(jié)點的擴展規(guī)則 根據(jù)問題所給定的條件，從一個結(jié)點出發(fā)，可以生成一個或多個新的結(jié)點，這個 9 過程通常稱為擴展。結(jié)點之間的關(guān)系一般可以表示成一棵樹，它被稱為解答樹。搜索算法的搜索過程實際上就是根據(jù)初始條件和擴展規(guī)則構(gòu)造一棵解答樹并尋找符合目標(biāo)狀態(tài)的結(jié)點的過程。 廣度優(yōu)先搜索算法中，解答樹上結(jié)點的擴展是沿結(jié)點深度的“斷層”進(jìn)行，也就是說，結(jié)點的擴展是按它們接近起始結(jié)點的程度依次進(jìn)行的。首先生成第一層結(jié)點，同時檢查目標(biāo)結(jié)點是否在所生成的結(jié)點中，如果不在，則將所有 的第一層結(jié)點逐一擴展，得到第二層結(jié)點，并檢查第二層結(jié)點是否包含目標(biāo)結(jié)點， ...對長度為 n+1 的任一結(jié)點進(jìn)行擴展之前，必須先考慮長度為 n的結(jié)點的每種可能的狀態(tài)。因此，對于同一層結(jié)點來說，求解問題的價值是相同的，我們可以按任意順序來擴展它們。這里采用的原則是先生成的結(jié)點先擴展。 結(jié)點的擴展規(guī)則也就是如何從現(xiàn)有的結(jié)點生成新結(jié)點。對不同的問題，結(jié)點的擴展規(guī)則也不相同，需要按照問題的要求確定。 3）搜索策略 為了便于進(jìn)行搜索