布隆過濾

㈠ 布隆過濾器的優點

相比於其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優勢。布隆過濾器回存儲空間和插入答/查詢時間都是常數。另外, Hash函數相互之間沒有關系，方便由硬體並行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。
布隆過濾器可以表示全集，其它任何數據結構都不能；
k和m相同，使用同一組Hash函數的兩個布隆過濾器的交並差運算可以使用位操作進行。
布隆過濾器

㈡ 布隆過濾器既然有錯誤率，為什麼還能應用在key-value系統中

bloom filter的特點是會出現誤報，但不會漏報，也就是說對於bloom filter驗證的一個數據文件，可能回不包含你查找的數據項答，但是包含你查找的數據項的數據文件它一定是會返回的，key-value系統中bloom filter返回的數據文件還是需要查看裡面的內容才能知道是否存在所需的數據的，這就保證了執行結果的正確性和完整性。因此key-value系統不會因此而出錯的，只是多訪問一些數據文件而已。在數據量很大key-value系統中，建立統一的B+樹索引的代價是非常大的，維護成本也很高，因此綜合起來bloom filter的性能是最好的。

㈢ 如何用python寫布隆過濾器

下面的是網路上找到的python的布隆過濾器的實現.

#!/usr/local/bin/python2.7
#coding=gbk
'''
Createdon2012-11-7

@author:palydawn
'''
importcmath
fromBitVectorimportBitVector

classBloomFilter(object):
def__init__(self,error_rate,elementNum):
#計算所需要的bit數
self.bit_num=-1*elementNum*cmath.log(error_rate)/(cmath.log(2.0)*cmath.log(2.0))

#四位元組對齊
self.bit_num=self.align_4byte(self.bit_num.real)

#分配內存
self.bit_array=BitVector(size=self.bit_num)

#計算hash函數個數
self.hash_num=cmath.log(2)*self.bit_num/elementNum

self.hash_num=self.hash_num.real

#向上取整
self.hash_num=int(self.hash_num)+1

#產生hash函數種子
self.hash_seeds=self.generate_hashseeds(self.hash_num)

definsert_element(self,element):
forseedinself.hash_seeds:
hash_val=self.hash_element(element,seed)
#取絕對值
hash_val=abs(hash_val)
#取模，防越界
hash_val=hash_val%self.bit_num
#設置相應的比特位
self.bit_array[hash_val]=1

#檢查元素是否存在，存在返回true，否則返回false
defis_element_exist(self,element):
forseedinself.hash_seeds:
hash_val=self.hash_element(element,seed)
#取絕對值
hash_val=abs(hash_val)
#取模，防越界
hash_val=hash_val%self.bit_num

#查看值
ifself.bit_array[hash_val]==0:
returnFalse
returnTrue

#內存對齊
defalign_4byte(self,bit_num):
num=int(bit_num/32)
num=32*(num+1)
returnnum

#產生hash函數種子,hash_num個素數
defgenerate_hashseeds(self,hash_num):
count=0
#連續兩個種子的最小差值
gap=50
#初始化hash種子為0
hash_seeds=[]
forindexinxrange(hash_num):
hash_seeds.append(0)
forindexinxrange(10,10000):
max_num=int(cmath.sqrt(1.0*index).real)
flag=1
fornuminxrange(2,max_num):
ifindex%num==0:
flag=0
break

ifflag==1:
#連續兩個hash種子的差值要大才行
ifcount>0and(index-hash_seeds[count-1])<gap:
continue
hash_seeds[count]=index
count=count+1

ifcount==hash_num:
break
returnhash_seeds

defhash_element(self,element,seed):
hash_val=1
forchinstr(element):
chval=ord(ch)
hash_val=hash_val*seed+chval
returnhash_val
'''
#測試代碼
bf=BloomFilter(0.001,1000000)
element='palydawn'
bf.insert_element(element)
printbf.is_element_exist('palydawn')'''

#其中使用了BitVector庫，python本身的二進制操作看起來很麻煩，這個就簡單多了

如果解決了您的問題請採納！
如果未解決請繼續追問

㈣ 看過的視頻讓用戶不再觀看為什麼使用布隆過濾器而不是直接使用setBit與getBit進行取值比對呢

不行。

因為布來隆過濾器的原源理是用多個hash函數對id進行hash後得到一系列值，而在布隆數組中看這些值對應的位上是否命中，如果都命中說明這個值重復。
用id不經過hash直接去對比，乍一想好像可以，但是你想想，假如id是10位，並且我們只用數字，那麼布隆過濾器的長度只有10位（0123456789）,這個長度的過濾器幾乎沒法使用，容量太低，誤差率太高。即使算上大小寫字母，也只有62個，看似62很多，但是這里定死了id必須用這62個字元，而假如中間加一層hash，那id用什麼字元和我布隆過濾器用什麼字元以及過濾器的長度都可以自由指定，靈活很多。

㈤ 基於布隆過濾器的非法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;
}

㈥ 如何使用bloomfilter構建大型Java緩存系統

在如抄今的軟體當中，緩存襲是解決很多問題的一個關鍵概念。你的應用可能會進行CPU密集型運算。你當然不想讓這些運算一邊又一邊的重復執行，相反，你可以只執行一次， 把這個結果放在內存中作為緩存。有時系統的瓶頸在I/O操作上，比如你不想重復的查...

㈦ 如何用布隆過濾器去重mysql

在資料庫中創建欄位的UNIQUE屬性
在資料庫中創建一個唯一的索引，在插入數據之前檢查待插入的數據是否存在
使用Set或HashSet保存數據，確保唯一

㈧ 布隆過濾器的缺點

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

㈨ 用python安裝布隆過濾器報錯，這怎麼解決

但是布隆過濾器的缺抄點和優點一樣明顯。誤算率是其中之一。隨著存入的元素數量增加，誤算率隨之增加。但是如果元素數量太少，則使用散列表足矣。另外，一般情況下不能從布隆過濾器中刪除元素。我們很容易想到把位列陣變成整數數組

㈩ 布隆過濾器用的多少個hash函數

相比於其它的數據結構，布隆過濾器在空間和時間方面都有巨大的優回勢。布隆過濾器存答儲空間和插入/查詢時間都是常數。另外, Hash函數相互之間沒有關系，方便由硬體並行實現。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優勢。