基于網(wǎng)頁去噪Hash的增量式網(wǎng)絡(luò)爬蟲研究＊

（海軍工程大學(xué)信息安全系 武漢 430033）

1 引言

在互聯(lián)網(wǎng)高速發(fā)展的今天，網(wǎng)站以前所未有的速度發(fā)生著變化，新網(wǎng)頁不斷地添加進(jìn)來，舊網(wǎng)頁內(nèi)容不斷地更新，這給搜索引擎中的網(wǎng)絡(luò)爬蟲帶來了巨大的挑戰(zhàn)。由于并沒有機(jī)制能夠?qū)⒕W(wǎng)站發(fā)生的變化主動(dòng)地推送給搜索引擎，網(wǎng)絡(luò)爬蟲必須實(shí)現(xiàn)增量抓取，以保證搜索引擎提供信息的實(shí)效性，無論是百度、Google這樣的廣泛搜索引擎，還是現(xiàn)在的垂直搜索引擎，增量抓取都是網(wǎng)絡(luò)爬蟲最需要考慮的問題。增量式抓取的目的在于保持本地?cái)?shù)據(jù)的新鮮度，只對(duì)新產(chǎn)生的網(wǎng)頁或變化的網(wǎng)頁進(jìn)行抓取，對(duì)沒有變化的網(wǎng)頁不進(jìn)行抓取，因此網(wǎng)頁更新判斷是首先要考慮的問題。可以依據(jù)http協(xié)議在http的請(qǐng)求中加入一個(gè)If-Modified-since屬性請(qǐng)求網(wǎng)頁對(duì)已下載過的網(wǎng)頁進(jìn)行更新［1］，如果網(wǎng)頁自上次采集后發(fā)生了變化則進(jìn)行抓取，這種方法的缺點(diǎn)是對(duì)于動(dòng)態(tài)網(wǎng)頁沒有任何作用，而且互聯(lián)網(wǎng)上有許多的靜態(tài)網(wǎng)頁是由動(dòng)態(tài)轉(zhuǎn)化而來，這些表態(tài)網(wǎng)頁幾乎每天都有一些細(xì)微的變化。因此僅僅根據(jù)If-Modified-Since屬性來判斷網(wǎng)頁是否變化是不準(zhǔn)確的［2］。通常的做法是保存網(wǎng)頁內(nèi)容更新前的Hash值與更新后的Hash值，通過對(duì)比判斷網(wǎng)頁是否發(fā)生變化。

經(jīng)典的Hash算法有MD5和SHA1［3］，在實(shí)驗(yàn)過程中發(fā)現(xiàn)用Hash算法定義網(wǎng)頁的變化過于嚴(yán)格，Hash值產(chǎn)生敏感度高，微小的網(wǎng)頁變化，例如：網(wǎng)頁中與主要內(nèi)容無關(guān)的廣告、圖片、版權(quán)信息、分割條、導(dǎo)航鏈接、搜索服務(wù)和版權(quán)信息等，都會(huì)導(dǎo)致Hash值的很大變化，網(wǎng)絡(luò)爬蟲仍然會(huì)將大部分正文內(nèi)容沒有變化的網(wǎng)頁抓取下來，達(dá)不到增量抓取的預(yù)期效果。

針對(duì)上述問題，本文將網(wǎng)頁去噪與Hash算法結(jié)合起來，提出去噪后的Hash 產(chǎn)生方法，即在對(duì)網(wǎng)頁Hash值產(chǎn)生前去掉網(wǎng)頁中的微小變化內(nèi)容，稱之為噪聲，然后對(duì)網(wǎng)頁正文部分產(chǎn)生Hash值并保存到Hash表中，基于去噪后的Hash值來判斷網(wǎng)頁是否發(fā)生變化。在開源網(wǎng)絡(luò)爬蟲Heritrix進(jìn)行實(shí)驗(yàn)后，結(jié)果表明，去噪后的網(wǎng)頁Hash 值能較好的反應(yīng)網(wǎng)頁正文的變化情況。

2 相關(guān)研究

