BloomFilter（布隆過濾器）

BloomFilter（布隆過濾器）

　　布隆過濾器（英語：Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制矢量和一系列隨機映射函數。布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難。
　　如果想判斷一個元素是不是在一個集合裡，一般想到的是將集合中所有元素保存起來，然後通過比較確定。鏈表、樹、散列表（又叫哈希表，Hash table）等等數據結構都是這種思路。但是隨著集合中元素的增加，我們需要的存儲空間越來越大。同時檢索速度也越來越慢，上述三種結構的檢索時間復雜度分別為O(n),O(log n),O(n/k)。

　　布隆過濾器的原理是，當一個元素被加入集合時，通過K個散列函數將這個元素映射成一個位數組中的K個點，把它們置為1。檢索時，我們只要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如果這些點有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。這就是布隆過濾器的基本思想。

　　若一個字符串對應的bit不全為1，則肯定沒有；
　　若一個字符串對應的Bit全為1，不一定有，因為有可能該字符串的所有位都剛好是被其他字符串所對應，這種情況稱為false positive 。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPqGhoaHXotLio7rX1rf7tK6808jruvO+zbG7srvE3Mm+s/3By6Os0vLOqsm+s/274dOwz+y1vcbky/vX1rf7tK6hozxiciAvPg0KoaGhocj00OjSqsm+s/3X1rf7tK6jrL/J0tTKudPDY291bnRpbmcgYmxvb20gZmlsdGVyKENCRimjrNXiysfSu9bWu/mxvmJsb29tIGZpbHRlcrXEseTM5aOsQ0JGvau7+bG+Ymxvb20gZmlsdGVyw7/Su7j2Yml0uMTOqtK7uPa8xsr9xvejrNXi0fm+zb/J0tTKtc/Wyb6z/dfWt/u0rrXEuabE3MHLoaM8YnIgLz4NCqGhoaE8YnIgLz4NCqGhoaG008nPw+bO0sPHv8nS1L+0tb1ibG9vbSBmaWx0ZXLW99Kq09DI/bj2ss7K/aO6PGJyIC8+DQqhoaGho7GjqbTmtKLX1rf7tK61xLj2yv1uPGJyIC8+DQqhoaGho7KjqSC5/s+juq/K/bj2yv1rPGJyIC8+DQqhoaGho7Ojqc67yv3X6bTz0KFtPC9wPg0KPHA+oaGhoc7Sw8fAtLfWzvbPwqO6PGJyIC8+DQqhoaGhyPSy5cjr0ru49tfWt/u0rqOszrvK/dfpYml0zrtqyc+7uc6qMLXEuMXCys/UyLvOqigxLTEvbSleazxiciAvPg0KoaGhocTHw7TO0sPHsuXI62649tfWt/u0rqOszrvK/dfpYml0zrtqyc+7uc6qMLXEuMXCys/UyLvOqjxiciAvPg0KKDEtMS9tKV5rbiZhc3ltcDtlXigta24vbSk8YnIgLz4NCqGhoaG8tMSz0rvOu86qMbXEuMXCynDOqqO6MS0gZV4oLWtuL20po6zEx8O0ttTT2sv509BruPa5/s+juq/K/aGhoaG21NOma867trzOqjGjqLPlzbujqbXEuMXCymbOqqO6KDEtIGVeKC1rbi9tKSApXms8YnIgLz4NCqGhoaG21MnPyr3H87W8x/O8q9a1o6y1w2s9bG4yICZ0aW1lczsgbSAvbsqxyKG1w9fu0KHWtaOstMvKsXDUvM6qMS8yKG0vMiBiaXRzIDEsIG0vMiBiaXRzIDApPGJyIC8+DQqhoaGhZiA9ICgxLXApo95rICZhc3ltcDsgKD8po95rID0oPymj3ihsbiAyKW0vbiAmYXN5bXA7ICgwLjYxODUpo95tL248L3A+DQo8cD6hoaGhyOe5+20gPSA4biwgdGhlbjxiciAvPg0KoaGhoSBrID0gOChsbiAyKSA9IDUuNTQ1ICh1c2UgNiBoYXNoIGZ1bmN0aW9ucyk8YnIgLz4NCqGhoaEgZiAmYXN5bXA7ICgwLjYxODUpbS9uID0gKDAuNjE4NSk4ICZhc3ltcDsgMC4wMiAoMiUgZmFsc2UgcG9zaXRpdmVzKTxiciAvPg0KoaGhoSBDb21wYXJlIHRvIGEgaGFzaCB0YWJsZTogZiAmYXN5bXA7IDEgJm5kYXNoOyBlLW4vbSA9IDEtZS0xLzggJmFzeW1wOyAwLjExPC9wPg0KPHByZSBjbGFzcz0="brush:sql;"> add(T item) { for(int i = 0; i < k; i++) array[hi(item)] = 1; } contains(T item) { for(int i = 0; i < k; i++) if(!array[hi(item)]) return false; return true; }

　　Bloom Filter通過允許少量的錯誤來節省大量的存儲空間，但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增加，誤算率隨之增加。但是如果元素數量太少，則使用散列表足矣。
　　另外，一般情況下不能從布隆過濾器中刪除元素. 我們很容易想到把位數組變成整數數組，每插入一個元素相應的計數器加1, 這樣刪除元素時將計數器減掉就可以了。然而要保證安全地刪除元素並非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器裡面. 這一點單憑這個過濾器是無法保證的。另外計數器回繞也會造成問題。

Counting Bloom Filter

　　Insertion ： increment counter
　　Deletion ： decrement counter
　　Overflow ： keep bit 1 forever

　　為了避免計數溢出，計數必須要有足夠的位數。
　　我們先計算第i個Counter被增加j次的概率，其中n為集合元素個數，k為哈希函數個數，m為Counter個數（對應著原來位數組的大小）：

　　上面等式右端的表達式中，前一部分表示從nk次哈希中選擇j次，中間部分表示j次哈希都選中了第i個Counter，後一部分表示其它nk – j次哈希都沒有選中第i個Counter。因此，第i個Counter的值大於j的概率可以限定為：
　　
　　　

add(T item)
{
　　for(int i = 0; i < k; i++)
　　　array[hi(item)]++;
}

contains(T item)
{
　　for(int i = 0; i < k; i++)
　　if(!array[hi(item)])
　　　return false;
　　return true;
}

remove(T item)
{
　　for(int i = 0; i < k; i++)
　　array[hi(item)]--;
}

應用舉例：
　　1）HTTP緩存服務器、Web爬蟲等
　　主要工作是判斷一條URL是否在現有的URL集合之中（可以認為這裡的數據量級上億）。
　　對於HTTP緩存服務器，當本地局域網中的PC發起一條HTTP請求時，緩存服務器會先查看一下這個URL是否已經存在於緩存之中，如果存在的話就沒有必要去原始的服務器拉取數據了（為了簡單起見，我們假設數據沒有發生變化），這樣既能節省流量，還能加快訪問速度，以提高用戶體驗。
　　對於Web爬蟲，要判斷當前正在處理的網頁是否已經處理過了，同樣需要當前URL是否存在於已經處理過的URL列表之中。

　　2）垃圾郵件過濾
　　假設郵件服務器通過發送方的郵件域或者IP地址對垃圾郵件進行過濾，那麼就需要判斷當前的郵件域或者IP地址是否處於黑名單之中。如果郵件服務器的通信郵件數量非常大（也可以認為數據量級上億），那麼也可以使用Bloom Filter算法。