基于Counting Bloom Filter的海量網頁快速去重研究

劉年國， 王　芬， 吳家奇， 李　雪， 陶　濤

(國網淮南供電公司， 安徽　淮南　232007)

?

基于Counting Bloom Filter的海量網頁快速去重研究

劉年國， 王芬， 吳家奇， 李雪， 陶濤

(國網淮南供電公司， 安徽淮南232007)

網頁去重是從給定的大量的數據集合中檢測出冗余的網頁，然后將冗余的網頁從該數據集合中去除的過程，其中基于同源網頁的URL去重的研究已經取得了很大的發展，但是針對海量網頁去重問題，目前還沒有很好的解決方案，文章在基于MD5指紋庫網頁去重算法的基礎上，結合Counting Bloom Filter算法的特性，提出了一種快速去重算法IMP-CBFilter。該算法通過減少I/O頻繁操作，來提高海量網頁去重的效率。實驗表明，IMP-CBFilter算法的有效性。

網頁去重；MD5指紋庫；Counting Bloom Filter；IMP-CBFilter算法

0　引言

隨著網絡技術的發展，網絡信息膨脹，搜索引擎已成為人們從互聯網獲取信息的重要手段，與此同時，人們對搜索引擎的質量要求越來越高。然而現在大量的重復網頁充斥著互聯網，將嚴重影響網頁檢索效率。據統計數據表明，近似網頁的比例占全部網頁的29%。清華大學IT可用性實驗室對Google、Baidu搜索引擎的研究表明，Google和Baidu的重復網頁占全部網頁的比率分別為3.4%和2.1%[1]。

與此同時，網頁去重又能帶來很多好處。首先，重復網頁的去除能夠節省存儲空間，并且可以提高檢索效率；其次，對重復網頁進行分析，可以在網頁下載時預先發現重復網頁，提高下載效率和準確度；最后，更少的重復資源可以提高搜索引擎的整體質量，提高可用度，為用戶提供方便。

綜上所述，在海量網頁中快速消除重復的網頁已經成為信息搜索中的研究重點。文獻[2]指出網頁去重的方法有三類：基于網頁結構和特征的抽取指紋信息方法、基于網頁內容的聚類方法、基于同源網頁的URL方法。本文只針對基于同源網頁的URL去重進行研究。為了實現海量網頁的快速去重, 本文在基于MD5指紋庫的網頁去重算法的基礎上，利用Counting Bloom Filter算法，提出一個節省空間的大規模數據表示和快速去重策略，以應對海量網頁去重的需求。在不影響去重效率的前提下，提出了IMP-CBFilter算法，解決了Counting Bloom Filter在處理海量網頁去重時所需要解決的計數器值溢出和更新問題。

1　相關研究

1.1基于同源網頁的URL去重技術

文獻[3]和[4]提出了基于Hash算法的網頁去重，需要維護一個Hash表，如果Hash函數設計得不好，在進行映射的時候，發生碰撞的幾率很大，此外使用的是URL作為鍵，URL字符串也占用了很大的存儲空間。當URL重復率較高的時候，需要進行較多的字符串匹配操作，這將嚴重影響URL的檢索速率。MD5指紋的網頁去重算法是Hash算法去重的一種，可以對URL字符串進行壓縮，得到一個壓縮字符串，并且MD5進行Hash映射碰撞的幾率非常小，但是它需要維持一個MD5指紋庫，對于海量的網頁(一份報告指出，截至2005年1月，網頁數量至少達到115億[5])的去重處理，將會產生頻繁的I/O操作瓶頸，嚴重影響網頁去重的速率。

文獻[6]和[7]提出基于查找樹的網頁URL去重算法，也可以節約存儲空間，用于URL檢索時，檢索算法的時間復雜度是O(n)，其中n是樹的層數，但是對于海量較長的URL，這也需要很大的空間，一般內存空間是無法承受的。而且每次檢索都需要做很長的字符比較，使得檢索速率較慢。

