□李耀華，楊海燕

(1.山西大學(xué)繼續(xù)教育學(xué)院，山西 太原 030006;2.山西廣播電視大學(xué)，山西 太原 030027)

網(wǎng)絡(luò)爬蟲是搜索引擎的重要組成部分。搜索引擎借助于網(wǎng)絡(luò)爬蟲才能在互聯(lián)網(wǎng)海量數(shù)據(jù)中有效搜集到相關(guān)的網(wǎng)頁信息。如何提高網(wǎng)絡(luò)爬蟲的搜索效率，是該領(lǐng)域研究的熱點(diǎn)。本文將分別對目前常用的網(wǎng)絡(luò)爬蟲的搜索策略進(jìn)行初步分析研究。

一、網(wǎng)絡(luò)爬蟲基本工作原理

網(wǎng)絡(luò)爬蟲Web Spider又叫Web Crawler或者Robot，是一個(gè)沿著鏈接漫游web文檔集合的程序。它一般駐留在服務(wù)器上，并且利用標(biāo)準(zhǔn)的http協(xié)議根據(jù)超鏈接和web文檔檢索的方法遍歷整個(gè)Internet網(wǎng)信息進(jìn)行搜索。

(一)網(wǎng)絡(luò)爬蟲的基本結(jié)構(gòu)。傳統(tǒng)的網(wǎng)絡(luò)爬蟲包括一個(gè)協(xié)議處理模塊。URL(統(tǒng)一資源定位符，Uniform Resource Locator的縮寫，也被稱為網(wǎng)頁地址，是因特網(wǎng)上標(biāo)準(zhǔn)的資源的地址。它最初是由Tim Berners－Lee發(fā)明用來作為萬維網(wǎng)的地址的)由兩部分構(gòu)成:協(xié)議模塊和檢測模塊。其中，協(xié)議模塊用來提供網(wǎng)絡(luò)爬蟲所需的網(wǎng)絡(luò)協(xié)議，解決如何獲取網(wǎng)頁;檢測模塊負(fù)責(zé)對采集的URL信息進(jìn)行排序，處理網(wǎng)絡(luò)上重復(fù)內(nèi)容，以提高網(wǎng)絡(luò)爬蟲的搜索效率。

(二)網(wǎng)絡(luò)爬蟲的工作流程。網(wǎng)絡(luò)爬蟲也是一個(gè)自動(dòng)提取網(wǎng)頁的程序，是搜索引擎的重要組成部分，其作用是為搜索引擎從Internet網(wǎng)上下載頁面。網(wǎng)絡(luò)爬蟲在獲取網(wǎng)絡(luò)信息時(shí)，通常會(huì)從一個(gè)“種子集”出發(fā)，獲得初始網(wǎng)頁上的URL，下載頁面并提取已下載頁面中的連接，抽取新的URL放入隊(duì)列，然后訪問提取出的連接所對應(yīng)的網(wǎng)頁，如此不斷重復(fù)便可遍歷整個(gè)網(wǎng)絡(luò)信息，直到滿足系統(tǒng)的一定停止條件。其中，種子集指種子鏈接集合，通常為幾個(gè)知名網(wǎng)站主頁連接地址。工作流程如圖1所示。但通用爬蟲搜索有以下幾方面不足:

圖1 通用網(wǎng)絡(luò)爬蟲工作流程圖

(1)因?yàn)樽ト〉哪繕?biāo)是覆蓋盡可能大的網(wǎng)絡(luò)，所以爬行的結(jié)果中必然會(huì)包含大量用戶不需要的網(wǎng)頁;

(2)無法很好地搜索和獲取信息含量密集而且具有一定結(jié)構(gòu)的數(shù)據(jù);

(3)通用搜索引擎大多是基于關(guān)鍵字的檢索，對于支持語義信息的查詢和索引擎智能化的要求則難以實(shí)現(xiàn)。

由此，通用爬蟲想在爬行網(wǎng)頁時(shí)，既保證網(wǎng)頁的質(zhì)量和數(shù)量，又要保證網(wǎng)頁的時(shí)效性是很難實(shí)現(xiàn)的。

(三)網(wǎng)絡(luò)爬蟲的搜索策略。為提高網(wǎng)絡(luò)爬蟲的搜索效率，網(wǎng)絡(luò)爬蟲需要在既定時(shí)間內(nèi)搜索到盡可能多的高質(zhì)量網(wǎng)頁，這是其面臨的主要技術(shù)難題。

一般而言，有五種方式表示頁面質(zhì)量的高低:Similarity(頁與爬行主題之間的相似度)、Backlink(面在Web圖中的入度大小)、PageRank(指向它的所有頁面平均權(quán)值之和)、For-wardlink(頁面在Web圖中的出度大小)、Location(頁面的信息位置);Parallel(并行性問題)。

