基于Counting Bloom Filter的海量網(wǎng)頁(yè)快速去重研究

劉年國(guó)， 王　芬， 吳家奇， 李　雪， 陶　濤

(國(guó)網(wǎng)淮南供電公司， 安徽　淮南　232007)

?

基于Counting Bloom Filter的海量網(wǎng)頁(yè)快速去重研究

劉年國(guó)， 王芬， 吳家奇， 李雪， 陶濤

(國(guó)網(wǎng)淮南供電公司， 安徽淮南232007)

網(wǎng)頁(yè)去重是從給定的大量的數(shù)據(jù)集合中檢測(cè)出冗余的網(wǎng)頁(yè)，然后將冗余的網(wǎng)頁(yè)從該數(shù)據(jù)集合中去除的過(guò)程，其中基于同源網(wǎng)頁(yè)的URL去重的研究已經(jīng)取得了很大的發(fā)展，但是針對(duì)海量網(wǎng)頁(yè)去重問(wèn)題，目前還沒(méi)有很好的解決方案，文章在基于MD5指紋庫(kù)網(wǎng)頁(yè)去重算法的基礎(chǔ)上，結(jié)合Counting Bloom Filter算法的特性，提出了一種快速去重算法IMP-CBFilter。該算法通過(guò)減少I(mǎi)/O頻繁操作，來(lái)提高海量網(wǎng)頁(yè)去重的效率。實(shí)驗(yàn)表明，IMP-CBFilter算法的有效性。

網(wǎng)頁(yè)去重；MD5指紋庫(kù)；Counting Bloom Filter；IMP-CBFilter算法

0　引言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，網(wǎng)絡(luò)信息膨脹，搜索引擎已成為人們從互聯(lián)網(wǎng)獲取信息的重要手段，與此同時(shí)，人們對(duì)搜索引擎的質(zhì)量要求越來(lái)越高。然而現(xiàn)在大量的重復(fù)網(wǎng)頁(yè)充斥著互聯(lián)網(wǎng)，將嚴(yán)重影響網(wǎng)頁(yè)檢索效率。據(jù)統(tǒng)計(jì)數(shù)據(jù)表明，近似網(wǎng)頁(yè)的比例占全部網(wǎng)頁(yè)的29%。清華大學(xué)IT可用性實(shí)驗(yàn)室對(duì)Google、Baidu搜索引擎的研究表明，Google和Baidu的重復(fù)網(wǎng)頁(yè)占全部網(wǎng)頁(yè)的比率分別為3.4%和2.1%[1]。

與此同時(shí)，網(wǎng)頁(yè)去重又能帶來(lái)很多好處。首先，重復(fù)網(wǎng)頁(yè)的去除能夠節(jié)省存儲(chǔ)空間，并且可以提高檢索效率；其次，對(duì)重復(fù)網(wǎng)頁(yè)進(jìn)行分析，可以在網(wǎng)頁(yè)下載時(shí)預(yù)先發(fā)現(xiàn)重復(fù)網(wǎng)頁(yè)，提高下載效率和準(zhǔn)確度；最后，更少的重復(fù)資源可以提高搜索引擎的整體質(zhì)量，提高可用度，為用戶(hù)提供方便。

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

1　相關(guān)研究

1.1基于同源網(wǎng)頁(yè)的URL去重技術(shù)

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

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

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

由上述所知，需要一種節(jié)省存儲(chǔ)空間的數(shù)據(jù)表示和快速判重的解決方案。本文在基于MD5指紋庫(kù)的網(wǎng)頁(yè)去重算法的基礎(chǔ)上，結(jié)合Counting Bloom filter算法，提出了滿(mǎn)足上述需求的網(wǎng)頁(yè)去重算法IMP-CBFilter。

1.2Couning Bloom Filter算法

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

Counting Bloom Filter算法也具有很好的時(shí)間和空間效率，利用這個(gè)特性可以解決海量網(wǎng)頁(yè)去重的頻繁I/O操作瓶頸問(wèn)題，從而提高海量網(wǎng)頁(yè)去重效率。此外，Counting Bloom Filter算法還支持刪除操作，因此它支持對(duì)網(wǎng)頁(yè)刪除操作。雖然Counting Bloom Filter算法可以提高海量網(wǎng)頁(yè)去重效率和支持對(duì)網(wǎng)頁(yè)的刪除操作，但是它并沒(méi)有解決標(biāo)準(zhǔn)Bloom Filter算法存在的誤判率問(wèn)題，這會(huì)導(dǎo)致用戶(hù)進(jìn)行網(wǎng)頁(yè)去重時(shí)，網(wǎng)頁(yè)去重機(jī)制會(huì)誤判MD5指紋庫(kù)中已經(jīng)存在該網(wǎng)頁(yè)。本文將結(jié)合Counting Bloom Filter算法和MD5指紋庫(kù)檢測(cè)技術(shù)，來(lái)研究海量網(wǎng)頁(yè)去重技術(shù)，從而提高網(wǎng)頁(yè)去重效率，其中涉及Counting Bloom Filter算法的計(jì)數(shù)器大小分析，Counting Bloom Filter算法的計(jì)數(shù)器溢出問(wèn)題，網(wǎng)頁(yè)刪除時(shí)引起的Counting Bloom Filter算法的計(jì)數(shù)器值更新問(wèn)題。

