单劫++王纯

摘要：内容管理系统的内容采集主要由爬虫进行搜集，但内容重复与否绝大多数情况下是根据内容所在的页面URI进行判定。作为一个完善的内容管理系统，必须具备对已有内容资源的识别功能。本文通过介绍布隆过滤器，并与传统的判重方式进行对比，同时改进布隆过滤器并应用于内容管理系统的资源判重的功能中，解决了内存占用无限增加，查询时间不断增长，记录内容无法删除等问题，实现了高效快速的资源判重。

关键词：计算机工程；布隆过滤器；内容管理系统；爬虫；哈希

中图分类号：TP399

文献标识码：A

DOI：10.3969/j.issn.1003-6970.2016.01.008

0 引言

Web信息的采集通常是利用网络爬虫等工具遍历万维网，它把万维网看作一个以网页为节点，网页间链接为边的超大规模有向图，然后利用图的遍历算法对万维网进行遍历。在网络遍历的过程中.需要判断待采集的页面是否已经采集过了，这就需要把已经采集的网页地址记录下来，组成已采集网页地址集合（记为：visited-set），当新的采集开始之前，首先判断其地址是否在visited-set中，如在其中，表示网页已经采集，否则采集网页，把网页地址放在visited-set中，从而避免网页的重复采集，浪费资源。为了实现集合中数据的快速查找，需要把URL映射为集合中的地址，这就需要设计一种高效且冲突率低的散列算法；同时由于万维网上网页数据的巨大，普通的Hash算法已经不能满足空间的要求，所以更需要一种节约空间的算法。

本文运用Bloom Filter设计了一种节省空间的大规模数据表示和查找方式，应用到内容管理系统中，以应对海量信息采集中判重的需求，文中分析了布隆过滤器相对于HashMap的优越之处，同时指出布隆过滤器的使用条件和弱点，并针对本系统的自身特点和需求，提出了一种针对过滤器的改进方案并予以实现，运用到该系统中。

1 布隆过滤器

1.1 概念

布隆过滤器是一种空间和时间效率很高的随机访问型数据结构，它利用位数组表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter看似简洁，但这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，BloomFilter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省，同时摒弃了冲突导致的一系列冲突处理。

1.2 集合表示和元素查询

初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。

为了表达S={xl，x2，…，xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1，…，m}的范围中。对任意一个元素X，第i个哈希函数映射的位置hi （x）就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在图2中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位）。

在判断v是否属于这个集合时，我们对v应用k次哈希函数，如果所有hi （y）的位置都是1（1≤i≤k），那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。图3中y1就不是集合中的元素。y2或者属于这个集合，或者刚好是一个false positive。

2 布隆过滤器在内容管理系统中的使用

内容管理系统由若干部分构成，其功能主要可以分为三大部分：来源、存储和展示。其中，布隆过滤器主要应用在来源部分中的去重。

作为内容管理系统，来源主要有两个方面：爬虫和手动上传。对于绝大多数的数据搜集，都是通过爬虫的自动化爬取获得的。因此，在不经过人为的干涉的情况下，如何能够有效地抓取不同的内容，防止重复内容对空间和时间的浪费，才是过滤过程的关键所在。因此，为了能让过滤器有的放矢，首先需要明确爬虫的工作机理。下面对爬虫的工作机制做一个简单的介绍。

2.1 爬虫工作流程

简单来说，爬虫可以归结为一个生产者和消费者的问题。

在爬取内容时经历了从“发现”到“爬取”的过程。“发现”，即为对目标链接的获取，目标来自于初始链接和内容中存在的链接。一旦发现目标链接之后，就要将其放入待爬取的队列中去，等待“爬取”功能的调用。那么，为了能够快速的判断哪些链接需要访问，哪些已经爬取过，最简单的办法就是，将已经访问过的链接（url）放入集合，在每次将新的链接放入队列之前，首先与集合中的历史信息相比对，若没有，则放入队列，否则丢弃。因此，历史信息的比对模块就应该放在生产者到队列之间，提供过滤作用。最通用的方式即为HashMap进行历史信息的存储，但针对HashMap的不足之处，本文使用了BloomFilter进行了替换，下面针对HashMap的不足进行了说明。

2.2 HashMap

如图5所示，HashMap的主体是由Entry[]构成的，该数组中的每一个Entry节点都由Key和Value组成。HashMap通过key.hashcode计算所在entry对应在数组中的下标位置，如果遇到冲突，则以链表的形式储存在链尾。

