基于網頁去噪Hash的增量式網絡爬蟲研究＊

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

1 引言

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

經典的Hash算法有MD5和SHA1［3］，在實驗過程中發現用Hash算法定義網頁的變化過于嚴格，Hash值產生敏感度高，微小的網頁變化，例如：網頁中與主要內容無關的廣告、圖片、版權信息、分割條、導航鏈接、搜索服務和版權信息等，都會導致Hash值的很大變化，網絡爬蟲仍然會將大部分正文內容沒有變化的網頁抓取下來，達不到增量抓取的預期效果。

針對上述問題，本文將網頁去噪與Hash算法結合起來，提出去噪后的Hash 產生方法，即在對網頁Hash值產生前去掉網頁中的微小變化內容，稱之為噪聲，然后對網頁正文部分產生Hash值并保存到Hash表中，基于去噪后的Hash值來判斷網頁是否發生變化。在開源網絡爬蟲Heritrix進行實驗后，結果表明，去噪后的網頁Hash 值能較好的反應網頁正文的變化情況。

2 相關研究

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

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

3 增量抓取模塊

3．1 Hash算法模塊

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

基于以上理論基礎，將Hash函數應用到增量式網絡爬蟲中，對抓取的網頁進行加密生成Hash值，通過對比新舊網頁的Hash值來判斷網頁是否發生變化。Hash 值相同則表示網頁沒有發生變化，不用進行抓取；Hash值不同則表明網頁發生了變化，需要進行增量抓取。

本文的增量抓取過程基于開源網絡爬蟲Heritrix［10］。Heritrix 是SourceForge 上基于Java 的開源爬蟲，采用了模塊化的設計，它由核心類和插件模塊構成。其系統架構如圖1所示。

圖1 Heritrix系統架構圖

Heritrix只能對網頁進行一次性抓取，要實現增量抓取必須在Heritrix中添加增量抓取模塊，本文在Heritrix的處理鏈中加入HttpContentDigest和ChangeEvaluator兩個模塊實現Heritirx增量抓取。

HttpContentDigest：該模塊對Fetch Processing Chain抓取下來的網頁產生一個Hash 值，該Hash值就是為了判斷網頁是否發生了變化。接口類java．security．MessageDigest 中的哈希函數SHA-1提供了Hash值產生功能。該模塊關鍵代碼如下：

圖2 Processing chain

1）創建一個消息摘要值，即Hash值，對文件進行處理；

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：該模塊對爬取網頁的當前Hash值與過去的Hash值進行比較，如果相等則處理鏈的進一步處理跳過，直接進入到提交鏈模塊，并且將爬取的該URI進行標記。該模塊關鍵代碼如下：

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（））；

重新設定鏈接：curi．clearOutlinks（）；

取消日志記錄：curi．addAnnotation（"unchanged"）；

設置文件內容為空，不寫入磁盤：

curi．setContentSize（0）；

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

3．2 網頁去噪模塊

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

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

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

3）噪聲去除策略：對于一個給定的網站，同一類型的網頁集合的布局設計基本上是一致的，相對應的DOM 樹也會有相同或相似的結構。基于此，對這個網頁先進行預處理將一些無關標簽去掉，將其轉換為XML文檔。然后將處理好的XML 文檔轉換為DOM 樹，先對其進行分類處理確定屬于哪一類型，然后從同一類型的網頁集合中選取其對應的DOM 樹進行遍歷，來尋找其相同的節點，并將相應的信息塊提取出來。

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

算法：噪聲提取

輸入：同一域名下的所有網頁的DOM 樹

輸出：噪聲提取模型

（1）從輸入集中隨機選擇兩個DOM 樹；

（2）令DOM 樹的body節點作為初始節點；

（3）若節點都含有子節點，則轉到（4），否則轉（7）；

（4）遍歷節點的子節點；

（5）將兩個節點的子節點做一一對比，若所有的子節點有相同，則轉（3），否則轉（6）；

（6）回溯到子節點的父節點，并從左到右記錄父節點以及父節點的所有兄弟節點；

