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