网页消重中多维布隆过滤器算法的运用

《网页消重中多维布隆过滤器算法的运用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、网页消重中多维布隆过滤器算法的运用　　0引言。　　进入21世纪以后，随着电子计算机以及相关技术的迅猛发展和X络通信设备的大量普及，互联X的总体规模日益增大，日新月异的互联X技术以及海量的互联X信息也促进了社会、经济和科技的高速发展，增加了人们获取信息的渠道和速度。根据2015年11月的最新数据，互联X上活动X站的数量达到了902,997,800个[1].X站的快速增长同时也意味着互联X中信息的急速膨胀，这些信息有些是有用的、有些是没用的、有些甚至完全是一些垃圾页面。面对由于互联X信息爆炸带来的信息孤岛、信息搜集困难等现象，人们发明了搜索引擎[2-4]以解决人们快速在互联X中找到所求的需

2、求。但是，由于搜索引擎的采集器是由程序自动运行的，所以在抓取X页信息的同时，也会收集到很多重复X页。因此，如果没有一个高效的URL去重模块，用以防止系统对已经抓取过的X页进行重复抓取，浪费宝贵的X络带宽和CPU时间，X络爬虫系统必将不堪重负。　　在众多的URL去重技术中[5-7],布隆过滤器（BloomFilter）[8]是其中优秀的一个，而其主要缺点在于较高的误识别率，但若使用多维布隆过滤器进行识别，可以大大降低误识别率。本文充分利用多维布隆过滤器查询快速、资源占有量少的特点，提出一种基于多维布隆过滤器的X页搜索去重方法，并给出程序设计方案及伪代码描述。　　1布隆过滤器。　　在互联X

3、中，要查找一个URL是否己经被抓取过，首先会想到的方法就是建立一个已抓取URL集合，然后查找新的URL是否存在已抓取URL集合中，如果用普通的顺序查找法，效率显然很低。而另一个比较简单的办法是采取传统的hash方法，即把每个URL看成一个元素，这就需要把每个元素存储在hash表中。在每次发现一个新的元素时，首先会通过hash函数计算出这个元素的对应位置，之后使用这个位置的元素与这个新元素进行对比，如果两者相同，就说明这个新元素是重复的，反之则说明这个新元素是还未保存过的。传统的hash方法不会发生错误，而且存在于hash表中的数据也可以随时删除。但是，对于X页去重来说，只需判断一个特定

4、的元素是否存在于集合中。因此，使用hash表保存下整个URL的内容会造成很大的内存浪费，然而内存资源有限，显然传统的hash方法不能很好的满足需求。　　布隆过滤器[9-11]是由Ho在1970年提出的。他仅使用了一系列的bit位来保存数据，就可以检测一个元素是否已经存在于集合内，因此这种算法有着很好的空间利用率。但是为了节约空间，这种算法也存在着一些问题，它会对元素产生错判。不过庆幸的是，这个算法只会对在集合内的元素产生错判，但是并不会对不在集合内的元素产生错判。也就是说，如果布隆过滤器返还的结果如果是false,说明元素确实不在集合内；如果返还的是ture,只能说明元素可能存在于集合

5、中。因此布隆过滤器实际上是一种牺牲了正确率换取时间和空间的算法。　　1.1布隆过滤器介绍。　　布隆过滤器的原理如下[12]:一个布隆过滤器由k个相互独立的哈希函数h1,h2,，hk（k值域为[0,1,2,，m],是整数）和一个位向量组成，初始时，位向量内全部为0.当需要插入一个新数据时，用k个哈希函数对n个数据对象的集合S={sl,s2,，sn}（m>n）的某个数据对象计算一个地址序（hi（s1），h2（sl），，hk（sl）），然后将位向量对应地址序列的位置置为1,称该位向量装入了s1.　　对于查询某个数据对象s2是否存在于集合时，同样先检查表示s2的位向量对应该数据对象地址序

6、列的位，如果均为1,则该数据对象属于位向量集，否则不属于位向量集。但是，即使是采用均匀的哈希函数，并且使用了多个不同的hash函数，地址冲突也是不能避免的，因此布隆过滤器算法可能对位向量中的同一个位多次置1.所以在进行数据查询时可能出现错判。关于布隆过滤器算法的缺点，会在1.3做详细讨论。　　由以上分析可知，当布隆过滤器算法用于URL去重时，由于每个地址不需要存储URL内容，只需存储1或0.因此，每个地址只需要一个bit的空间。在每次X络爬虫得到一个新的URL的时候，会先判断这个元素是否属于集合，此时会对该元素重新进行多次哈希，当哈希后所得的对应位置都为1时，就判断该元素已经存在于集合

7、中。那么就抛弃这个URL,反之，就保存这个URL,并且更新集合信息。具体原理图如下图1.　　1.2布隆过滤器的优点。　　布隆过滤器的优点是空间效率和查询时间都远远超过一般的算法。在占用空间上，布隆过滤器只需要哈希表1/8~1/4的大小就能解决同样的问题[13];更重要的是，在时间复杂度方面，布隆过滤器的查找时间为常数，不随过滤器增大而变慢。　　1.3布隆过滤器的缺点。　　由以上分析可知，布隆过滤器算法比起普通算法，在时间和空间利用率上有着明显的