（7）從左到右記錄所有節點；

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

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

（10）結束。

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

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

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

4 實驗結果與分析

本實驗的硬件環境為：CPU：Intel Celeron E3300 雙核；主頻：2．5GHz／前端總線頻率：800MHz；內存：DDR2 3GB 雙通道；工作頻率：400MHz；硬盤：7200 轉。軟件配置環境：Eclipse平臺。

本實驗從2013年7月30日至8月3日，對中安在線（www．anhuinews．com）進行了連續6次抓取實驗，設置條件如下：Heritrix版本：1．14．4；最大線程：50；最大深度：3；其它設置：Heritrix1．14．4默認設置。

1）網頁去噪前增量抓取實驗

在Heritrix處理鏈中加入增量處理模塊：HttpContentDigest和ChangeEvaluator，對中安在線進行第一次普通抓取，間隔1小時后在普通抓取的基礎上進行第二次增量抓取，連續六組實驗情況如圖4所示。

圖4 網頁去噪前增量抓取實驗

可以看出，在加入增量抓取模塊后，每組實驗中，第二次增量抓取的網頁數相對第一次普通抓取網頁減少，但第一次抓取的網頁大部分還是被抓取下來，只實現了小部分網頁的增量抓取。調出Heritrix的Hash值產生的日志文件，對比每次實驗中HttpContentDigest模塊對第一次普通抓取網頁與第二次增量抓取網頁產生的Hash值，隨機選取其中六個網頁，其六組實驗的Hash值如表1所示。

同一網頁在每組實驗中，兩次抓取的時間間隔均在1 小時以內，產生的Hash 值確完全不同，這樣在網頁提取時，對相同的網頁又進行了二次抓取。進入網頁存儲文件mirror，調出兩次抓取的網頁，對比分析發現，網頁僅僅是在訪問量與網頁時間上有細微的差別，網頁正文沒有變化，可見網頁噪聲對基于Hash的增量抓取結果影響很大。

2）網頁去噪后增量抓取實驗

在Heritrix處理鏈中加入網頁去噪模塊與增量抓取模塊，以相同的方法對中安在線進行六組普通抓取與增量抓取實驗，實驗情況如圖5所示。

表1 Hash值對比

圖5 網頁去噪后增量抓取實驗

對網頁進行去噪處理后，可以發現，Heritrix增量抓取的網頁明顯減少。進入網頁存儲文件mirror，調出新抓取的網頁，對比分析發現，增量抓取的網頁在正文內容上有較大變化，對于相同的網頁則沒有進行重復抓取，較去噪前Heritrix的增量抓取有較大的改善。

5 結語

目前，針對搜索引擎的增量式爬蟲受到越來越多的關注。本文以開源網絡爬蟲Heritrix為基礎，利用其擴展性好的優點，提出基于網頁去噪Hash的增量式抓取方法，在利用SHA-1算法對網頁產生Hash值前先對網頁進行去噪，只對網頁正文部分進行Hash計算，有效解決了經典Hash算法過于敏感，對網頁變化判斷不準確的問題，改善了網站的增量式抓取效率。由于網站結構的復雜性和多變性，不同網站的更新變化頻率也不相同，本文只針對單一網站進行了增量抓取實驗，根據不同網站的變化頻率動態調節抓取時間是下一步需要考慮的問題。

［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］道格拉斯編．密碼學原理與實踐［M］．第3版．馮國登，譯．北京：電子工業出版社，2010：213-219．

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

［5］雷凱，王東海．搜索引擎增量式搜集的實現與評測［J］．計算機工程，2008，34（13）：78-80．

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

［7］龔誠．網頁增量式采集技術研究［D］．哈爾濱：哈爾濱工業大學，2007：35-37．

［8］李莎莎．增量式Web信息采集與信息提取系統的研究與實現［D］．武漢：武漢理工大學，2011：22-25．

［9］黃月江，祝世雄．現代密碼分析學［M］．北京：國防工業出版社，2012：137-139．

［10］Heritrix官網［EB／OL］．http：／／crawler．archive．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．