亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

布隆過濾器 (Bloom Filter) 詳解

系統 1920 0

布隆過濾器 (Bloom Filter)是由Burton Howard Bloom于1970年提出,它是一種space efficient的概率型數據結構,用于判斷一個元素是否在集合中。在垃圾郵件過濾的黑白名單方法、爬蟲(Crawler)的網址判重模塊中等等經常被用到。哈希表也能用于判斷元素是否在集合中,但是布隆過濾器只需要哈希表的1/8或1/4的空間復雜度就能完成同樣的問題。布隆過濾器可以插入元素,但不可以刪除已有元素。其中的元素越多,false positive rate(誤報率)越大,但是false negative (漏報)是不可能的。

本文將詳解布隆過濾器的相關算法和參數設計,在此之前希望大家可以先通過谷歌黑板報的 數學之美系列二十一 - 布隆過濾器(Bloom Filter) 來得到些基礎知識。

一. 算法描述

一個empty bloom filter是一個有m bits的bit array,每一個bit位都初始化為0。并且定義有k個不同的hash function,每個都以uniform random distribution將元素hash到m個不同位置中的一個。在下面的介紹中n為元素數,m為布隆過濾器或哈希表的slot數,k為布隆過濾器重hash function數。

為了add一個元素,用k個hash function將它hash得到bloom filter中k個bit位,將這k個bit位置1。

為了query一個元素,即判斷它是否在集合中,用k個hash function將它hash得到k個bit位。若這k bits全為1,則此元素在集合中;若其中任一位不為1,則此元素比不在集合中(因為如果在,則在add時已經把對應的k個bits位置為1)。

不允許remove元素,因為那樣的話會把相應的k個bits位置為0,而其中很有可能有其他元素對應的位。因此remove會引入false negative,這是絕對不被允許的。

當k很大時,設計k個獨立的hash function是不現實并且困難的。對于一個輸出范圍很大的hash function(例如MD5產生的128 bits數),如果不同bit位的相關性很小,則可把此輸出分割為k份。或者可將k個不同的初始值(例如0,1,2, … ,k-1)結合元素,feed給一個hash function從而產生k個不同的數。

當add的元素過多時,即n/m過大時(n是元素數,m是bloom filter的bits數),會導致false positive過高,此時就需要重新組建filter,但這種情況相對少見。

二. 時間和空間上的優勢

當可以承受一些誤報時,布隆過濾器比其它表示集合的數據結構有著很大的空間優勢。例如self-balance BST, tries, hash table或者array, chain,它們中大多數至少都要存儲元素本身,對于小整數需要少量的bits,對于字符串則需要任意多的bits(tries是個例外,因為對于有相同prefixes的元素可以共享存儲空間);而chain結構還需要為存儲指針付出額外的代價。對于一個有1%誤報率和一個最優k值的布隆過濾器來說,無論元素的類型及大小,每個元素只需要9.6 bits來存儲。這個優點一部分繼承自array的緊湊性,一部分來源于它的概率性。如果你認為1%的誤報率太高,那么對每個元素每增加4.8 bits,我們就可將誤報率降低為原來的1/10。add和query的時間復雜度都為O(k),與集合中元素的多少無關,這是其他數據結構都不能完成的。

如果可能元素范圍不是很大,并且大多數都在集合中,則使用確定性的bit array遠遠勝過使用布隆過濾器。因為bit array對于每個可能的元素空間上只需要1 bit,add和query的時間復雜度只有O(1)。注意到這樣一個哈希表(bit array)只有在忽略collision并且只存儲元素是否在其中的二進制信息時,才會獲得空間和時間上的優勢,而在此情況下,它就有效地稱為了k=1的布隆過濾器。

而當考慮到collision時,對于有m個slot的bit array或者其他哈希表(即k=1的布隆過濾器),如果想要保證1%的誤判率,則這個bit array只能存儲m/100個元素,因而有大量的空間被浪費,同時也會使得空間復雜度急劇上升,這顯然不是space efficient的。解決的方法很簡單,使用k>1的布隆過濾器,即k個hash function將每個元素改為對應于k個bits,因為誤判度會降低很多,并且如果參數k和m選取得好,一半的m可被置為為1,這充分說明了布隆過濾器的space efficient性。

三. 舉例說明

以垃圾郵件過濾中黑白名單為例:現有1億個email的黑名單,每個都擁有8 bytes的指紋信息,則可能的元素范圍為 clip_image002 ,對于bit array來說是根本不可能的范圍,而且元素的數量(即email列表)為 clip_image002[6] ,相比于元素范圍過于稀疏,而且還沒有考慮到哈希表中的collision問題。

若采用哈希表,由于大多數采用open addressing來解決collision,而此時的search時間復雜度為 :

clip_image002[8]

即若哈希表半滿(n/m = 1/2),則每次search需要probe 2次,因此在保證效率的情況下哈希表的存儲效率最好不超過50%。此時每個元素占8 bytes,總空間為:

clip_image002[10]

若采用Perfect hashing(這里可以采用Perfect hashing是因為主要操作是search/query,而并不是add和remove),雖然保證worst-case也只有一次probe,但是空間利用率更低,一般情況下為50%,worst-case時有不到一半的概率為25%。