2　基于Counting Bloom Filter的海量網(wǎng)頁(yè)去重技術(shù)

2.1基于MD5指紋庫(kù)的網(wǎng)頁(yè)去重過(guò)程

圖1　基于指紋庫(kù)的網(wǎng)頁(yè)去重流程圖

基于MD5指紋庫(kù)的網(wǎng)頁(yè)去重技術(shù)主要是對(duì)網(wǎng)頁(yè)URL進(jìn)行MD5指紋處理，然后根據(jù)MD5指紋庫(kù)，來(lái)進(jìn)行下一步處理，具體流程如圖1所示。

首先，通過(guò)MD5指紋算法計(jì)算即將被處理的網(wǎng)頁(yè)URL的指紋值MD5-value，然后根據(jù)指紋值MD5-value查詢(xún)MD5指紋庫(kù)，如果MD5指紋庫(kù)中不存在指紋值MD5-value，說(shuō)明該網(wǎng)頁(yè)不是重復(fù)網(wǎng)頁(yè)，則將該網(wǎng)頁(yè)保留下來(lái)，并將對(duì)應(yīng)的指紋值MD5-value寫(xiě)入MD5指紋庫(kù)中；如果MD5指紋庫(kù)中存在指紋值MD5-value，說(shuō)明已經(jīng)存在相同的網(wǎng)頁(yè)，則將該網(wǎng)頁(yè)刪除，并更新指紋庫(kù)信息，使指紋值MD5-value引用次數(shù)加1。

2.2Counting Bloom Filter算法的計(jì)數(shù)器大小分析

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

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

如果每個(gè)計(jì)數(shù)器占用的bit個(gè)數(shù)n為4時(shí)，那么計(jì)數(shù)器最大可以表示的數(shù)字為15，當(dāng)大于15時(shí)就溢出。這個(gè)概率為：

由上面的結(jié)果可知，這個(gè)概率已經(jīng)很小，可以應(yīng)用到大部分應(yīng)用場(chǎng)景。

2.3基于IMP-CBFilter算法的海量網(wǎng)頁(yè)去重研究

圖2　基于IMP-CBFilter算法的海量網(wǎng)頁(yè)去重流程

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

假設(shè)每個(gè)計(jì)數(shù)器占用n個(gè)bit，這樣可以表示整數(shù)的范圍為0到2n-1。當(dāng)一個(gè)網(wǎng)頁(yè)URL的指紋MD5-value經(jīng)過(guò)Counting Bloom Filter算法的哈希函數(shù)計(jì)算映射到第i個(gè)計(jì)數(shù)器CountI。如果CountI的值為0到2n-2時(shí)，對(duì)CountI的值加1；如果CountI的值為2n-1時(shí)，CountI的值保持不變。由這個(gè)規(guī)定可知，對(duì)于每個(gè)計(jì)數(shù)器的值value，當(dāng)value的范圍是0到2n-2時(shí)，說(shuō)明已經(jīng)至多有value個(gè)網(wǎng)頁(yè)URL的指紋MD5-value經(jīng)過(guò)Counting Bloom Filter算法的哈希函數(shù)計(jì)算映射到這個(gè)計(jì)數(shù)器上；當(dāng)value為2n-1，說(shuō)明可能已經(jīng)至少有2n-1個(gè)網(wǎng)頁(yè)URL的指紋MD5-value經(jīng)過(guò)Counting Bloom Filter算法的哈希函數(shù)計(jì)算映射到這個(gè)計(jì)數(shù)器上。

雖然上述處理方法解決了Counting Bloom Filter算法的計(jì)數(shù)器溢出問(wèn)題，但是進(jìn)行網(wǎng)頁(yè)刪除操作時(shí)，如果被刪除網(wǎng)頁(yè)URL的指紋MD5-value經(jīng)過(guò)Counting Bloom Filter算法的哈希函數(shù)計(jì)算映射到計(jì)數(shù)器CountI值value為2n-1時(shí)，此時(shí)無(wú)法對(duì)value進(jìn)行正確處理。為了解決這個(gè)問(wèn)題，本文解決方法如下。

當(dāng)進(jìn)行網(wǎng)頁(yè)去重處理時(shí)，如果通過(guò)Counting Bloom Fiter算法或者指紋庫(kù)判定該網(wǎng)頁(yè)為未出現(xiàn)的網(wǎng)頁(yè)時(shí)，則將該網(wǎng)頁(yè)URL的指紋值MD5-value對(duì)應(yīng)的哈希值(計(jì)數(shù)器編號(hào))添加到指紋庫(kù)中。經(jīng)過(guò)這樣處理后，進(jìn)行網(wǎng)頁(yè)刪除操作時(shí)，一旦遇到計(jì)數(shù)器的值value為2n-1時(shí)，只需要統(tǒng)計(jì)指紋庫(kù)中該計(jì)數(shù)器的個(gè)數(shù)，并對(duì)計(jì)數(shù)器值value進(jìn)行正確更新。

