布隆过滤器

布隆过滤器（）是1970年由伯頓·霍華德·布隆（Burton Howard Bloom）提出的高空间效率的概率数据结构。由一个通过一系列散列函数对样本元素映射而成的二进制位数组组成。布隆过滤器可用于检索一个元素是否在一个集合中，其空间效率和查询时间效率都远超一般算法。它不会产生假阴性（漏报），但有一定的假阳性（误报）率且难以删除元素。

基本概念
如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为O(n),O(\log n),O(1)。

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。所以布隆过滤器可能会产生假陽性，但不会产生假阴性。

算法描述
一個「空布隆过滤器」是一個由位組成的位数组（），所有位都被設置為0。它配備了個不同的散列函数，這些函數將集合元素映射到個可能的數組位置之一。為了達到最佳效果，散列函數應為均勻分佈且獨立。通常，是一個小的常數，它取決於期望的假陽性（誤報）率，而與和要添加的元素數量成正比。

要「添加」一個元素，將其分別輸入到個散列函數中，以獲得個數組位置。將所有獲得的位置的位設置為1。

要「檢驗」一個元素是否在集合中，將其輸入到每個散列函數中，以獲得個數組位置。如果這些位置「存在」位為0的位置，則該元素一定不在集合中；如果它在集合中，那麼當它被插入時，所有位都應該已經是1。如果所有位都已為1，説明該元素可能在集合中，又或許這些位是在插入其他元素時碰巧被設置爲1，從而導致假陽性。就一個簡單的布隆过滤器而言，並不能區分這兩種情況，但更先進的技術可以解決這個問題。

設計個不同的獨立散列函數的要求對於大的可能是難以實現的。對於一個具有寬輸出的良好散列函數，這種散列的不同位域之間應該幾乎沒有相關性，因此這種散列類型可以用於通過將其輸出切片成多個位域來生成多個「不同」的散列函數。或者，可以將個不同的初始值（例如0, 1, ...,  − 1）傳遞給一個接受初始值的散列函數；或者將這些值加入（或追加）到鍵。對於較大的和/或，散列函數之間的獨立性可以放寬，而假陽性率的增加可以忽略不計。（具體而言，展示了使用增强双重散列和三重散列（双散列的變體，實際上是用兩個或三個散列值播種的簡單隨機數生成器）導出個索引的有效性。）

這樣簡單的布隆过滤器无法移除元素，因爲無法得知它映射到的位中的哪些位應該被移除。雖然將這些位中的任何一位設置為零足以移除該元素，但它也會移除任何恰好映射到該位的其他元素。由於簡單的算法沒有提供任何方法來確定是否已添加任何其他影響要移除元素的位的元素，因此清除任何位都會引入假阴性（漏報）的可能性。

若要模拟从布隆过滤器中一次性移除元素的操作，可以引入一个辅助布隆过滤器（「移除過濾器」），用于存储已移除的元素。 然而，第二個过滤器中的假陽性會變成複合过滤器（「原過濾器」與「移除過濾器」的聯合體）中的假阴性，這是不被希望遇到的。在這種方法中，卻無法重新添加先前被移除的元素，因為還須將其從「移除過濾器」中移除，這又會回到最初的問題。

常見的情況是，所有鍵（待過濾的所有元素）都能夠被獲取（可用），但枚舉它們的代价较高（例如，需要多次的硬碟讀取）。當假陽性率變得太高時，可以重新生成过滤器；但此類事件應該是相對罕見的。

优劣分析
相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数（O(k)）。另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

假阳性率是布隆过滤器的不足之一。随着存入的元素数量增加，假阳性率随之增加。但是如果元素数量太少，则使用散列表足矣。在降低假阳性率方面，有不少工作，使得出现了很多布隆过滤器的变种。

时间与空间优势
尽管存在假阳性风险，布隆过滤器在表示集合的数据结构中比其他数据结构（如自平衡二叉搜索树、字典树、哈希表或简单的数组或链表）具有显著的空间优势。这些数据结构中的大多数都需要存储至少数据项本身，这可能需要从少量位（对于小整数）到任意数量的位（例如对于字符串，字典树是例外，因为它们可以在具有相同前缀的元素之间共享存储）。然而，布隆过滤器完全不存储数据项，且须为过滤器的实际存储另行提供解决方案。链式结构会产生额外的线性空间开销用于指针。相比之下，具有1%误报率和最优k值的布隆过滤器，每个元素只需要大约9.6位，无论元素的大小如何。这一优势部分源于其紧凑性，继承自数组，部分源于其概率性质。通过为每个元素增加大约4.8位，可以将1%的误报率降低一个数量级。