因此，hashMap首先需要存储对象本身和它的key，其使用场景更趋向于，通过key去获取对象本身，而不仅仅是判断该对象是否存在，这样就会在仅仅需要判断对象是否存在的使用场景下造成极大的浪费，原因如下：

对象本身所需要的空间并不固定，有的对象很大，有的仅仅是基本类型，因此，该空间无法预估。

hashmap本身为了达到快速查找，在0（1）的时间复杂度获取对象的目的，随着对象的加入，需要不断的扩容，这同时造成了时间和空间上的开销，使得”增加历史资源”的性能降低。

为了降低哈希的冲突率，hashmap本身会在资源总量的基础上多预留一部分空间，从而造成浪费。

综合以上HashMap的不足之处，结合“过滤及判重”功能的需求，布隆过滤器的优势非常突出：

1.不需要存储对象本身，只需要知道该对象是否存在。

2.可以在0 （l）时间复杂度内完成对对象存在性的判定。

3.在预估存储目标的数量级后，可基本确定空间大小，不需动态调整。

但是，布隆过滤器也没有做到十全十美，它依靠了错误率和冗余空间换取了高速度的查询，相比于HashMap，加入了“错误率”这一概念，替换了“冲突”。下面分析BloomFilter的错误率情况，及所需位数组大小的判定条件。

2.3 错误率估计

Bloom Filter在判断一个元素是否属于它表示的集合时会有一定的错误率（false positive rate），不妨设：m为bit数组长度，n为集合元素个数，k为hash函数的个数和p为误判概率。

假设kn

现在查询一个不在集合中的元素，当它所对应的k个位置都为1时会发生误判，这个概率p是：（（1-1/m）^kn）^k.既然Bloom Filter要靠多个哈希函数将集合映射到位数组中，如果哈希函数的个数多，那么在对一个不属于集合的元素进行查询时得到0的概率就大；但另一方面，如果哈希函数的个数少，那么位数组中的0就多。为了得到最优的哈希函数个数，在给定m和n的情况下，当k取以下值时，误判率p的值最小：k=（m/n） In2-0.7（m/n）此时误判率p等于：Pmin=（1-1/2）^k=0.6185^（m/n）。换句话说，要想保持错误率低，最好让位数组有一半还空着。

2.4 位数组的大小

在不超过一定错误率的情况下，设Bloom Filter至少需要m位才能表示全集中任意n个元素的集合。假设全集中共有u个元素，允许的最大错误率为e，下面我们来求位数组的位数m。

假设X为全集中任取n个元素的集合，F（X）是表示X的位数组。那么对于集合X中任意一个元素x，在s=F（X）中查询x都能得到肯定的结果，即s能够接受x。显然，由于Bloom Filter引入了错误，s能够接受的不仅仅是X中的元素，它还能够e（u-n）个误判（false positive）。因此，对于一个确定的位数组来说，它能够接受总共n+e（u-n）个元素。在n+e（u-n）个元素中，s真正表示的只有其中n个，所以一个确定的位数组可以表示n+e（u-n）/n个集合。m位的位数组共有2m个不同的组合，进而可以推出，m位的位数组可以表示2^m（n+e（u-n）/n）个集合。全集中n个元素的集合总共有（u！）/（n！*（u_n）！），因此要让m位的位数组能够表示所有n个元素的集合，必须有（2^m）（n+e（u-n）/n）>（u！）/（n！*（u-n）！）.

综上所述，我们得出结论：在错误率不大于e的情况下，m至少要等于n log2 （1/e）才能表示任意n个元素的集合。

上文中计算出，当k= In2- （m/n）时错误率f最小，这时f=（1/2） k=（1/2） mln2/n。现在令f≤e，可以推出n《log2（1/e））/ln2）=nlog2elog2 （l/e）≤m

这个结果比之前计算的下界n log2 （l/e）大了log2（e）≈1.44倍。这说明在哈希函数的个数取到最优时，要让错误率不超过e，m至少需要取到最小值的1.44倍。

3 布隆过滤器的工程改进和实现

上面所述，布隆过滤器引入了错误率这一项，传统的过滤器还有一个最大的缺陷，即：无法删除已有的记录。由于原生的布隆过滤器所引用的数组是bit数组（这也是它体积小的最大优势），因此，当hash散列之后，对应位只有0和1的区别。最终，即便多个对象被某个散列函数定位到同一个下标，值也只能标记为1，而不能累计。在这一点上，如果使用integer数据类型对比bit数据类型，则可以做到累计的效果，因此具备删除的可行性，但是势必会使得整个数组的体积增大，integer为32位，则整个数组将至少膨胀为原来的32倍。单从这一点上对过滤器的优化不是很困难，只要存储够用即可。为了适用于内容管理系统，为系统增加删除资源的功能，因此过滤器选择优化方案即为将bit替换为integer类型。

