【文章內(nèi)容簡(jiǎn)介】 搜索引擎并不能支持定制搜索和信息處理、挖掘，只能以 形式存在。 可以預(yù)見(jiàn)將來(lái)互聯(lián)網(wǎng)信息抓取、挖掘和再處理，將成為人們?cè)絹?lái)越多的需求，而滿足這種需求的，就是各種各樣的爬蟲(chóng)與相關(guān)的信息處理工具?，F(xiàn)在網(wǎng)絡(luò)上流 行的信息采集工具、網(wǎng)站聚合工具，都是未來(lái)新一代爬蟲(chóng)的先驅(qū)，甚至已經(jīng)具備其特點(diǎn)。但是互聯(lián)網(wǎng)本身，不 管 ，還沒(méi)有為爬蟲(chóng)時(shí)代的到來(lái)做好充分 4 準(zhǔn)備?，F(xiàn)在游行的 SEO，就是強(qiáng)勢(shì)搜索引擎條件下對(duì)網(wǎng)站結(jié)構(gòu)產(chǎn)生的影響。爬蟲(chóng)時(shí)代到來(lái)之后，互聯(lián)網(wǎng)上會(huì)出現(xiàn)專(zhuān)門(mén)的信息站點(diǎn)，就是提供給爬蟲(chóng)看的站點(diǎn)。 傳統(tǒng)的網(wǎng)絡(luò)爬蟲(chóng)技術(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ī)制，以往的爬蟲(chóng)們?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ú)法理解的。由此可以看出，以往的爬蟲(chóng)是基于協(xié)議驅(qū)動(dòng)的，而對(duì)于 AJAX 這樣的技術(shù)，所需要的爬蟲(chóng)引擎必須是基于事件驅(qū)動(dòng)的。 5 第二章 相 關(guān)技術(shù)背景 網(wǎng)絡(luò)爬蟲(chóng)的定義 定義 1：網(wǎng)絡(luò)爬蟲(chóng)是一個(gè)自動(dòng)提取網(wǎng)頁(yè)的程序，它為搜索引擎從 Web上下載網(wǎng)頁(yè)，是搜索引擎的重要組成部分。通用網(wǎng)絡(luò)爬蟲(chóng)從一個(gè)或若干初始網(wǎng)頁(yè)的 URL開(kāi)始，獲得初始網(wǎng)頁(yè)上的 URL 列表；在抓取網(wǎng)頁(yè)的過(guò)程中，不斷從當(dāng)前頁(yè)面上抽取新的 URL 放入待爬行隊(duì)列，直到滿足系統(tǒng)的停止條件。 定義 2：主題網(wǎng)絡(luò)爬蟲(chóng)就是根據(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ò)爬蟲(chóng)抓取的網(wǎng)頁(yè)將會(huì)被系統(tǒng)存儲(chǔ)，進(jìn)行一定的分析、過(guò)濾，并建立索引，對(duì)于主題網(wǎng)絡(luò)爬蟲(chóng)來(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ò)爬蟲(chóng)的基本思路就是按照事先給出的主題，分超鏈接和已經(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)致爬蟲(chóng)的陷入 (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)用于聚焦爬蟲(chó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)題是，在爬蟲(chóng)抓取路徑上的很多相關(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)度算法 主題爬蟲(chóng)的系統(tǒng)組成最初考慮是對(duì)頁(yè)面的過(guò)濾，不像普通爬蟲(chóng)對(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)度的分析是主題爬蟲(chóng)設(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è)將被丟棄，將此類(lèi)網(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)性。這樣極大的提高到主題爬蟲(chóng)的效率，也極大的提 高了垂直搜索引擎的應(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ò)爬蟲(chóng)模型的分析和概要設(shè)計(jì) 網(wǎng)絡(luò)爬蟲(chóng)的模型分析 首先建立 URL 任務(wù)列表，即開(kāi)始要爬取 的 URL。由 URL任務(wù)列表開(kāi)始，根據(jù)預(yù)先設(shè)定的深度爬取網(wǎng)頁(yè)，同時(shí)判斷 URL 是否重復(fù)， 按照一定算法和排序方式搜索頁(yè)面，然后對(duì)頁(yè)面按照一定算法進(jìn)行分析，并提取相關(guān) URL，最后將所得 URL返回任務(wù)列表。之后將任務(wù)列表中 URL 重新開(kāi)始爬取，從而使網(wǎng)絡(luò)爬蟲(chóng)進(jìn)行循環(huán)運(yùn)行。 網(wǎng)絡(luò)爬蟲(chóng)的搜索策略 本文的搜索策略為廣度優(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)系一般可以表示成一棵樹(shù)，它被稱為解答樹(shù)。搜索算法的搜索過(guò)程實(shí)際上就是根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一棵解答樹(shù)并尋找符合目標(biāo)狀態(tài)的結(jié)點(diǎn)的過(guò)程。 廣度優(yōu)先搜索算法中，解答樹(shù)上結(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)生成