布隆過濾器
假如有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太浪費空間。針對這個問題，布隆提出了一種基于二進制向量和一系列随機函數的資料結構-布隆過濾器。它的空間使用率和時間效率是很多算法無法企及的，但是它也有一些缺點，就是會有一定的誤判率并且不支援删除操作。
下面來讨論一下布隆過濾器的原理和它的應用。
一.布隆過濾器的原理
布隆過濾器需要的是一個位數組（這個和位圖有點類似）和k個映射函數（和Hash表類似），在初始狀态時，對于長度為m的位數組array，它的所有位都被置為0，如下圖所示：
如果要查找某個元素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函數，具體可以參考：《常見的Hash算法》這篇博文，裡面列舉了很多常見的Hash函數。并且可以證明布隆過濾器的誤判率和位數組的大小以及映射函數的個數有關，相關證明可參考這篇博文：《布隆過濾器 (Bloom Filter) 詳解》。假設誤判率為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，可以支援删除元素，感興趣的讀者可以查閱相關文獻資料。
二.布隆過濾器的應用
布隆過濾器在很多場合能發揮很好的效果，比如：網頁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。
/*布隆過濾器簡易版本 2012.11.10*/
#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.baidu.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;
}