文獻[8]提出基于Rabin指紋方法的URL檢索算法，該算法將通過Rabin算法計算得到的指紋映射成16進制數字形成的字符串，再把此字符串存儲在一棵鍵樹中，然后利用鍵樹對URL檢索，該算法可以有效減少存儲空間。但是檢索效率不是太理想。

由上述所知，需要一種節省存儲空間的數據表示和快速判重的解決方案。本文在基于MD5指紋庫的網頁去重算法的基礎上，結合Counting Bloom filter算法，提出了滿足上述需求的網頁去重算法IMP-CBFilter。

1.2Couning Bloom Filter算法

Counting Bloom Filter算法是為了支持刪除操作而由標準Bloom Filter算法改進而來的。標準Bloom Filter算法是1970年由布隆提出的，它實際上是由一個很長的二進制數組和一系列隨機散列函數構成[9,10]。標準Bloom Filter算法的主要作用是判斷一個集合中是否存在某個元素，它的空間效率和時間效率都比較好，比較適合海量數據集的表示和檢測，缺點是有一定的誤判率和不支持刪除操作[11]。Counting Bloom Filter算法和標準Bloom Filter算法的不同主要在位數組上，標準Bloom Filter算法是對每一bit操作，但是Counting Bloom Filter算法是將位數組的每個bit擴展為多個bit來表示一個計數器。在插入元素的時候，通過對計數器的值進行加1操作來代替置1操作；在刪除元素的時候，不是進行置0，而是在計數器的值上減1，這樣就實現了刪除操作[12]。

Counting Bloom Filter算法也具有很好的時間和空間效率，利用這個特性可以解決海量網頁去重的頻繁I/O操作瓶頸問題，從而提高海量網頁去重效率。此外，Counting Bloom Filter算法還支持刪除操作，因此它支持對網頁刪除操作。雖然Counting Bloom Filter算法可以提高海量網頁去重效率和支持對網頁的刪除操作，但是它并沒有解決標準Bloom Filter算法存在的誤判率問題，這會導致用戶進行網頁去重時，網頁去重機制會誤判MD5指紋庫中已經存在該網頁。本文將結合Counting Bloom Filter算法和MD5指紋庫檢測技術，來研究海量網頁去重技術，從而提高網頁去重效率，其中涉及Counting Bloom Filter算法的計數器大小分析，Counting Bloom Filter算法的計數器溢出問題，網頁刪除時引起的Counting Bloom Filter算法的計數器值更新問題。

2　基于Counting Bloom Filter的海量網頁去重技術

2.1基于MD5指紋庫的網頁去重過程

圖1　基于指紋庫的網頁去重流程圖

基于MD5指紋庫的網頁去重技術主要是對網頁URL進行MD5指紋處理，然后根據MD5指紋庫，來進行下一步處理，具體流程如圖1所示。

首先，通過MD5指紋算法計算即將被處理的網頁URL的指紋值MD5-value，然后根據指紋值MD5-value查詢MD5指紋庫，如果MD5指紋庫中不存在指紋值MD5-value，說明該網頁不是重復網頁，則將該網頁保留下來，并將對應的指紋值MD5-value寫入MD5指紋庫中；如果MD5指紋庫中存在指紋值MD5-value，說明已經存在相同的網頁，則將該網頁刪除，并更新指紋庫信息，使指紋值MD5-value引用次數加1。

2.2Counting Bloom Filter算法的計數器大小分析