通過(guò)解決上述Counting Bloom Filter算法在處理海量網(wǎng)頁(yè)去重時(shí)面臨的問(wèn)題后，本文接下來(lái)將要闡述網(wǎng)頁(yè)去重技術(shù)的具體過(guò)程。具體流程如圖2所示。

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

如果M1，M2，M3，……，MK中的值至少有一個(gè)為0時(shí)，可以確定MD5指紋庫(kù)中不存在和MD5-value一樣的網(wǎng)頁(yè)，則將網(wǎng)頁(yè)保留下來(lái)，并分別對(duì)M1，M2，M3，……，MK中的不為2n-1的值進(jìn)行加1操作。因?yàn)榫W(wǎng)頁(yè)集中第一次存在該網(wǎng)頁(yè)，所以該網(wǎng)頁(yè)被引用次數(shù)Count為1。最后，將網(wǎng)頁(yè)URL的指紋MD5-value，引用次數(shù)Count=1以及hash1，hash2，……，hashk添加到MD5指紋庫(kù)中。

如果M1，M2，M3，……，MK中的值都不為0時(shí)，由于誤判率的存在，不能判斷MD5指紋庫(kù)中是否存在和MD5-value一樣的網(wǎng)頁(yè)，則在MD5指紋庫(kù)查找是否已經(jīng)存在指紋MD5-value。如果MD5指紋庫(kù)中存在和指紋MD5-value一樣的指紋，說(shuō)明網(wǎng)頁(yè)集中已經(jīng)存在相同的網(wǎng)頁(yè)，則不需要保留該網(wǎng)頁(yè)，只需要將MD5指紋庫(kù)中相應(yīng)指紋MD5-value的引用次數(shù)Count加1；如果MD5指紋庫(kù)中不存在指紋MD5-value時(shí)，說(shuō)明MD5指紋庫(kù)中不存在和MD5-value一樣的網(wǎng)頁(yè)，則將網(wǎng)頁(yè)保留下來(lái)，并分別對(duì)M1，M2，M3，……，MK中的不為2n-1的值進(jìn)行加1操作。因?yàn)榫W(wǎng)頁(yè)集中第一次存在該網(wǎng)頁(yè)，所以該網(wǎng)頁(yè)被引用次數(shù)Count為1。最后，將網(wǎng)頁(yè)URL的指紋MD5-value，引用次數(shù)Count=1以及hash1，hash2，……，hashk添加到MD5指紋庫(kù)中，并且分別對(duì)M1，M2，M3,……，MK中的不為2n-1的值進(jìn)行加1操作。

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

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

本實(shí)驗(yàn)數(shù)據(jù)來(lái)源于數(shù)據(jù)堂。根據(jù)文獻(xiàn)[12]選取Counting Bloom Filter參數(shù)k和m/n，分別為8和20。在不同的數(shù)據(jù)量下(500000,1000000,1500000,2000000)進(jìn)行測(cè)試實(shí)驗(yàn)并進(jìn)行分析，具體過(guò)程如下。

分別在上述四組數(shù)據(jù)量下，測(cè)試并記錄基于MD5指紋庫(kù)的網(wǎng)頁(yè)去重處理時(shí)間和基于IMP-CBFilter算法的網(wǎng)頁(yè)去重處理時(shí)間。 根據(jù)上述測(cè)試方案，得到的測(cè)試結(jié)果如圖3所示。

圖3　網(wǎng)頁(yè)去重技術(shù)數(shù)據(jù)對(duì)比圖

由圖3可知，隨著網(wǎng)頁(yè)數(shù)據(jù)量的增加，MD5指紋庫(kù)查詢(xún)?nèi)ブ丶夹g(shù)指紋檢測(cè)時(shí)間延長(zhǎng)越嚴(yán)重，這是因?yàn)橹饕龅絀/O操作瓶頸，而本文提出的IMP-CBFilter算法在進(jìn)行指紋MD5-value檢測(cè)時(shí)利用Counting Bloom Filter算法減少了I/O操作，從而提高了指紋MD5-value檢測(cè)的速率，最終提高了海量網(wǎng)頁(yè)去重的效率。

4　總結(jié)與展望

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

[1] 閻亞杰.網(wǎng)頁(yè)去重方法研究[J].電腦開(kāi)發(fā)與應(yīng)用，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及其應(yīng)用綜述[J].計(jì)算機(jī)科學(xué),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.

[責(zé)任編輯：張一]

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

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

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

TP393

A

1672-9706(2016)03- 0092- 06

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

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

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