网页消重中多维布隆过滤器算法的运用论文
网页消重中多维布隆过滤器算法的运用论文
0 引言。
进入 21 世纪以后，随着电子计算机以及相关技术的迅猛发展和网络通信设备的大量普及，互联网的总体规模日益增大，日新月异的互联网技术以及海量的互联网信息也促进了社会、经济和科技的高速发展，增加了人们获取信息的渠道和速度。根据 2015 年 11月的最新数据，互联网上活动网站的数量达到了 902,997,800 个[1].网站的快速增长同时也意味着互联网中信息的急速膨胀，这些信息有些是有用的、有些是没用的、有些甚至完全是一些垃圾页面。面对由于互联网信息爆炸带来的信息孤岛、信息搜集困难等现象，人们发明了搜索引擎[2-4]以解决人们快速在互联网中找到所求的需求。但是，由于搜索引擎的采集器是由程序自动运行的，所以在抓取网页信息的同时，也会收集到很多重复网页。因此，如果没有一个高效的URL 去重模块，用以防止系统对已经抓取过的网页进行重复抓取，浪费宝贵的网络带宽和 CPU 时间，网络爬虫系统必将不堪重负。
在众多的 URL 去重技术中[5-7] ,布隆过滤器（Bloom Filter）[8]是其中优秀的一个，而其主要缺点在于较高的误识别率，但若使用多维布隆过滤器进行识别，可以大大降低误识别率。本文充分利用多维布隆过滤器查询快速、资源占有量少的特点，提出一种基于多维布隆过滤器的网页搜索去重方法，并给出程序设计方案及伪代码描述。
1 布隆过滤器。
在互联网中，要查找一个 URL 是否己经被抓取过，首先会想到的方法就是建立一个已抓取 URL 集合，然后查找新的 URL 是否存在已抓取 URL 集合中，如果用普通的顺序查找法，效率显然很低。而另一个比较简单的办法是采取传统的 hash 方法，即把每个URL 看成一个元素，这就需要把每个元素存储在 hash表中。在每次发现一个新的元素时，首先会通过 hash函数计算出这个元素的对应位置，之后使用这个位置的元素与这个新元素进行对比，如果两者相同，就说明这个新元素是重复的，反之则说明这个新元素是还未保存过的。传统的 hash 方法不会发生错误，而且存在于 hash 表中的数据也可以随时删除。但是，对于网页去重来说，只需判断一个特定的元素是否存在于集合中。因此，使用 hash 表保存下整个 URL 的内容会造成很大的内存浪费，然而内存资源有限，显然传统的 hash 方法不能很好的满足需求。
布隆过滤器[9-11]是由 Howard Bloom 在 1970 年提出的。他仅使用了一系列的 bit 位来保存数据，就可以检测一个元素是否已经存在于集合内，因此这种算法有着很好的空间利用率。但是为了节约空间，这种算法也存在着一些问题，它会对元素产生错判。不过庆幸的是，这个算法只会对在集合内的元素产生错判，但是并不会对不在集合内的元素产生错判。也就是说，如果布隆过滤器返还的结果如果是 false,说明元素确实不在集合内；如果返还的是 ture,只能说明元素可能存在于集合中。因此布隆过滤器实际上是一种牺牲了正确率换取时间和空间的算法。
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 的位向量对应该数据对象地址序列的位，如果均为 1,则该数据对象属于位向量集，否则不属于位向量集。但是，即使是采用均匀的哈希函数，并且使用了多个不同的 hash 函数，地址冲突也是不能避免的，因此布隆过滤器算法可能对位向量中的同一个位多次置 1.所以在进行数据查询时可能出现错判。关于布隆过滤器算法的缺点，会在 1.3 做详细讨论。
由以上分析可知，当布隆过滤器算法用于 URL去重时，由于每个地址不需要存储 URL 内容，只需存储 1 或 0.因此，每个地址只需要一个 bit 的空间。在每次网络爬虫得到一个新的 URL 的时候，会先判断这个元素是否属于集合，此时会对该元素重新进行多次哈希，当哈希后所得的对应位置都为 1 时，就判断该元素已经存在于集合中。那么就抛弃这个 URL,反之，就保存这个 URL,并且更新集合信息。具体原理图如下图 1.
1.2 布隆过滤器的优点。
布隆过滤器的优点是空间效率和查询时间都远远超过一般的算法。在占用空间上，布隆过滤器只需要哈希表 1/8~1/4 的大小就能解决同样的问题[13];更重要的是，在时间复杂度方面，布隆过滤器的查找时间为常数，不随过滤器增大而变慢。
1.3 布隆过滤器的缺点。
由以上分析可知，布隆过滤器算法比起普通算法，在时间和空间利用率上有着明显的优势，但是布隆过滤器算法也并非十全十美的，他存在着以下问题：
（1）因为利用固定的 hash 函数，并且得到的存储结果仅仅是某个槽号，因此查找的时间是个常数，但是每个槽中存储的不是实际 url,因此，可能会出现某个 url 映像的几个位置都己经被其他 url 占据的情况，产生错判。
（2）因为一个 url 对应多个槽，而且这些槽是可以重复利用的，因此不用处理冲突。但是正因为如此该算法不能随便删除某个已经存在的 url,否则会出错。
2 一种改进布隆过滤器算法。
根据上文提及到的，布隆过滤器的缺点是其误识别率，因此，如何在不降低判别性能的前提下降低布隆过滤器的误识别率就是研究的主要方向，本文基于此目的提出了一种改进的布隆过滤器算法，称为多维布隆过滤器。
2.1 基本思想。
多维布隆过滤器的基本想法是，通过使用 S 组位向量来表达数据集合，每组位向量对应k个hash函数，每组位向量包含 2 个位向量，其中一个是 N 位大小的V1,另一个是 N/k 位大小的 V2,每组 hash 函数划分到两部分 k1和 d2,用于 V1映射的是 k1,用于 V2映射的是 d2.
插入元素时，对于每组位向量，k1把该元素映射到 V1中并在 V1对应位置置 1,k2把数据元素映射到V2中并在 V2对应位置置 1.判定元素时，分别检查经过每组的 hash 函数 k1和 k2的映射后，V1和 V2的相关位置是否为 1,若有一组位向量全为 1,则认为该元素属于集合。
形式化描述多维布隆过滤器算法就是如下：
其中，（ s ,i , j）V表示第 s 组位向量中第 i 个向量中的第 j 位。
2.2 性能分析。
分析上述算法，可以看出来，多维布隆过滤器实际上是由多组基本的布隆过滤器构成的。每个布隆过滤器都作为多维布隆过滤器的一部分，参加整体运算。
因此，这里可以得到每组两个位向量的误识别率为：
由公式可知，在 s,k,n 这些参数一致的情况下，多维布隆过滤器同标准布隆过滤器相比，具有较低的误判率，并且维数越高，误判率越低。
不同维度的"过滤器在搜索去重中处于并行工作的状态，因此，基于此技术应用实现的多维布隆过滤器引擎查询时间和标准布隆过滤器引擎查询时间相等。
多维布隆过滤器引擎每一维都使用了 2 个标准的布隆过滤器引擎，参数一致的情况下，占用的存储空间是标准的布隆过滤器引擎的 2S 倍。
但是当维数过多时，要让每一个维度都处于并行工作状态对 CPU 要求较高，而且维数越多，对存储空间的需求也就越大。
3 应用与评价。
对于上面章节讨论的改进布隆过滤器算法-多维布隆过滤器算法的理论研究，我们仍需要进行大量的实验对其进行验证。本论文设计实现程序，从而模拟了两种算法，进而通过实验对两种算法的性能进行比较。
3.1 实验评价标准。
为了能够更加直观的对比试验结果，试验根据重复网页对搜索引擎的影响制定了以下三个主要的比较数据。他们是：
（1）运行速度：在一定抓取范围内，每种算法完成所用的时间。因为实际运用中网页数量过于庞大，因此这里设定一个固定时间，在这段时间内抓取到非重复 URL 的数量越多，则算法运行的速度越快。
速度=非重复 URL 数量/时间
（2）重复率：也就是在第二章提到的重要评价指标。
重复率=重复的 URL /抓取到的 URL 总数
（3）空间利用率：用于去重的位向量组所占空间。
用 Bit 为单位。
3.2 实验步骤。
本实验使用 Heritrix 作为爬虫，主要抓取一些时事新闻。因此，实验首先抓取几个常用的站页面做基础。本论文中是先抓取的新浪，网易，腾讯，搜狐。之后在百度里搜索某个新闻关键词做为基础。
开始抓取搜索到的网页。之后分别使用三种不同的算法，在抓取范围相同的前提下，设定时间为 1 小时。
并且，为了实验数据更加准确，本实验为每种算法设置不同的可选参数来验证前面的结论，具体如下：
●布隆过滤器：hash 函数个数 k;向量空间大小 N
●多维布隆过滤器：每组 hash 函数个数 k;向量空间大小 N;向量维度 S
3.3 结果与分析。
对于实验结果，我们首先对比多维布隆过滤器中，在 k=4,N=150 时，不同向量维度 S 下的误识别率变化，如图 2 所示。
从图 4.5 中，我们可以得到结论，误识别率随着 S值的增加而减小。S 值增加往往意味着，多维布隆过滤器算法所需的空间大小也相应提高，所以，在实际中，我们一般取 S 的值小于 4.
随后，我们固定 S=4,k=4,对比标准布隆过滤器和多维布隆过滤器在位向量空间变化时的误识别率，如图 3 所示。
由上图可得，多维布隆过滤器和标准布隆过滤器的误识别率随着位向量空间的增加一直降低，而且多维布隆过滤器误识别率相比标准过滤器一直都要低。
最后，我们固定 S=4,N=150,对比标准布隆过滤器和多维布隆过滤器在hash函数数量k变化时的误识别率，如图 4 所示。
从图 4 中，我们可以得到结论，误识别率随着 k值的增加而减小。k 值增加往往意味着，hash 算法所需的运算时间也相应提高，所以，在实际中，我们一般取 k 的值小于 4.
综上，通过实验可以得到结论，hash 函数数量以及位向量空间大小都可以影响布隆过滤器和多维布隆过滤器的误识别率，向量的维度也可以影响多维布隆过滤器的误识别率。并且，在相同 hash 函数数量或向量空间大小时，多维布隆过滤器的误识别率均低于布隆过滤器。
4 结语。
本文详细阐述了布隆过滤器的原理，通过对原理、实现步骤进行分析，得出此算法在网页消重中的作用以及缺陷。此后，根据布隆过滤器存在的误识别率的缺点，本文提出了一种改进的布隆过滤器算法--多维布隆过滤器，降低了传统布隆过滤器算法的误识别率。实验结果表明：多维布隆过滤器的误识别率要显着低于传统的布隆过滤器算法，能够显着提高网页消重的性能。
参考文献
[1] Netcraft.November 2015 Web Server Survey [OL].[2015-11-16].
[2] 阮卫华。搜索引擎优化技术的研究与实现[J].软件，2014,35（7）：72-77
[3] 郑晓健。面向领域主题的智能搜索引擎设计[J].软件，2014,35（3）：4-5
[4] 郭世龙，王晨升。主题爬虫设计与实现[J].软件，2013,34（12）：107-109
[5] Manber U.Finding similar files in a large file system[A].Proceedings of the USENIX winter 1994 technical conference[C].1994,1.