增量式網(wǎng)絡(luò)爬蟲一般用于更新本地?cái)?shù)據(jù)。其基本思想：增量式爬蟲不抓取沒有變化的網(wǎng)頁，只抓取新產(chǎn)生的網(wǎng)頁或者己經(jīng)發(fā)生變化的網(wǎng)頁。增量式抓取的理想狀況是抓取到的信息與網(wǎng)絡(luò)中的信息完全一致，但這僅僅是理想狀況，由于Web的異構(gòu)性、動(dòng)態(tài)性和復(fù)雜性使得抓取到的網(wǎng)頁有可能在相當(dāng)短的時(shí)間內(nèi)就發(fā)生了變化，所以在現(xiàn)實(shí)中是不可能實(shí)現(xiàn)的，能做的就是抓取一切辦法盡量逼近這種理想狀況。增量式抓取能提高網(wǎng)頁采集的效率，由于不抓取沒有變化的網(wǎng)頁，因此極大地減少了數(shù)據(jù)抓取量從而減少了抓取的時(shí)間和存儲(chǔ)資源的浪費(fèi)。其缺點(diǎn)是增量式抓取帶來了算法復(fù)雜性和難度的增加。

目前在實(shí)現(xiàn)增量式抓取方面的研究有很多，文獻(xiàn)［4］為了檢測頁面變化的情況，通過記錄并對(duì)比每次抓取時(shí)URL 對(duì)應(yīng)頁面的最后修改時(shí)間Last-Modified來判斷該頁面是否進(jìn)行了修改。文獻(xiàn)［5］針對(duì)傳統(tǒng)的周期性集中式搜索（Crawler）的弱點(diǎn)和增量式Crawler的難點(diǎn)，給出了判別網(wǎng)頁更新的MD5算法。文獻(xiàn)［6］在基于Hash函數(shù)“判斷待采頁面是否在已采頁面集合中”方面，對(duì)Hash 函數(shù)Tianlhash、ELFhash、HfIp、hf和Strhash的性能進(jìn)行了比較。文獻(xiàn)［7］中提到去掉網(wǎng)頁中標(biāo)簽信息、標(biāo)簽內(nèi)部信息、注釋信息和腳本代碼的網(wǎng)頁摘要獲取方法，但沒有給出具體的網(wǎng)頁摘要獲取過程。文獻(xiàn)［8］中采用基于網(wǎng)頁框架和規(guī)則的方式對(duì)網(wǎng)頁噪聲進(jìn)行劃分，然后獲取網(wǎng)頁的MD5值對(duì)網(wǎng)頁進(jìn)行增量采集。目前的增量抓取系統(tǒng)主要有IBM Almaden研究中心開發(fā)的Web Fountain Crawler，智利大學(xué)開發(fā)的一個(gè)增量搜集系統(tǒng)Univ．Chile Crawler和天網(wǎng)增量搜集系統(tǒng)。

3 增量抓取模塊

3．1 Hash算法模塊

Hash函數(shù)是密碼學(xué)中一個(gè)重要的分支，由于它是一種單向函數(shù)，是一類加密映射，將任意長度的輸入壓縮成固定長度的輸出，而且一般情況輸出長度均比輸入長度要短。Hash函數(shù)的安全性基礎(chǔ)在于三點(diǎn)：1）從Hash值很難得到輸入值的任何相關(guān)信息；2）很難找到兩個(gè)輸入能有相同的Hash值；3）找到一個(gè)有特定的Hash值的輸入很困難，并且，從一個(gè)特定的輸入尋找有相似性的輸入更加困難［9］。

基于以上理論基礎(chǔ)，將Hash函數(shù)應(yīng)用到增量式網(wǎng)絡(luò)爬蟲中，對(duì)抓取的網(wǎng)頁進(jìn)行加密生成Hash值，通過對(duì)比新舊網(wǎng)頁的Hash值來判斷網(wǎng)頁是否發(fā)生變化。Hash 值相同則表示網(wǎng)頁沒有發(fā)生變化，不用進(jìn)行抓取；Hash值不同則表明網(wǎng)頁發(fā)生了變化，需要進(jìn)行增量抓取。

