布隆过滤器、计数布隆过滤器与其应用课件.pptx
,信息安全课程报告,Bloom filter - The course report of Information security,布隆过滤器,组长： 汇报人：,目录,CONTENTS,1,背景介绍,2,算法描述,3,误判概率证明和计算,4,优劣详解,6,布隆过滤器设计和应用,5,布隆过滤器改进方案,布隆过滤器 背景介绍,The background of Bloom filter,01,比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断 它是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。,背景介绍,一般来讲，计算机中的集合是用哈希表（hash table）来存储的。 Hash函数作用就是把要存的数据映射成hash表中的一个位置，这个位置就是你要存放该数据的地方。一般把hash表的每个位置都叫做“槽（slot）”。 它的好处是快速准确，缺点是浪费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来 了。,Hash函数,假设hash表的大小为9（即有9个槽），hash(k) = k mod 9，现在要把一串数据存到表里：5,28,19,15,20,33,12,17,10 hash(5)=5, hash(28)=1，hash(19)=1， 0 1 2 3 4 5 6 7 8 n个关键字映射到k个槽中，n只要大于k，一定至少有一个槽放了多于1个元素，所以不能完全避免碰撞（冲突） 。,Hash函数,位图法就是Bitmap的缩写。就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。 位图法可以理解为通过一个bit数组来存储特定数据的一种数据结构；由于bit是数据的最小单位，所以这种数据结构往往是非常节省存储空间。,位图法,比如一个公司有8个员工，现在需要记录公司的考勤记录，传统的方案是记录下每天正常考勤的员工的ID列表，比如2012-01-01:1,2,3,4,5,6,7,8。 假如员工ID采用byte数据类型，则保存每天的考勤记录需要N个byte，其中N是当天考勤的总人数。 1 2 3 4 5 6 7 8 这样可以每天采用恒定的1个byte即可保存当天的考勤记录。,位图法,布隆过滤器（Bloom Filter），它结合了位图和Hash表两者的优点. 位图的优点是节省空间，但是只能处理整型值一类的问题，无法处理字符串一类的问题. 而Hash表却恰巧解决了位图无法解决的问题，然而Hash太浪费空间。,布隆过滤器,计数布隆过滤器,计数布隆过滤器是对基本布隆过滤器的改进，使布隆过滤器可以支持删除成员。 因为布隆过滤器的基本单位是1个bit，只能表达2种状态，即存在、不存在。 如果把基本单位1bit拓展成多个bit，这样就能增加更多信息，表达出多种状态。,布隆过滤器 算法描述,The description of its core algorithm,02,Bloom Filter,布隆过滤器（Bloom Filter）是一种概率空间高效的数据结构。用于检索一个元素是否在一个集合中。 存在“在集合内（可能错误）”和“不在集合内（绝对不在集合内）”两种情况。,温故知新,核心思想就是利用多个不同的Hash函数来解决“冲突”。 如何判断某元素x是否在一个集合中？,X1,X2,X3.Xn,R,X,核心思想,算法原理,Bloom Filter需要一个位数组(和位图类似)和K个映射函数(和Hash表类似)。包含两种操作：插入和查询1.初始化：将所有位置02. 集合R=r1,r2.rn,通过k个相互独立的映射函数h1,h2,.hk，将集合R中的每个元素rj(1=j=n)映射为K个值3.将位数组中相对应的arrayh1，arrayh2，arrayh3.arrayhk置为1,算法原理,算法原理,4.将待查询元素映射到位数组中，若对应每位都是1，则在集合中；否则，不在。注：会出现两种情况：（1）没有发生误判（2）发生了误判（false positive）false positive：有可能会把不属于这个集合的元素误认为属于这个集合。,删除操作：不允许删除一个元素，会导致false negative。false negative：把属于这个集合的元素误认为不属于这个集合。,算法原理,1亿邮箱,16亿二进制,随机数生成器F1-8,f1 = F1 f2 = F2f3 = F3f4 = F4 f5 = F5f6 = F6f7 = F7f8 = F8,信息指纹,随机数生成器G,g1,g2,g3,g4,g5,g6,g7,g8,添加地址,g2,f1 = F1 = f1 f2 = F2 f3 = F3 = m2f4 = F4 = m3 f5 = F5 = m4f6 = F6 = m5f7 = F7 = m6f8 = F8 = m7,g1,16亿二进制,随机数生成器F1-8,s1 = F1 s2 = F2s3 = F3s4 = F4 s5 = F5s6 = F6s7 = F7s8 = F8,信息指纹,t1,t2,t3,t4,t5,t6,t7,t8,查询地址,s1 = F1 = s1 s2 = F2 s3 = F3 = s2s4 = F4 = s3s5 = F5 = s4s6 = F6 = s5s7 = F7 = s6s8 = F8 = s7,t2,误识别概率：万分之一以下,信息指纹,一段文字中包含的信息是信息熵，理论上无损编码最短长度就是信息熵，但如果仅仅区分几段文字或者图片，则不需要这么长的编码，任何一段信息文字，都可以对应一个不太长的随机数，作为区别它和其它信息的指纹（Fingerprint)。只要算法设计的好，任何两段信息的指纹都很难重复，就如同人类的指纹一样。信息指纹在加密、信息压缩和处理中有着广泛的应用。 目前常用的信息指纹算法为Mersenne Twister算法，译为马特赛特旋转演算法，是伪随机数发生器之一，其主要作用是生成伪随机数。此算法是Makoto Matsumoto （松本）和Takuji Nishimura （西村）于1997年开发的，基于有限二进制字段上的矩阵线性再生。可以快速产生高质量的伪随机数，修正了古老随机数产生算法的很多缺陷。,证明与计算误判概率,The proof and calculation of error probability,03,误判概率证明,假设布隆过滤器中的散列函数满足简单均匀散列假设： 每个元素都等概率地散列到所有桶中的任何一个，与其它元素被散列到哪个桶无关。,记号,k ：布隆过滤器中散列函数的个数；m：布隆过滤器中全部比特位个数；n ：布隆过滤器中存在比特位个数。,假设,误判概率证明,对某一特定比特位在一个元素由某特定散列插入时没有被插入的概率为：,没有被置位为1的概率为：,如果插入了1个元素，但都未将其置位的概率为：,如果插入了n个元素，但都未将其置位的概率为：,则此位被置位的概率为：,误判概率证明,现在考虑查询阶段，若对应某个待查询元素的k个 比特位全部置位为1，则可判定其在集合中。因此将某元素误判的概率为：,当m很大时：,从上式中可以看出：当m增大或n减小时，都会使得误判率减小，这也符合直觉。,误判概率计算,现在计算对于给定的m和n，k为何值时可以使得误判率最低。设误判率为f(k)的函数为：,两边取对数 ：,两边对k求导：,设 ， 则简化为,误判概率证明,现在,当k = 0.7 * m / n 时，此时误判率最低。若想保持某固定误判率不变，布隆过滤器的比特数m与被加的元素数n应该是线性同步增加的。,布隆过滤器 优劣详解,The explanation of the pros and cons,04,添加和查询的时间复杂度都为O(k)，与集合中元素的多少无关，这是其他数据结构都不能完成的。 散列函数相互之间没有关系，方便由硬件并行实现。 布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。,优点,当可以承受一些误报时，布隆过滤器比其它表示集合的数据结构有着很大的空间优势。,优点,自平衡二叉搜索树,字典树,散列表,数组,链表,对于一个有1%误报率和一个最优k值的布隆过滤器来说，无论元素的类型及大小，每个元素只需要9.6 bits来存储。,优点,如果你认为1%的误报率太高，那么对每个元素每增加4.8 bits，我们就可将误报率降低为原来的1/10。,优点,比特数组,布隆过滤器,可能元素范围不是很大，并且大多数都在集合中, ,忽略碰撞并且只存储元素是否在其中的二进制信息时,k=1的布隆过滤器,使用k1的布隆过滤器，即k个哈希函数将每个元素改为对应于k个bits，因为误判度会降低很多，并且如果参数k和m选取得好，一半的m可被置为1，这充分说明了布隆过滤器的空间效率性。,优点,空间效率性,布隆过滤器可以表示全集，其它任何数据结构都不能。 k和m相同，使用同一组散列函数的两个布隆过滤器的交并差运算可以使用位操作进行。,优点,在增加了错误率这个因素之后，布隆过滤器通过允许少量的错误来节省大量的存储空间。,优点,错误率,有误判的概率，即存在假阳性（FalsePosition），无法获取集合中的元素数据。 随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。（误判补救方法是：再建立一个小的白名单，存储那些可能被误判的信息。）,缺点,一般情况下不能从布隆过滤器中删除元素。 另外计数器回绕也会造成问题。,缺点,布隆过滤器 改进方案,The design and application in Bloom filter,05,1亿邮箱,16亿二进制,随机数生成器F1-8,f1 = F1 f2 = F2f3 = F3f4 = F4 f5 = F5f6 = F6f7 = F7f8 = F8,信息指纹,随机数生成器G,f1,f2,f3,f4,f5,f6,f7,f8,添加地址,f2,f1 = F1 = f1 f2 = F2 f3 = F3 = m2f4 = F4 = m3 f5 = F5 = m4f6 = F6 = m5f7 = F7 = m6f8 = F8 = m7,f1,Counter,增加删除功能Counting Bloom Filter,Counting Bloom Filter的出现解决了这个问题，它将标准Bloom Filter位数组的每一位扩展为一个小的计数器(Counter)，在插入元素时给对应的k(k为哈希函数个数)个Counter的值分别加1，删除元素时给对应的k个Counter的值分别减1，Counting Bloom Filter通过多占用几倍的存储空间的代价，给Bloom Filter增加了删除操作。,A,B,A,B,BF,CBF,Counting Bloom Filter,n：集合元素个数，k：Hash函数个数，k = 0.7 * m / n M：位数组的大小,从nk次哈希中选择j次,j次哈希都选中了第i个Counter,其它nkj次哈希没有选中第i个Counter,出现频率查询Spectral Bloom Filter,基本思想：1.元素x对应的k个counter中的最小值mx=出现频率fx2.fx mx的概率和标准bloom filter的误判概率相同,A,B,k个位置全部发生碰撞,Spectral Bloom Filter,索引结构,子串长度log3N位,Coarse Vector,子串长度=log3N位,子串长度(loglogN)3位,LOOK UP TABLE,Offset Vector,子串长度=(loglogN)3位,log2N个counter,logN/loglogN,Dynamic Count Filter,Counter,OverFlow Vector,Counting Bloom Filter Vector,x=log(M/n),y = floor(log(max(OFj) + 1,M：集合中元素的个数n：集合中元素种类,查询一个counter时，DCF要求两次内存访问。假设想查询位置为j的counter的值，我们先读出CBFV和OFV的值，分别为Cj和OFj，那么counter的值就可以表示为Vj = (2xOFj Cj)。,Dynamic Count Filter,当OFV的最大值减少到2x 1时，我们可以选择马上重建OFV，也可以采用一些策略延迟OFV的重建，以避免一些临时性的减少导致OFV反复重建。,布隆过滤器 设计和应用,The design and application in Bloom filter,06,布隆过滤器应用,假设有一条URL，那么就先建立32个二进制常量(取不同值，误报率会不同)。即4字节的向量，然后将这32个二进制位全部设置为0，对于这条URL，用8个不同的随机数产生8个信息指纹，再用一个随机数产生器把这8个信息指纹映射到1到32的8个自然数，并把这些位置置为1。如果要检测某条URL是否在这个Bloom Filter中，我们仍然用上述8个随机数产生8个信息指纹，并将这8个指纹对应到布隆过滤器的8个二进制位，如果8位都为1，则说明这条URL在这个Bloom Filter中，否则只要有一位不为1，就说明不在。Bloom Filter绝不会漏掉任何一个重复的URL，但可能会有误报情况，虽然这种可能性很小，上述说的误报概率只有千万分之一，可以通过建立一个小的名单，存储可能误判的URL，并进行比较。,已爬URL的过滤代码实现,class BloomFilter private static final int BIT_SIZE = 2 28 ;/二进制向量的位数 private static final int seeds = new int3, 5, 7, 11, 13, 31, 37, 61;/用于生成信息指纹的8个随机数，最好选取质数 private BitSet bits = new BitSet(BIT_SIZE); private Hash func = new Hashseeds.length;/用于存储8个随机哈希值对象 public BloomFilter() for(int i = 0; i seeds.length; i+) funci = new Hash(BIT_SIZE, seedsi); ,已爬URL的过滤代码实现,ublic void addValue(String value) /将字符串value哈希为8个或多个整数，然后在这些整数的bit上变为1 if(value != null) for(Hash f : func) bits.set(f.hash(value), true); public boolean contains(String value) if(value = null) return false; boolean ret = true; /将要比较的字符串重新以上述方法计算hash值，再与布隆过滤器比对 for(Hash f : func) ret = ret ,已爬URL的过滤代码实现,/*随机哈希值对象*/public static class Hash private int size;/二进制向量数组大小 private int seed;/随机数种子 public Hash(int cap, int seed) this.size = cap; this.seed = seed; /* 计算哈希值(也可以选用别的恰当的哈希函数) */ public int hash(String value) int result = 0; int len = value.length(); for(int i = 0; i len; i+) result = seed * result + value.charAt(i); return (size - 1) ,public class Test public static void main(String args) BloomFilter b = new BloomFilter(); b.addValue(); b.addValue(); System.out.println(b.contains(); System.out.println(b.contains(); ,计数布隆过滤器,负载均衡（load balance）：将任务平摊到多个操作单元上执行，共同完成工作。半流 ：由相同的数据包组成的集合。全流：标识的半流和标识的半流的并集 。大部分的多媒体协议信令和数据传输采用的是不同的端口。传统的负载均衡算法不能保证将多媒体会话映射到一个处理核上。因此应该根据流的信息动态调整映射位置。通过增加DP、SP的端口信息生成信息摘要，通过布隆过滤器直接映射到同一个处理器上面。,计数布隆过滤器,将需要调整的全流标识生成对应的摘要信息Digest，将其保存到精确流匹配布隆过滤器中，对于每一个到来的 IP数据包，提取标识并生成 Digest然后根据和 Digest查询 ESBF结构 ，如果在其中，则转发到指定的处理核 否则 ，对 Digest取模得到对应的处理核 ID。通过保存全流的标识到哈希表中 ，可以动态指定某个全流到相应的处理核,计数布隆过滤器,ESBF算法基于 CBF,利用 CBF的多个哈希函数保证算法具有更低的冲突概率,CBF可以高效的根据(DA, SA, DP, SP)和k个哈希函数对IP包映射到不同的CPU上面进行处理。同时也可以对索引记录高效的插入和删除。动态更改处理IP包的CPU。,计数布隆过滤器,插入算法代码如下：Insertelem(x，id)Digest DIGEST HASH(x)；创建链表结点并将 digest、id域赋值 ；for(i=l to k)ifLinkheadbi(x)counter=0)将结点添加到链表尾部；elseif(链表长度为 counter)将结点添加 到链表尾部；else将结点添加到链表头部；)Linkhead(h。(x)counter+；)插入算法将由生成的 Digest依次插入到 k个链表之中。为了节省空间，如果结点都添加到链表尾部 ，则 k个链表可以共享一个链表结点 。,计数布隆过滤器,删除算法代码如下 ：Deletelem(x)Digest DIGEST HASH(x)；for(i=1 to k)j=O；while(jLinkheadh(x)counter)if(结点 中的 digest域与 Digest相等)将结点从链表中删除 ，跳出循环；j+；Linkhead(h。(x)Counter一； 删除算法将 k个链表 中结点 digest的值与生成的 Digest相 等的结点从链表 中依次删除。,计数布隆过滤器,查询算法代 码如 下：Lookup(x)Digest DIGEST HASH(x)；for(i=l to k)if(Linkhead(h，(x)counter=0)return false；J-k个 counter中最小值对应 的 hi(x)for(i：1 to LinkheadDcounter)i结点 中的 digest域与 Digest相等)return 结点的 id域；return false；)查询算法取 k个计数器 中值最小的计数器所对应 的链表进行比较，最坏情况下比较的次数为该最小计数器的值。,感谢聆听，批评指导,THANK YOU TO LISTEN TO CRITICISM GUIDANCE,布隆过滤器,组长： 汇报人：,