在替换前，根据上述公式，取n为1000000个页面链接，￡为0.01错误率，算得的最小空间是0.88M，不妨取IM（工程中采用1M），而替换后过滤器的总大小为32M，但很好的在原有误判率的基础上解决了删除的问题。由于误判的定性为：将不存在的对象判做有，因此对于存在的对象而言，是不可能判做没有的，因此删除的过程中不会存在错误。基于上述的理论推导，对改进版的布隆过滤器具体实现参数如下：

public class BloomFilter{

private intm；

private intn；

private intk；

private Atomiclnteger count= new Atomicclnteger （0）：

int[] vector；

static final Charset charset=Charset.forName（“UTF-8”）：

static final String algorithmName=“MD5”；

）

重要参数分析说明：

整型变量m为vector的长度，也就是过滤器所能容纳的最多的int整型个数，如果vector数组越大，在其他变量保持不变的情况下能够减少过滤器的冲突率。

整型变量n，表示预期元素数量；m和n所代表的意义是不同的，需要区分开。n所代表的元素数量并不是指int数组的数量。由于课题需要对统一资源定位符（ur1）进行判重，因此n所代表的就是url的数量，即整个过滤器预期能够在某个准确率内的最大容纳url的数值。

整型变量k，表示hash函数个数，即当一个url进行判重时，需要对该url的摘要进行hash散列的次数。由于过滤器需要根据hash散列的结果寻找对应位置的integer，进而判定是否重复，因此需要进行多次相互之间没有关联的hash散列求值，在一定的准确率内，k拥有一个最优解。

容器vector，即布隆过滤器的主要数据结构，数据类型为Integer数组，每个元素为一个32位的int值，用于累计命中次数，拥有删除的能力。

algorithmName参数限定了生成消息摘要的算法。JDK自带使用MD5算法对字符串进行摘要加密的方法。该算法以5 12位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。BloomFilter会借助经过k次散列得到的k个下标位置的相应值，判断是否重复。若这k个位置上存在为0的计数，则认为该url没有出现过，反之，若k个位置均不为0，意味着该url已经重复。

系统使用集合规模为350000的int数组，且根据系统需求，误判率为百分之一即可，经测算所占空间约为20M，可完全满足系统的空间要求，同时能够确保判重顺利正常的进行。根据以上对布隆过滤器的改造，需要实现的关键步骤是对目标对象进行散列求值，以下为生成Hash码的具体实现，使用MD5生成摘要，然后进行k次hash获得32位的int数组，数组中的每一个数字代表布隆过滤器的下标，然后再依次对k个下标中的int位进行比对，判断是否存在重复url。以下为改进版布隆过滤器生成Hash摘要的主要实现部分：

public static int[] createHashes （byte[] data， int k）{

int[] result=new int[k]；

int curhsh=0；

byte salt=0；

while （curHash

byte[] digest；

synchronized （digestFunction）{

digestFunction.update （salt）；

salt++：

digest= digestFunction.digest （data）；

）

for （int i=0i

int h=0；

for（intj=（I*4）；j<（i*4_卜4）；j++）{

h<<=8；

hl=（（int） digest[j]） &OxFF；

）

result[curHash]=h；

curHash++；

）

）

return result；

）

其中，对于MD5生成的每一个digest值，由于保证了其128位的长度，因此可以统一对其进行每四个字节分割，再将获得的四个字节首位连接起来，得到一个新的integer值，即为最终散列结果。结果返回长度为k的int数组，其中的每个元素都是散列结果。

4 结论

布隆过滤器在识别邮件黑名单、过滤重复资源的效率上有一定优势，同时因其同等数量级下占用内存小，查找效率高而获得广泛应用。尤其是在内容管理系统中，使得过滤功能可以非常的高效而轻量，做到事半功倍。但是，如此高效便捷的工具使用也是有条件的，系统必须容忍一定概率的误判。虽然改进版的布隆过滤器能够提供删除功能，但是代价为将原有空间增大了32倍。至于使用时，是选择零错误率的Hash Map还是选择高效的Bloom Filter，就要看工程的背景了。在本项目中，原生的布隆过滤器无法达到项目对已经记录在案的资源进行删除的需求，因此对布隆过滤器进行了改造，使用int数组数据类型替换了原有的BitSet数据类型，并更改优化了原有的基于bit的哈希散列值的生成方式，使得生成hash结果更高效。改进版布隆过滤器在本系统中得到了很好的应用。