轉(zhuǎn)自: http://blog.huang-wei.com/2010/11/02/bloom-filter/
介紹
Bloom Filter是一種簡單的節(jié)省空間的隨機(jī)化的數(shù)據(jù)結(jié)構(gòu),支持用戶查詢的集合。一般我們使用STL的std::set, stdext::hash_set,std::set是用紅黑樹實(shí)現(xiàn)的,stdext::hash_set是用桶式哈希表。上述兩種數(shù)據(jù)結(jié)構(gòu),都會需要保存原始數(shù)據(jù)信息,當(dāng)數(shù)據(jù)量較大時(shí),內(nèi)存就會是個(gè)問題。如果應(yīng)用場景中允許出現(xiàn)一定幾率的誤判,且不需要逆向遍歷集合中的數(shù)據(jù)時(shí),Bloom Filter是很好的結(jié)構(gòu)。
優(yōu)點(diǎn)
- 查詢操作十分高效。
- 節(jié)省空間。
- 易于擴(kuò)展成并行。
- 集合計(jì)算方便。
- 代碼實(shí)現(xiàn)方便。
- 有誤判的概率,即存在False Position。
- 無法獲取集合中的元素?cái)?shù)據(jù)。
- 不支持刪除操作。
缺點(diǎn)
- 有誤判的概率,即存在False Position。
- 無法獲取集合中的元素?cái)?shù)據(jù)。
- 不支持刪除操作。
定義
Bloom Filter是一個(gè)有m位的位數(shù)組,初始全為0,并有k個(gè)各自獨(dú)立的哈希函數(shù)。
圖1
添加操作
每個(gè)元素,用k個(gè)哈希函數(shù)計(jì)算出大小為k的哈希向量
,將向量里的每個(gè)哈希值對應(yīng)的位設(shè)置為1。時(shí)間復(fù)雜度為
,一般字符串哈希函數(shù)的時(shí)間復(fù)雜度也就是
。
查詢操作
和添加類似,先計(jì)算出哈希向量,如果每個(gè)哈希值對應(yīng)的位都為1,則該元素存在。時(shí)間復(fù)雜度與添加操作相同。
示例
圖2表示m=16,k=2的Bloom Filter, 和 的哈希值分別為(3, 6)和(10, 3)。
圖2
False Position
如果某元素不在Bloom Filter中,但是它所有哈希值的位置均被設(shè)為1。這種情況就是False Position,也就是誤判。
借用示例,如下:
圖3
這個(gè)問題其實(shí)和哈希表中的沖突是相同的道理,哈希表中可以使用開散列和閉散列的方法,而Bloom Filter則允許這樣的情況發(fā)生,它更關(guān)心于誤判的發(fā)生概率。
概率
宏觀上,我們能得出以下結(jié)論:
參數(shù)表 | 變量 | 減少 | 增加 |
哈希函數(shù)總數(shù) | K |
l 更少的哈希值計(jì)算
l 增加False Position的概率 |
l 更多的計(jì)算
l 位值0減少 |
Bloom Filter 大小 | M |
l 更少的內(nèi)存
l 增加False Position的概率 |
l 更多的內(nèi)存
l 降低概率 |
元素總數(shù) | N | l 降低False Position的概率 | l 增加概率 |
False Position的概率為
。
假設(shè)m和n已知,為了最小化False Position,則
。
數(shù)據(jù)
圖4
擴(kuò)展
Counter Bloom Filter
Bloom Filter有個(gè)缺點(diǎn),就是不支持刪除操作,因?yàn)樗恢滥骋粋€(gè)位從屬于哪些向量。那我們可以給Bloom Filter加上計(jì)數(shù)器,添加時(shí)增加計(jì)數(shù)器,刪除時(shí)減少計(jì)數(shù)器。
但這樣的Filter需要考慮附加的計(jì)數(shù)器大小,假如同個(gè)元素多次插入的話,計(jì)數(shù)器位數(shù)較少的情況下,就會出現(xiàn)溢出問題。如果對計(jì)數(shù)器設(shè)置上限值的話,會導(dǎo)致Cache Miss,但對某些應(yīng)用來說,這并不是什么問題,如Web Sharing。
Compressed Bloom Filter
為了能在服務(wù)器之間更快地通過網(wǎng)絡(luò)傳輸Bloom Filter,我們有方法能在已完成Bloom Filter之后,得到一些實(shí)際參數(shù)的情況下進(jìn)行壓縮。
將元素全部添加入Bloom Filter后,我們能得到真實(shí)的空間使用率,用這個(gè)值代入公式計(jì)算出一個(gè)比m小的值,重新構(gòu)造Bloom Filter,對原先的哈希值進(jìn)行求余處理,在誤判率不變的情況下,使得其內(nèi)存大小更合適。
應(yīng)用
加速查詢
適用于一些key-value存儲系統(tǒng),當(dāng)values存在硬盤時(shí),查詢就是件費(fèi)時(shí)的事。
將Storage的數(shù)據(jù)都插入Filter,在Filter中查詢都不存在時(shí),那就不需要去Storage查詢了。
當(dāng)False Position出現(xiàn)時(shí),只是會導(dǎo)致一次多余的Storage查詢。
圖5
l Google的BigTable也使用了Bloom Filter,以減少不存在的行或列在磁盤上的查詢,大大提高了數(shù)據(jù)庫的查詢操作的性能。
l 在Internet Cache Protocol中的Proxy-Cache很多都是使用Bloom Filter存儲URLs,除了高效的查詢外,還能很方便得傳輸交換Cache信息。
網(wǎng)絡(luò)應(yīng)用
l P2P網(wǎng)絡(luò)中查找資源操作,可以對每條網(wǎng)絡(luò)通路保存Bloom Filter,當(dāng)命中時(shí),則選擇該通路訪問。
l 廣播消息時(shí),可以檢測某個(gè)IP是否已發(fā)包。
l 檢測廣播消息包的環(huán)路,將Bloom Filter保存在包里,每個(gè)節(jié)點(diǎn)將自己添加入Bloom Filter。
l 信息隊(duì)列管理,使用Counter Bloom Filter管理信息流量。
垃圾郵件地址過濾
來自于Google黑板報(bào)的例子。
像網(wǎng)易,QQ這樣的公眾電子郵件(email)提供商,總是需要過濾來自發(fā)送垃圾郵件的人(spamer)的垃圾郵件。
一個(gè)辦法就是記錄下那些發(fā)垃圾郵件的 email 地址。由于那些發(fā)送者不停地在注冊新的地址,全世界少說也有幾十億個(gè)發(fā)垃圾郵件的地址,將他們都存起來則需要大量的網(wǎng)絡(luò)服務(wù)器。
如果用哈希表,每存儲一億個(gè) email 地址,就需要 1.6GB 的內(nèi)存(用哈希表實(shí)現(xiàn)的具體辦法是將每一個(gè) email 地址對應(yīng)成一個(gè)八字節(jié)的信息指紋,然后將這些信息指紋存入哈希表,由于哈希表的存儲效率一般只有 50%,因此一個(gè) email 地址需要占用十六個(gè)字節(jié)。一億個(gè)地址大約要 1.6GB, 即十六億字節(jié)的內(nèi)存)。因此存貯幾十億個(gè)郵件地址可能需要上百 GB 的內(nèi)存。
而Bloom Filter只需要哈希表 1/8 到 1/4 的大小就能解決同樣的問題。
Bloom Filter決不會漏掉任何一個(gè)在黑名單中的可疑地址。而至于誤判問題,常見的補(bǔ)救辦法是在建立一個(gè)小的白名單,存儲那些可能別誤判的郵件地址。
引用
[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] 數(shù)學(xué)之美系列二十一 - 布隆過濾器(Bloom Filter); http://www.google.com.hk/ggblog/googlechinablog/2007/07/bloom-filter_7469.html
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
