布隆过滤器

Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。例如 网页URL的去重,垃圾邮件的判别,集合重复元素的判别,查询加速(比如基于key-value的存储系统)等。

(1) 实例

  为了说明Bloom Filter存在的重要意义,举一个实例:

  假设要你写一个网络蜘蛛(web crawler)。由于网络间的链接错综复杂,蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”,就需要知道蜘蛛已经访问过那些URL。给一个URL,怎样知道蜘蛛是否已经访问过呢?稍微想想,就会有如下几种方案:

  1. 将访问过的URL保存到数据库。

  2. 用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。

  3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。

  4. Bit-Map方法。建立一个BitSet,将每个URL经过一个哈希函数映射到某一位。

  方法1~3都是将访问过的URL完整保存,方法4则只标记URL的一个映射位。

  以上方法在数据量较小的情况下都能完美解决问题,但是当数据量变得非常庞大时问题就来了。

  方法1的缺点:数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了?

  方法2的缺点:太消耗内存。随着URL的增多,占用的内存会越来越多。就算只有1亿个URL,每个URL只算50个字符,就需要5GB内存。

  方法3:由于字符串经过MD5处理后的信息摘要长度只有128Bit,SHA-1处理后也只有160Bit,因此方法3比方法2节省了好几倍的内存。

  方法4消耗内存是相对较少的,但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么?若要降低冲突发生的概率到1%,就要将BitSet的长度设置为URL个数的100倍。

  实质上上面的算法都忽略了一个重要的隐含条件:允许小概率的出错,不一定要100%准确!也就是说少量url实际上没有没网络蜘蛛访问,而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。

(2) Bloom Filter的算法

废话说到这里,下面引入本篇的主角——Bloom Filter。其实上面方法4的思想已经很接近Bloom Filter了。方法四的致命缺点是冲突概率高,为了降低冲突的概念,Bloom Filter使用了多个哈希函数,而不是一个。

###

Bloom Filter是1970年由Bloom提出的。它实际上是一个很长的二进制向量和一系列随机映射函数(Hash函数)。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。Bloom Filter广泛的应用于各种需要查询的场合中,如Orocle的数据库,Google的BitTable也用了此技术。

如果想判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表,树等等数据结构都是这种思路. 但是随着集合中元素的增加,我们需要的存储空间越来越大,检索速度也越来越慢(O(n),O(logn))。

这时候就可以利用哈希表这个数据结构(它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit array)中的一个点)。这样一来,我们只要看看这个点是不是1就知道可以集合中有没有它了。这就是Bloom Filter的基本思想。

但这时,哈希冲突会是一个问题:假设Hash函数是良好的,如果我们的位阵列长度为m个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m/100个元素。显然这就不叫空间效率了(Space-efficient)了。解决方法也简单,就是使用多个Hash,如果它们有一个说元素不在集合中,那肯定就不在。如果它们都说在,虽然也有一定可能性它们都在说谎,不过直觉上判断这种事情的概率是比较低的。这种多个Hash组成的数据结构就叫Bloom Filter。

一个Bloom Filter是基于一个m位的位向量(b1,…bm),这些位向量的初始值为0。另外,还有一系列的hash函数(h1,…hk),这些hash函数的值域属于1~m。下图是一个bloom filter插入x,y,z并判断某个值w是否在该数据集的示意图:

URL

上图中,m=18,k=3;插入x是,三个hash函数分别得到蓝线对应的三个值,并将对应的位向量改为1,插入y,z时,类似的,分别将红线,紫线对应的位向量改为1。查找时,当查找x时,三个hash值对应的位向量都为1,因此判断x在此数据集中。y,z也是如此。但是查找w时,w有个hash值对应的位向量为0,因此可以判断不在此集合中。但是,假如w的最后那个hash值比上图中的大1,这是就会认为w在此集合中,而事实上,w可能不在此集合中,因此可能出现误报。显然的,插入数据越多,1的位数越多,误报的概率越大。

Wiki的Bloom Filter词条有关于误报的概率的详细分析:Probability of false positives。从分析可以看出,当k比较大时,误报概率还是比较小的,因此这存储还是很空间有效滴。

Bloom Filter有以下几个特点:

不存在漏报(False Negative),即某个元素在某个集合中,肯定能报出来。
可能存在误报(False Positive),即某个元素不在某个集合中,可能也被爆出来。
确定某个元素是否在某个集合中的代价和总的元素数目无关。

优点:
相比于其它的数据结构,Bloom Filter在空间和时间方面都有巨大的优势。Bloom Filter存储空间和插入/查询时间都是常数。另外, Hash函数相互之间没有关系,方便由硬件并行实现。Bloom Filter不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

缺点:
另外,一般情况下不能从Bloom Filter中删除元素. 我们很容易想到把位列阵变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在Bloom Filter里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

Bloom Filter(布隆过滤器)原理

布隆过滤器需要的是一个位数组(这个和位图有点类似)和k个映射函数(和Hash表类似),在初始状态时,对于长度为m的位数组array,它的所有位都被置为0。对于有n个元素的集合S={s1,s2……sn},通过k个映射函数{f1,f2,……fk},将集合S中的每个元素sj(1<=j<=n)映射为k个值{g1,g2……gk},然后再将位数组array中相对应的array[g1],array[g2]……array[gk]置为1;如果要查找某个元素item是否在S中,则通过映射函数{f1,f2…..fk}得到k个值{g1,g2…..gk},然后再判断array[g1],array[g2]……array[gk]是否都为1,若全为1,则item在S中,否则item不在S中。这个就是布隆过滤器的实现原理。