上述基于MD5指紋庫的網頁去重過程直接對指紋庫進行查詢是否存在即將被處理的網頁URL的指紋值MD5-value，在網頁數據量比較小時，指紋庫的指紋數據信息可以完全存放到服務器內存中，查找速度比較快，但是隨著網頁URL不斷地被檢測，指紋庫中的指紋數據信息也會不斷增加，會超過服務器內存的大小，這樣在指紋庫中進行查詢指紋MD5-value時，會頻繁地進行I/O操作，以至于影響海量網頁去重的效率。由第一章可知，可以利用Counting Bloom Filter算法的特性來解決這個問題。雖然Counting Bloom Filter算法可以支持文件的刪除操作，但是Counting Bloom Filter算法是以使用更多內存空間的代價換取支持刪除操作。本文接下來探討Counting Bloom Filter算法需要設置多大的計數器來滿足一般需要的刪除操作。

令集合元素個數為N個，Counting Bloom Filter算法所需哈希函數個數為k個，每個計數器占n個bit，計數器個數為m。假設第i個計數器被增加j次，那么它的概率為：

如果每個計數器占用的bit個數n為4時，那么計數器最大可以表示的數字為15，當大于15時就溢出。這個概率為：

由上面的結果可知，這個概率已經很小，可以應用到大部分應用場景。

2.3基于IMP-CBFilter算法的海量網頁去重研究

圖2　基于IMP-CBFilter算法的海量網頁去重流程

由于MD5指紋庫中存儲海量MD5指紋值，如果每次檢測網頁是否已經存在都需要查詢MD5指紋庫中是否存在和即將進行去重處理的網頁一樣的指紋，并且服務器的內存是一定的，就會產生頻繁的I/O操作，嚴重影響網頁去重的效率。為了解決這個問題，本文將在海量網頁去重問題上使用Counting Bloom Filter算法。雖然Counting Bloom Filter算法可以支持刪除操作，但是還是存在誤判率問題。本文結合Counting Bloom Filter算法的可刪除特性和指紋庫的無誤判率特性，提出了針對海量網頁URL去重技術——IMP-CBFilter算法，從而提高海量網頁去重的效率。但是根據2.2節對Counting Bloom Filter算法的計數器大小的探討可知，Counting Bloom Filter算法存在小概率的計數器溢出問題，為了解決這個問題，本文對計數的值進行如下處理。

假設每個計數器占用n個bit，這樣可以表示整數的范圍為0到2n-1。當一個網頁URL的指紋MD5-value經過Counting Bloom Filter算法的哈希函數計算映射到第i個計數器CountI。如果CountI的值為0到2n-2時，對CountI的值加1；如果CountI的值為2n-1時，CountI的值保持不變。由這個規定可知，對于每個計數器的值value，當value的范圍是0到2n-2時，說明已經至多有value個網頁URL的指紋MD5-value經過Counting Bloom Filter算法的哈希函數計算映射到這個計數器上；當value為2n-1，說明可能已經至少有2n-1個網頁URL的指紋MD5-value經過Counting Bloom Filter算法的哈希函數計算映射到這個計數器上。

雖然上述處理方法解決了Counting Bloom Filter算法的計數器溢出問題，但是進行網頁刪除操作時，如果被刪除網頁URL的指紋MD5-value經過Counting Bloom Filter算法的哈希函數計算映射到計數器CountI值value為2n-1時，此時無法對value進行正確處理。為了解決這個問題，本文解決方法如下。

當進行網頁去重處理時，如果通過Counting Bloom Fiter算法或者指紋庫判定該網頁為未出現的網頁時，則將該網頁URL的指紋值MD5-value對應的哈希值(計數器編號)添加到指紋庫中。經過這樣處理后，進行網頁刪除操作時，一旦遇到計數器的值value為2n-1時，只需要統計指紋庫中該計數器的個數，并對計數器值value進行正確更新。

通過解決上述Counting Bloom Filter算法在處理海量網頁去重時面臨的問題后，本文接下來將要闡述網頁去重技術的具體過程。具體流程如圖2所示。

