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 位。
