布隆過濾器、計數(shù)布隆過濾器與其應(yīng)用課件

信息安全課程報告Bloomfilter--------ThecoursereportofInformationsecurity布隆過濾器組長：

匯報人：信息安全課程報告Bloomfilter--------1目錄CONTENTS1背景介紹2算法描述3誤判概率證明和計算4優(yōu)劣詳解6布隆過濾器設(shè)計和應(yīng)用5布隆過濾器改進(jìn)方案目錄CONTENTS1背景介紹2算法描述3誤判概率證明和計算2布隆過濾器背景介紹ThebackgroundofBloomfilter01布隆過濾器ThebackgroundofBloomf3比如在字處理軟件中，需要檢查一個英語單詞是否拼寫正確（也就是要判斷它是否在已知的字典中）；在FBI，一個嫌疑人的名字是否已經(jīng)在嫌疑名單上；在網(wǎng)絡(luò)爬蟲里，一個網(wǎng)址是否被訪問過等等。背景介紹背景介紹4

一般來講，計算機(jī)中的集合是用哈希表（hashtable）來存儲的。Hash函數(shù)作用就是把要存的數(shù)據(jù)映射成hash表中的一個位置，這個位置就是你要存放該數(shù)據(jù)的地方。一般把hash表的每個位置都叫做“槽（slot）”。

它的好處是快速準(zhǔn)確，缺點(diǎn)是浪費(fèi)存儲空間。當(dāng)集合比較小時，這個問題不顯著，但是當(dāng)集合巨大時，哈希表存儲效率低的問題就顯現(xiàn)出來了。Hash函數(shù)一般來講，計算機(jī)中的集合是用哈希表（hashta5

假設(shè)hash表的大小為9（即有9個槽），hash(k)=kmod9，現(xiàn)在要把一串?dāng)?shù)據(jù)存到表里：5,28,19,15,20,33,12,17,10hash(5)=5,hash(28)=1，hash(19)=1，

012345678

n個關(guān)鍵字映射到k個槽中，n只要大于k，一定至少有一個槽放了多于1個元素，所以不能完全避免碰撞（沖突）

。

Hash函數(shù)285 假設(shè)hash表的大小為9（即有9個槽），hash(k)=6

位圖法就是Bitmap的縮寫。就是用每一位來存放某種狀態(tài)，適用于大規(guī)模數(shù)據(jù)，但數(shù)據(jù)狀態(tài)又不是很多的情況。通常是用來判斷某個數(shù)據(jù)存不存在的。

位圖法可以理解為通過一個bit數(shù)組來存儲特定數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)；由于bit是數(shù)據(jù)的最小單位，所以這種數(shù)據(jù)結(jié)構(gòu)往往是非常節(jié)省存儲空間。位圖法 位圖法就是Bitmap的縮寫。就是用每一位來存放某種狀態(tài)，7

比如一個公司有8個員工，現(xiàn)在需要記錄公司的考勤記錄，傳統(tǒng)的方案是記錄下每天正常考勤的員工的ID列表，比如2012-01-01:[1,2,3,4,5,6,7,8]。假如員工ID采用byte數(shù)據(jù)類型，則保存每天的考勤記錄需要N個byte，其中N是當(dāng)天考勤的總?cè)藬?shù)。

12345678這樣可以每天采用恒定的1個byte即可保存當(dāng)天的考勤記錄。位圖法01110011 比如一個公司有8個員工，現(xiàn)在需要記錄公司的考勤記錄，傳統(tǒng)的8

布隆過濾器（BloomFilter），它結(jié)合了位圖和Hash表兩者的優(yōu)點(diǎn).

位圖的優(yōu)點(diǎn)是節(jié)省空間，但是只能處理整型值一類的問題，無法處理字符串一類的問題.

而Hash表卻恰巧解決了位圖無法解決的問題，然而Hash太浪費(fèi)空間。布隆過濾器 布隆過濾器（BloomFilter），它結(jié)合了位圖和Ha9計數(shù)布隆過濾器

計數(shù)布隆過濾器是對基本布隆過濾器的改進(jìn)，使布隆過濾器可以支持刪除成員。因?yàn)椴悸∵^濾器的基本單位是1個bit，只能表達(dá)2種狀態(tài)，即存在、不存在。如果把基本單位1bit拓展成多個bit，這樣就能增加更多信息，表達(dá)出多種狀態(tài)。計數(shù)布隆過濾器計數(shù)布隆過濾器是對基本布隆過濾10布隆過濾器

算法描述Thedescriptionofit'scorealgorithm02布隆過濾器Thedescriptionofit'sc11BloomFilter

布隆過濾器（BloomFilter）是一種概率空間高效的數(shù)據(jù)結(jié)構(gòu)。用于檢索一個元素是否在一個集合中。存在“在集合內(nèi)（可能錯誤）”和“不在集合內(nèi)（絕對不在集合內(nèi)）”兩種情況。BloomFilter布隆過濾器（Bloo

溫故知新溫故知新

核心思想就是利用多個不同的Hash函數(shù)來解決“沖突”。如何判斷某元素x是否在一個集合中？X1,X2,X3....XnRX核心思想核心思想就是利用多個不同的Hash函數(shù)來解決“沖突”算法原理

BloomFilter需要一個位數(shù)組(和位圖類似)和K個映射函數(shù)(和Hash表類似)。包含兩種操作：插入和查詢1.初始化：將所有位置02.集合R={r1,r2...rn},通過k個相互獨(dú)立的映射函數(shù){h1,h2,......hk}，將集合R中的每個元素rj(1<=j<=n)映射為K個值3.將位數(shù)組中相對應(yīng)的array[h1]，array[h2]，array[h3]......array[hk]置為1算法原理BloomFilter需要一個位數(shù)15算法原理算法原理算法原理算法原理174.將待查詢元素映射到位數(shù)組中，若對應(yīng)每位都是1，則在集合中；否則，不在。注：會出現(xiàn)兩種情況：（1）沒有發(fā)生誤判（2）發(fā)生了誤判（falsepositive）falsepositive：有可能會把不屬于這個集合的元素誤認(rèn)為屬于這個集合。刪除操作：不允許刪除一個元素，會導(dǎo)致falsenegative。falsenegative：把屬于這個集合的元素誤認(rèn)為不屬于這個集合。算法原理4.將待查詢元素映射到位數(shù)組中，若對應(yīng)每位都是1，則在集合中1800000000001億郵箱16億二進(jìn)制隨機(jī)數(shù)生成器F1-8f1=F1

