本文關鍵詞：簡析搜索引擎中網絡爬蟲的搜索策略，由筆耕文化傳播整理發(fā)布。

隨著互聯(lián)網的興起及發(fā)展，人們獲取信息的途徑由傳統(tǒng)方式逐漸被網絡替代。 起初人們主要通過瀏覽網頁來獲取所需信息， 但隨著Web不斷龐大用這種方式來尋找自己所需的信息變得越來越困難�，F(xiàn)在大多數(shù)的人很大程度上依賴于搜索引擎來幫助自己獲取有用信息，因此搜索引擎技術作為最典型的Web信息獲取技術 其發(fā)展直接影響人們獲取信息的質量。

自從1994 年4 月世界上第一個Web 檢索工具Web Crawler 問世以來， 目前較流行的搜索引擎已有Google、Yahoo、AltaVista、Infoseek、InfoMarket等。出于商業(yè)機密的考慮， 目前各個搜索引擎使用的Crawler 系統(tǒng)的技術內幕一般都不公開，現(xiàn)有的文獻也僅限于概要性介紹。隨著Web 信息資源呈指數(shù)級增長及Web 信息資源動態(tài)變化， 傳統(tǒng)的搜索引擎提供的信息檢索服務已不能滿足人們日益增長的對個性化服務的需要，它們正面臨著巨大的挑戰(zhàn)。以何種策略訪問Web提高搜索效率 成為近年來專業(yè)搜索引擎網絡爬蟲研究的主要問題之一。

1　網絡爬蟲的工作原理

網絡爬蟲出自Sp ider 的意譯，具有相同詞義的詞語還有Crawler、robots、bots、wanderer等等。網絡爬蟲定義有廣義和狹義之分，狹義上的定義為利用標準的http協(xié)議根據超鏈和Web文檔檢索的方法遍歷萬維網信息空間的軟件程序；而廣義則是所有能利用http協(xié)議檢索Web文檔的軟件都稱之為網絡爬蟲。

網絡爬蟲是一個功能很強的自動提取網頁的程序, 它為搜索引擎從萬維網上下載網頁，，是搜索引擎的重要組成。 它通過請求站點上的HTML 文檔訪問某一站點。它遍歷Web 空間，不斷從一個站點移動到另一個站點，自動建立索引并加入到網頁數(shù)據庫中。網絡爬蟲進入某個超級文本時, 它利用HTML語言的標記結構來搜索信息及獲取指向其他超級文本的URL 地址，可以完全不依賴用戶干預實現(xiàn)網絡上的自動“爬行”和搜索。 網絡爬蟲在搜索時往往采用一定的搜索策略。

2　寬度或深度優(yōu)先搜索策略

搜索引擎所用的第一代網絡爬蟲主要是基于傳統(tǒng)的圖算法，如寬度優(yōu)先或深度優(yōu)先算法來索引整個Web，一個核心的URL 集被用來作為一個種子集合，這種算法遞歸的跟蹤超鏈接到其它頁面，而通常不管頁面的內容，因為最終的目標是這種跟蹤能覆蓋整個Web。這種策略通常用在通用搜索引擎中，因為通用搜索引擎獲得的網頁越多越好，沒有特定的要求. 如圖1 所示：

2. 1　寬度優(yōu)先搜索算法

寬度優(yōu)先搜索算法(又稱廣度優(yōu)先搜索) 是最簡便的圖的搜索算法之一， 這一算法也是很多重要的圖的算法的原型. Dijktra 單源最短路徑算法和Prim 最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想.寬度優(yōu)先搜索算法是沿著樹的寬度遍歷樹的節(jié)點，如果發(fā)現(xiàn)目標則算法中止。該算法的設計和實現(xiàn)相對簡單屬于盲目搜索。 在目前為覆蓋盡可能多的網頁，一般使用寬度優(yōu)先搜索方法。也有很多研究將寬度優(yōu)先搜索策略應用于聚焦爬蟲中。其基本思想是認為與初始U RL 在一定鏈接距離內的網頁具有主題相關性的概率很大。 另外一種方法是將寬度優(yōu)先搜索與網頁過濾技術結合使用， 先用廣度優(yōu)先策略抓取網頁，再將其中無關的網頁過濾掉. 這些方法的缺點在于， 隨著抓取網頁的增多大量的無關網頁將被下載并過濾,算法的效率將變低。

2. 2　深度優(yōu)先搜索