本文的增量抓取過程基于開源網(wǎng)絡(luò)爬蟲Heritrix［10］。Heritrix 是SourceForge 上基于Java 的開源爬蟲，采用了模塊化的設(shè)計(jì)，它由核心類和插件模塊構(gòu)成。其系統(tǒng)架構(gòu)如圖1所示。

圖1 Heritrix系統(tǒng)架構(gòu)圖

Heritrix只能對(duì)網(wǎng)頁進(jìn)行一次性抓取，要實(shí)現(xiàn)增量抓取必須在Heritrix中添加增量抓取模塊，本文在Heritrix的處理鏈中加入HttpContentDigest和ChangeEvaluator兩個(gè)模塊實(shí)現(xiàn)Heritirx增量抓取。

HttpContentDigest：該模塊對(duì)Fetch Processing Chain抓取下來的網(wǎng)頁產(chǎn)生一個(gè)Hash 值，該Hash值就是為了判斷網(wǎng)頁是否發(fā)生了變化。接口類java．security．MessageDigest 中的哈希函數(shù)SHA-1提供了Hash值產(chǎn)生功能。該模塊關(guān)鍵代碼如下：

圖2 Processing chain

1）創(chuàng)建一個(gè)消息摘要值，即Hash值，對(duì)文件進(jìn)行處理；

MessageDigest digest＝null；

digest＝MessageDigest．getInstance（SHA1）；

digest．reset（）；

2）文件處理；

Matcher m＝TextUtils．getMatcher（regexpr，cs）；

s＝m．replaceAll（""）；

TextUtils．recycleMatcher（m）；

digest．update（s．getBytes（））；

3）獲取新的摘要值；

byte［］newDigestValue＝digest．digest（）；

4）保存新的摘要值；

curi．setContentDigest（SHA1，newDigestValue）；

ChangeEvaluator：該模塊對(duì)爬取網(wǎng)頁的當(dāng)前Hash值與過去的Hash值進(jìn)行比較，如果相等則處理鏈的進(jìn)一步處理跳過，直接進(jìn)入到提交鏈模塊，并且將爬取的該URI進(jìn)行標(biāo)記。該模塊關(guān)鍵代碼如下：

1）新Hash值與舊Hash值均為空，不做任何處理；

if（currentDigest＝＝null ＆＆oldDigest＝＝null）if（logger．isLoggable（Level．FINER））

logger．finer（"On"＋curi．toString（）＋"both digest are null"）；

return；

2）新舊Hash值均不為空且兩者相等；

if（currentDigest！＝null ＆＆oldDigest！＝null

＆＆currentDigest．equals（oldDigest））

curi．putInt（A＿CONTENT＿STATE＿KEY，CONTENT＿UNCHANGED）；

跳過之后處理鏈的處理階段：

curi．skipToProcessorChain（getController（）．get-PostprocessorChain（））；

重新設(shè)定鏈接：curi．clearOutlinks（）；

取消日志記錄：curi．a(chǎn)ddAnnotation（"unchanged"）；

設(shè)置文件內(nèi)容為空，不寫入磁盤：

curi．setContentSize（0）；

3）新舊Hash值不同，判斷文件內(nèi)容改變，則按鏈接順序進(jìn)行抓取，并且更新訪問與版本計(jì)數(shù)器。

3．2 網(wǎng)頁去噪模塊

基于網(wǎng)頁Hash值的唯一性，可以判斷網(wǎng)頁是否發(fā)生變化，但由于網(wǎng)頁中噪聲的存在，即使網(wǎng)頁正文沒有發(fā)生變化，微小的噪聲變化也會(huì)導(dǎo)致網(wǎng)頁Hash的很大變化，由此判斷網(wǎng)頁變化是不準(zhǔn)確的，必須對(duì)網(wǎng)頁去噪后僅對(duì)正文部分產(chǎn)生Hash值，去噪后的Hash 值能客觀地反映網(wǎng)頁是否變化。本文采用基于內(nèi)容分塊的網(wǎng)頁去噪方法對(duì)網(wǎng)頁進(jìn)行噪聲去除［11］。