f2=F2f3=F3f4=F4

f5=F5f6=F6f7=F7f8=F8信息指紋隨機(jī)數(shù)生成器G1011111110g1g2g3g4g5g6g7g8添加地址g'21111111110f‘1=F‘1

=f1

f’2=F’2f‘3=F’3=m2f’4=F‘4=m3f‘5=F’5=m4f’6=F‘6=m5f‘7=F’7=m6f’8=F‘8=m7g'100000000001億郵箱16億二進(jìn)制隨機(jī)數(shù)生成器F1-81916億二進(jìn)制隨機(jī)數(shù)生成器F1-8s1=F1

s2=F2s3=F3s4=F4

s5=F5s6=F6s7=F7s8=F8信息指紋1111111110t1t2t3t4t5t6t7t8查詢地址s'1=F'1=s1

s'2=F'2s'3=F'3=s2s'4=F'4

=s3s'5=F'5=s4s'6=F'6=s5s'7=F'7=s6s'8=F'8=s7t'2誤識別概率：萬分之一以下16億二進(jìn)制隨機(jī)數(shù)生成器F1-8s1=F1信息指紋120信息指紋一段文字中包含的信息是信息熵，理論上無損編碼最短長度就是信息熵，但如果僅僅區(qū)分幾段文字或者圖片，則不需要這么長的編碼，任何一段信息文字，都可以對應(yīng)一個不太長的隨機(jī)數(shù)，作為區(qū)別它和其它信息的指紋（Fingerprint)。只要算法設(shè)計的好，任何兩段信息的指紋都很難重復(fù)，就如同人類的指紋一樣。信息指紋在加密、信息壓縮和處理中有著廣泛的應(yīng)用。目前常用的信息指紋算法為MersenneTwister算法，譯為馬特賽特旋轉(zhuǎn)演算法，是偽隨機(jī)數(shù)發(fā)生器之一，其主要作用是生成偽隨機(jī)數(shù)。此算法是MakotoMatsumoto（松本）和TakujiNishimura（西村）于1997年開發(fā)的，基于有限二進(jìn)制字段上的矩陣線性再生?？梢钥焖佼a(chǎn)生高質(zhì)量的偽隨機(jī)數(shù)，修正了古老隨機(jī)數(shù)產(chǎn)生算法的很多缺陷。信息指紋一段文字中包含的信息是信息熵，理論上無損編碼最短長度證明與計算誤判概率Theproofandcalculationoferrorprobability03證明與計算Theproofandcalculation22誤判概率證明假設(shè)布隆過濾器中的散列函數(shù)滿足簡單均勻散列假設(shè)：每個元素都等概率地散列到所有桶中的任何一個，與其它元素被散列到哪個桶無關(guān)。記號k：布隆過濾器中散列函數(shù)的個數(shù)；m：布隆過濾器中全部比特位個數(shù)；n：布隆過濾器中存在比特位個數(shù)。假設(shè)誤判概率證明假設(shè)布隆過濾器中的散列函數(shù)滿足簡單均勻散列假設(shè)：23誤判概率證明對某一特定比特位在一個元素由某特定散列插入時沒有被插入的概率為：沒有被置位為1的概率為：如果插入了1個元素，但都未將其置位的概率為：如果插入了n個元素，但都未將其置位的概率為：則此位被置位的概率為：誤判概率證明對某一特定比特位在一個元素由某特定散列插入時沒有24誤判概率證明現(xiàn)在考慮查詢階段，若對應(yīng)某個待查詢元素的k個比特位全部置位為1，則可判定其在集合中。因此將某元素誤判的概率為：當(dāng)m很大時：從上式中可以看出：當(dāng)m增大或n減小時，都會使得誤判率減小，這也符合直覺。誤判概率證明現(xiàn)在考慮查詢階段，若對應(yīng)某個待查詢元素的k個比25誤判概率計算現(xiàn)在計算對于給定的m和n，k為何值時可以使得誤判率最低。設(shè)誤判率為f(k)的函數(shù)為：兩邊取對數(shù)：兩邊對k求導(dǎo)：設(shè)

，則簡化為誤判概率計算現(xiàn)在計算對于給定的m和n，k為何值時可以使得誤判26誤判概率證明現(xiàn)在當(dāng)k=0.7*m/n時，此時誤判率最低。若想保持某固定誤判率不變，布隆過濾器的比特數(shù)m與被加的元素數(shù)n應(yīng)該是線性同步增加的。誤判概率證明現(xiàn)在當(dāng)k=0.7*m/n時，此時誤27布隆過濾器優(yōu)劣詳解Theexplanationoftheprosandcons04布隆過濾器Theexplanationofthepr28

添加和查詢的時間復(fù)雜度都為O(k)，與集合中元素的多少無關(guān)，這是其他數(shù)據(jù)結(jié)構(gòu)都不能完成的。

散列函數(shù)相互之間沒有關(guān)系，方便由硬件并行實(shí)現(xiàn)。

布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴(yán)格的場合有優(yōu)勢。優(yōu)點(diǎn)添加和查詢的時間復(fù)雜度都為O(k)，與集合中當(dāng)可以承受一些誤報時，布隆過濾器比其它表示集合的數(shù)據(jù)結(jié)構(gòu)有著很大的空間優(yōu)勢。優(yōu)點(diǎn)自平衡二叉搜索樹字典樹散列表數(shù)組鏈表當(dāng)可以承受一些誤報時，布隆過濾器比其它表示集對于一個有1%誤報率和一個最優(yōu)k值的布隆過濾器來說，無論元素的類型及大小，每個元素只需要9.6bits來存儲。優(yōu)點(diǎn)

