Bloom Filter 原理與應用
介紹
Bloom Filter是一種簡單的節省空間的隨機化的數據結構，支持用戶查詢的集合。一般我們使用STL的std::set, stdext::hash_set，std::set是用紅黑樹實現的，stdext::hash_set是用桶式哈希表。上述兩種數據結構，都會需要保存原始數據信息，當數據量較大時，內存就會是個問題。如果應用場景中允許出現一定幾率的誤判，且不需要逆向遍歷集合中的數據時，Bloom Filter是很好的結構。
優點
- 查詢操作十分高效。
- 節省空間。
- 易于擴展成并行。
- 集合計算方便。
- 代碼實現方便。
- 有誤判的概率，即存在False Position。
- 無法獲取集合中的元素數據。
- 不支持刪除操作。
缺點
- 有誤判的概率，即存在False Position。
- 無法獲取集合中的元素數據。
- 不支持刪除操作。
定義
Bloom Filter是一個有m位的位數組，初始全為0，并有k個各自獨立的哈希函數。
圖1
添加操作
每個元素，用k個哈希函數計算出大小為k的哈希向量  "\bg_white \left (H_{1},H_{2}\cdots ,H_{k} \right )")
，將向量里的每個哈希值對應的位設置為1。時間復雜度為  "\bg_white k\cdot O(F_{H})")
，一般字符串哈希函數的時間復雜度也就是 "\bg_white O(n)")
。
查詢操作
和添加類似，先計算出哈希向量，如果每個哈希值對應的位都為1，則該元素存在。時間復雜度與添加操作相同。
示例
圖2表示m=16，k=2的Bloom Filter， 和 的哈希值分別為(3, 6)和(10, 3)。
圖2
False Position
如果某元素不在Bloom Filter中，但是它所有哈希值的位置均被設為1。這種情況就是False Position，也就是誤判。
借用示例，如下：
圖3
這個問題其實和哈希表中的沖突是相同的道理，哈希表中可以使用開散列和閉散列的方法，而Bloom Filter則允許這樣的情況發生，它更關心于誤判的發生概率。
概率
宏觀上，我們能得出以下結論：
| 參數表 | 變量 | 減少 | 增加 |
| 哈希函數總數 | K | l 更少的哈希值計算 l 增加False Position的概率 | l 更多的計算 l 位值0減少 |
| Bloom Filter 大小 | M | l 更少的內存 l 增加False Position的概率 | l 更多的內存 l 降低概率 |
| 元素總數 | N | l 降低False Position的概率 | l 增加概率 |
False Position的概率為 ^{k} "F=(1-e^{-\frac{kn}{m}})^{k}")
。
假設m和n已知，為了最小化False Position，則 
。
數據
圖4
擴展
Counter Bloom Filter
Bloom Filter有個缺點，就是不支持刪除操作，因為它不知道某一個位從屬于哪些向量。那我們可以給Bloom Filter加上計數器，添加時增加計數器，刪除時減少計數器。
但這樣的Filter需要考慮附加的計數器大小，假如同個元素多次插入的話，計數器位數較少的情況下，就會出現溢出問題。如果對計數器設置上限值的話，會導致Cache Miss，但對某些應用來說，這并不是什么問題，如Web Sharing。
Compressed Bloom Filter
為了能在服務器之間更快地通過網絡傳輸Bloom Filter，我們有方法能在已完成Bloom Filter之后，得到一些實際參數的情況下進行壓縮。
將元素全部添加入Bloom Filter后，我們能得到真實的空間使用率，用這個值代入公式計算出一個比m小的值，重新構造Bloom Filter，對原先的哈希值進行求余處理，在誤判率不變的情況下，使得其內存大小更合適。
應用
加速查詢
適用于一些key-value存儲系統，當values存在硬盤時，查詢就是件費時的事。
將Storage的數據都插入Filter，在Filter中查詢都不存在時，那就不需要去Storage查詢了。
當False Position出現時，只是會導致一次多余的Storage查詢。
圖5
l Google的BigTable也使用了Bloom Filter，以減少不存在的行或列在磁盤上的查詢，大大提高了數據庫的查詢操作的性能。
l 在Internet Cache Protocol中的Proxy-Cache很多都是使用Bloom Filter存儲URLs，除了高效的查詢外，還能很方便得傳輸交換Cache信息。
網絡應用
l P2P網絡中查找資源操作，可以對每條網絡通路保存Bloom Filter，當命中時，則選擇該通路訪問。
l 廣播消息時，可以檢測某個IP是否已發包。
l 檢測廣播消息包的環路，將Bloom Filter保存在包里，每個節點將自己添加入Bloom Filter。
l 信息隊列管理，使用Counter Bloom Filter管理信息流量。
垃圾郵件地址過濾
來自于Google黑板報的例子。
像網易，QQ這樣的公眾電子郵件（email）提供商，總是需要過濾來自發送垃圾郵件的人（spamer）的垃圾郵件。
一個辦法就是記錄下那些發垃圾郵件的 email 地址。由于那些發送者不停地在注冊新的地址，全世界少說也有幾十億個發垃圾郵件的地址，將他們都存起來則需要大量的網絡服務器。
如果用哈希表，每存儲一億個 email 地址，就需要 1.6GB 的內存（用哈希表實現的具體辦法是將每一個 email 地址對應成一個八字節的信息指紋，然后將這些信息指紋存入哈希表，由于哈希表的存儲效率一般只有 50%，因此一個 email 地址需要占用十六個字節。一億個地址大約要 1.6GB， 即十六億字節的內存）。因此存貯幾十億個郵件地址可能需要上百 GB 的內存。
而Bloom Filter只需要哈希表 1/8 到 1/4 的大小就能解決同樣的問題。
Bloom Filter決不會漏掉任何一個在黑名單中的可疑地址。而至于誤判問題，常見的補救辦法是在建立一個小的白名單，存儲那些可能別誤判的郵件地址。
引用
[1] Bloom filter; http://en.wikipedia.org/wiki/Bloom_filter
[2] Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol;http://pages.cs.wisc.edu/~cao/papers/summary-cache/
[3] Network Applications of Bloom Filters: A Survey;http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.127.9672&rep=rep1&type=pdf
[4] An Examination of Bloom Filters and their Applications;http://cs.unc.edu/~fabian/courses/CS600.624/slides/bloomslides.pdf
[5] 數學之美系列二十一 － 布隆過濾器（Bloom Filter）;http://www.google.com.hk/ggblog/googlechinablog/2007/07/bloom-filter_7469.html