1）噪聲內(nèi)容確定：網(wǎng)頁按照布局可劃分為不同的區(qū)域，如正文、廣告、圖片、版權(quán)信息、分割條、導(dǎo)航鏈接、搜索服務(wù)和版權(quán)信息等，將這些不同的區(qū)域分為兩塊，即正文塊和噪聲塊。正文塊部分反映HTML頁面的正文信息，是需要保留的部分；噪聲塊部分是需要去除的部分。通過去除噪聲塊，達(dá)到凈化網(wǎng)頁，提取正文的目的。

2）網(wǎng)頁預(yù)處理：網(wǎng)頁數(shù)據(jù)大多是使用HTML手工生成的文檔，因此時(shí)常存在語法錯(cuò)誤。首先要對(duì)文檔進(jìn)行預(yù)處理，去除掉無關(guān)的標(biāo)簽，修復(fù)語法錯(cuò)誤，轉(zhuǎn)換為語法限制性更強(qiáng)、編排良好、具有可擴(kuò)展性的文檔，DOM 樹是其中一種形式。對(duì)于一個(gè)給定的網(wǎng)站，同一類型的網(wǎng)頁集合的布局設(shè)計(jì)基本上是一致的。那么與他們相對(duì)應(yīng)的DOM 樹也會(huì)有相同或相似的結(jié)構(gòu)。先對(duì)其進(jìn)行分類處理確定屬于哪一類型。然后從同一類型的網(wǎng)頁集合中選取其對(duì)應(yīng)的DOM 樹進(jìn)行遍歷，來尋找其相同的節(jié)點(diǎn)，并將相應(yīng)的信息塊提取出來。這些信息塊則是我們確定的疑網(wǎng)頁噪聲內(nèi)容。

3）噪聲去除策略：對(duì)于一個(gè)給定的網(wǎng)站，同一類型的網(wǎng)頁集合的布局設(shè)計(jì)基本上是一致的，相對(duì)應(yīng)的DOM 樹也會(huì)有相同或相似的結(jié)構(gòu)。基于此，對(duì)這個(gè)網(wǎng)頁先進(jìn)行預(yù)處理將一些無關(guān)標(biāo)簽去掉，將其轉(zhuǎn)換為XML文檔。然后將處理好的XML 文檔轉(zhuǎn)換為DOM 樹，先對(duì)其進(jìn)行分類處理確定屬于哪一類型，然后從同一類型的網(wǎng)頁集合中選取其對(duì)應(yīng)的DOM 樹進(jìn)行遍歷，來尋找其相同的節(jié)點(diǎn)，并將相應(yīng)的信息塊提取出來。

4）噪聲提取算法：網(wǎng)頁噪聲塊的提取過程就是DOM 樹的融合過程，即將同一域名下的所有DOM 樹融合，找出DOM 樹中的共性部分，提取出噪聲塊［12］。網(wǎng)頁噪聲提取算法具體如下：

算法：噪聲提取

輸入：同一域名下的所有網(wǎng)頁的DOM 樹

輸出：噪聲提取模型

（1）從輸入集中隨機(jī)選擇兩個(gè)DOM 樹；

（2）令DOM 樹的body節(jié)點(diǎn)作為初始節(jié)點(diǎn)；

（3）若節(jié)點(diǎn)都含有子節(jié)點(diǎn)，則轉(zhuǎn)到（4），否則轉(zhuǎn)（7）；

（4）遍歷節(jié)點(diǎn)的子節(jié)點(diǎn)；

（5）將兩個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)做一一對(duì)比，若所有的子節(jié)點(diǎn)有相同，則轉(zhuǎn)（3），否則轉(zhuǎn)（6）；

（6）回溯到子節(jié)點(diǎn)的父節(jié)點(diǎn)，并從左到右記錄父節(jié)點(diǎn)以及父節(jié)點(diǎn)的所有兄弟節(jié)點(diǎn)；

（7）從左到右記錄所有節(jié)點(diǎn)；

