海量數據處理之Bloom Filter詳解

前言

本博客內曾已經整理過 十道海量數據處理面試題與十個方法大總結 。接下來，本博客內會重點分析那些海量數據處理的方法，并重寫十道海量數據處理的面試題。如果有任何問題，歡迎不吝指正。謝謝。

一、什么是Bloom Filter

Bloom Filter 是一種空間效率很高的隨機數據結構，它利用位數組很簡潔地表示一個集合，并能判斷一個元素是否屬于這個集合。 Bloom Filter 的這種高效是有一定代價的：在判斷一個元素是否屬于某個集合時，有可能會把不屬于這個集合的元素誤認為屬于這個集合（ false positive ）。因此， Bloom Filter 不適合那些“零錯誤”的應用場合。而在能容忍低錯誤率的應用場合下， Bloom Filter 通過極少的錯誤換取了存儲空間的極大節省。

有人可能想知道它的中文叫法，倒是有被譯作稱布隆過濾器。該不該譯，譯的是否恰當，由諸君品之。下文之中，如果有諸多公式不慎理解，也無礙，只作稍稍了解即可。

1.1、集合表示和元素查詢

下面我們具體來看 Bloom Filter 是如何用位數組表示集合的。初始狀態時， Bloom Filter 是一個包含 m 位的位數組，每一位都置為 0 。

為了表達 S={x ₁ , x ₂ ,…,x _n } 這樣一個 n 個元素的集合， Bloom Filter 使用 k 個相互獨立的哈希函數（ Hash Function ），它們分別將集合中的每個元素映射到 {1,…,m} 的范圍中。對任意一個元素 x ，第 i 個哈希函數映射的位置 h _i (x) 就會被置為 1 （ 1 ≤ i ≤ k ）。注意，如果一個位置多次被置為 1 ，那么只有第一次會起作用，后面幾次將沒有任何效果。在下圖中， k=3 ，且有兩個哈希函數選中同一個位置（從左邊數第五位，即第二個“1“處）。

在判斷 y 是否屬于這個集合時，我們對 y 應用 k 次哈希函數，如果所有 h _i (y) 的位置都是 1 （ 1 ≤ i ≤ k ），那么我們就認為 y 是集合中的元素，否則就認為 y 不是集合中的元素。下圖中 y ₁ 就不是集合中的元素（因為y1有一處指向了“0”位）。 y ₂ 或者屬于這個集合，或者剛好是一個 false positive 。

1.2、錯誤率估計

前面我們已經提到了， Bloom Filter 在判斷一個元素是否屬于它表示的集合時會有一定的錯誤率（ false positive rate ），下面我們就來估計錯誤率的大小。在估計之前為了簡化模型，我們假設 kn<m 且各個哈希函數是完全隨機的。當集合 S={x ₁ , x ₂ ,…,x _n } 的所有元素都被 k 個哈希函數映射到 m 位的位數組中時，這個位數組中某一位還是 0 的概率是：

其中 1/m 表示任意一個哈希函數選中這一位的概率（前提是哈希函數是完全隨機的）， (1-1/m) 表示哈希一次沒有選中這一位的概率。要把 S 完全映射到位數組中，需要做 kn 次哈希。某一位還是 0 意味著 kn 次哈希都沒有選中它，因此這個概率就是（ 1-1/m ）的 kn 次方。令 p = e ^-kn/m 是為了簡化運算，這里用到了計算e時常用的近似：

令ρ為位數組中 0 的比例，則ρ的數學期望E(ρ)= p’ 。在ρ已知的情況下，要求的錯誤率（ false positive rate ）為：

(1- ρ)為位數組中 1 的比例， (1- ρ) ^k 就表示 k 次哈希都剛好選中 1 的區域，即 false positive rate 。上式中第二步近似在前面已經提到了，現在來看第一步近似。 p’ 只是ρ的數學期望，在實際中ρ的值有可能偏離它的數學期望值。 M. Mitzenmacher 已經證明 ^[2] ，位數組中0的比例非常集中地分布在它的數學期望值的附近。因此，第一步的近似得以成立。分別將 p 和 p’ 代入上式中，得：

相比 p’ 和 f’ ，使用 p 和 f 通常在分析中更為方便。

1.3、最優的哈希函數個數

既然 Bloom Filter 要靠多個哈希函數將集合映射到位數組中，那么應該選擇幾個哈希函數才能使元素查詢時的錯誤率降到最低呢？這里有兩個互斥的理由：如果哈希函數的個數多，那么在對一個不屬于集合的元素進行查詢時得到 0 的概率就大；但另一方面，如果哈希函數的個數少，那么位數組中的 0 就多。為了得到最優的哈希函數個數，我們需要根據上一小節中的錯誤率公式進行計算。

