布隆過(guò)濾器 (Bloom Filter) 詳解
原文鏈接:http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html
布隆過(guò)濾器 (Bloom Filter)是由Burton Howard Bloom于1970年提出,它是一種space efficient的概率型數(shù)據(jù)結(jié)構(gòu)琴锭,用于判斷一個(gè)元素是否在集合中读虏。在垃圾郵件過(guò)濾的黑白名單方法、爬蟲(chóng)(Crawler)的網(wǎng)址判重模塊中等等經(jīng)常被用到徽缚。哈希表也能用于判斷元素是否在集合中,但是布隆過(guò)濾器只需要哈希表的1/8或1/4的空間復(fù)雜度就能完成同樣的問(wèn)題革屠。布隆過(guò)濾器可以插入元素凿试,但不可以刪除已有元素。其中的元素越多似芝,false positive rate(誤報(bào)率)越大那婉,但是false negative (漏報(bào))是不可能的。
本文將詳解布隆過(guò)濾器的相關(guān)算法和參數(shù)設(shè)計(jì)党瓮,在此之前希望大家可以先通過(guò)谷歌黑板報(bào)的數(shù)學(xué)之美系列二十一 - 布隆過(guò)濾器(Bloom Filter)來(lái)得到些基礎(chǔ)知識(shí)详炬。
1. 算法描述
一個(gè)empty bloom filter是一個(gè)有m bits的bit array,每一個(gè)bit位都初始化為0寞奸。并且定義有k個(gè)不同的hash function呛谜,每個(gè)都以u(píng)niform random distribution將元素hash到m個(gè)不同位置中的一個(gè)。在下面的介紹中n為元素?cái)?shù)枪萄,m為布隆過(guò)濾器或哈希表的slot數(shù)呻率,k為布隆過(guò)濾器重hash function數(shù)。
為了add一個(gè)元素呻引,用k個(gè)hash function將它hash得到bloom filter中k個(gè)bit位礼仗,將這k個(gè)bit位置1。
為了query一個(gè)元素逻悠,即判斷它是否在集合中元践,用k個(gè)hash function將它hash得到k個(gè)bit位。若這k bits全為1童谒,則此元素在集合中单旁;若其中任一位不為1,則此元素比不在集合中(因?yàn)槿绻诩⒁粒瑒t在add時(shí)已經(jīng)把對(duì)應(yīng)的k個(gè)bits位置為1)象浑。
不允許remove元素,因?yàn)槟菢拥脑挄?huì)把相應(yīng)的k個(gè)bits位置為0琅豆,而其中很有可能有其他元素對(duì)應(yīng)的位愉豺。因此remove會(huì)引入false negative,這是絕對(duì)不被允許的茫因。
當(dāng)k很大時(shí)蚪拦,設(shè)計(jì)k個(gè)獨(dú)立的hash function是不現(xiàn)實(shí)并且困難的。對(duì)于一個(gè)輸出范圍很大的hash function(例如MD5產(chǎn)生的128 bits數(shù)),如果不同bit位的相關(guān)性很小驰贷,則可把此輸出分割為k份盛嘿。或者可將k個(gè)不同的初始值(例如0,1,2, … ,k-1)結(jié)合元素括袒,feed給一個(gè)hash function從而產(chǎn)生k個(gè)不同的數(shù)次兆。
當(dāng)add的元素過(guò)多時(shí),即n/m過(guò)大時(shí)(n是元素?cái)?shù)锹锰,m是bloom filter的bits數(shù))类垦,會(huì)導(dǎo)致false positive過(guò)高,此時(shí)就需要重新組建filter城须,但這種情況相對(duì)少見(jiàn)。
2. 時(shí)間和空間上的優(yōu)勢(shì)
當(dāng)可以承受一些誤報(bào)時(shí)米苹,布隆過(guò)濾器比其它表示集合的數(shù)據(jù)結(jié)構(gòu)有著很大的空間優(yōu)勢(shì)糕伐。例如self-balance BST, tries, hash table或者array, chain,它們中大多數(shù)至少都要存儲(chǔ)元素本身蘸嘶,對(duì)于小整數(shù)需要少量的bits良瞧,對(duì)于字符串則需要任意多的bits(tries是個(gè)例外,因?yàn)閷?duì)于有相同prefixes的元素可以共享存儲(chǔ)空間)训唱;而chain結(jié)構(gòu)還需要為存儲(chǔ)指針付出額外的代價(jià)褥蚯。對(duì)于一個(gè)有1%誤報(bào)率和一個(gè)最優(yōu)k值的布隆過(guò)濾器來(lái)說(shuō),無(wú)論元素的類(lèi)型及大小况增,每個(gè)元素只需要9.6 bits來(lái)存儲(chǔ)赞庶。這個(gè)優(yōu)點(diǎn)一部分繼承自array的緊湊性,一部分來(lái)源于它的概率性澳骤。如果你認(rèn)為1%的誤報(bào)率太高歧强,那么對(duì)每個(gè)元素每增加4.8 bits,我們就可將誤報(bào)率降低為原來(lái)的1/10为肮。add和query的時(shí)間復(fù)雜度都為O(k)摊册,與集合中元素的多少無(wú)關(guān),這是其他數(shù)據(jù)結(jié)構(gòu)都不能完成的颊艳。
如果可能元素范圍不是很大茅特,并且大多數(shù)都在集合中,則使用確定性的bit array遠(yuǎn)遠(yuǎn)勝過(guò)使用布隆過(guò)濾器棋枕。因?yàn)閎it array對(duì)于每個(gè)可能的元素空間上只需要1 bit白修,add和query的時(shí)間復(fù)雜度只有O(1)。注意到這樣一個(gè)哈希表(bit array)只有在忽略collision并且只存儲(chǔ)元素是否在其中的二進(jìn)制信息時(shí)重斑,才會(huì)獲得空間和時(shí)間上的優(yōu)勢(shì)熬荆,而在此情況下,它就有效地稱為了k=1的布隆過(guò)濾器。
而當(dāng)考慮到collision時(shí)卤恳,對(duì)于有m個(gè)slot的bit array或者其他哈希表(即k=1的布隆過(guò)濾器)累盗,如果想要保證1%的誤判率,則這個(gè)bit array只能存儲(chǔ)m/100個(gè)元素突琳,因而有大量的空間被浪費(fèi)若债,同時(shí)也會(huì)使得空間復(fù)雜度急劇上升,這顯然不是space efficient的拆融。解決的方法很簡(jiǎn)單蠢琳,使用k>1的布隆過(guò)濾器,即k個(gè)hash function將每個(gè)元素改為對(duì)應(yīng)于k個(gè)bits镜豹,因?yàn)檎`判度會(huì)降低很多傲须,并且如果參數(shù)k和m選取得好,一半的m可被置為為1趟脂,這充分說(shuō)明了布隆過(guò)濾器的space efficient性泰讽。
3. 舉例說(shuō)明
以垃圾郵件過(guò)濾中黑白名單為例:現(xiàn)有1億個(gè)email的黑名單,每個(gè)都擁有8 bytes的指紋信息昔期,則可能的元素范圍為若采用哈希表般贼,由于大多數(shù)采用open addressing來(lái)解決collision愧哟,而此時(shí)的search時(shí)間復(fù)雜度為 :
即若哈希表半滿(n/m = 1/2),則每次search需要probe 2次哼蛆,因此在保證效率的情況下哈希表的存儲(chǔ)效率最好不超過(guò)50%翅雏。此時(shí)每個(gè)元素占8 bytes,總空間為:
若采用Perfect hashing(這里可以采用Perfect hashing是因?yàn)橹饕僮魇莝earch/query人芽,而并不是add和remove)望几,雖然保證worst-case也只有一次probe,但是空間利用率更低萤厅,一般情況下為50%橄抹,worst-case時(shí)有不到一半的概率為25%。
若采用布隆過(guò)濾器惕味,取k=8楼誓。因?yàn)閚為1億,所以總共需要被置位為1名挥,又因?yàn)樵诒WC誤判率低且k和m選取合適時(shí)疟羹,空間利用率為50%(后面會(huì)解釋),所以總空間為:
所需空間比上述哈希結(jié)構(gòu)小得多,并且誤判率在萬(wàn)分之一以下榄融。
4. 誤判概率的證明和計(jì)算
假設(shè)布隆過(guò)濾器中的hash function滿足simple uniform hashing假設(shè):每個(gè)元素都等概率地hash到m個(gè)slot中的任何一個(gè)参淫,與其它元素被hash到哪個(gè)slot無(wú)關(guān)。若m為bit數(shù)愧杯,則對(duì)某一特定bit位在一個(gè)元素由某特定hash function插入時(shí)沒(méi)有被置位為1的概率為:
則k個(gè)hash function中沒(méi)有一個(gè)對(duì)其置位的概率為:
如果插入了n個(gè)元素涎才,但都未將其置位的概率為:
則此位被置位的概率為:
現(xiàn)在考慮query階段,若對(duì)應(yīng)某個(gè)待query元素的k bits全部置位為1力九,則可判定其在集合中耍铜。因此將某元素誤判的概率為:
從上式中可以看出棕兼,當(dāng)m增大或n減小時(shí),都會(huì)使得誤判率減小抵乓,這也符合直覺(jué)伴挚。
現(xiàn)在計(jì)算對(duì)于給定的m和n,k為何值時(shí)可以使得誤判率最低臂寝。設(shè)誤判率為k的函數(shù)為:
, 則簡(jiǎn)化為
摊灭,兩邊取對(duì)數(shù)
, 兩邊對(duì)k求導(dǎo)
下面求最值
時(shí)誤判率最低,此時(shí)誤判率為:
可以看出若要使得誤判率≤1/2帚呼,則:
這說(shuō)明了若想保持某固定誤判率不變掏缎,布隆過(guò)濾器的bit數(shù)m與被add的元素?cái)?shù)n應(yīng)該是線性同步增加的。
5. 設(shè)計(jì)和應(yīng)用布隆過(guò)濾器的方法
應(yīng)用時(shí)首先要先由用戶決定要add的元素?cái)?shù)n和希望的誤差率P煤杀。這也是一個(gè)設(shè)計(jì)完整的布隆過(guò)濾器需要用戶輸入的僅有的兩個(gè)參數(shù)眷蜈,之后的所有參數(shù)將由系統(tǒng)計(jì)算,并由此建立布隆過(guò)濾器沈自。
系統(tǒng)首先要計(jì)算需要的內(nèi)存大小m bits:
再由m酌儒,n得到hash function的個(gè)數(shù):
至此系統(tǒng)所需的參數(shù)已經(jīng)備齊,接下來(lái)add n個(gè)元素至布隆過(guò)濾器中枯途,再進(jìn)行query忌怎。
根據(jù)公式,當(dāng)k最優(yōu)時(shí):
因此可驗(yàn)證當(dāng)P=1%時(shí)酪夷,存儲(chǔ)每個(gè)元素需要9.6 bits:
而每當(dāng)想將誤判率降低為原來(lái)的1/10榴啸,則存儲(chǔ)每個(gè)元素需要增加4.8 bits:
這里需要特別注意的是,9.6 bits/element不僅包含了被置為1的k位晚岭,還把包含了沒(méi)有被置為1的一些位數(shù)鸥印。此時(shí)的
才是每個(gè)元素對(duì)應(yīng)的為1的bit位數(shù)。
從而使得P(error)最小時(shí),我們注意到:
库说,即
此概率為某bit位在插入n個(gè)元素后未被置位的概率狂鞋。因此,想保持錯(cuò)誤率低璃弄,布隆過(guò)濾器的空間使用率需為50%要销。