（8）由所記錄的節(jié)，奴依次回溯到body節(jié)點(diǎn)，形成中間可疑噪聲信息塊提取模型；

（9）若剩余輸入集中的DOM 樹大于1，從剩余DOM 樹中選取一個(gè)DOM 樹，轉(zhuǎn)（2），否則，形成的8中形成的可疑噪聲信息塊提取模型即為結(jié)果可疑噪聲信息塊提取模型；

（10）結(jié)束。

網(wǎng)頁噪聲提取算法實(shí)際上是層次遍歷DOM樹的過程，當(dāng)給定網(wǎng)站網(wǎng)頁集遍歷完成后，即可得到網(wǎng)頁噪聲模型。

5）去噪后基于Hash 的增量抓取模型如圖3所示。

圖3 去噪后基于Hash的增量抓取模型

4 實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)的硬件環(huán)境為：CPU：Intel Celeron E3300 雙核；主頻：2．5GHz／前端總線頻率：800MHz；內(nèi)存：DDR2 3GB 雙通道；工作頻率：400MHz；硬盤：7200 轉(zhuǎn)。軟件配置環(huán)境：Eclipse平臺(tái)。

本實(shí)驗(yàn)從2013年7月30日至8月3日，對(duì)中安在線（www．a(chǎn)nhuinews．com）進(jìn)行了連續(xù)6次抓取實(shí)驗(yàn)，設(shè)置條件如下：Heritrix版本：1．14．4；最大線程：50；最大深度：3；其它設(shè)置：Heritrix1．14．4默認(rèn)設(shè)置。

1）網(wǎng)頁去噪前增量抓取實(shí)驗(yàn)

在Heritrix處理鏈中加入增量處理模塊：HttpContentDigest和ChangeEvaluator，對(duì)中安在線進(jìn)行第一次普通抓取，間隔1小時(shí)后在普通抓取的基礎(chǔ)上進(jìn)行第二次增量抓取，連續(xù)六組實(shí)驗(yàn)情況如圖4所示。

圖4 網(wǎng)頁去噪前增量抓取實(shí)驗(yàn)

可以看出，在加入增量抓取模塊后，每組實(shí)驗(yàn)中，第二次增量抓取的網(wǎng)頁數(shù)相對(duì)第一次普通抓取網(wǎng)頁減少，但第一次抓取的網(wǎng)頁大部分還是被抓取下來，只實(shí)現(xiàn)了小部分網(wǎng)頁的增量抓取。調(diào)出Heritrix的Hash值產(chǎn)生的日志文件，對(duì)比每次實(shí)驗(yàn)中HttpContentDigest模塊對(duì)第一次普通抓取網(wǎng)頁與第二次增量抓取網(wǎng)頁產(chǎn)生的Hash值，隨機(jī)選取其中六個(gè)網(wǎng)頁，其六組實(shí)驗(yàn)的Hash值如表1所示。

同一網(wǎng)頁在每組實(shí)驗(yàn)中，兩次抓取的時(shí)間間隔均在1 小時(shí)以內(nèi)，產(chǎn)生的Hash 值確完全不同，這樣在網(wǎng)頁提取時(shí)，對(duì)相同的網(wǎng)頁又進(jìn)行了二次抓取。進(jìn)入網(wǎng)頁存儲(chǔ)文件mirror，調(diào)出兩次抓取的網(wǎng)頁，對(duì)比分析發(fā)現(xiàn)，網(wǎng)頁僅僅是在訪問量與網(wǎng)頁時(shí)間上有細(xì)微的差別，網(wǎng)頁正文沒有變化，可見網(wǎng)頁噪聲對(duì)基于Hash的增量抓取結(jié)果影響很大。

2）網(wǎng)頁去噪后增量抓取實(shí)驗(yàn)

在Heritrix處理鏈中加入網(wǎng)頁去噪模塊與增量抓取模塊，以相同的方法對(duì)中安在線進(jìn)行六組普通抓取與增量抓取實(shí)驗(yàn)，實(shí)驗(yàn)情況如圖5所示。

表1 Hash值對(duì)比

