原创

计数型布隆过滤器(Counting Bloom Filter)

1. 前言

标准的 Bloom Filter 是一种比较简单的数据结构,只支持插入和查找两种操作。在所要表达的集合是静态集合的时候,标准 Bloom Filter 可以很好地工作,但是如果要表达的集合经常变动,标准Bloom Filter的弊端就显现出来了,因为它不支持删除操作。这就引出来了本文要谈的 Counting Bloom Filter,后文简写为 CBF。

2. Bloom Filter 为什么不支持删除

BF 为什么不能删除元素?我们可以举一个例子来说明。

比如要删除集合中的成员 dantezhao,那么就会先用 k 个哈希函数对其计算,因为 dantezhao 已经是集合成员,那么在位数组的对应位置一定是 1,我们如要要删除这个成员 dantezhao,就需要把计算出来的所有位置上的 1 置为 0,即将 5 和 16 两位置为 0 即可。

file

问题来了!现在,先假设 yyj 本身是属于集合的元素,如果需要查询 yyj 是否在集合中,通过哈希函数计算后,我们会去判断第 16 和 第 26 位是否为 1, 这时候就得到了第 16 位为 0 的结果,即 yyj 不属于集合。 显然这里是误判的。

3. Counting Bloom Filter

3.1 原理

Counting Bloom Filter 的出现,解决了上述问题,它将标准 Bloom Filter 位数组的每一位扩展为一个小的计数器(Counter),在插入元素时给对应的 k (k 为哈希函数个数)个 Counter 的值分别加 1,删除元素时给对应的 k 个 Counter 的值分别减 1。Counting Bloom Filter 通过多占用几倍的存储空间的代价, 给 Bloom Filter 增加了删除操作。基本原理是不是很简单?看下图就能明白它和 Bloom Filter 的区别在哪。

file

3.2 Counter 大小的选择

对于大多数应用程序来说,4位就足够了。

file

上述公式为计算第i个Counter被增加j次的概率,其中n为集合元素个数,k为Hash函数个数,m为Counter个数(对应着原来位数组的大小),前一部分表示从nk次哈希中选择j次,中间部分表示j次哈希都选中了第i个Counter,后一部分表示其它nk–j次哈希都没有选中第i个Counter,因此,第i个Counter的值大于j的概率可以限定为:

file

其中的第二次缩放用到了估计阶乘的斯特林公式:

file

在前面我们提到过k的最优值为(ln2)m/n,现在我们限制k ≤(ln2)m/n,就可以得到如下结论:

file

如果每个Counter分配4位,那么当Counter的值达到16时就会溢出。这个概率为:

file

这个值足够小,因此对于大多数应用程序来说,4位就足够了。
正文到此结束
本文目录