如果你認(rèn)為1%的誤報率太高，那么對每個元素每增加4.8bits，我們就可將誤報率降低為原來的1/10。對于一個有1%誤報率和一個最優(yōu)k值的布隆過濾優(yōu)點(diǎn)比特數(shù)組布隆過濾器可能元素范圍不是很大，并且大多數(shù)都在集合中

>>忽略碰撞并且只存儲元素是否在其中的二進(jìn)制信息時k=1的布隆過濾器優(yōu)點(diǎn)比特數(shù)組布隆過濾器可能元素范圍不是很大，并且大多數(shù)都在集

使用k>1的布隆過濾器，即k個哈希函數(shù)將每個元素改為對應(yīng)于k個bits，因?yàn)檎`判度會降低很多，并且如果參數(shù)k和m選取得好，一半的m可被置為1，這充分說明了布隆過濾器的空間效率性。優(yōu)點(diǎn)空間效率性使用k>1的布隆過濾器，即k個哈希函數(shù)將每個布隆過濾器可以表示全集，其它任何數(shù)據(jù)結(jié)構(gòu)都不能。

k和m相同，使用同一組散列函數(shù)的兩個布隆過濾器的交并差運(yùn)算可以使用位操作進(jìn)行。優(yōu)點(diǎn)布隆過濾器可以表示全集，其它任何數(shù)據(jù)結(jié)構(gòu)都不

在增加了錯誤率這個因素之后，布隆過濾器通過允許少量的錯誤來節(jié)省大量的存儲空間。優(yōu)點(diǎn)錯誤率在增加了錯誤率這個因素之后，布隆過濾器通過允

有誤判的概率，即存在假陽性（False

Position），無法獲取集合中的元素數(shù)據(jù)。

隨著存入的元素數(shù)量增加，誤算率隨之增加。但是如果元素數(shù)量太少，則使用散列表足矣。（誤判補(bǔ)救方法是：再建立一個小的白名單，存儲那些可能被誤判的信息。）缺點(diǎn)有誤判的概率，即存在假陽性（False

Po

一般情況下不能從布隆過濾器中刪除元素。

另外計數(shù)器回繞也會造成問題。缺點(diǎn)缺點(diǎn)布隆過濾器改進(jìn)方案ThedesignandapplicationinBloomfilter05布隆過濾器Thedesignandapplicatio3800000000001億郵箱16億二進(jìn)制隨機(jī)數(shù)生成器F1-8f1=F1

f2=F2f3=F3f4=F4

f5=F5f6=F6f7=F7f8=F8信息指紋隨機(jī)數(shù)生成器G1011111110f1f2f3f4f5f6f7f8添加地址f'22111111110f‘1=F‘1

=f1

f’2=F’2f‘3=F’3=m2f’4=F‘4=m3f‘5=F’5=m4f’6=F‘6=m5f‘7=F’7=m6f’8=F‘8=m7f'1Counter00000000001億郵箱16億二進(jìn)制隨機(jī)數(shù)生成器F1-839增加刪除功能——CountingBloomFilterCountingBloomFilter的出現(xiàn)解決了這個問題，它將標(biāo)準(zhǔn)BloomFilter位數(shù)組的每一位擴(kuò)展為一個小的計數(shù)器(Counter)，在插入元素時給對應(yīng)的k(k為哈希函數(shù)個數(shù))個Counter的值分別加1，刪除元素時給對應(yīng)的k個Counter的值分別減1，CountingBloomFilter通過多占用幾倍的存儲空間的代價，給BloomFilter增加了刪除操作。10110AB10210ABBFCBF增加刪除功能——CountingBloomFilterC40CountingBloomFiltern：集合元素個數(shù)，k：Hash函數(shù)個數(shù)，k=0.7*m/nM：位數(shù)組的大小從nk次哈希中選擇j次j次哈希都選中了第i個Counter其它nk–j次哈希沒有選中第i個CounterCountingBloomFiltern：集合元素個數(shù)，41出現(xiàn)頻率查詢——SpectralBloomFilter基本思想：1.元素x對應(yīng)的k個counter中的最小值mx>=出現(xiàn)頻率fx2.fx≠mx的概率和標(biāo)準(zhǔn)bloomfilter的誤判概率相同5016111210ABk個位置全部發(fā)生碰撞出現(xiàn)頻率查詢——SpectralBloomFilter42SpectralBloomFilter索引結(jié)構(gòu)co1co2co3co4o1o2o3o4子串長度>log3N位CoarseVectorco1‘co2’o1‘o2’子串長度<=log3N位子串長度>(loglogN)3位LOOKUPTABLEOffsetVector子串長度<=(loglogN)3位log2N個counterlogN/loglogNSpectralBloomFilter索引結(jié)構(gòu)co1co43DynamicCountFilter025701026527Counter000001000100010OverFlowVectorCountingBloomFilterVectorx=log(M/n)y=floor(log(max(OFj)))+1M：集合中元素的個數(shù)n：集合中元素種類查詢一個counter時，DCF要求兩次內(nèi)存訪問。假設(shè)想查詢位置為j的counter的值，我們先讀出CBFV和OFV的值，分別為Cj和OFj，那么counter的值就可以表示為Vj=(2x×OFj＋Cj)。DynamicCountFilter025701026544DynamicCountFilter最大值增加至2x+1時，每次OFV大小改變的時候都需要重建。重建是一件開銷很大的工作，必須重新創(chuàng)建一個OFV數(shù)組，然后把舊OFV數(shù)組的值拷貝到新建的OFV數(shù)組中，最后把舊OFV數(shù)組的空間釋放掉。1000001000100010當(dāng)OFV的最大值減少到2x–1時，我們可以選擇馬上重建OFV，也可以采用一些策略延遲OFV的重建，以避免一些臨時性的減少導(dǎo)致OFV反復(fù)重建。000001000000010DynamicCountFilter最大值增加至2x+145布隆過濾器設(shè)計和應(yīng)用ThedesignandapplicationinBloomfilter06布隆過濾器Thedesignandapplicatio46布隆過濾器應(yīng)用假設(shè)有一條URL，那么就先建立32個二進(jìn)制常量(取不同值，誤報率會不同)。即4字節(jié)的向量，然后將這32個二進(jìn)制位全部設(shè)置為0，對于這條URL，用8個不同的隨機(jī)數(shù)產(chǎn)生8個信息指紋，再用一個隨機(jī)數(shù)產(chǎn)生器把這8個信息指紋映射到1到32的8個自然數(shù)，并把這些位置置為1。如果要檢測某條URL是否在這個BloomFilter中，我們?nèi)匀挥蒙鲜?個隨機(jī)數(shù)產(chǎn)生8個信息指紋，并將這8個指紋對應(yīng)到布隆過濾器的8個二進(jìn)制位，如果8位都為1，則說明這條URL在這個BloomFilter中，否則只要有一位不為1，就說明不在。BloomFilter絕不會漏掉任何一個重復(fù)的URL，但可能會有誤報情況，雖然這種可能性很小，上述說的誤報概率只有千萬分之一，可以通過建立一個小的名單，存儲可能誤判的URL，并進(jìn)行比較。布隆過濾器應(yīng)用假設(shè)有一條URL，那么就先建立32個二進(jìn)制常量已爬URL的過濾代碼實(shí)現(xiàn)classBloomFilter{privatestaticfinalintBIT_SIZE=2<<28;//二進(jìn)制向量的位數(shù)privatestaticfinalint[]seeds=newint[]{3,5,7,11,13,31,37,61};//用于生成信息指紋的8個隨機(jī)數(shù)，最好選取質(zhì)數(shù)privateBitSetbits=newBitSet(BIT_SIZE);privateHash[]func=newHash[seeds.length];//用于存儲8個隨機(jī)哈希值對象publicBloomFilter(){for(inti=0;i<seeds.length;i++){func[i]=newHash(BIT_SIZE,seeds[i]);}}已爬URL的過濾代碼實(shí)現(xiàn)classBloomFilter{已爬URL的過濾代碼實(shí)現(xiàn)publicvoidaddValue(Stringvalue){//將字符串value哈希為8個或多個整數(shù)，然后在這些整數(shù)的bit上變?yōu)?if(value!=null){for(Hashf:func)bits.set(f.hash(value),true);}}publicbooleancontains(Stringvalue){if(value==null)returnfalse;booleanret=true;//將要比較的字符串重新以上述方法計算hash值，再與布隆過濾器比對for(Hashf:func)ret=ret&&bits.get(f.hash(value));returnret;}已爬URL的過濾代碼實(shí)現(xiàn)publicvoidaddVal已爬URL的過濾代碼實(shí)現(xiàn)/**隨機(jī)哈希值對象*/publicstaticclassHash{privateintsize;//二進(jìn)制向量數(shù)組大小privateintseed;//隨機(jī)數(shù)種子publicHash(intcap,intseed){this.size=cap;this.seed=seed;}/**計算哈希值(也可以選用別的恰當(dāng)?shù)墓：瘮?shù))*/publicinthash(Stringvalue){intresult=0;intlen=value.length();for(inti=0;i<len;i++){result=seed*result+value.charAt(i);}return(size-1)&result;}}publicclassTest{publicstaticvoidmain(String[]args){BloomFilterb=newBloomFilter();b.addValue("");b.addValue("");System.out.println(b.contains(""));System.out.println(b.contains(""));}}已爬URL的過濾代碼實(shí)現(xiàn)/**隨機(jī)哈希值對象*/public計數(shù)布隆過濾器負(fù)載均衡（loadbalance）：將任務(wù)平攤到多個操作單元上執(zhí)行，共同完成工作。半流：由相同<DA，SA，DP,SP>的數(shù)據(jù)包組成的集合。全流：<DA，SA，DP,SP>標(biāo)識的半流和<SA，DA，SP,DP>標(biāo)識的半流的并集。大部分的多媒體協(xié)議信令和數(shù)據(jù)傳輸采用的是不同的端口。傳統(tǒng)的負(fù)載均衡算法不能保證將多媒體會話映射到一個處理核上。因此應(yīng)該根據(jù)流的信息動態(tài)調(diào)整映射位置。通過增加DP、SP的端口信息生成信息摘要，通過布隆過濾器直接映射到同一個處理器上面。計數(shù)布隆過濾器負(fù)載均衡（loadbalance）：將任務(wù)平計數(shù)布隆過濾器將需要調(diào)整的全流標(biāo)識生成對應(yīng)的摘要信息Digest，將其保存到精確流匹配布隆過濾器中，對于每一個到來的IP數(shù)據(jù)包，提取<DA，SA，DP,SP>標(biāo)識并生成Digest然后根據(jù)<DA，SA，DP,SP>和Digest查詢ESBF結(jié)構(gòu)，如果在其中，則轉(zhuǎn)發(fā)到指定的處理核否則，對Digest取模得到對應(yīng)的處理核ID。通過保存全流的標(biāo)識到哈希表中，可以動態(tài)指定某個全流到相應(yīng)的處理核計數(shù)布隆過濾器將需要調(diào)整的全流標(biāo)識生成對應(yīng)的摘要信息Dige計數(shù)布隆過濾器ESBF算法基于CBF,利用CBF的多個哈希函數(shù)保證算法具有更低的沖突概率,CBF可以高效的根據(jù)(DA,SA,DP,SP)和k個哈希函數(shù)對IP包映射到不同的CPU上面進(jìn)行處理。同時也可以對索引記錄高效的插入和刪除。動態(tài)更改處理IP包的CPU。

計數(shù)布隆過濾器ESBF算法基于CBF,利用CBF的多個哈計數(shù)布隆過濾器插入算法代碼如下：Insertelem(x，id){DigestDIGEST—HASH(x)；創(chuàng)建鏈表結(jié)點(diǎn)并將digest、id域賦值；for(i=ltok){ifLinkhead[bi(x)]．counter==0)將結(jié)點(diǎn)添加到鏈表尾部；else{if(鏈表長度為counter)將結(jié)點(diǎn)添加到鏈表尾部；else將結(jié)點(diǎn)添加到鏈表頭部；)Linkhead(h。(x))．counter++；)插入算法將由<DA，SA，DP,SP>生成的Digest依次插入到k個鏈表之中。為了節(jié)省空間，如果結(jié)點(diǎn)都添加到鏈表尾部，則k個鏈表可以共享一個鏈表結(jié)點(diǎn)。計數(shù)布隆過濾器插入算法代碼如下：計數(shù)布隆過濾器刪除算法代碼如下：Deletelem(x){DigestDIGEST—HASH(x)；for(i=1tok){j=O；while(j≠Linkhead[h．(x)．counter){if(結(jié)點(diǎn)中的digest域與Digest相等)將結(jié)點(diǎn)從鏈表中刪除，跳出循環(huán)；j++；}Linkhead(h。(x))．Counter一；}}刪除算法將k個鏈表中結(jié)點(diǎn)digest的值與<DA，SA，DP,SP>生成的Digest相等的結(jié)點(diǎn)從鏈表中依次刪除。計數(shù)布隆過濾器計數(shù)布隆過濾器查詢算法代碼如下：Lookup(x){DigestDIGEST—HASH(x)；for(i=ltok)if(Linkhead(h，(x))．counter==0)returnfalse；J<--k個counter中最小值對應(yīng)的hi(x)for(i：1toLinkheadD．counter){i結(jié)點(diǎn)中的digest域與Digest相等)return結(jié)點(diǎn)的id域；}returnfalse；)查詢算法取k個計數(shù)器中值最小的計數(shù)器所對應(yīng)的鏈表進(jìn)行比較，最壞情況下比較的次數(shù)為該最小計數(shù)器的值。計數(shù)布隆過濾器查詢算法代碼如下：感謝聆聽，批評指導(dǎo)THANKYOUTOLISTENTOCRITICISMGUIDANCE布隆過濾器組長：

匯報人：感謝聆聽，批評指導(dǎo)THANKYOUTOLISTENT57信息安全課程報告Bloomfilter--------ThecoursereportofInformationsecurity布隆過濾器組長：

匯報人：信息安全課程報告Bloomfilter--------58目錄CONTENTS1背景介紹2算法描述3誤判概率證明和計算4優(yōu)劣詳解6布隆過濾器設(shè)計和應(yīng)用5布隆過濾器改進(jìn)方案目錄CONTENTS1背景介紹2算法描述3誤判概率證明和計算59布隆過濾器背景介紹ThebackgroundofBloomfilter01布隆過濾器ThebackgroundofBloomf60比如在字處理軟件中，需要檢查一個英語單詞是否拼寫正確（也就是要判斷它是否在已知的字典中）；在FBI，一個嫌疑人的名字是否已經(jīng)在嫌疑名單上；在網(wǎng)絡(luò)爬蟲里，一個網(wǎng)址是否被訪問過等等。背景介紹背景介紹61

一般來講，計算機(jī)中的集合是用哈希表（hashtable）來存儲的。Hash函數(shù)作用就是把要存的數(shù)據(jù)映射成hash表中的一個位置，這個位置就是你要存放該數(shù)據(jù)的地方。一般把hash表的每個位置都叫做“槽（slot）”。

它的好處是快速準(zhǔn)確，缺點(diǎn)是浪費(fèi)存儲空間。當(dāng)集合比較小時，這個問題不顯著，但是當(dāng)集合巨大時，哈希表存儲效率低的問題就顯現(xiàn)出來了。Hash函數(shù)一般來講，計算機(jī)中的集合是用哈希表（hashta62

假設(shè)hash表的大小為9（即有9個槽），hash(k)=kmod9，現(xiàn)在要把一串?dāng)?shù)據(jù)存到表里：5,28,19,15,20,33,12,17,10hash(5)=5,hash(28)=1，hash(19)=1，

012345678

n個關(guān)鍵字映射到k個槽中，n只要大于k，一定至少有一個槽放了多于1個元素，所以不能完全避免碰撞（沖突）

。

Hash函數(shù)285 假設(shè)hash表的大小為9（即有9個槽），hash(k)=63

位圖法就是Bitmap的縮寫。就是用每一位來存放某種狀態(tài)，適用于大規(guī)模數(shù)據(jù)，但數(shù)據(jù)狀態(tài)又不是很多的情況。通常是用來判斷某個數(shù)據(jù)存不存在的。

位圖法可以理解為通過一個bit數(shù)組來存儲特定數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)；由于bit是數(shù)據(jù)的最小單位，所以這種數(shù)據(jù)結(jié)構(gòu)往往是非常節(jié)省存儲空間。位圖法 位圖法就是Bitmap的縮寫。就是用每一位來存放某種狀態(tài)，64

比如一個公司有8個員工，現(xiàn)在需要記錄公司的考勤記錄，傳統(tǒng)的方案是記錄下每天正?？记诘膯T工的ID列表，比如2012-01-01:[1,2,3,4,5,6,7,8]。假如員工ID采用byte數(shù)據(jù)類型，則保存每天的考勤記錄需要N個byte，其中N是當(dāng)天考勤的總?cè)藬?shù)。

12345678這樣可以每天采用恒定的1個byte即可保存當(dāng)天的考勤記錄。位圖法01110011 比如一個公司有8個員工，現(xiàn)在需要記錄公司的考勤記錄，傳統(tǒng)的65

布隆過濾器（BloomFilter），它結(jié)合了位圖和Hash表兩者的優(yōu)點(diǎn).

位圖的優(yōu)點(diǎn)是節(jié)省空間，但是只能處理整型值一類的問題，無法處理字符串一類的問題.

而Hash表卻恰巧解決了位圖無法解決的問題，然而Hash太浪費(fèi)空間。布隆過濾器 布隆過濾器（BloomFilter），它結(jié)合了位圖和Ha66計數(shù)布隆過濾器

計數(shù)布隆過濾器是對基本布隆過濾器的改進(jìn)，使布隆過濾器可以支持刪除成員。因?yàn)椴悸∵^濾器的基本單位是1個bit，只能表達(dá)2種狀態(tài)，即存在、不存在。如果把基本單位1bit拓展成多個bit，這樣就能增加更多信息，表達(dá)出多種狀態(tài)。計數(shù)布隆過濾器計數(shù)布隆過濾器是對基本布隆過濾67布隆過濾器

算法描述Thedescriptionofit'scorealgorithm02布隆過濾器Thedescriptionofit'sc68BloomFilter

布隆過濾器（BloomFilter）是一種概率空間高效的數(shù)據(jù)結(jié)構(gòu)。用于檢索一個元素是否在一個集合中。存在“在集合內(nèi)（可能錯誤）”和“不在集合內(nèi)（絕對不在集合內(nèi)）”兩種情況。BloomFilter布隆過濾器（Bloo

溫故知新溫故知新

核心思想就是利用多個不同的Hash函數(shù)來解決“沖突”。如何判斷某元素x是否在一個集合中？X1,X2,X3....XnRX核心思想核心思想就是利用多個不同的Hash函數(shù)來解決“沖突”算法原理

BloomFilter需要一個位數(shù)組(和位圖類似)和K個映射函數(shù)(和Hash表類似)。包含兩種操作：插入和查詢1.初始化：將所有位置02.集合R={r1,r2...rn},通過k個相互獨(dú)立的映射函數(shù){h1,h2,......hk}，將集合R中的每個元素rj(1<=j<=n)映射為K個值3.將位數(shù)組中相對應(yīng)的array[h1]，array[h2]，array[h3]......array[hk]置為1算法原理BloomFilter需要一個位數(shù)72算法原理算法原理算法原理算法原理744.將待查詢元素映射到位數(shù)組中，若對應(yīng)每位都是1，則在集合中；否則，不在。注：會出現(xiàn)兩種情況：（1）沒有發(fā)生誤判（2）發(fā)生了誤判（falsepositive）falsepositive：有可能會把不屬于這個集合的元素誤認(rèn)為屬于這個集合。刪除操作：不允許刪除一個元素，會導(dǎo)致falsenegative。falsenegative：把屬于這個集合的元素誤認(rèn)為不屬于這個集合。算法原理4.將待查詢元素映射到位數(shù)組中，若對應(yīng)每位都是1，則在集合中7500000000001億郵箱16億二進(jìn)制隨機(jī)數(shù)生成器F1-8f1=F1

f2=F2f3=F3f4=F4

f5=F5f6=F6f7=F7f8=F8信息指紋隨機(jī)數(shù)生成器G1011111110g1g2g3g4g5g6g7g8添加地址g'21111111110f‘1=F‘1

=f1

f’2=F’2f‘3=F’3=m2f’4=F‘4=m3f‘5=F’5=m4f’6=F‘6=m5f‘7=F’7=m6f’8=F‘8=m7g'100000000001億郵箱16億二進(jìn)制隨機(jī)數(shù)生成器F1-87616億二進(jìn)制隨機(jī)數(shù)生成器F1-8s1=F1

s2=F2s3=F3s4=F4

s5=F5s6=F6s7=F7s8=F8信息指紋1111111110t1t2t3t4t5t6t7t8查詢地址s'1=F'1=s1

s'2=F'2s'3=F'3=s2s'4=F'4

=s3s'5=F'5=s4s'6=F'6=s5s'7=F'7=s6s'8=F'8=s7t'2誤識別概率：萬分之一以下16億二進(jìn)制隨機(jī)數(shù)生成器F1-8s1=F1信息指紋177信息指紋一段文字中包含的信息是信息熵，理論上無損編碼最短長度就是信息熵，但如果僅僅區(qū)分幾段文字或者圖片，則不需要這么長的編碼，任何一段信息文字，都可以對應(yīng)一個不太長的隨機(jī)數(shù)，作為區(qū)別它和其它信息的指紋（Fingerprint)。只要算法設(shè)計的好，任何兩段信息的指紋都很難重復(fù)，就如同人類的指紋一樣。信息指紋在加密、信息壓縮和處理中有著廣泛的應(yīng)用。目前常用的信息指紋算法為MersenneTwister算法，譯為馬特賽特旋轉(zhuǎn)演算法，是偽隨機(jī)數(shù)發(fā)生器之一，其主要作用是生成偽隨機(jī)數(shù)。此算法是MakotoMatsumoto（松本）和TakujiNishimura（西村）于1997年開發(fā)的，基于有限二進(jìn)制字段上的矩陣線性再生?？梢钥焖佼a(chǎn)生高質(zhì)量的偽隨機(jī)數(shù)，修正了古老隨機(jī)數(shù)產(chǎn)生算法的很多缺陷。信息指紋一段文字中包含的信息是信息熵，理論上無損編碼最短長度證明與計算誤判概率Theproofandcalculationoferrorprobability03證明與計算Theproofandcalculation79誤判概率證明假設(shè)布隆過濾器中的散列函數(shù)滿足簡單均勻散列假設(shè)：每個元素都等概率地散列到所有桶中的任何一個，與其它元素被散列到哪個桶無關(guān)。記號k：布隆過濾器中散列函數(shù)的個數(shù)；m：布隆過濾器中全部比特位個數(shù)；n：布隆過濾器中存在比特位個數(shù)。假設(shè)誤判概率證明假設(shè)布隆過濾器中的散列函數(shù)滿足簡單均勻散列假設(shè)：80誤判概率證明對某一特定比特位在一個元素由某特定散列插入時沒有被插入的概率為：沒有被置位為1的概率為：如果插入了1個元素，但都未將其置位的概率為：如果插入了n個元素，但都未將其置位的概率為：則此位被置位的概率為：誤判概率證明對某一特定比特位在一個元素由某特定散列插入時沒有81誤判概率證明現(xiàn)在考慮查詢階段，若對應(yīng)某個待查詢元素的k個比特位全部置位為1，則可判定其在集合中。因此將某元素誤判的概率為：當(dāng)m很大時：從上式中可以看出：當(dāng)m增大或n減小時，都會使得誤判率減小，這也符合直覺。誤判概率證明現(xiàn)在考慮查詢階段，若對應(yīng)某個待查詢元素的k個比82誤判概率計算現(xiàn)在計算對于給定的m和n，k為何值時可以使得誤判率最低。設(shè)誤判率為f(k)的函數(shù)為：兩邊取對數(shù)：兩邊對k求導(dǎo)：設(shè)

，則簡化為誤判概率計算現(xiàn)在計算對于給定的m和n，k為何值時可以使得誤判83誤判概率證明現(xiàn)在當(dāng)k=0.7*m/n時，此時誤判率最低。若想保持某固定誤判率不變，布隆過濾器的比特數(shù)m與被加的元素數(shù)n應(yīng)該是線性同步增加的。誤判概率證明現(xiàn)在當(dāng)k=0.7*m/n時，此時誤84布隆過濾器優(yōu)劣詳解Theexplanationoftheprosandcons04布隆過濾器Theexplanationofthepr85

添加和查詢的時間復(fù)雜度都為O(k)，與集合中元素的多少無關(guān)，這是其他數(shù)據(jù)結(jié)構(gòu)都不能完成的。

散列函數(shù)相互之間沒有關(guān)系，方便由硬件并行實(shí)現(xiàn)。

布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴(yán)格的場合有優(yōu)勢。優(yōu)點(diǎn)添加和查詢的時間復(fù)雜度都為O(k)，與集合中當(dāng)可以承受一些誤報時，布隆過濾器比其它表示集合的數(shù)據(jù)結(jié)構(gòu)有著很大的空間優(yōu)勢。優(yōu)點(diǎn)自平衡二叉搜索樹字典樹散列表數(shù)組鏈表當(dāng)可以承受一些誤報時，布隆過濾器比其它表示集對于一個有1%誤報率和一個最優(yōu)k值的布隆過濾器來說，無論元素的類型及大小，每個元素只需要9.6bits來存儲。優(yōu)點(diǎn)

如果你認(rèn)為1%的誤報率太高，那么對每個元素每增加4.8bits，我們就可將誤報率降低為原來的1/10。對于一個有1%誤報率和一個最優(yōu)k值的布隆過濾優(yōu)點(diǎn)比特數(shù)組布隆過濾器可能元素范圍不是很大，并且大多數(shù)都在集合中

>>忽略碰撞并且只存儲元素是否在其中的二進(jìn)制信息時k=1的布隆過濾器優(yōu)點(diǎn)比特數(shù)組布隆過濾器可能元素范圍不是很大，并且大多數(shù)都在集

使用k>1的布隆過濾器，即k個哈希函數(shù)將每個元素改為對應(yīng)于k個bits，因?yàn)檎`判度會降低很多，并且如果參數(shù)k和m選取得好，一半的m可被置為1，這充分說明了布隆過濾器的空間效率性。優(yōu)點(diǎn)空間效率性使用k>1的布隆過濾器，即k個哈希函數(shù)將每個布隆過濾器可以表示全集，其它任何數(shù)據(jù)結(jié)構(gòu)都不能。