搜索策略就是指提取出頁面鏈接后如何訪問。通用的搜索引擎往往希望得到較高的網(wǎng)絡(luò)覆蓋率，所以常采用遍歷的方式進(jìn)行訪問，見圖2。相反，主題搜索引擎的服務(wù)范圍則是限制在特定的人群和主題范圍內(nèi)，通常采用“最好優(yōu)先”的原則，選擇最有價(jià)值的連接進(jìn)行訪問，見圖3，其關(guān)鍵就在于如何評價(jià)最有價(jià)值的連接。

圖2

圖3

二、遍歷搜索策略

該搜索策略對所有提取出的鏈接都一一進(jìn)行爬取，目的在于遍歷網(wǎng)絡(luò)上的所有信息資源。

(一)寬度優(yōu)先策略。寬度優(yōu)先搜索(Breadth－First Search)是一種簡便常用的搜索算法(又稱廣度優(yōu)先搜索)。這一算法也是其他很多重要算法之原型，其主要用來解決最優(yōu)解問題。其基本思想是:從起始網(wǎng)頁源頂點(diǎn)p開始，沿著樹的寬度遍歷樹的每一個(gè)節(jié)點(diǎn)，獲取相關(guān)所有鏈接網(wǎng)頁，進(jìn)而再沿這些節(jié)點(diǎn)繼續(xù)抓取該網(wǎng)頁中的所有鏈接頁面，最終遍歷所有頂點(diǎn)。即，首先完成一個(gè)層次的搜索，其次再進(jìn)行下一層次的搜索，也稱之為分層處理。該算法的設(shè)計(jì)模式和技術(shù)實(shí)現(xiàn)比較簡單且能獲得較高的網(wǎng)頁覆蓋率，但該算法的設(shè)計(jì)和實(shí)現(xiàn)相對簡單，屬于盲目搜索，因而效率較低。換句話說，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。為盡可能覆蓋較多網(wǎng)頁，寬度優(yōu)先搜索方法是較好的選擇。

(二)深度優(yōu)先策略。深度優(yōu)先搜索(Depth－First Search)，也是一種早期在開發(fā)爬蟲過程中使用較多的方法。其設(shè)計(jì)思路是盡量“深”入地搜索信息資源。在深度優(yōu)先搜索中，針對最新發(fā)現(xiàn)的網(wǎng)頁源頂點(diǎn)p，如果它還有以此為起點(diǎn)而尚未搜索到的路徑，則沿此路徑繼續(xù)搜索下去。反之，如果當(dāng)頂點(diǎn)p的所有路徑均己被搜索過，則回溯到初始點(diǎn)。這一搜索過程將一直持續(xù)到已發(fā)現(xiàn)的從源頂點(diǎn)p可達(dá)到的所有頂點(diǎn)為止。但是如果仍然存在未被發(fā)現(xiàn)的頂點(diǎn)p’，則繼續(xù)選擇其中一個(gè)作為源頂點(diǎn)并重復(fù)以上過程，最終實(shí)現(xiàn)所有頂點(diǎn)都被遍歷。

但是深度優(yōu)先策略不足之處是，深度優(yōu)先策略在很多情況下會(huì)導(dǎo)致網(wǎng)絡(luò)爬蟲的陷入問題(trapped)，導(dǎo)致盲目搜索。

三、最好優(yōu)先策略

“最好優(yōu)先”(Best－First Search)的爬蟲也稱聚集爬蟲，是根據(jù)相關(guān)網(wǎng)頁分析算法，預(yù)測候選URL與目標(biāo)網(wǎng)頁的相似度，根據(jù)“最好優(yōu)先”原則進(jìn)行訪問，選取評價(jià)最好的一個(gè)或幾個(gè)URL，以便快速、有效地獲得更多的與目標(biāo)網(wǎng)頁相似度高的頁面進(jìn)行抓取。最好優(yōu)先策略只訪問經(jīng)過網(wǎng)頁分析算法預(yù)測為“有用”的網(wǎng)頁。專業(yè)的搜索引擎網(wǎng)絡(luò)爬蟲通常會(huì)采用“最好優(yōu)先”原則訪問WEB。但由于所有搜索鏈接均包含在相關(guān)網(wǎng)頁中，因此頁面價(jià)值往往與頁面內(nèi)鏈接價(jià)值存在正相關(guān)關(guān)系，于是對鏈接價(jià)值的評價(jià)有時(shí)也可轉(zhuǎn)換為對頁面價(jià)值的評價(jià)。

