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