布隆过滤器

维基百科，自由的百科全书

[编辑] 历史

Bloom Filter(布隆过滤器)是 1970 年由 Bloom 在^[1]中提出的. 一般都说它是一种 simple space-efficient randomized data structure for representing a set in order to support membership queries . Bloom Filter 可以用于检索一个元素是否在一个集合中. 它的优点是空间效率和查询时间都远远超过一般的算法，缺点是 false positive 和删除困难.

所谓的 false positive 是一个概率论中的概念，可以简单的理解成把假的说成真的. 相对的, false negative 就是把真的说成假的.

[编辑] 基本思想

如果我们想判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定. 链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢( $O (n), O (log n)$ ). 不过世界上还有一种叫作 hash table 的数据结构. 它可以通过一个 hash 函数将一个元素映射成一个 bit array 中的一个点. 这样一来，我们只要看看这个点是不是1就知道可以集合中有没有它了. 这就是 Bloom Filter 的基本思想.

Hash 面临的问题就是冲突. 假设 hash 函数是良好的，如果我们的 bit array 长度为 $m$ 个点，那么如果我们想将冲突率降低到例如 1%, 这个 Hash Table 就只能容纳 $m / 100$ 个元素. 显然这就不叫 space-efficient 了. 解决方法也简单，就是使用多个 hash, 如果它们有一个说元素不在集合中，那肯定就不在. 如果它们都说在，虽然也有一定可能性它们在说谎，不过直觉上判断这种事情的概率是比较低的.

[编辑] 性能

我们来分析一下 false positive 的概率.

假设我们有 $k$ 个 hash 函数，我们的 bit-array 长度为 $m$ , 里面已经插入了 $n$ 个元素. 我们的 hash 函数是非常好的.

当我们插入第一个元素时，经过一个 hash 它使1个确定的点为0的概率就是 $1 - \frac{1}{m}$ , 所有 hash 函数都使这个点为0的概率就是 $(1 - \frac{1}{m})^k$ . 插入 $n$ 个元素后依然为0的概率是 $(1 - \frac{1}{m})^{kn}$ , 那么它为1的概率就是 $1- (1 - \frac{1}{m})^{kn}$ .

当我们判断一个实际上不在这个集合中的元素时，所有 hash 函数都说在的可能性就是: $\left(1- \left(1 - \frac{1}{m}\right)^{kn}\right)^k$ . $m$ 和 $n$ 都逼近无穷大时，这个概率大约就是 $\left(1-e^{-kn/m}\right)^k$ .

上式表明, bit-array 长度( $m$ )越大; 元素数量( $n$ )越少, false positive 的概率越小.

另外，对 $k$ (hash 函数的数量)求一个偏微分，可以找到一个使 false positive 概率最小的 $k$ . 这个数是:

$\frac{m}{n}\ln 2 \approx \frac{9m}{13n} \approx 0.7\frac{m}{n}$ ,

false positive 的概率为:

$\left(\frac{1}{2}\right)^{k} \approx {0.6185}^{m/n}$ .

上式实际上是在说, $k$ 合适的情况下，每个元素平均长度是 9.6 bit 时 Bloom Filter 出错的概率是 1%. 这个长度每增加 4.8 位错误率降低 10 倍.

[编辑] 优点

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

Bloom Filter 可以表示全集，其它任何数据结构都不能;

$k$ 和 $m$ 相同，使用同一组 hash 函数的两个 Bloom Filter 的交并差运算可以使用位操作进行.

[编辑] 缺点

但是 Bloom Filter 的缺点和优点一样明显. False Positive 是其中之一. 随着存入的元素数量增加, false 率随之增加. 但是如果元素数量太少，则使用 hash table 足矣.

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

在降低 false 率方面，有不少工作，使得出现了很多 Bloom Filter 的变种.

[编辑] 变种

[编辑] Counting filters

就是前面提到的支持删除元素的 filter.

[编辑] Bloomier filters

通过使用级连的 Bloom Filter.

B Chazelle, J Kilian, R Rubinfeld, A Tal - Proc. 15th ACM/SIAM Symposium on Discrete Algorithms (SODA), 2004

这个技术解决的是这样的问题:

有一个大集合 $D = \left\{0, 1, 2, \dots, n-1 \right\}$ , $S$ 是它的子集, $R = \left\{ X, 1, 2, \dots, 2^r-1 \right\}$ , $f$ 是一个 $D \mapsto R$ 的关系. 现在对 $S$ 中的任意一个元素 $a$ , 我想看看 $f (a)$ 是多少.

