【正文】 大的集合 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), 而前兩種策略在這種, 把網(wǎng)絡(luò)爬蟲(chóng)經(jīng)過(guò)若干無(wú)關(guān)頁(yè)面的訪(fǎng)問(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ò)程中增加了用戶(hù)的負(fù)擔(dān). 基于語(yǔ)境圖的聚焦搜索基于鞏固學(xué)習(xí)的網(wǎng)絡(luò)爬蟲(chóng)通過(guò)計(jì)算鏈接的 Q 價(jià)值可以確定搜索方向 , 但它卻電子科技大學(xué)成都學(xué)院本科畢業(yè)設(shè)計(jì)論文12無(wú)法估計(jì)距離目標(biāo)頁(yè)面的遠(yuǎn)近. 為此, Diligent 等提出了基于“語(yǔ)境圖”的搜索策略, 它通過(guò)構(gòu)建典型頁(yè)面的 web“語(yǔ)境圖”來(lái)估計(jì)離目標(biāo)頁(yè)面的距離 , 距離較近的頁(yè)面較早得到訪(fǎng)問(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ù)以?xún)|計(jì)的網(wǎng)頁(yè)，這些網(wǎng)頁(yè)以超鏈接形式互相聯(lián)系在一起，每一網(wǎng)頁(yè)對(duì)應(yīng)一個(gè)超鏈接，也稱(chēng)統(tǒng)一資源定位符（URL）。其中 T 為計(jì)算中的頁(yè)面總量, C 1 是阻尼常數(shù)因子, in (p ) 為所有指向 p 的頁(yè)面的集合, out (C) 為頁(yè)面 C 出鏈的集合. 基于 PageRank 算法的網(wǎng)絡(luò)爬蟲(chóng)在搜索過(guò)程中, 通過(guò)計(jì)算每個(gè)已訪(fǎng)問(wèn)頁(yè)面的 PageRank 值來(lái)確定頁(yè)面的價(jià)值, 并優(yōu)先選擇PageRank 值大的頁(yè)面中的鏈接進(jìn)行訪(fǎng)問(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 值越大?！∨佬胁呗詼\析 寬度或深度優(yōu)先搜索策略搜索引擎所用的第一代網(wǎng)絡(luò)爬蟲(chóng)主要是基于傳統(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ù)的節(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), 根據(jù)“最好優(yōu)先原則”進(jìn)行訪(fǎng)問(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)而決定鏈接訪(fǎng)問(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ì)查詢(xún)結(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 )getHeaderField()方法僅僅獲得服務(wù)器返回的頭標(biāo)志，其通信開(kāi)銷(xiāo)是最小的，因此在下載網(wǎng)頁(yè)前進(jìn)行此測(cè)試，不僅能減小網(wǎng)絡(luò)流量，而且能提高程序效率。當(dāng)成功創(chuàng)建一個(gè) URL 對(duì)象后，我們調(diào)用 openConnection 函數(shù)建立與URL 的通信，此時(shí)，我們就獲得了一個(gè) URLConnection 對(duì)象的引用，URLConnection 類(lèi)包含了許多與網(wǎng)絡(luò)上的 URL 通信的函數(shù)。在使用URL 類(lèi)之前，必須創(chuàng)建一個(gè) URL 對(duì)象，創(chuàng)建的方法是使用其構(gòu)造函數(shù)，通過(guò)向其指定一個(gè) URL 地址，就能實(shí)例化該類(lèi)。當(dāng)需要替換時(shí)，鏈表最后的位置就是最近最少被命中位置，我們只需要將新的內(nèi)容放在鏈表前面，淘汰鏈表最后的位置就實(shí)現(xiàn)了LRU 算法。原理是：cache 的所有位置都用雙向鏈表連接起來(lái)，當(dāng)一個(gè)位置被命中后，就將通過(guò)調(diào)整鏈表的指向?qū)⒃撐恢谜{(diào)整到鏈表的頭位置，新加入的內(nèi)容直接放在鏈表的頭上。不過(guò)，我沒(méi)有用過(guò)這種方式，有機(jī)會(huì)可以嘗試一下。URL 去重存儲(chǔ)庫(kù)使用 Berkeley DB，壓縮后的 URL 字符串作為 Key，或者直接使用壓縮后的 URL 字節(jié)數(shù)組作為 Key，對(duì)于 Value 可以使用 Boolean，一個(gè)字節(jié)，或者使用字節(jié)數(shù)組，實(shí)際 Value 只是一個(gè)狀態(tài)標(biāo)識(shí)，減少 Value 存儲(chǔ)占用存儲(chǔ)空間。去重，可以考慮對(duì)某個(gè)鍵，存在一個(gè)值，這個(gè)值就是那個(gè)鍵的狀態(tài)。在 Java 中有一個(gè) Map 類(lèi)非常好，你可以將壓縮后的 URL 串作為 Key，而將 Boolean 作為 Value 進(jìn)行存儲(chǔ)，然后將工作中的 Map 在爬蟲(chóng)停止工作后序列化到本地磁盤(pán)上；當(dāng)下一次啟動(dòng)新的爬蟲(chóng)任務(wù)的時(shí)候，再將這個(gè) Map 反序列化到內(nèi)存中，供爬蟲(chóng)進(jìn)行 URL 去重檢測(cè)。從另一個(gè)方面來(lái)說(shuō)，非常少的碰撞，對(duì)于搜索引擎的爬蟲(chóng)是可以容忍的。這樣就可以對(duì)URL 字符串進(jìn)行壓縮，得到一個(gè)壓縮字符串，同時(shí)可以直接得到一個(gè) Hash 地址。而且，這里使用的是 URL 作為鍵，URL 字符串也占用了很大的存儲(chǔ)空間。當(dāng)需要進(jìn)行檢測(cè) URL 是否重復(fù)的時(shí)候，只需要將這個(gè) URL 進(jìn)行Hash 映射，如果得到的地址已經(jīng)存在，說(shuō)明已經(jīng)被下載過(guò)，放棄下載，否則，將該 URL 及其 Hash 地址作為鍵值對(duì)存放到 Hash 表中。試想，如果已經(jīng)下載了 100 億網(wǎng)頁(yè)，那么對(duì)應(yīng)著 100 億個(gè)鏈接，也就是這個(gè)檢查 URL是否重復(fù)的記事本文件就要存儲(chǔ)這 100 億 URL，況且，很多 URL 字符串的長(zhǎng)度也不小，占用存儲(chǔ)空間不說(shuō)，查找效率超級(jí)低下，這種方案肯定放棄。每次有一個(gè)爬蟲(chóng)線(xiàn)程得到一個(gè)任務(wù)URL 開(kāi)始下載之前，通過(guò)到磁盤(pán)上的該文件中檢索，如果沒(méi)有出現(xiàn)過(guò)，則將這個(gè)新的 URL 寫(xiě)入記事本的最后一行，否則就放棄該 URL 的下載。 基于磁盤(pán)的順序存儲(chǔ)這里，就是指把每個(gè)已經(jīng)下載過(guò)的 URL 進(jìn)行順序存儲(chǔ)。如果實(shí)現(xiàn)去重，一定是建立一個(gè) URL 存儲(chǔ)庫(kù)，并且已經(jīng)下載完成的 URL 在進(jìn)行檢測(cè)時(shí)候，要加載到內(nèi)存中，在內(nèi)存中進(jìn)行檢測(cè)一定會(huì)比直接從磁盤(pán)上讀取速度快很多。非常容易想到，在搜索引擎系統(tǒng)中建立一個(gè)全局的專(zhuān)門(mén)用來(lái)檢測(cè)，是否某一個(gè) URL 對(duì)應(yīng)的網(wǎng)頁(yè)文件曾經(jīng)被下載過(guò)的 URL 存儲(chǔ)庫(kù)，這就是方案。 網(wǎng)絡(luò)爬蟲(chóng) URL 去重儲(chǔ)存庫(kù)設(shè)計(jì)電子科技大學(xué)成都學(xué)院本科畢業(yè)設(shè)計(jì)論文6在爬蟲(chóng)啟動(dòng)工作的過(guò)程中，我們不希望同一個(gè)網(wǎng)頁(yè)被多次下載，因?yàn)橹貜?fù)下載不僅會(huì)浪費(fèi) CPU 機(jī)時(shí)，還會(huì)為搜索引擎系統(tǒng)增加負(fù)荷。以下在新浪新聞頁(yè)面為例，新浪一個(gè)新聞頁(yè)面大小為 50～60k，每個(gè)頁(yè)面有 90～100 個(gè) URL，如果每秒下載 10 個(gè)頁(yè)面，就會(huì)產(chǎn)生 900～1000 次的 URL 排重操作，每次排重操作都要在幾百萬(wàn)至幾千萬(wàn)的 URL 庫(kù)中去查詢(xún)。其關(guān)鍵在于允許一個(gè)作業(yè)只裝入部分的頁(yè)或段就可以啟動(dòng)運(yùn)行，當(dāng)作業(yè)運(yùn)行的時(shí)候在內(nèi)存中找不到所需要的頁(yè)或段的時(shí)候，就會(huì)發(fā)生請(qǐng)求調(diào)入，而從外存中找到的頁(yè)或段將會(huì)置換內(nèi)存中暫時(shí)不運(yùn)行的頁(yè)面到外存。這種情況非常類(lèi)似于操作系統(tǒng)中虛擬儲(chǔ)存器管理。 URL 消重 URL 消重的意義在 SPIDER 系統(tǒng)實(shí)際運(yùn)行的過(guò)程中，每秒下載的 10 個(gè)頁(yè)面中，分析的 URL大多數(shù)是重復(fù)的，實(shí)際上新的 URL 才幾個(gè)。JAVA 使用 synchronized 關(guān)鍵字來(lái)定義程序中要求線(xiàn)程同步的部分。這樣使它在共享的線(xiàn)程之間可以相互協(xié)調(diào)。由于 JAVA 中的每個(gè)對(duì)象都