【文章內容簡介】 于傳統(tǒng)的圖算法 , 如寬度優(yōu)先或深度優(yōu)先算法來索引整個 Web, 一個核心的 U RL 集被用來作為一個種子集合 , 這種算法遞歸的跟蹤超鏈接到其它頁面 , 而通常不管頁面的內容 , 因為最終的目標是這種跟蹤能覆蓋整個 Web. 這種策略通常用在通用搜索引擎中 ,因為通用搜索引擎獲得的網頁越多越好 , 沒有特定的要求 . 寬度優(yōu)先搜索算法 寬度優(yōu)先搜索算法 (又稱廣度優(yōu)先搜索 ) 是最簡便的圖的搜索算法之一 , 這一 算法也是很多重要的圖的算法的原型 . Dijkstra 單源最短路徑算法和 Prim 最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想 .寬度優(yōu)先搜索算法是沿著樹的寬度遍歷樹的節(jié)點 , 如果發(fā)現(xiàn)目標 , 則算法中止 . 該算法的設計和實現(xiàn)相對簡單 , 屬于盲目搜索 . 在目前為覆蓋盡可能多的網頁 , 一般使用寬度優(yōu)先搜第二章 相關技術介紹 9 索方法 . 也有很多研究將寬度優(yōu)先搜索策略應用于聚焦爬蟲中 . 其基本思想是認為與初始 U RL 在一定鏈接距離內的網頁具有主題相關性的概率很大 . 另外一種方法是將寬度優(yōu)先搜索與網頁過濾技術結合使用 , 先用廣度優(yōu)先策略 抓取網頁 , 再將其中無關的網頁過濾掉 . 這些方法的缺點在于 , 隨著抓取網頁的增多 , 大量的無關網頁將被下載并過濾 , 算法的效率將變低 . 深度優(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)先在很多情況下會導致爬蟲的陷入 ( trapped) 問題 , 所以它既不是完備的 , 也不是最優(yōu)的 . 聚焦搜索策略 基于第一代網絡爬蟲的搜索引擎抓取的網頁一般少于 1 000 000 個網頁 , 極少重新搜集網頁并去刷新索引 . 而且其檢索速度非常慢 , 一般都要等待 10 s 甚至更長的時間 . 隨著網頁頁信息的指數級增長及動態(tài)變化 , 這些通用搜索引擎的局限性越來越大 , 隨著科學技術的發(fā)展 , 定向抓取相關網頁資源的聚焦爬蟲便應運而生 .聚焦爬蟲的爬 行策略只挑出某一個特定主題的頁面 , 根據“最好優(yōu)先原則”進行訪問 , 快速、有效地獲得更多的與主題相關的頁面 , 主要通過內容和 Web 的鏈接結構來指導進一步的頁面抓取 [ 2 ]. 聚焦爬蟲會給它所下載下來的頁面分配一個評價分 , 然后根據得分排序 , 最后插入到一個隊列中 . 最好的下一個搜索將通過對彈出隊列中的第一個頁面進行分析而執(zhí)行 , 這種策略保證爬蟲能優(yōu)先跟蹤那些最有可能鏈接到目標頁面的頁面 . 決定網絡爬蟲搜索策略的關鍵是如何評價鏈接價值 , 即鏈接價值的計算方法 , 不同的價值評價方法計算出的鏈接的價值不同 , 表現(xiàn)出的鏈接的“重要程度”也不同 , 從而決定了不同的搜索策略 . 由于鏈接包含于頁面之中 ,而通常具有較高價值的頁面包含的鏈接也具有較高的價值 , 因而對鏈接價值的評價有時也轉換為對頁面價值的評價 . 這種策略通常運用在專業(yè)搜索引擎中 , 因為這種搜索引擎只關心某一特定主題的頁面 . 基于內容評價的搜索策略 基于內容評價的搜索策略 [ 3, 4 ] , 主要是根據主題 (如關鍵詞、主題相關文檔 ) 電子科技大學成都學院本科畢業(yè)設計論文 10 與鏈接文本的相似度來評價鏈接價值的高低 , 并以此決定其搜索策略 : 鏈接文本是指鏈接周圍的說明文字和鏈接 U RL 上的文字信息 , 相似度的評價通常采用以下公式 : sim (d i, d j ) =Σ mk= 1w ik w jk(Σ mk= 1w 2ik ) (Σ mk= 1w 2jk ) 其中 , di 為新文本的特征向量 , d j 為第 j 類的中心向量 ,m 為特征向量的維數 ,wk 為向量的第 K 維 .由于 Web 頁面不同于傳統(tǒng)的文本 , 它是一種半結構化的文檔 , 包含許多結構信息 Web 頁面不是單獨存在的 , 頁面中的鏈接指示了頁面之間的相互關系 , 因而有些學者提出了基于鏈接結構評價鏈接價值的方法 . 基于鏈接結 構評價的搜索策略 基于鏈接結構評價的搜索策略 , 是通過對 Web 頁面之間相互引用關系的分析來確定鏈接的重要性 , 進而決定鏈接訪問順序的方法 . 通常認為有較多入鏈或出鏈的頁面具有較高的價值 . PageRank 和 Hits 是其中具有代表性的算法 . PageRank 算法 基于鏈接評價的搜索引擎的優(yōu)秀代表是 Google ( , 它獨創(chuàng)的“鏈接評價體系” (PageRank 算法 ) 是基于這樣一種認識 , 一個網頁的重要性取決于它被其它網頁鏈接的數量 , 特 別是一些已經被認定是“重要”的網頁的鏈接數量 . PageRank 算法最初用于 Google 搜索引擎信息檢索中對查詢結果的排序過程 [ 5 ] , 近年來被應用于網絡爬蟲對鏈接重要性的評價 , PageRank 算法中 , 頁面的價值通常用頁面的 PageRank 值表示 , 若設頁面 p 的 PageRank 值為 PR (p ) , 則 PR (p ) 采用如下迭代公式計算 : PR (p ) = C 1T+ (1 C) Σ C∈ in (p )PR (p )ou t (C) 其中 T 為計算中的頁面總量 , C 1 是阻尼常數因子 , in (p ) 為所有指向 p 的頁面的集合 , out (C) 為頁面 C出鏈的集合 . 基于 PageRank 算法的網絡爬蟲在搜索過程中 , 通過計算每個已訪問頁面的 PageRank 值來確定頁面的價值 , 并優(yōu)先選擇 PageRank 值大的頁面中的鏈接進行訪問 . H ITS 算法 HITS 方法定義了兩個重要概念 : Authority 和 Hub. Authority 表示一個權威頁面被其它頁面引用的數量 , 即該權威頁面的入度值 . 網頁被引用的數量越大 , 則該網頁的 Authority 值越大 。 Hub 表示一個 Web 頁面指向其它頁面的數量 , 即該頁面的出度值 . 網頁的出度值越大 , 其 Hub 值越高 . 由于 Hub 值高的頁面通常都提供了指向權威頁面的鏈接 , 因而起到了隱含說明某主題頁面權威性的第二章 相關技術介紹 11 作用 .HITS (Hyperlink Induced Top ic Search) 算法是利用 Hub246。Authority 方法的搜索方法 ,Authority 表示一個頁面被其它頁面引用的數量 , 即該頁面的入度值 . Hub 表示一個 Web 頁面指向其它頁面的數量 , 即該頁面的出度值 . 算法如下 : 將查詢 q 提交給傳統(tǒng)的基于關鍵字匹配的搜索引擎 . 搜索引擎返回很多網頁 , 從中取前 n 個網頁作為根集 , 用 S 表示 .通過向 S 中加入被 S 引用的網頁和引用 S 的網頁 將 S 擴展成一個更大的集合 T 中的 Hub 網頁為頂點集 V l, 以權威網頁為頂點集 V 2,V1 中的網頁到 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 ) 收斂 . A (u) = Σ v: (v , u) ∈ EH (v ) (1) H (v ) = Σ v: (v, u) ∈ EA (v ) (2) 式 (1) 反映了若一個網頁由很多好的 Hub 指向 , 則其權威值會相應增加 (即權威值增加為所有指向它的網頁的現(xiàn)有 Hub 值之和 ). 式 (2) 反映了若一個網頁指向許多好的權威頁 , 則 Hub 值也會相應增加 (即 Hub 值增加為該網頁鏈接的所有網頁的權威值之和 ).雖然基于鏈接結構價的搜索考慮了鏈接的結構和頁面之間的引用關系 , 但忽略了頁面與主題的相關性 , 在某些情況下 , 會出現(xiàn)搜索偏離主題的問題 . 另外 , 搜索過程中需要重復計算 PageRank 值或 Authority 以及 Hub 權重 , 計算復雜度隨頁面和鏈接數量的增長呈指數級增長 [ 6 ]. 基于鞏固學習的聚焦搜索 近 年來對 Web 信息資源分布的研究表明很多類型相同的網站在構建方式上 , 主題相同的網頁在組織方式上都存在著一定的相似性 , 有的學者就考慮將鞏固學習引入網絡爬蟲的訓練過程中 , 從這些相似性獲取一些“經驗” , 而這些經驗信息在搜索距相關頁面集較遠的地方往往能獲得較好的回報 , 而前兩種策略在這種情況下容易迷失方向 .在鞏固學習模型中 , 把網絡爬蟲經過若干無關頁面的訪問之后才能獲得的主題相關頁面稱為未來回報 , 對未來回報的預測值稱為未來回報價值 , 用 Q 價值表示 . 這種方法的核心就是學習如何計算鏈接的 Q 價值 , 根據未來 回報價值確定正確的搜索方向 . 目前這類搜索策略不足之處在于學習效率低的問題 , 而且在訓練過程中增加了用戶的負擔 . 基于語境圖的聚焦搜索 電子科技大學成都學院本科畢業(yè)設計論文 12 基于鞏固學習的網絡爬蟲通過計算鏈接的 Q 價值可以確定搜索方向 , 但它卻無法估計距離目標頁面的遠近 . 為此 , Diligent 等提出了基于“語境圖”的搜索策略 , 它通過構建典型頁面的 web“語境圖”來估計離目標頁面的距離 , 距離較近的頁面較早得到訪問 [ 7 ].基于“語境圖”的搜索策略需要借助已有的通用搜索引擎構建“語境圖” , 而搜索引擎的檢索結果并非一定代表真 實的 web 結構 , 因而這種方式也具有局限性 . 第三章 系統(tǒng)需求分析及模塊設計 13 第 三 章 系統(tǒng)需求分析及 模塊 設計 系統(tǒng)需求分析 SPIDER 要獲取的對象是存在于網絡上數以億計的網頁，這些網頁以超鏈接形式互相聯(lián)系在一起，每一網頁對應一個超鏈接 ， 也稱統(tǒng)一資源定位符 （ URL） 。我們可以把網絡看做一個圖 M(V,E)， 網絡中的網頁構成節(jié)點集 V，他們之間的鏈接構成邊集 E， SPIDER 正是從某一節(jié)點開始 ， 沿著邊 ， 遍歷圖 M， 每訪問到圖中一個節(jié)點 Vi，就進行一定的處理。 為了達到上述目的 ， 一個 SPIDER 必須被設計成多線程的 ， A 個線程并發(fā)地在 網絡上協(xié)同工作 ， 才有可能在盡可能短的時間內遍歷完網絡中的網頁 。 但網頁數目是如此之大 ， 如果任 SPIDER 程序無窮地搜索下去 ， 那么程序幾乎不能終止。所以我們限制 SPIDER 每次工作只訪問一個站點。一個再大型的站點 ，其中的網頁數目也是有限的 ， 因此 SPIDER 程序能在有限的時間內結束。 當 SPIDER 程序訪問到一個網頁 ， 必須進行以下幾項基本處理 ： 抽取網頁中包含的文本 ； 抽取網頁中包含的 URL， 并將其區(qū)分為網站內 URL 或網站外 URL。 SPIDER 體系結構 此爬蟲程序主要分為三個部分：任務執(zhí)行端，任務調度端， 數據服務端。 每一個 SPIDER 任務執(zhí)行端關聯(lián)一個站點 ,一個線程下載一個基于 URL 鏈接的頁面 , 并進行 Web 頁面解析 , 得到站內 URL 和發(fā)現(xiàn)新站點 URL 另外 ,將URL 隊列持久化到數據庫 , 因此在 SPIDER 任務執(zhí)行端以外 Down 掉后 , 能夠斷點續(xù)傳 . SPIDER 客戶端線程間的協(xié)調通信采用 Java 的線程同步技術 synchronized,在數據服務端中對 URL 進行緩存提高了系統(tǒng)處理速度 . SPIDER 的任務執(zhí)行和任務調度端都需要維持一個 URL 隊列 : 任務執(zhí)行端的 URL 隊 列中存儲了 站內URL。 任務調度端則是站點的 URL. 在這些 URL 隊列上有大量的操作 , 包括URL 查找 、 URL 插入 、 URL 狀態(tài)更新等 . 如果 SPIDER 以 300 頁 246。秒的速度下載 Web 頁面 , 平均將會產生 2021 多個 URL [12] , 因此簡單的采用內存數據結構存儲這些 URL 隊列有一定的問題 , 系統(tǒng)沒有足夠的內存空間 。而采用直接持久化到數據庫 , 則需要大量的數據庫連接、查詢等操作 , 系統(tǒng)效率會明顯下降 . 如果采用 URL 壓縮的辦法 ,盡管在一定程度上可以平衡空間和時間的矛盾 , 但仍然不適用于大規(guī)模數 據采集的 SPIDER. 電子科技大學成都學院本科畢業(yè)設計論文 14 圖 SPIDER 體系結 各主要功能模塊（類）設計 SPIDERWorker 類 ：該類 繼承自線程類，請求任務 URL， 根據得到的 URL下載相應的 HTML 代碼 ，利用 HTML 代碼 調用其他模塊完成相關 處理 。 SPI