布隆過濾器識別錯誤率

A. 布隆過濾器的缺點

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

B. BloomFilter詳解（布隆過濾器）

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

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

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

三 如何設計bloomfilter

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

bloomfilter的各個參數的錯誤率

公式推完了，大家可以看看，裡面的數學公式基本用到了指數函數 對數函數 微積分求導法則 概率論的知識，大家可以補充看下課本。

個人介紹：杜寶坤，京東聯邦學習從0到1構建者，帶領團隊構建了京東的聯邦學習解決方案，實現了電知慧局商營銷領域支持超大規模的工業化聯邦學習解決方案，支持超大規模樣本PSI隱私對齊、安全的樹模型與神經網路模型等眾多模型支持，並且實現了廣告搭讓側等業務領域的落地，開創了新的業務增長點，產生了顯著的業務經濟效益。

個人喜歡研究技術。基碧猛於從全鏈路思考與決策技術規劃的考量，研究的領域比較多，從架構、數據到演算法與演算法框架均有涉及。歡迎喜歡技術的同學和我交流，郵箱： [email protected]

C. 布隆過濾器和替代演算法

布隆過濾器和替代演算法：但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增加，誤算率隨之增加。但是如果元素數量太少，則使用散列表足矣。

但是包含查找的數據項的數據文件它一定是會返回的，key-value系統中bloom filter返回的數據文件還是需要查看裡面的內容才能知道是否存在所需的數據的，這就保證了執行結果的正確性和完整性。

只是多訪問一些數據文件而已。在數據量很大key-value系統中，建立統一的B+樹索引的代價是非常大的，維護成本也很高，因此綜合起來bloom filter的性能是最好的。

缺點：

但是布隆過濾器的缺點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增加，誤算率隨之增加。常見的補救辦法是建立一個小的白名單，存儲那些可能被誤判的元素。但是如果元素數量太少，則使用散列表足矣。

另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位列陣變成整數數組，每插入一個元素相應的計數器加1, 這樣刪除元素時將計數器減掉就可以了。

D. 布隆過濾器

[TOC]

通過解決方案：

Java中如將數據存儲在內存中，最簡單的演算法結構是HashMap。通過HashMap判斷key是否存在，來判斷數據是否存在。通過hash演算法查找元素，時間復雜度基本是 O(1) （可能存在hash沖突後轉換成鏈表或紅黑樹的情況，時間復雜度的影響可以忽略）。

使用HashMap速度很快，存儲簡單，絕大部分場景可以使用。但是HashMap 佔用的空間比較大 ：

為什麼出現布隆過濾器：

舉例：

如1000萬個Integer存儲在內存中，佔用空間為：4x32x10000000位，即1220兆。如布隆過濾器通過4位元組存儲（布隆過濾器通過多次hash對數據計算後-->幾次hash根據數據量指定，得到多個數據， 佔用多個位 ），則佔用空間為610M。比原有空間少一半。

個人覺得，此比較在字元等的比較中尤為有效。
一個字元串多個字元，根據編碼方式，一個字元兩個或三個位元組，如10個字元，字元串存儲佔用20個位元組，還有相關字元串相關的類信息的內存佔用。
位存儲，根據數據量的大小，hash的位數，靈活計算。如4個位元組，則是原hashMap佔用空間的五分之一。

（1）定義位元組向量

先定義一個指定長度的位元組數組（位元組數組，數組內每個元素的值）。

如長度為8（一個位元組大小），默認所有元素值均為0，如下：

（2）計算哈希值

將要寫入過濾器的數據，根據一定數量的哈希函數，得到多個哈希值，再依次判斷每個哈希值對應的索引。

如使用3個哈希函數，計算得到3個哈希值，判定哈希值對應的位元組向量為為1，3，7。

（3）更新位元組向量

將計算出的位元組向量的索引， 對應的位元組向量中的元素值更高為1 （無論之前為0或者為1，均更改為1）。如下：

（1）計算哈希值

將要判斷過濾器中是否存在的數據，根據一定數量的哈希函數，得到多個哈希值，再依次判斷每個哈希值對應的索引。

如使用3個哈希函數，計算得到3個哈希值，判定哈希值對應的位元組向量為為1，3，7。

注意：哈希函數的判斷方式和計算索引的方式，需和寫入數據時完全一致。