假設Counting Bloom Filter算法所需哈希函數個數為k個，每個計數器占n個bit，計數器個數為m。首先通過MD5指紋算法計算網頁URL的指紋值MD5-value，然后通過Counting Bloom Filter算法的k個哈希函數計算指紋MD5-value的值，并記為hash1，hash2，……，hashk，并取得第hash1計數器，第hash2計數器，……，hashk計數器的值，記為M1，M2，M3,……，MK，然后判斷M1，M2，M3,……，MK中的值是否都不為0。

如果M1，M2，M3，……，MK中的值至少有一個為0時，可以確定MD5指紋庫中不存在和MD5-value一樣的網頁，則將網頁保留下來，并分別對M1，M2，M3，……，MK中的不為2n-1的值進行加1操作。因為網頁集中第一次存在該網頁，所以該網頁被引用次數Count為1。最后，將網頁URL的指紋MD5-value，引用次數Count=1以及hash1，hash2，……，hashk添加到MD5指紋庫中。

如果M1，M2，M3，……，MK中的值都不為0時，由于誤判率的存在，不能判斷MD5指紋庫中是否存在和MD5-value一樣的網頁，則在MD5指紋庫查找是否已經存在指紋MD5-value。如果MD5指紋庫中存在和指紋MD5-value一樣的指紋，說明網頁集中已經存在相同的網頁，則不需要保留該網頁，只需要將MD5指紋庫中相應指紋MD5-value的引用次數Count加1；如果MD5指紋庫中不存在指紋MD5-value時，說明MD5指紋庫中不存在和MD5-value一樣的網頁，則將網頁保留下來，并分別對M1，M2，M3，……，MK中的不為2n-1的值進行加1操作。因為網頁集中第一次存在該網頁，所以該網頁被引用次數Count為1。最后，將網頁URL的指紋MD5-value，引用次數Count=1以及hash1，hash2，……，hashk添加到MD5指紋庫中，并且分別對M1，M2，M3,……，MK中的不為2n-1的值進行加1操作。

上述海量網頁去重IMP-CBFilter算法不僅可以提高海量網頁去重的效率，還保證了Counting Bloom Filter的計數器不是多次記錄被引用的網頁，而是只記錄一次被引用的網頁，緩解了計數器的溢出，也進一步提高了海量網頁去重的效率。

3　實驗結果與分析

本實驗數據來源于數據堂。根據文獻[12]選取Counting Bloom Filter參數k和m/n，分別為8和20。在不同的數據量下(500000,1000000,1500000,2000000)進行測試實驗并進行分析，具體過程如下。

分別在上述四組數據量下，測試并記錄基于MD5指紋庫的網頁去重處理時間和基于IMP-CBFilter算法的網頁去重處理時間。 根據上述測試方案，得到的測試結果如圖3所示。

圖3　網頁去重技術數據對比圖

由圖3可知，隨著網頁數據量的增加，MD5指紋庫查詢去重技術指紋檢測時間延長越嚴重，這是因為主要遇到I/O操作瓶頸，而本文提出的IMP-CBFilter算法在進行指紋MD5-value檢測時利用Counting Bloom Filter算法減少了I/O操作，從而提高了指紋MD5-value檢測的速率，最終提高了海量網頁去重的效率。

4　總結與展望

針對加快海量網頁去重的需求，文章在基于MD5指紋庫的基礎上，結合Counting Bloom Filter算法的特性，提出IMP-CBFilter算法。并且分析和解決了其中的關鍵技術問題，主要包括Counting Bloom Filter算法的計數器溢出問題，Counting Bloom Filter算法的計數器大小問題，刪除操作時引起Counting Bloom Filter算法的計數器值更新問題。在此基礎上，詳細闡述了海量網頁去重過程。最后通過進一步的模擬實驗，證明了本文提出的IMP-CBFilter算法的有效性。

[1] 閻亞杰.網頁去重方法研究[J].電腦開發與應用，2008，21(8):60- 62.

[2] LI Zhi-yi, LIANG Shi-jin. National research on deleting duplicated web pages: status and summary[J]. Library and Information Service,2011(07):118-121.