k和m相同，使用同一組散列函數(shù)的兩個布隆過濾器的交并差運(yùn)算可以使用位操作進(jìn)行。優(yōu)點(diǎn)布隆過濾器可以表示全集，其它任何數(shù)據(jù)結(jié)構(gòu)都不

在增加了錯誤率這個因素之后，布隆過濾器通過允許少量的錯誤來節(jié)省大量的存儲空間。優(yōu)點(diǎn)錯誤率在增加了錯誤率這個因素之后，布隆過濾器通過允

有誤判的概率，即存在假陽性（False

Position），無法獲取集合中的元素數(shù)據(jù)。

隨著存入的元素數(shù)量增加，誤算率隨之增加。但是如果元素數(shù)量太少，則使用散列表足矣。（誤判補(bǔ)救方法是：再建立一個小的白名單，存儲那些可能被誤判的信息。）缺點(diǎn)有誤判的概率，即存在假陽性（False

Po

一般情況下不能從布隆過濾器中刪除元素。

另外計數(shù)器回繞也會造成問題。缺點(diǎn)缺點(diǎn)布隆過濾器改進(jìn)方案ThedesignandapplicationinBloomfilter05布隆過濾器Thedesignandapplicatio9500000000001億郵箱16億二進(jìn)制隨機(jī)數(shù)生成器F1-8f1=F1

