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