实例

假定我们存储一亿个URL,我们先建立一个十六亿二进制(比特),即两亿字节的向量,然后将这十六亿个二进制全部设置为零。对于每一个URL,我们用八个不同的随机数产生器(F1,F2, …,F8) 产生八个信息指纹(f1, f2, …, f8)。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, …,g8。现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个URL都进行这样的处理后。一个针对这些URL的布隆过滤器就建成了。

URL

现在,让我们看看如何用布隆过滤器来检测一个URL是否已访问。我们用相同的八个随机数产生器(F1, F2, …, F8)对这个地址产生八个信息指纹 s1,s2,…,s8,然后将这八个指纹对应到布隆过滤器的八个二进制位,分别是 t1,t2,…,t8。如果该URL已访问,显然,t1,t2,..,t8 对应的八个二进制一定是一。这样在遇到任何已访问的URL,我们都能准确地发现。

布隆过滤器决不会漏掉任何一个已访问的URL。但是,它有一条不足之处。也就是它有极小的可能将未访问的URL判定为已访问的URL,因为有可能某个URL正巧对应个八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。在上面的例子中,误识概率在万分之一以下。

布隆过滤器的好处在于快速,省空间。但是有一定的误识别率。

常见的补救办法是在建立一个小的白名单,存储那些可能别误判的URL。

(3) Bloom Filter参数选择

(1)哈希函数选择

  哈希函数的选择对性能的影响应该是很大的,一个好的哈希函数要能近似等概率的将字符串映射到各个Bit。选择k个不同的哈希函数比较麻烦,一种简单的方法是选择一个哈希函数,然后送入k个不同的参数。

(2)Bit数组大小选择

  哈希函数个数k、位数组大小m、加入的字符串数量n的关系可以参考参考文献1。该文献证明了对于给定的m、n,当 k = ln(2)* m/n 时出错的概率是最小的。

  同时该文献还给出特定的k,m,n的出错概率。例如:根据参考文献1,哈希函数个数k取10,位数组大小m设为字符串个数n的20倍时,false positive发生的概率是0.0000889 ,这个概率基本能满足网络爬虫的需求了。

(4) 布隆过滤器应用

布隆过滤器在很多场合能发挥很好的效果,比如:网页URL的去重,垃圾邮件的判别,集合重复元素的判别,查询加速(比如基于key-value的存储系统)等。
下面举几个例子:

  1. 有两个URL集合A,B,每个集合中大约有1亿个URL,每个URL占64字节,有1G的内存,如何找出两个集合中重复的URL。
    很显然,直接利用Hash表会超出内存限制的范围。这里给出两种思路:

    第一种:如果不允许一定的错误率的话,只有用分治的思想去解决,将A,B两个集合中的URL分别存到若干个文件中{f1,f2…fk}和{g1,g2….gk}中,然后取f1和g1的内容读入内存,将f1的内容存储到hash_map当中,然后再取g1中的url,若有相同的url,则写入到文件中,然后直到g1的内容读取完毕,再取g2…gk。然后再取f2的内容读入内存。。。依次类推,知道找出所有的重复url。

    第二种:如果允许一定错误率的话,则可以用布隆过滤器的思想。

(4) Bloom Filter实现代码

  下面给出一个简单的Bloom Filter的Java实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import java.util.BitSet;

/**
* Bloom Filter
*/
public class BloomFilter {

// BitSet初始分配2^24个bit
private static final int DEFAULT_SIZE = 1 << 24;

// 不同哈希函数的种子,一般应取质数
private static final int[] seeds = new int[] { 3, 5, 7, 11, 13, 31, 37, 61 };

//
private BitSet bits = new BitSet(DEFAULT_SIZE);

// 哈希函数对象
private SimpleHash[] func = new SimpleHash[seeds.length];

public BloomFilter() {
int length = seeds.length;
for (int i = 0; i < length; i++) {
func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
}

/**
* 将字符串标记到bits中
*
* @param value
*/
public void add(String value) {
for (SimpleHash f : func) {
bits.set(f.hash(value), true);
}
}

/**
* 判断字符串是否已经被bits标记
*
* @param value
* @return
*/
public boolean contains(String value) {
if (value == null) {
return false;
}
boolean ret = true;
for (SimpleHash f : func) {
ret = ret && bits.get(f.hash(value));
}
return ret;
}

/**
* 哈希函数类
*
*/
public class SimpleHash {
private int cap;
private int seed;

public SimpleHash(int cap, int seed) {
this.cap = cap;
this.seed = seed;
}

/**
* 字符串哈希,选取好的哈希函数很重要<br>
* hash函数,采用简单的加权和hash
*
* @param value
* @return
*/
public int hash(String value) {
int result = 0;
int len = value.length();
for (int i = 0; i < len; i++) {
result = seed * result + value.charAt(i);
}
return (cap - 1) & result;
}

}// end class SimpleHash

}

参考:

[1] Pei Cao. Bloom Filters - the math. http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
[2] Wikipedia. Bloom filter. http://en.wikipedia.org/wiki/Bloom_filter
[3] http://blog.csdn.net/v_july_v/article/details/6685894
[4] http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html
[5] http://blog.csdn.net/dadoneo/article/details/6847481
[6] http://blog.csdn.net/jiaomeng/article/details/1495500
[7] http://www.cnblogs.com/hxsyl/p/4176280.html
[8] http://www.cnblogs.com/KevinYang/archive/2009/02/01/1381803.html