（2）判斷是否存在

如原位元組數組中，對應1，3，7中存在的元素的值都為1。則判定為此元素 可能存在 ，但凡有一個元素的值不為1，則判定此元素 一定不存在 。

布隆過濾器，主要需實現的目標是， 在指定的數據個數范圍內，滿足誤判率在設定的范圍內 ，誤判率太高的話，無法起到過濾數據的情況，誤判率不能為0。

因此需要計算兩個數據來滿足 存儲數據的個數 和 誤判率 ：

使用布隆過濾器的決定性因素之一，就是此演算法插入數據和查詢數據的速度必須非常快。因此在對數據進行哈希運算的時候， 需選擇計算快的哈希演算法 。

而且， 寫入數據以及查詢數據的哈希演算法，順序和演算法都需完全一致 。

待完善。。。。。

可以通過google的 guava ，在內存中輕松實現布隆過濾器。

無需手動計算滿足位元組數組的長度和哈希個數，只需要輸入 擬輸入數據的個數 和 期望誤判率 即可。

不輸入期望誤判率的情況下，誤判率為0.03，即100個非范圍內的數據進行校驗時，約三個數據會判定為存在。

多次執行，結果一致，根據結果判定：

內存的存儲存在局限性，可以使用redis中的bitMap來實現位元組數組的存儲。

使用redis實現布隆過濾器。需要根據公式，手動計算位元組數組的長度和哈希的個數。

實現過程，待完善。。。。。。

E. 基於布隆過濾器的非法URL識別，有沒有能用Java

假如有1億個不重復的正整數（大致范圍已知），但是只有1G的內存可用，如何判斷該范圍內的某個數是否出現在這1億個數中？最常用的處理辦法是利用點陣圖，1*108/1024*1024*8=11.9，也只需要申請12M的內存。但是如果是1億個郵件地址，如何確定某個郵件地址是否在這1億個地址中？這個時候可能大家想到的最常用的辦法就是利用Hash表了，但是大家可以細想一下，如果利用Hash表來處理，必須開辟空間去存儲這1億個郵件地址，因為在Hash表中不可能避免的會發生碰撞，假設一個郵件地址只佔8個位元組，為了保證Hash表的碰撞率，所以需要控制Hash表的裝填因子在0.5左右，那麼至少需要2*8*108/1024*1024*1024=1.5G的內存空間，這種情況下利用Hash表是無法處理的。這個時候要用到另外一種數據結構-布隆過濾器（Bloom Filter），它是由Burton Howard Bloom在1970年提出的，它結合了點陣圖和Hash表兩者的優點，點陣圖的優點是節省空間，但是只能處理整型值一類的問題，無法處理字元串一類的問題，而Hash表卻恰巧解決了點陣圖無法解決的問題，然而Hash太浪費空間。針對這個問題，布隆提出了一種基於二進制向量和一系列隨機函數的數據結構-布隆過濾器。它的空間利用率和時間效率是很多演算法無法企及的，但是它也有一些缺點，就是會有一定的誤判率並且不支持刪除操作。

布隆過濾器的原理
1
布隆過濾器需要的是一個位數組（這個和點陣圖有點類似）和k個映射函數（和Hash表類似），在初始狀態時，對於長度為m的位數組array，它的所有位都被置為0

2
對於有n個元素的集合S={s1,s2......sn}，通過k個映射函數{f1,f2,......fk}，將集合S中的每個元素sj(1<=j<=n)映射為k個值{g1,g2......gk}，然後再將位數組array中相對應的array[g1],array[g2]......array[gk]置為1：

