海量數(shù)據(jù)處理之Bloom Filter詳解

前言

本博客內(nèi)曾已經(jīng)整理過 十道海量數(shù)據(jù)處理面試題與十個(gè)方法大總結(jié) 。接下來，本博客內(nèi)會(huì)重點(diǎn)分析那些海量數(shù)據(jù)處理的方法，并重寫十道海量數(shù)據(jù)處理的面試題。如果有任何問題，歡迎不吝指正。謝謝。

一、什么是Bloom Filter

Bloom Filter 是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。 Bloom Filter 的這種高效是有一定代價(jià)的：在判斷一個(gè)元素是否屬于某個(gè)集合時(shí)，有可能會(huì)把不屬于這個(gè)集合的元素誤認(rèn)為屬于這個(gè)集合（ false positive ）。因此， Bloom Filter 不適合那些“零錯(cuò)誤”的應(yīng)用場(chǎng)合。而在能容忍低錯(cuò)誤率的應(yīng)用場(chǎng)合下， Bloom Filter 通過極少的錯(cuò)誤換取了存儲(chǔ)空間的極大節(jié)省。

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

1.1、集合表示和元素查詢

下面我們具體來看 Bloom Filter 是如何用位數(shù)組表示集合的。初始狀態(tài)時(shí)， Bloom Filter 是一個(gè)包含 m 位的位數(shù)組，每一位都置為 0 。

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

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

1.2、錯(cuò)誤率估計(jì)

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

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

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

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

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

1.3、最優(yōu)的哈希函數(shù)個(gè)數(shù)

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

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

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

需要強(qiáng)調(diào)的一點(diǎn)是， p = 1/2 時(shí)錯(cuò)誤率最小這個(gè)結(jié)果并不依賴于近似值 p 和 f 。同樣對(duì)于 f’ = exp(k ln(1 ? (1 ? 1/m) ^kn )) ， g’ = k ln(1 ? (1 ? 1/m) ^kn ) ， p’ = (1 ? 1/m) ^kn ，我們可以將 g’ 寫成

同樣根據(jù)對(duì)稱性法則可以得到當(dāng) p’ = 1/2 時(shí)， g’ 取得最小值。

1.4、位數(shù)組的大小

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

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

個(gè)集合。 m 位的位數(shù)組共有 2 ^m 個(gè)不同的組合，進(jìn)而可以推出， m 位的位數(shù)組可以表示

個(gè)集合。全集中 n 個(gè)元素的集合總共有

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

即：

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

上一小節(jié)中我們?cè)愠霎?dāng) k = ln2· (m/n) 時(shí)錯(cuò)誤率 f 最小，這時(shí) f = (1/2) ^k = (1/2) ^{mln2 / n} 。現(xiàn)在令 f ≤ ? ，可以推出

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

1.5、概括

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

自從 Burton Bloom 在 70 年代提出 Bloom Filter 之后， Bloom Filter 就被廣泛用于拼寫檢查和數(shù)據(jù)庫系統(tǒng)中。近一二十年，伴隨著網(wǎng)絡(luò)的普及和發(fā)展， Bloom Filter 在網(wǎng)絡(luò)領(lǐng)域獲得了新生，各種 Bloom Filter 變種和新的應(yīng)用不斷出現(xiàn)。可以預(yù)見，隨著網(wǎng)絡(luò)應(yīng)用的不斷深入，新的變種和應(yīng)用將會(huì)繼續(xù)出現(xiàn)， Bloom Filter 必將獲得更大的發(fā)展。

二、適用范圍

可以用來實(shí)現(xiàn)數(shù)據(jù)字典，進(jìn)行數(shù)據(jù)的判重，或者集合求交集

三、基本原理及要點(diǎn)

四、擴(kuò)展

五、問題實(shí)例

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

完。

海量數(shù)據(jù)處理之Bloom Filter詳解