但最好優(yōu)先策略存在一個(gè)問題:因最佳優(yōu)先策略只是一種局部最優(yōu)搜索算法，所以網(wǎng)絡(luò)爬蟲在抓取有用信息的過程路徑上會(huì)有很多相關(guān)網(wǎng)頁被忽略。因此該策略在應(yīng)用時(shí)應(yīng)結(jié)合具體情況進(jìn)行必要改進(jìn)，以跳出局部最優(yōu)點(diǎn)。

(一)基于內(nèi)容評價(jià)的搜索策略?；ヂ?lián)網(wǎng)上不良信息、不安全信息日益增多已成為危害社會(huì)的嚴(yán)重問題，對互聯(lián)網(wǎng)信息內(nèi)容進(jìn)行必要的監(jiān)控成為一項(xiàng)迫切任務(wù)。而網(wǎng)絡(luò)爬蟲在信息搜索中起著明顯的作用。

基于內(nèi)容評價(jià)的搜索策略是根據(jù)搜索內(nèi)容的主題與被鏈接網(wǎng)頁文本的相似度來評價(jià)鏈接價(jià)值的高與低，進(jìn)而決定搜索策略。其中，相似度評價(jià)通常一般采用以下公式:

其中，di為新獲取文本的特征向量值，dj為第j類鏈接文本的中心向量值，m為特征向量di的維數(shù)，wk為向量w的第k維。

基于內(nèi)容評價(jià)的搜索策略并不只有這一種計(jì)算方法，除上述公式外，還有 Best－First Search，F(xiàn)ish Search和 Shark Search算法。

(二)基于鏈接結(jié)構(gòu)評價(jià)的搜索策略。基于鏈接結(jié)構(gòu)評價(jià)的搜索策略屬于web頁面的半結(jié)構(gòu)化設(shè)計(jì)，通過對頁面間的超鏈接進(jìn)行關(guān)聯(lián)分析其引用關(guān)系來確定鏈接的重要性，由此確定鏈接訪問的次序。因此這種結(jié)構(gòu)化特征使文本鏈接的重要性可通過鏈接分析來加以確定，主要根據(jù)文獻(xiàn)計(jì)量學(xué)的引文分析理論來進(jìn)行。常規(guī)認(rèn)為有較多入鏈或出鏈的頁面具有較高的價(jià)值。PageRank算法和Hits算法是其中具有代表性的算法。

1.PageRank(網(wǎng)頁級(jí)別)算法。PageRank算法是Google創(chuàng)始人Larry Page和Sergey Brin于1997年構(gòu)建早期的搜索系統(tǒng)原型時(shí)提出的鏈接分析算法。該算法隨著Google在商業(yè)上獲得巨大成功后成為其它搜索引擎和學(xué)界所關(guān)注的計(jì)算模型?？梢哉fPageRank算法是后來很多鏈接分析算法的基礎(chǔ)。

例如Google搜索引擎信息檢索中對查詢結(jié)果的排序過程。其對web頁面的排序，在揉合了諸如Title標(biāo)識(shí)和Keywords標(biāo)識(shí)等所有其它因素之后，根據(jù)搜索的信息內(nèi)容在頁面中的出現(xiàn)次數(shù)，并用頁面長度和html標(biāo)簽的重要性提示等進(jìn)行權(quán)重修訂。使那些更具等級(jí)的網(wǎng)頁在搜索結(jié)果中的排名獲得提升，最終提高搜索結(jié)果相關(guān)性和搜索質(zhì)量。近年來被應(yīng)用于網(wǎng)絡(luò)爬蟲對鏈接重要性的評價(jià)。Google通過PageRank來調(diào)整結(jié)果，其級(jí)別從0到10級(jí)，10級(jí)為滿分。鏈接提供的頁面越重要?jiǎng)t此鏈入值越高。此外，還可通過其它文檔鏈接到當(dāng)前頁面的鏈接數(shù)量來確定當(dāng)前頁面的重要性，這樣可以有效地抵制那些被人為加工過的頁面欺騙搜索引擎的手法。

該算法中，通常用PageRank值表示頁面的價(jià)值，若設(shè)頁面p的PageRank值為PR(p)，則PR(p)用如下公式表示:

其中:T為所計(jì)算中頁面總量，γ＜1為阻尼系數(shù)，in(p)為所有指向頁面p的集合，out(γ)為頁面γ出鏈的集合。按照PageRank算法，爬蟲在信息搜索過程中，通過計(jì)算已訪問頁面的PageRank值來確定頁面的重要性，并確定訪問次序。