然而，如果潜在值的数量较少且其中许多值可能存在于集合中，布隆过滤器很容易被确定性位数组超越，后者只需要为每个潜在元素使用一位。如果哈希表开始忽略冲突并仅存储每个桶是否包含条目的信息，它们将获得空间和时间优势；在这种情况下，它们实际上已成为k=1的布隆过滤器。

布隆过滤器还具有一个不寻常的特性，即添加项目或检查项目是否在集合中的时间都是固定常数，O(k)，完全独立于集合中已有的项目数量。没有其他常数空间集合数据结构具有这种特性，但稀疏哈希表的平均访问时间可能使其在实践中比某些布隆过滤器更快。然而，在硬件实现中，布隆过滤器表现出色，因为它的k次查找是独立的并且可以并行化。

要理解其空间效率，可以将通用布隆过滤器与其k=1的特殊情况进行比较。如果k=1，为了保持足够低的假阳性率，而只允许一小部分位被置位为1，这意味着数组必然非常大并包含很长的全零序列。相对于其大小，数组所包含的信息量较低。通常意义的布隆过滤器（k大于1）允许更多的位被置位为1，同时仍然保持较低的假阳性率；如果参数（k和m）选择得当，约有一半的位会被置位，并且这些位要明显随机，从而最小化冗余并最大化信息量。

假阳性率
假设哈希函数以相等概率选择数组中的每个位置。设为数组的总位数，则某个位在元素插入过程中“未被”某个哈希函数置位为1的概率为

1 - \frac 1 m

设为哈希函数的数量，并且每个哈希函数之间没有显著的相关性，那么该位未被任何哈希函数置位为1的概率是(1-\frac1m)^k。

通过关于e^{-1}的著名公式，

\lim_{m \to \infty}(1-\frac{1}m)^m=\frac{1}e

得出：对于较大的，

(1-\frac1m)^k=((1-\frac1m)^m)^{k/m}\approx{e}^{-k/m}

假设过滤器已经被插入了个元素，那么某个位仍为0的概率是

(1-\frac1m)^{kn}\approx{e}^{-kn/m}

于是，为1的概率是

1-(1-\frac1m)^{kn}\approx{1}-{e}^{-kn/m}

假设测试一个不在集合中的元素。基于上述的概率计算，由哈希函数计算的位数组的每个位置都为1。所有这些位置都为1的概率，将导致算法错误地报告该元素在集合中（假阳性），通常给出概率为

\epsilon=(1-[1-\frac1m]^{kn})^k\approx{(1-e^{-kn/m})^k}

然此论未必完善，因其假设每位置位之概率互相独立。假设有较理想之近似，可得：假阳性率随（数组总位数）的增加而降低，并随（插入元素数）的增加而升高。

不考虑独立性，假阳性的真实概率是

\frac{1}{m^{k(n+1)}}\sum_{i=1}^m{i}^ki!\binom{m}{i}\begin{Bmatrix}kn\\i\end{Bmatrix}

其中{花括号}表示第二类斯特林数。

Mitzenmacher和Upfal曾提出一种无需独立性假设即可得到相同近似结果的分析。在过滤器中添加了所有个项目后，设为位（数组总位数）中为0的比例。（即仍为0的位数是。）然后，在测试不在集合中的元素时，对于由任何个哈希函数给出的数组位置，该位被置位为1的概率是1-q。因此，所有个哈希函数都找到其位被置位为1的概率是(1-q)^{k}。此外，的期望值，即为一个给定的数组位置在个元素分别经过个哈希函数处理后，依然保持纯洁（未被置位）的概率。其计算方式（同上）如下：

E[q]=(1-\frac1m)^{kn}

在不依赖独立性假设的前提下，可以证明的取值高度集中在其期望值附近。具体而言，利用吾妻不等式，可证得：

Pr(|q-E[q]|\geq\frac\lambda{m})\leq2exp(-2\lambda^2/kn)

因此可得，假阳性（误报）的准确概率如前所述为：

\sum_{t}Pr(q={t})(1-t)^k\approx(1-E[q])^k=(1-[1-\frac1m]^{kn})^k\approx(1-e^{-kn/m})^k

注解
參考
引用
文献
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*. Open source implementation [https://github.com/efficient/cuckoofilter available on github] .
*. A preliminary version appeared at SIGCOMM '98.
*
*
*
*
*
*
*
*
*
*
*
*
*
*. Prototype implementation [https://github.com/epournaras/DIAS available on github] .
*
*
*
*
*
*
*
*

外部链接

• [http://www.sigma.me/2011/09/13/hash-and-bloom-filter.html Hash和Bloom Filter介绍]