若采用布隆過濾器,取k=8。因為n為1億,所以總共需要 clip_image002[12] 被置位為1,又因為在保證誤判率低且k和m選取合適時,空間利用率為50%(后面會解釋),所以總空間為:

clip_image002[14]

所需空間比上述哈希結構小得多,并且誤判率在萬分之一以下。

四. 誤判概率的證明和計算

假設布隆過濾器中的hash function滿足simple uniform hashing假設:每個元素都等概率地hash到m個slot中的任何一個,與其它元素被hash到哪個slot無關。若m為bit數,則對某一特定bit位在一個元素由某特定hash function插入時沒有被置位為1的概率為:

clip_image002[16]

則k個hash function中沒有一個對其置位的概率為:

clip_image002[18]

如果插入了n個元素,但都未將其置位的概率為:

clip_image002[20]

則此位被置位的概率為:

clip_image002[22]

現在考慮query階段,若對應某個待query元素的k bits全部置位為1,則可判定其在集合中。因此將某元素誤判的概率為:

clip_image002[24]

由于 clip_image002[26] ,并且 clip_image002[28] 當m很大時趨近于0,所以

clip_image002[30]

從上式中可以看出,當m增大或n減小時,都會使得誤判率減小,這也符合直覺。

現在計算對于給定的m和n,k為何值時可以使得誤判率最低。設誤判率為k的函數為:

clip_image002[32]

clip_image002[34] , 則簡化為

clip_image002[36] ,兩邊取對數

clip_image002[38] , 兩邊對k求導

clip_image002[40]

下面求最值

clip_image002[42]

clip_image002[44] clip_image004

clip_image002[44] clip_image006

clip_image002[44] clip_image008

clip_image002[44] clip_image010

clip_image002[44] clip_image012

clip_image002[44] clip_image014

clip_image002[44] clip_image002[52]

因此,即當 clip_image002[54] 時誤判率最低,此時誤判率為:

clip_image002[56]

可以看出若要使得誤判率≤1/2,則:

clip_image002[58]

這說明了若想保持某固定誤判率不變,布隆過濾器的bit數m與被add的元素數n應該是線性同步增加的。

五. 設計和應用布隆過濾器的方法

應用時首先要先由用戶決定要add的元素數n和希望的誤差率P。這也是一個設計完整的布隆過濾器需要用戶輸入的僅有的兩個參數,之后的所有參數將由系統計算,并由此建立布隆過濾器。

系統首先要計算需要的內存大小m bits:

clip_image002[60]

再由m,n得到hash function的個數:

clip_image002[52]

至此系統所需的參數已經備齊,接下來add n個元素至布隆過濾器中,再進行query。

根據公式,當k最優時:

clip_image002[66]

clip_image004[8]

因此可驗證當P=1%時,存儲每個元素需要9.6 bits:

clip_image002[70]

而每當想將誤判率降低為原來的1/10,則存儲每個元素需要增加4.8 bits:

clip_image002[72]

這里需要特別注意的是,9.6 bits/element不僅包含了被置為1的k位,還把包含了沒有被置為1的一些位數。此時的

clip_image002[74]

才是每個元素對應的為1的bit位數。

clip_image002[76] 從而使得P(error)最小時,我們注意到:

clip_image002[78] 中的 clip_image002[80] ,即

clip_image002[82]

此概率為某bit位在插入n個元素后未被置位的概率。因此,想保持錯誤率低,布隆過濾器的空間使用率需為50%。

如果您滿意我的博客,請點擊“ 訂閱Allen Sun的技術博客 ”即可訂閱,謝謝:)

原創文章屬于 Allen Sun
歡迎轉載,但請注明文章作者 Allen Sun 和鏈接

布隆過濾器 (Bloom Filter) 詳解


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 日本大片久久久高清免费看 | 精品视频在线免费看 | 亚洲欧美成人综合久久久 | 久久网免费 | 麻豆国产高清精品国在线 | 操久久久 | 久草在线看片 | 成年女人在线观看片免费视频 | 亚洲国产成人久久综合野外 | 久草在线2 | 色妞ww精品视频7777 | 91久国产在线观看 | 欧美日韩中文字幕久久伊人 | 欧美激情免费观看 | 久久精品这里是免费国产 | 国产露脸系列magnet | 天天做天天爽爽快快 | 免费看黄色片视频 | a级毛片视频 | 操操网站 | 欧美成人一区二区 | 一级毛片区 | 国产精品视频久久久久 | 精品成人一区二区三区免费视频 | 国产精品香蕉在线一区 | 成人爽a毛片在线视频网站 成人爽视频 | 99久久免费国产香蕉麻豆 | 亚洲三及片 | 国产中文欧美 | www中文字幕| 久久日韩精品激情 | 成年女人免费视频播放77777 | 成人国产在线看不卡 | 国产精品综合 | 亚洲精品一二三 | 久久伊人色综合 | 国产男女爱视频在线观看 | 精品免费久久久久久影院 | 野花成人 | 男女啪啪猛烈免费网站 | 波多野结衣三区 |