圖5 網(wǎng)頁去噪后增量抓取實(shí)驗(yàn)

對(duì)網(wǎng)頁進(jìn)行去噪處理后，可以發(fā)現(xiàn)，Heritrix增量抓取的網(wǎng)頁明顯減少。進(jìn)入網(wǎng)頁存儲(chǔ)文件mirror，調(diào)出新抓取的網(wǎng)頁，對(duì)比分析發(fā)現(xiàn)，增量抓取的網(wǎng)頁在正文內(nèi)容上有較大變化，對(duì)于相同的網(wǎng)頁則沒有進(jìn)行重復(fù)抓取，較去噪前Heritrix的增量抓取有較大的改善。

5 結(jié)語

目前，針對(duì)搜索引擎的增量式爬蟲受到越來越多的關(guān)注。本文以開源網(wǎng)絡(luò)爬蟲Heritrix為基礎(chǔ)，利用其擴(kuò)展性好的優(yōu)點(diǎn)，提出基于網(wǎng)頁去噪Hash的增量式抓取方法，在利用SHA-1算法對(duì)網(wǎng)頁產(chǎn)生Hash值前先對(duì)網(wǎng)頁進(jìn)行去噪，只對(duì)網(wǎng)頁正文部分進(jìn)行Hash計(jì)算，有效解決了經(jīng)典Hash算法過于敏感，對(duì)網(wǎng)頁變化判斷不準(zhǔn)確的問題，改善了網(wǎng)站的增量式抓取效率。由于網(wǎng)站結(jié)構(gòu)的復(fù)雜性和多變性，不同網(wǎng)站的更新變化頻率也不相同，本文只針對(duì)單一網(wǎng)站進(jìn)行了增量抓取實(shí)驗(yàn)，根據(jù)不同網(wǎng)站的變化頻率動(dòng)態(tài)調(diào)節(jié)抓取時(shí)間是下一步需要考慮的問題。

［1］Munish Kumar．A New Approach for Web Page Ranking solution：sNorm（p）Algorithm［J］．International Journal of Computer Applications，2010，9（10）：20-23．

［2］Dong H，Hussain F K．Focused Crawling for Automatic Service Discovery，Annotation and Classification in Industrial Digital Ecosystems［J］．IEEE Trans on Industrial Electronics，2011，58（6）：2106-2116．

［3］道格拉斯編．密碼學(xué)原理與實(shí)踐［M］．第3版．馮國登，譯．北京：電子工業(yè)出版社，2010：213-219．

［4］楊頌，歐陽柳波．基于Heritrix的面向電子商務(wù)網(wǎng)站增量爬蟲研究［J］．軟件導(dǎo)刊，2010，9（7）：38-39．

［5］雷凱，王東海．搜索引擎增量式搜集的實(shí)現(xiàn)與評(píng)測［J］．計(jì)算機(jī)工程，2008，34（13）：78-80．

［6］吳麗輝，白碩，張剛．Web信息采集中的哈希函數(shù)比較［J］．小型微型計(jì)算機(jī)系統(tǒng)，2006，27（4）：673-676．

［7］龔誠．網(wǎng)頁增量式采集技術(shù)研究［D］．哈爾濱：哈爾濱工業(yè)大學(xué)，2007：35-37．

［8］李莎莎．增量式Web信息采集與信息提取系統(tǒng)的研究與實(shí)現(xiàn)［D］．武漢：武漢理工大學(xué)，2011：22-25．

［9］黃月江，祝世雄．現(xiàn)代密碼分析學(xué)［M］．北京：國防工業(yè)出版社，2012：137-139．

［10］Heritrix官網(wǎng)［EB／OL］．http：／／crawler．a(chǎn)rchive．org．

［11］G．S．Manku，A．Jain，A．D．Sarma．Detecting nearduplicates for web crawling［C］／／Proceedings of the 16th International World Wide Web Conference，2007，20（2）：43-50．

［12］M．R．Henzinger．Finding near-duplicate web pages：a large-scale evaluation of algorithms［C］／／SIGIR，2006，12（3）：284-291．