基于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-)，男，安徽淮南人，国网淮南供电公司信通分公司，工程师，通信运维班成员，从事通信运维研究多年。