先用 p 和 f 進行計算。注意到 f = exp(k ln(1 ? e ^?kn/m )) ，我們令 g = k ln(1 ? e ^?kn/m ) ，只要讓 g 取到最小， f 自然也取到最小。由于 p = e ^-kn/m ，我們可以將 g 寫成

根據對稱性法則可以很容易看出當 p = 1/2 ，也就是 k = ln2· (m/n) 時， g 取得最小值。在這種情況下，最小錯誤率 f 等于 (1/2) ^k ≈ (0.6185) ^m/n 。另外，注意到p是位數組中某一位仍是0的概率，所以 p = 1/2 對應著位數組中0和1各一半。換句話說，要想保持錯誤率低，最好讓位數組有一半還空著。

需要強調的一點是， p = 1/2 時錯誤率最小這個結果并不依賴于近似值 p 和 f 。同樣對于 f’ = exp(k ln(1 ? (1 ? 1/m) ^kn )) ， g’ = k ln(1 ? (1 ? 1/m) ^kn ) ， p’ = (1 ? 1/m) ^kn ，我們可以將 g’ 寫成

同樣根據對稱性法則可以得到當 p’ = 1/2 時， g’ 取得最小值。

1.4、位數組的大小

下面我們來看看，在不超過一定錯誤率的情況下， Bloom Filter 至少需要多少位才能表示全集中任意 n 個元素的集合。假設全集中共有 u 個元素，允許的最大錯誤率為 ? ，下面我們來求位數組的位數 m 。

假設 X 為全集中任取 n 個元素的集合， F(X) 是表示 X 的位數組。那么對于集合 X 中任意一個元素 x ，在 s = F(X) 中查詢 x 都能得到肯定的結果，即 s 能夠接受 x 。顯然，由于 Bloom Filter 引入了錯誤， s 能夠接受的不僅僅是 X 中的元素，它還能夠 ? (u - n) 個 false positive 。因此，對于一個確定的位數組來說，它能夠接受總共 n + ? (u - n) 個元素。在 n + ? (u - n) 個元素中， s 真正表示的只有其中 n 個，所以一個確定的位數組可以表示

個集合。 m 位的位數組共有 2 ^m 個不同的組合，進而可以推出， m 位的位數組可以表示

個集合。全集中 n 個元素的集合總共有

個，因此要讓 m 位的位數組能夠表示所有 n 個元素的集合，必須有

即：

上式中的近似前提是 n 和 ?u 相比很小，這也是實際情況中常常發生的。根據上式，我們得出結論：在錯誤率不大于 ? 的情況下， m 至少要等于 n log ₂ (1/?) 才能表示任意 n 個元素的集合。

上一小節中我們曾算出當 k = ln2· (m/n) 時錯誤率 f 最小，這時 f = (1/2) ^k = (1/2) ^{mln2 / n} 。現在令 f ≤ ? ，可以推出

這個結果比前面我們算得的下界 n log ₂ (1/?) 大了 log ₂ e ≈ 1.44 倍。這說明在哈希函數的個數取到最優時，要讓錯誤率不超過 ? ， m 至少需要取到最小值的 1.44 倍。

1.5、概括

在計算機科學中，我們常常會碰到時間換空間或者空間換時間的情況，即為了達到某一個方面的最優而犧牲另一個方面。 Bloom Filter 在時間空間這兩個因素之外又引入了另一個因素：錯誤率。在使用 Bloom Filter 判斷一個元素是否屬于某個集合時，會有一定的錯誤率。也就是說，有可能把不屬于這個集合的元素誤認為屬于這個集合（ False Positive ），但不會把屬于這個集合的元素誤認為不屬于這個集合（ False Negative ）。在增加了錯誤率這個因素之后， Bloom Filter 通過允許少量的錯誤來節省大量的存儲空間。

自從 Burton Bloom 在 70 年代提出 Bloom Filter 之后， Bloom Filter 就被廣泛用于拼寫檢查和數據庫系統中。近一二十年，伴隨著網絡的普及和發展， Bloom Filter 在網絡領域獲得了新生，各種 Bloom Filter 變種和新的應用不斷出現。可以預見，隨著網絡應用的不斷深入，新的變種和應用將會繼續出現， Bloom Filter 必將獲得更大的發展。

二、適用范圍

可以用來實現數據字典，進行數據的判重，或者集合求交集

三、基本原理及要點

四、擴展

五、問題實例

1. http://blog.csdn.net/jiaomeng/article/details/1495500
2. http://blog.redfox66.com/post/2010/09/24/mass-data-topic-1-start.aspx 。

完。

海量數據處理之Bloom Filter詳解