深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索圖。在深度優(yōu)先搜索中，對于最新發(fā)現(xiàn)的頂點，如果它還有以此為起點而未探測到的邊 就沿此邊繼續(xù)漢下去。當結點v 的所有邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)結點v 有那條邊的始結點。這一過程一直進行到已發(fā)現(xiàn)從源結點可達的所有結點為止。如果還存在未被發(fā)現(xiàn)的結點，則選擇其中一個作為源結點并重復以上過程，整個進程反復進行直到所有結點都被發(fā)現(xiàn)為止. 深度優(yōu)先在很多情況下會導致爬蟲的陷入( t rapped) 問題, 所以它既不是完備的，也不是最優(yōu)的。

3　聚焦搜索策略

基于第一代網絡爬蟲的搜索引擎抓取的網頁一般少于1 000 000 個網頁, 極少重新搜集網頁并去刷新索引。而且其檢索速度非常慢，一般都要等待10s甚至更長的時間. 隨著網頁頁信息的指數(shù)級增長及動態(tài)變化， 這些通用搜索引擎的局限性越來越大，隨著科學技術的發(fā)展, 定向抓取相關網頁資源的聚焦爬蟲便應運而生。

聚焦爬蟲的爬行策略只挑出某一個特定主題的頁面，根據“最好優(yōu)先原則”進行訪問，快速、有效地獲得更多的與主題相關的頁面，主要通過內容和Web 的鏈接結構來指導進一步的頁面抓取。圖2表明了典型的應用聚焦策略爬蟲的爬行規(guī)則。

聚焦爬蟲會給它所下載下來的頁面分配一個評價分，然后根據得分排序。最后插入到一個隊列中. 最好的下一個搜索將通過對彈出隊列中的第一個頁面進行分析而執(zhí)行，這種策略保證爬蟲能優(yōu)先跟蹤那些最有可能鏈接到目標頁面的頁面。決定網絡爬蟲搜索策略的關鍵是如何評價鏈接價值，即鏈接價值的計算方法， 不同的價值評價方法計算出的鏈接的價值不同, 表現(xiàn)出的鏈接的“重要程度”也不同， 從而決定了不同的搜索策略。由于鏈接包含于頁面之中，而通常具有較高價值的頁面包含的鏈接也具有較高的價值，因而對鏈接價值的評價有時也轉換為對頁面價值的評價. 這種策略通常運用在專業(yè)搜索引擎中，因為這種搜索引擎只關心某一特定主題的頁面。

3. 1　基于內容評價的搜索策略

基于內容評價的搜索策略主要是根據主題(如關鍵詞、主題相關文檔) 與鏈接文本的相似度來評價鏈接價值的高低，并以此決定其搜索策略： 鏈接文本是指鏈接周圍的說明文字和鏈接URL 上的文字信息， 相似度的評價通常采用以下公式：

其中di為新文本的特征向量，dj為第j類的中心向量，m為特征向量的維數(shù)，wk為向量的第K維。

由于Web頁面不同于傳統(tǒng)的文本，它是一種半結構化的文檔，包含許多結構信息Web頁面不是單獨存在的，頁面中的鏈接指示了頁面之間的相互關系，因而有些學者提出了基于鏈接結構評價鏈接價值的方法。

3. 2　基于鏈接結構評價的搜索策略

基于鏈接結構評價的搜索策略，是通過對Web頁面之間相互引用關系的分析來確定鏈接的重要性，進而決定鏈接訪問順序的方法。通常認為有較多入鏈或出鏈的頁面具有較高的價值。PageRank和Hits是其中具有代表性的算法。

3. 2. 1 　PageRank 算法

基于鏈接評價的搜索引擎的優(yōu)秀代表是Google，它獨創(chuàng)的“鏈接評價體系”(PageRank 算法) 是基于這樣一種認識，一個網頁的重要性取決于它被其它網頁鏈接的數(shù)量，特別是一些已經被認定是“重要”的網頁的鏈接數(shù)量。PageRank 算法最初用于Google 搜索引擎信息檢索中對查詢結果的排序過程，近年來被應用于網絡爬蟲對鏈接重要性的評價，PageRank 算法中頁面的價值通常用頁面的PageRank值表示，若
設頁面p 的PageRank 值為PR (p ) ，則PR (p ) 采用如下迭代公式計算：

其中T 為計算中的頁面總量，C< 1 是阻尼常數(shù)因子，in (p ) 為所有指向p 的頁面的集合，ou t (C) 為頁面C出鏈的集合. 基于PageRank 算法的網絡爬蟲在搜索過程中通過計算每個已訪問頁面的PageRank 值來確定頁面的價值，并優(yōu)先選擇PageRank 值大的頁面中的鏈接進行訪問。

3. 2. 2　H ITS 算法

HITS 方法定義了兩個重要概念：Authority和Hub. Authority 表示一個權威頁面被其它頁面引用的數(shù)量，即該權威頁面的入度值。網頁被引用的數(shù)量越大, 則該網頁的Authority值越大； Hub 表示一個Web頁面指向其它頁面的數(shù)量，即該頁面的出度值。網頁的出度值越大其Hub 值越高。由于Hub 值高的頁面通常都提供了指向權威頁面的鏈接，因而起到了隱含說明某主題頁面權威性的作用。

