布隆过滤器原理及使用

什么是布隆过滤器

1970年，由布隆提出来的一个用于判断元素是否在集合中的高效的算法，集合中的元素可以增加，但是要删除一个元素比较困难，同时还有少量的误报率。

在数据量比较小的时候，我们可以使用 Hash 来判断元素是否命中，但是当元素增加起来后，Hash 算法需要的空间就会急速增长，查找时间也会增加。布隆过滤器主要用在样本集合量大但是很少有删除元素，不要求爬虫URL去重等。

布隆过滤器原理

爬虫URL去重

初始条件

设数据集合 ai(i∈[1,n])，作为待操作的集合。
Bloom Filter 用一个长度为 0。
≥m。

加入url的处理

首先经过 1。

检查是否重复

首先将该元素经过上步中类似操作，获得 0 存在，表明，此元素不在之前的集合中，为新元素。

执行示意图

布隆过滤器原理及使用

算法特点

对于已经在集合中的元素，通过上述中的查找方法，一定可以判定该元素在集合中。
对于不在集合中的元素，可能会被误判在集合中。

布隆过滤器的选择与质量评估

m

设样本个数为 $n$

k

根据已求得的 $m$

计算真实失误率

根据向上取整的 $m 、 n 、 k$

Python实现布隆过滤器

安装PyBloom

Python中有多个实现 BloomFilter 的包详情可以自己搜索Pypi，本文中主要介绍 PyBloom，可以通过 pip 进行安装。

pip install pybloom

也可以直接去作者的github上下载源码编译安装。

python setup.py install

PyBloom源码解析

pybloom主要包括两个类：BloomFilter和ScalableBloomFilter。

BloomFilter 是一个定容的过滤器，in运算符即可。

ScalableBloomFilter类

在ScalableBloomFilter的 add 方法中可以看到：

布隆过滤器原理及使用

其本质依旧是创建了一个BloomFilter类。

BloomFilter类

在BloomFilter的 __init__ 函数中：

布隆过滤器原理及使用

可以看到它引用了Python的bitarray库来实现布隆过滤器。

在BloomFilter的 add 方法中：

布隆过滤器原理及使用

可以看到，我们可以通过设置 False。

PyBloom的使用

使用BloomFilter

from pybloom import BloomFilter
bf = BloomFilter(capacity=10000, error_rate=0.001)
bf.add('test-bf')
print 'test-bf' in bf

True

使用ScalableBloomFilter

from pybloom import ScalableBloomFilter
sbf = ScalableBloomFilter(mode=ScalableBloomFilter.SMALL_SET_GROWTH)
sbf.add('test-sbf')
print 'sbf' in sbf

False

什么是布隆过滤器