布隆過濾器

布隆過濾器（Bloom Filter）是1970年由伯頓·霍華德·布隆（Burton Howard Bloom）提出的高空間效率的機率數據結構。由一個通過一系列散列函數對樣本元素映射而成的二進位位數組組成。布隆過濾器可用於檢索一個元素是否在一個集合中，其空間效率和查詢時間效率都遠超一般演算法。它不會產生假陰性（漏報），但有一定的假陽性（誤報）率且難以刪除元素。

## 基本概念

如果想判斷一個元素是不是在一個集合里，一般想到的是將集合中所有元素保存起來，然後通過比較確定。鍊表、樹、散列表（又叫哈希表，Hash table）等等數據結構都是這種思路。但是隨著集合中元素的增加，我們需要的存儲空間越來越大。同時檢索速度也越來越慢，上述三種結構的檢索時間複雜度分別為$O(n),O(\log n),O(1)$。

布隆過濾器的原理是，當一個元素被加入集合時，通過K個散列函數將這個元素映射成一個位數組中的K個點，把它們置為1。檢索時，我們只要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如果這些點有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。這就是布隆過濾器的基本思想。所以布隆過濾器可能會產生假陽性，但不會產生假陰性。

## 演算法描述

<image>

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

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

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

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

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

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

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

## 優劣分析

相比於其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器存儲空間和插入/查詢時間都是常數（$O(k)$）。另外，散列函數相互之間沒有關係，方便由硬體並行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。

假陽性率是布隆過濾器的不足之一。隨著存入的元素數量增加，假陽性率隨之增加。但是如果元素數量太少，則使用散列表足矣。在降低假陽性率方面，有不少工作，使得出現了很多布隆過濾器的變種。

## 時間與空間優勢

<image>

儘管存在假陽性風險，布隆過濾器在表示集合的數據結構中比其他數據結構（如自平衡二叉搜索樹、字典樹、哈希表或簡單的陣列或鍊表）具有顯著的空間優勢。這些數據結構中的大多數都需要存儲至少數據項本身，這可能需要從少量位（對於小整數）到任意數量的位（例如對於字串，字典樹是例外，因為它們可以在具有相同前綴的元素之間共享存儲）。然而，布隆過濾器完全不存儲數據項，且須為過濾器的實際存儲另行提供解決方案。鏈式結構會產生額外的線性空間開銷用於指針。相比之下，具有1%誤報率和最優k值的布隆過濾器，每個元素只需要大約9.6位，無論元素的大小如何。這一優勢部分源於其緊湊性，繼承自陣列，部分源於其機率性質。通過為每個元素增加大約4.8位，可以將1%的誤報率降低一個數量級。

然而，如果潛在值的數量較少且其中許多值可能存在於集合中，布隆過濾器很容易被確定性位數組超越，後者只需要為每個潛在元素使用一位。如果哈希表開始忽略衝突並僅存儲每個桶是否包含條目的資訊，它們將獲得空間和時間優勢；在這種情況下，它們實際上已成為$k=1$的布隆過濾器。

布隆過濾器還具有一個不尋常的特性，即添加項目或檢查項目是否在集合中的時間都是固定常數，$O(k)$如前所述，$k$為散列函數數。完全獨立於集合中已有的項目數量。沒有其他常數空間集合數據結構具有這種特性，但稀疏哈希表的平均訪問時間可能使其在實踐中比某些布隆過濾器更快。然而，在硬體實現中，布隆過濾器表現出色，因為它的k次查找是獨立的並且可以並行化。

要理解其空間效率，可以將通用布隆過濾器與其$k=1$的特殊情況進行比較。如果$k=1$，為了保持足夠低的假陽性率，而只允許一小部分位被置位為1，這意味著陣列必然非常大並包含很長的全零序列。相對於其大小，陣列所包含的資訊量較低。通常意義的布隆過濾器（k大於1）允許更多的位被置位為1，同時仍然保持較低的假陽性率；如果參數（k和m）選擇得當，約有一半的位會被置位，並且這些位要明顯隨機，從而最小化冗餘並最大化資訊量。

## 假陽性率

<image>

假設哈希函數以相等機率選擇陣列中的每個位置。設m為陣列的總位數，則某個位在元素插入過程中「未被」某個哈希函數置位為1的機率為

$$1 - \frac 1 m$$

設k為哈希函數的數量，並且每個哈希函數之間沒有顯著的相關性，那麼該位未被任何哈希函數置位為1的機率是$(1-\frac1m)^k$。

通過關於$e^{-1}$的著名公式。

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

得出：對於較大的m。

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

假設過濾器已經被插入了n個元素，那麼某個位仍為0的機率是

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

於是，為1的機率是

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

假設測試一個不在集合中的元素。基於上述的機率計算，由哈希函數計算的k位數組的每個位置都為1。所有這些位置都為1的機率，將導致演算法錯誤地報告該元素在集合中（假陽性），通常給出機率為

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

然此論未必完善，因其假設每位置位之機率互相獨立。假設有較理想之近似，可得：假陽性率隨m（陣列總位數）的增加而降低，並隨n（插入元素數）的增加而升高。

不考慮獨立性，假陽性的真實機率是

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

其中{花括號}表示第二類斯特林數。

Mitzenmacher和Upfal曾提出一種無需獨立性假設即可得到相同近似結果的分析。在過濾器中添加了所有n個項目後，設q為m位（陣列總位數）中為0的比例。（即仍為0的位數是。）然後，在測試不在集合中的元素時，對於由任何k個哈希函數給出的陣列位置，該位被置位為1的機率是$1-q$。因此，所有k個哈希函數都找到其位被置位為1的機率是$(1-q)^{k}$。此外，q的期望值，即為一個給定的陣列位置在n個元素分別經過k個哈希函數處理後，依然保持純潔（未被置位）的機率。其計算方式（同上）如下：

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

在不依賴獨立性假設的前提下，可以證明q的取值高度集中在其期望值附近。具體而言，利用吾妻不等式，可證得：

$$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 available on github .
- . A preliminary version appeared at SIGCOMM '98.
- . Prototype implementation available on github .