f2=F2f3=F3f4=F4

f5=F5f6=F6f7=F7f8=F8信息指紋隨機(jī)數(shù)生成器G1011111110f1f2f3f4f5f6f7f8添加地址f'22111111110f‘1=F‘1

=f1

f’2=F’2f‘3=F’3=m2f’4=F‘4=m3f‘5=F’5=m4f’6=F‘6=m5f‘7=F’7=m6f’8=F‘8=m7f'1Counter00000000001億郵箱16億二進(jìn)制隨機(jī)數(shù)生成器F1-896增加刪除功能——CountingBloomFilterCountingBloomFilter的出現(xiàn)解決了這個問題，它將標(biāo)準(zhǔn)BloomFilter位數(shù)組的每一位擴(kuò)展為一個小的計數(shù)器(Counter)，在插入元素時給對應(yīng)的k(k為哈希函數(shù)個數(shù))個Counter的值分別加1，刪除元素時給對應(yīng)的k個Counter的值分別減1，CountingBloomFilter通過多占用幾倍的存儲空間的代價，給BloomFilter增加了刪除操作。10110AB10210ABBFCBF增加刪除功能——CountingBloomFilterC97CountingBloomFiltern：集合元素個數(shù)，k：Hash函數(shù)個數(shù)，k=0.7*m/nM：位數(shù)組的大小從nk次哈希中選擇j次j次哈希都選中了第i個Counter其它nk–j次哈希沒有選中第i個CounterCountingBloomFiltern：集合元素個數(shù)，98出現(xiàn)頻率查詢——SpectralBloomFilter基本思想：1.元素x對應(yīng)的k個counter中的最小值mx>=出現(xiàn)頻率fx2.fx≠mx的概率和標(biāo)準(zhǔn)bloomfilter的誤判概率相同5016111210ABk個位置全部發(fā)生碰撞出現(xiàn)頻率查詢——SpectralBloomFilter99SpectralBloomFilter索引結(jié)構(gòu)co1co2co3co4o1o2o3o4子串長度>log3N位CoarseVectorco1‘co2’o1‘o2’子串長度<=log3N位子串長度>(loglogN)3位LOOKUPTABLEOffsetVector子串長度<=(loglogN)3位log2N個counterlogN/loglogNSpectralBloomFilter索引結(jié)構(gòu)co1co100DynamicCountFilter025701026527Counter000001000100010OverFlowVectorCountingBloomFilterVectorx=log(M/n)y=floor(log(max(OFj)))+1M：集合中元素的個數(shù)n：集合中元素種類查詢一個counter時，DCF要求兩次內(nèi)存訪問。假設(shè)想查詢位置為j的counter的值，我們先讀出CBFV和OFV的值，分別為Cj和OFj，那么counter的值就可以表示為Vj=(2x×OFj＋Cj)。DynamicCountFilter0257010265101DynamicCountFilter最大值增加至2x+1時，每次OFV大小改變的時候都需要重建。重建是一件開銷很大的工作，必須重新創(chuàng)建一個OFV數(shù)組，然后把舊OFV數(shù)組的值拷貝到新建的OFV數(shù)組中，最后把舊OFV數(shù)組的空間釋放掉。1000001000100010當(dāng)OFV的最大值減少到2x–1時，我們可以選擇馬上重建OFV，也可以采用一些策略延遲OFV的重建，以避免一些臨時性的減少導(dǎo)致OFV反復(fù)重建。000001000000010DynamicCountFilter最大值增加至2x+1102布隆過濾器設(shè)計和應(yīng)用ThedesignandapplicationinBloomfilter06布隆過濾器Thedesignandapplicatio103布隆過濾器應(yīng)用假設(shè)有一條URL，那么就先建立32個二進(jìn)制常量(取不同值，誤報率會不同)。即4字節(jié)的向量，然后將這32個二進(jìn)制位全部設(shè)置為0，對于這條URL，用8個不同的隨機(jī)數(shù)產(chǎn)生8個信息指紋，再用一個隨機(jī)數(shù)產(chǎn)生器把這8個信息指紋映射到1到32的8個自然數(shù)，并把這些位置置為1。如果要檢測某條URL是否在這個BloomFilter中，我們?nèi)匀挥蒙鲜?個隨機(jī)數(shù)產(chǎn)生8個信息指紋，并將這8個指紋對應(yīng)到布隆過濾器的8個二進(jìn)制位，如果8位都為1，則說明這條URL在這個BloomFilter中，否則只要有一位不為1，就說明不在。BloomFilter絕不會漏掉任何一個重復(fù)的URL，但可能會有誤報情況，雖然這種可能性很小，上述說的誤報概率只有千萬分之一，可以通過建立一個小的名單，存儲可能誤判的URL，并進(jìn)行比較。布隆過濾器應(yīng)用假設(shè)有一條URL，那么就先建立32個二進(jìn)制常量已爬URL的過濾代碼實(shí)現(xiàn)classBloomFilter{privatestaticfinalintBIT_SIZE=2<<28;//二進(jìn)制向量的位數(shù)privatestaticfinalint[]seeds=newint[]{3,5,7,11,13,31,37,61};//用于生成信息指紋的8個隨機(jī)數(shù)，最好選取質(zhì)數(shù)privateBitSetbits=newBitSet(BIT_SIZE);privateHash[]func=newHash[seeds.length];//用于存儲8個隨機(jī)哈希值對象publicBloomFilter(){for(inti=0;i<seeds.length;i++){func[i]=newHash(BIT_SIZE,seeds[i]);}}已爬URL的過濾代碼實(shí)現(xiàn)classBloomFilter{已爬URL的過濾代碼實(shí)現(xiàn)publicvoidaddValue(Stringvalue){//將字符串value哈希為8個或多個整數(shù)，然后在這些整數(shù)的bit上變?yōu)?if(value!=null){for(Hashf:func)bits.set(f.hash(value),true);}}publicbooleancontains(Stringvalue){if(value==null)returnfalse;booleanret=true;//將要比較的字符串重新以上述方法計算hash值，再與布隆過濾器比對for(Hashf:func)ret=ret&&bits.get(f.hash(value));returnret;}已爬URL的過濾代碼實(shí)現(xiàn)publicvoidaddVal已爬URL的過濾代碼實(shí)現(xiàn)/**隨機(jī)哈希值對象*/publicstaticclassHash{privateintsize;//二進(jìn)制向量數(shù)組大小privateintseed;//隨機(jī)數(shù)種子publicHash(intcap,intseed){