[3] Nam G W, Park J H , Kim T Y. Dynamic management of URL based on object-oriented paradigm[C]∥ Proceedings of the International Conference on Parallel and Distributed Systems. Taiwan, China: IEEE Computer Society Press, 1998: 226-230.

[4] Marc Najork, Allan Heydon. High-performance web crawling[C]. Handbook of Massive Data Sets，Kluwer Academic Publishers Inc, 2001: 25- 45.

[5] Gulli A, Signorini A. The indexable web is more than 11.5 billion pages[C]. Special Interest Tracks and Posters of the 14th International Conference on World Wide Web WWW. 05. ACM Press, 2005: 902-903.

[6] Yun-ming Y E, Shui Y U, Fan-yuan M A, et al. On distributed web crawler: architecture, algorithms and strategy[J]. Acta Electronica Sinica, 2002(S1): 2008-2011.

[7] Kasom Koht-arsa, Surasak Sanguanpong. In-memory URL compression[C]. Chiangmai：National Computer Science and Engineering Conference(NCSEC-2001), 2001: 425- 428.

[8] JIANG Zong-li, ZHAO Qin, XIAO Hua, et al. High performance parallel crawler[J]. Computer Engineering and Design, 2006, 27(24): 4762- 4766.

[9] Bloom B. Space/time tradeoffs in hash coding with allowable errors[J]. Communication of the ACM, 1970, 13(7): 422- 426.

[10] Nasre R, Rajan K, Govindarajan R, et al. Scalable context-sensitive points-to analysis using multi-dimensional bloom filters[M]∥Programming Languages and Systems. Springer Berlin Heidelberg, 2009: 47- 62.

[11] 肖明忠,代亞非.Bloom Filter及其應用綜述[J].計算機科學,2004,30(4):180-183.

[12] LIU Wei, GUO Yuan-bo, HUANG Peng. Pattern matching engine based on multi-dimensional bloom filters[J]. Journal Of Computer Applications, 2011, 31(1): 107-109.

[責任編輯：張一]

Rapid De-Duplication of Massive Web Page Based on Counting Bloom Filter

LIUNian-guo,WANGFen,WUJia-qi,LIXue,TAOTao

(StateGridHuainanPowerSupplyCompany,Huainan232007,China)

Web page de-duplication is a process which detects redundant duplicate content pages from a given amount of data collection, and then removes from the collection. The research of web de-duplication based on URL filter has achieved great development. But there is no ideal solution to solve this kind of problem with massive web pages filter. Based on MD5 fingerprint database web de-duplication algorithm, and the utilization of Counting Bloom filter algorithm, an algorithm for rapid de-duplication named as IMP-CBFilter has been proposed in this paper. It could improve the efficiency of mass web pages filter by reducing the frequent operation of I/O. The results indicate higher performance by using IMP-CBFilter algorithm.

web page de-duplication; MD5 fingerprint database; Counting Bloom Filter; IMP-CBFilter algorithm

2016- 04-20

劉年國(1976-)，男，安徽淮南人，國網淮南供電公司信通分公司，高級工程師，副主任，從事信息安全研究多年。

王芬(1980-)，女，安徽淮南人，國網淮南供電公司信通分公司，工程師，信息運維班班長，從事信息安全研究多年。

TP393

A

1672-9706(2016)03- 0092- 06

吳家奇(1988-)，男，安徽淮南人，國網淮南供電公司信通分公司，助理工程師，信息運維班成員，從事信息安全研究多年。E-mail：466233993@qq.com

李雪(1987-)，女，安徽淮南人，國網淮南供電公司信通分公司，助理工程師，信息運維班成員，從事信息安全研究多年。

陶濤(1988-)，男，安徽淮南人，國網淮南供電公司信通分公司，工程師，通信運維班成員，從事通信運維研究多年。