Bloom Filter(布隆過濾器)

上一篇 / 下一篇 2008-06-11 11:50:20 / 个人分类：學習資料

文件版本: V1.0
开发商: 本站原创
文件来源: 本地
界面语言: 繁体中文
授权方式: 免费
运行平台: Win9X/Win2000/WinXP

轉自：WiKi

Bloom Filter(布隆過濾器)是 1970 年由 Bloom 在^[1]中提出的. 一般都說它是一種simple space-efficient randomized data structure for representing a set in order to support membership queries. Bloom Filter 可以用於檢索一個元素是否在一個集合中. 它的優點是空間效率和查詢時間都遠遠超過一般的演算法, 缺點是false positive和刪除困難.

所謂的 false positive 是一個機率論中的概念, 可以簡單的理解成把假的說成真的. 相對的, false negative 就是把真的說成假的.

參考文獻
[1]B.Bloom. Space/time tradeoffs in hash coding with allowable errors. Communications of the ACM, 13(7):422-426, July 1970.

轉自：朱熹之の空间

（筆記）Bloom Filter與壓縮Bloom Filter

Bloom Filter是B.Bloom於1970年在[1]中提出的一種資料結構，用以概率的表示集合，以支援成員關係查詢（例如，查詢“元素X是否屬於集合Y？”）。該結構的不足在於，其有可能將非成員錯誤的識別為成員。2002年，Mitzenmacher對其進行了改進，提出了壓縮Bloom Filter[2]，其具有更好的存儲效率，以及更小的錯誤率。

Bloom Filter即是用m位元的存儲空間，通過使用k個雜湊函數進行運算，來表示一個元素是否屬於一個擁有n個元素的集合。其構建方式如下所示：
（1）將存儲空間初始化為0；
（2）使用給定的k個雜湊函數，對集合中每個元素進行雜湊運算，將每次運算結果表示的位置1。

驗證某一元素是否屬於某給定集合時，對其進行k次雜湊運算，並查看運算結果表示的位是否為1。如果每次運算的結果均為1，則表示其為該集合中的元素，否則不是集合的成員。

需要注意的是，Bloom Filter有一定的出錯概率。如果元素在集合中，則Bloom Filter一定能夠將其正確的識別出；如果元素不在集合中，則Bloom Filter有一定的概率將其錯誤的認為是集合中的成員。其概率為：

顯然，在（p為某一特定位為0的概率），即在時，錯誤率最小，為。

壓縮Bloom Filter則是基於這樣一個假設：傳輸體積比存儲體積更為重要。設在網路傳輸中，存儲空間的位元長為z。經過壓縮後，若能夠用H(p)位來表示1位元的資訊，即有z=m*H(p)。發送方需要將Bloom Filter進行壓縮後再進行傳輸，接收方對其進行解壓並進行相應操作。在實際應用中，可給定n與z，通過選擇m與k來優化f，要求m*H(p)≤z。特別的，若m=z，p=1/2，則壓縮Bloom Filter即為普通的Bloom Filter。顯然，壓縮Bloom Filter的錯誤率要小於普通的Bloom Filter，有。

參考文獻
[1]B.Bloom. Space/time tradeoffs in hash coding with allowable errors. Communications of the ACM, 13(7):422-426, July 1970.
[2]M.Mitzenmacher. Compressed Bloom Filters. IEEE/ACM Transactions on Networking (TON), Volume 10, Issue 5, pages 604-612, 2002.

轉自：焦萌的专栏

集合表示和元素查詢

下面我們具體來看Bloom Filter是如何用位元陣列表示集合的。初始狀態時，Bloom Filter是一個包含m位元的位元陣列，每一位元都置為0。

為了表達S={x₁, x₂,…,x_n}這樣一個n個元素的集合，Bloom Filter使用k個相互獨立的雜湊函數（Hash Function），它們分別將集合中的每個元素映射到{1,…,m}的範圍中。對任意一個元素x，第i個雜湊函數映射的位置h_i(x)就會被置為1（1≤i≤k）。注意，如果一個位置多次被置為1，那麼只有第一次會起作用，後面幾次將沒有任何效果。在下圖中，k=3，且有兩個雜湊函數選中同一個位置（從左邊數第五位）。