Bloomier Filter 保证，对于 $S$ 中的元素，返回正确的值; 对于 $S$ 以外的值，尽可能返回 $X$ .

举例而言, Bloomier Filter 适合于这样的应用: 北航图书馆有6层，每层都有不少藏书(当然实际情况并非如此), 管理员使用 Bloomier Filter 来存储 Book1-Floor1 这样的 Key-value pair. 我现在想查询 bookX 这本书在几层. Bloomier Filter 保证，如果图书馆收藏了这本书，那么就一定会返回正确的楼层; 如果没有收藏，则尽可能返回错误.

以一个最简单的情况说明，如果 $R = \left\{ X, 1, 2\right\}$ , 那么建立两组 Bloom Filter, 把 $f (a) = 1$ (2)的放到 $A 0$ ( $B 0$ )中. 如果发现这个元素会导致 false, 那么将它放入小一些的 $A 1$ ( $B 1$ )中，再发现 false 就放更入小一些的 $A 2$ ( $B 2$ )中，如此往复. 实际上过了几层还会 false 的元素已经不多了，那时使用一个其它的数据结构保存就可以了.

Bloomier filters 没有完全解决 false positive 的问题.

[编辑] Generalized Bloom Filters

R. P. Laufer, P. B. Velloso, and O. C. M. B. Duarte, “Generalized Bloom filters,” Electrical Engineering Program, COPPE/UFRJ, Tech. Rep. GTA-05-43, Sept. 2005.WebPage(加州大学)

Bloom Filter 可以表示全集，这也给它带来了安全隐患. 在 P2P 应用中，一个恶意的结点可以通过构造 all-one bloom filter 对外声称它拥有所有的资源，导致其它结点都将请求发给它，造成破坏; 在使用 Bloom filter 回溯攻击者时，攻击者通过精心构造标志符(IP 地址?)导致 Filter 全1, 回溯无法进行. 这一切都是因为两个原因:

Bloom Filter 使用全1表示全集;
False positive 的概率随着 n 的增加而增加，最终总是会上升到1.

Generalized Bloom Filters 试图解决这个问题. Generalized Bloom Filters 的 false positive 是有上限的，作为代价, Generalized Bloom Filters 引入了 false negative.

Fig. 1 - 插入过程.

上图描述了 Generalized Bloom Filters 的插入过程. Generalized Bloom Filters 不再需要将 bit-array 初始化成全0, 在插入时，通过 $g_1, g_2, \dots, g_{k_0}$ 这 $k 0$ 个 hash 函数将点 Reset(即变成0) , 通过 $h_1, h_2, \dots, h_{k_1}$ 这 $k 0$ 个 hash 函数将点 Set(即变成1) . 规定如果某个 $h$ 和某个 $g$ 冲突, Set 检索过程不言自明. 很显然, false negative 将可能发生.

作者通过论证，证明 false positive 和 false negative 的概率都是有上限的.

$F_p = \left(\frac{k_0}{k_0 + k_1}\right)^{k_0} + \left(\frac{k_1}{k_0 + k_1}\right)^{k_1}$

$F n$ 的表达式则麻烦一些，但是它只和 $k 0$ , $k 1$ , $m / n$ 有关. 设计者可以先预设 $F p$ , 再通过调整 $m / n$ 限定 $F n$ , 于是二者都是可以控制的. (我觉得这个说法有些牵强，毕竟其它的实现也可以通过调整 $m / n$ 降低 false 率.)

[编辑] Bloom Filter 与 R-tree

华工的 Yu Hua 和 Dan Feng 在 RBF: A New Storage Structure for Space-Efficient Queries for Multidimensional Metadata in OSS 这篇文章中提出将 Bloom Filter 和 R-tree 结合，以支持所谓的点查询(例如列出 size=100GB 的文件)和范围查询(例如列出 size>=100GB 的文件). R-tree 对后者支持较好，而在 R-tree 的结点中使用 Bloom Filter 达到 space-efficient 的目的. 他们说这个查询的复杂度是 $O (1)$ . 但是现在无法看到具体是怎么实现的.

[编辑] 外部链接

[编辑] 其它

Bloom Filter 是一个集合的有损编码.

[编辑] 参考

^ Space/time trade-offs in hash coding with allowable errors

[_note-0] Space/time trade-offs in hash coding with allowable errors

[1]