2.Hits算法。1997年康奈爾大學(xué)(Cornell University)的Jon Kleinberg首次提出了Hits算法(Hyperlink－Induced Topic Search)。Hits算法也是Web結(jié)構(gòu)挖掘中最具有權(quán)威性和使用最廣泛的算法之一。該算法中引入了兩個(gè)重要的概念:內(nèi)容權(quán)威度(Authority Scores)和鏈接權(quán)威度(Hub Scores)來對網(wǎng)頁質(zhì)量進(jìn)行評估。其基本思想是利用頁面之間的引用鏈來挖掘隱含在其中的有用信息，具有計(jì)算簡單且效率高的特點(diǎn)。

Hits算法中網(wǎng)頁的Authority值表示所有導(dǎo)入鏈接所在的頁面的Hub值之和，即一個(gè)頁面被其它頁面所引用的次數(shù)，被其它頁面引用的次數(shù)越多，則這個(gè)頁面的Authority值就會(huì)越大;頁面的Hub值表示指的是頁面上所有導(dǎo)出鏈接指向頁面的Authority值之和，一個(gè)頁面指向其他頁面的次數(shù)，指向其它頁面的次數(shù)越多，這個(gè)頁面的Hub值就會(huì)越大。由于在Hub值高的頁面中通常都包含了指向Authority頁面的鏈接，因而能夠起到說明頁面權(quán)威性的作用。Hits算法正是利用這種相互關(guān)系來發(fā)現(xiàn)Authority頁面的。

(三)基于鞏固學(xué)習(xí)的搜索策略。相關(guān)研究表明，多數(shù)類似網(wǎng)站在設(shè)計(jì)方式上，同類網(wǎng)頁存在一定相似性，因而有人將鞏固學(xué)習(xí)(Reinforcement Learning)搜索策略引入到網(wǎng)絡(luò)爬蟲的研究中以減小搜索空間，提高效率。在該模型中，將網(wǎng)絡(luò)爬蟲遍歷無關(guān)頁面訪問后才能獲得的主題頁面稱之為未來回報(bào)，即搜索到隱含的結(jié)構(gòu)信息。在綜合考量計(jì)算立即回報(bào)價(jià)值和未來回報(bào)價(jià)值結(jié)合的前提下確定正確的搜索方向。

隨著互聯(lián)網(wǎng)技術(shù)的廣泛應(yīng)用，互聯(lián)網(wǎng)信息量的海量增長使傳統(tǒng)的通用搜索引擎面臨著巨大的挑戰(zhàn)，各類針對特定人群的“專業(yè)搜索引擎”便應(yīng)運(yùn)而生。網(wǎng)絡(luò)爬蟲搜索就是典型代表。網(wǎng)絡(luò)爬蟲各類搜索策略各有利弊，尚無單一標(biāo)準(zhǔn)去評價(jià)其優(yōu)劣。互聯(lián)網(wǎng)搜索問題屬于“多目標(biāo)”規(guī)劃問題。降低計(jì)算的復(fù)雜程度，提高搜索鏈接價(jià)值的準(zhǔn)確性，增加網(wǎng)絡(luò)爬蟲的自適應(yīng)能力，是提高網(wǎng)絡(luò)爬蟲效率的核心問題。

［1］歐陽柳波等.專業(yè)搜索引擎搜索策略綜述［J］.計(jì)算機(jī)工程，2004，(30):32 －33.

［2］李勇，韓亮.主題搜索引擎中網(wǎng)絡(luò)爬蟲的搜索策略研究［J］.計(jì)算機(jī)工程與科學(xué)，2008，(3):4 －6.

［3］歐陽柳波等.網(wǎng)絡(luò)蜘蛛搜索策略進(jìn)展研究［J］.小型微型計(jì)算機(jī)系統(tǒng)，2005，(4):703 －703.

［4］劉世濤.簡析搜索引擎中網(wǎng)絡(luò)爬蟲的搜索策略［J］.阜陽師范學(xué)院學(xué)報(bào)，2006，(3):59 －62.

［5］龔勇.搜索引擎中網(wǎng)絡(luò)爬蟲的研究［D］.武漢:武漢理工大學(xué)，2010.

［6］李學(xué)勇.搜索引擎中網(wǎng)絡(luò)蜘蛛搜索策略比較研究［J］.計(jì)算機(jī)技術(shù)與自動(dòng)化，2003，(4):63 －65.

［7］李學(xué)勇等.網(wǎng)絡(luò)蜘蛛搜索策略比較研究［J］.計(jì)算機(jī)工程與應(yīng)用，2004，(4):63 －67.

［8］劉漢興，劉財(cái)興.主題爬蟲的搜索策略研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008，(12):33 －38.

［9］劉偉.搜索引擎中網(wǎng)絡(luò)爬蟲的設(shè)計(jì)與實(shí)現(xiàn)［J］.科技傳播，2011，(20):178 －181.