HITS (Hyperlink- Induced Topic Search) 算法是利用Hub.Authority方法的搜索方法，Authority表示一個頁面被其它頁面引用的數(shù)量， 即該頁面的入度值。Hub 表示一個W eb 頁面指向其它頁面的數(shù)量，即該頁面的出度值。算法如下：將查詢q 提交給傳統(tǒng)的基于關鍵字匹配的搜索引擎。搜索引擎返回很多網頁，從中取前n 個網頁作為根集用S 表示。通過向S 中加入被S 引用的網頁和引用S 的網頁將S 擴展成一個更大的集合T。以T 中的Hub 網頁為頂點集V l，以權威網頁頂點集V 2，V 1 中的網頁到V 2 中的網頁的超鏈接為邊集E , 形成一個二分有向圖S G = (V 1,V 2, E )。對V 1 中的任一個頂點v，用H (v ) 表示網頁v 的Hub值，對V 2 中的頂點u, 用A (u) 表示網頁的Authority值。開始時H (v ) = A (u) = 1，對u 執(zhí)行公式(1) 來修改它的A (u) ，對v 執(zhí)行公式(2) 來修改它的H (v ) ，然后規(guī)范化A (u) ，H (v ) ，如此不斷的重復計算上述運算，直到A (u)，H (v ) 收斂。

式(1) 反映了若一個網頁由很多好的Hub 指向，則其權威值會相應增加(即權威值增加為所有指向它的網頁的現(xiàn)有Hub值之和)。式(2) 反映了若一個網頁指向許多好的權威頁，則Hub 值也會相應增加(即Hub 值增加為該網頁鏈接的所有網頁的權威值之和)。雖然基于鏈接結構評價的搜索考慮了鏈接的結構和頁面之間的引用關系，但忽略了頁面與主題的相關性，在某些情況下會出現(xiàn)搜索偏離主題的問題。另外搜索過程中需要重復計算PageRank值或Authority以及Hub權重，計算復雜度隨頁面和鏈接數(shù)量的增長呈指數(shù)級增長。

3. 3　基于鞏固學習的聚焦搜索

近年來對W eb 信息資源分布的研究表明很多類型相同的網站在構建方式上，主題相同的網頁在組織方式上都存在著一定的相似性，有的學者就考慮將鞏固學習引入網絡爬蟲的訓練過程中，從這些相似性獲取一些“經驗”，而這些經驗信息在搜索距相關頁面集較遠的地方往往能獲得較好的回報，而前兩種策略在這種情況下容易迷失方向。在鞏固學習模型中，把網絡爬蟲經過若干無關頁面的訪問之后才能獲得的主題相關頁面稱為未來回報，對未來回報的預測值稱為未來回報價值，用Q價值表示。這種方法的核心就是學習如何計算鏈接的Q 價值，根未來回報價值確定正確的搜索方向。目前這類搜索策略不足之處在于學習效率低的問題，而且在訓練過程中增加了用戶的負擔。

3. 4　基于語境圖的聚焦搜索

基于鞏固學習的網絡爬蟲通過計算鏈接的Q價值可以確定搜索方向，但它卻無法估計距離目標頁面的遠近。為此 Diligen t 等提出了基于“語境圖”的搜索策略，它通過構建典型頁面的web“語境圖”來估計離目標頁面的距離，距離較近的頁面較早得到訪問。基于“語境圖”的搜索策略需要借助已有的通用搜索引擎構建“語境圖”，而搜索引擎的檢索結果并非一定代表真實的web 結構，因而這種方式也具有局限性。

4　小結

通過以的分析，各類搜索策略各有的優(yōu)缺點，網絡爬蟲搜索策略的研究對搜索引擎的應用與發(fā)展有著重要意義。一種好的策略就是要在合理的時間限度內，以較少的網絡資源、存儲資源和計算資源的消耗獲得更多的與主題相關頁面。因而未來網絡爬蟲所使用的策略應該在提高鏈接價值預測的準確性、降低計算的時空復雜度，以及增加網絡爬蟲的自適應性等方面有所發(fā)展，有所突破。

本文作者：劉世濤(江蘇聯(lián)合職業(yè)技術學院連云港財經分院, 江蘇連云港　222003)

碼字很辛苦，轉載請注明來自標點符的《簡析搜索引擎中網絡爬蟲的搜索策略》

分享到：()

  本文關鍵詞：簡析搜索引擎中網絡爬蟲的搜索策略，由筆耕文化傳播整理發(fā)布。