3
如果要查找某個元素item是否在S中，則通過映射函數{f1,f2.....fk}得到k個值{g1,g2.....gk}，然後再判斷array[g1],array[g2]......array[gk]是否都為1，若全為1，則item在S中，否則item不在S中。這個就是布隆過濾器的實現原理。
當然有讀者可能會問：即使array[g1],array[g2]......array[gk]都為1，能代表item一定在集合S中嗎？不一定，因為有這個可能：就是集合中的若干個元素通過映射之後得到的數值恰巧包括g1,g2,.....gk，那麼這種情況下可能會造成誤判，但是這個概率很小，一般在萬分之一以下。
很顯然，布隆過濾器的誤判率和這k個映射函數的設計有關，到目前為止，有很多人設計出了很多高效實用的hash函數。並且可以證明布隆過濾器的誤判率和位數組的大小以及映射函數的個數有關。假設誤判率為p，位數組大小為m，集合數據個數為n，映射函數個數為k，它們之間的關系如下：
p=2-(m/n)*ln2 可得 m=(-n*lnp)/(ln2)2=-2*n*lnp=2*n*ln(1/p)
k=(m/n)*ln2=0.7*(m/n)
可以驗證若p=0.1，(m/n)=9.6，即存儲每個元素需要9.6bit位，此時k=0.7*(m/n)=6.72，即存儲每個元素需要9.6個bit位，其中有6.72個bit位被置為1了，因此需要7個映射函數。從這里可以看出布隆過濾器的優越性了，比如上面例子中的，存儲一個郵件地址，只需要10個bit位，而用hash表存儲需要8*8=64個bit位。
一般情況下，p和n由用戶設定，然後根據p和n的值設計位數組的大小和所需的映射函數的個數，再根據實際情況來設計映射函數。
尤其要注意的是，布隆過濾器是不允許刪除元素的，因為若刪除一個元素，可能會發生漏判的情況。不過有一種布隆過濾器的變體Counter Bloom Filter，可以支持刪除元素，感興趣的讀者可以查閱相關文獻資料。
END
布隆過濾器的應用
布隆過濾器在很多場合能發揮很好的效果，比如：網頁URL的去重，垃圾郵件的判別，集合重復元素的判別，查詢加速（比如基於key-value的存儲系統）等，下面舉幾個例子：
1.有兩個URL集合A,B，每個集合中大約有1億個URL，每個URL佔64位元組，有1G的內存，如何找出兩個集合中重復的URL。
很顯然，直接利用Hash表會超出內存限制的范圍。這里給出兩種思路：
第一種：如果不允許一定的錯誤率的話，只有用分治的思想去解決，將A,B兩個集合中的URL分別存到若干個文件中{f1,f2...fk}和{g1,g2....gk}中，然後取f1和g1的內容讀入內存，將f1的內容存儲到hash_map當中，然後再取g1中的url，若有相同的url，則寫入到文件中，然後直到g1的內容讀取完畢，再取g2...gk。然後再取f2的內容讀入內存。。。依次類推，知道找出所有的重復url。
第二種：如果允許一定錯誤率的話，則可以用布隆過濾器的思想。
2.在進行網頁爬蟲時，其中有一個很重要的過程是重復URL的判別，如果將所有的url存入到資料庫中，當資料庫中URL的數量很多時，在判重時會造成效率低下，此時常見的一種做法就是利用布隆過濾器，還有一種方法是利用berkeley db來存儲url，Berkeley db是一種基於key-value存儲的非關系資料庫引擎，能夠大大提高url判重的效率。
布隆過濾器的簡易版本實現：
#include<iostream>
#include<bitset>
#include<string>
#define MAX 2<<24
using namespace std;

bitset<MAX> bloomSet; //簡化了由n和p生成m的過程

int seeds[7]={3, 7, 11, 13, 31, 37, 61}; //使用7個hash函數

int getHashValue(string str,int n) //計算Hash值
{
int result=0;
int i;
for(i=0;i<str.size();i++)
{
result=seeds[n]*result+(int)str[i];
if(result > 2<<24)
result%=2<<24;
}
return result;
}

bool isInBloomSet(string str) //判斷是否在布隆過濾器中
{
int i;
for(i=0;i<7;i++)
{
int hash=getHashValue(str,i);
if(bloomSet[hash]==0)
return false;
}
return true;
}

void addToBloomSet(string str) //添加元素到布隆過濾器
{
int i;
for(i=0;i<7;i++)
{
int hash=getHashValue(str,i);
bloomSet.set(hash,1);
}
}

void initBloomSet() //初始化布隆過濾器
{
addToBloomSet("http://www..com");
addToBloomSet("http://www.cnblogs.com");
addToBloomSet("http://www.google.com");
}

int main(int argc, char *argv[])
{

int n;
initBloomSet();
while(scanf("%d",&n)==1)
{
string str;
while(n--)
{
cin>>str;
if(isInBloomSet(str))
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}

}
return 0;
}