因此将某元素误判的概率为：
从上式中可以看出： 当m增大或n减小时，都会使得误判率减小， 这也符合直觉。
误判概率计算
两边取对数 ： 现在计算对于给定的m和n，k为何值时可以使得误 判率最低。 设误判率为f(k)的函数为：
两边对k求导： 设 ， 则简化为
误判概率证明
现在
当k = 0.7 * m / n 时，此时误判率最低。 若想保持某固定误判率不变，布隆过滤器的比特数 m与被加的元素数n应该是线性同步增加的。
误判概率证明
对某一特定比特位在一个元素由某特定散列插入时 没有被插入的概率为：
如果插入了n个元素，但都未将其置位的概率为：
没有被置位为1的概率为：
则此位被置位的概率为：
如果插入了1个元素，但都未将其置位的概率为：
误判概率证明
当m很大时： 现在考虑查询阶段，若对应某个待查询元素的k个 比特位全部置位为1，则可判定其在集合中。
添加地址
1亿 邮箱
0 0 0 0
16亿二进制
0
0
0
0
0
0
abc123@
abc456@
随机数生成器 F1-8
随机数生成器G
1 1 0 1 1 1 1 1 1
f1 = F1 f2 = F2 f3 = F3 f4 = F4 f5 = F5 f6 = F6 f7 = F7 f8 = F8
X
X1,X2,X3.... Xn
R
算法原理
Bloom Filter需要一个位数组(和位图类似)和K个映射函数(和Hash表类
似)。包含两种操作：插入和查询
1.初始化：将所有位置0
2. 集合R={r1,r2...rn},通过k个相互独立的映射函数{h1,h2,......hk}，将集合R
中的每个元素rj(1<=j<=n)映射为K个值
5
n个关键字映射到k个槽中，n只要大于k，一定至少有一个槽放了多于1个元
位图法
位图法就是Bitmap的缩写。就是用每一位来存放某种状态，适用于 大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存 不存在的。
位图法可以理解为通过一个bit数组来存储特定数据的一种数据结构； 由于bit是数据的最小单位，所以这种数据结构往往是非常节省存储空间。
The explanation of the pros and cons
优劣详解
布隆过滤器
优点
添加和查询的时间复杂度都为O(k)，与集合中元素的多 少无关，这是其他数据结构都不能完成的。 散列函数相互之间没有关系，方便由硬件并行实现。 布隆过滤器不需要存储元素本身，在某些对保密要求非 常严格的场合有优势。
算法描述
布隆过滤器
Bloom Filter
布隆过滤器（Bloom Filter）是一种概率空间高效的数据结 构。用于检索一个元素是否在一个集合中。 存在“在集合内（可能错误）”和“不在集合内（绝对不在集 合内）”两种情况。
温故知新
核心思想
核心思想就是利用多个不同的Hash函数来解决“冲突”。 如何判断某元素x是否在一个集合中？
信息 指纹
1
0
f1 f'1
f'2f2f8f3 Nhomakorabeaf4
f5
f6
f7
增加删除功能——Counting Bloom Filter
Counting Bloom Filter的出现解 决了这个问题，它将标准Bloom Filter位数组的每一位扩展为一个 小的计数器(Counter)，在插入元素 时给对应的k(k为哈希函数个数)个 Counter的值分别加1，删除元素时 给对应的k个Counter的值分别减1， Counting Bloom Filter通过多占用 几倍的存储空间的代价，给Bloom Filter增加了删除操作。
3.将位数组中相对应的array[h1]，array[h2]，array[h3]......array[hk]置为1
算法原理
算法原理
算法原理
4.将待查询元素映射到位数组中，若对应每位都是1，则在集合中； 否则，不在。 注：会出现两种情况：（1）没有发生误判（2）发生了误判 （false positive） false positive：有可能会把不属于这个集合的元素误认为属于这 个集合。 删除操作： 不允许删除一个元素，会导致false negative。 false negative：把属于这个集合的元素误认为不属于这个集合。
1
1
1
1
1
1
1
1
1
0
t1
t'2
t2
t8
t3
t4
t5
t6
t7
s1 = F1 s2 = F2 s3 = F3 s4 = F4 s5 = F5 s6 = F6 s7 = F7 s8 = F8 s'1 = F'1 = s1 s'2 = F'2 s'3 = F'3 = s2 s'4 = F'4 = s3 s'5 = F'5 = s4 s'6 = F'6 = s5 s'7 = F'7 = s6 s'8 = F'8 = s7
建立一个小的白名单，存储那些可能被误判的信息。）
缺点
一般情况下不能从布隆过滤器中删除元素。
另外计数器回绕也会造成问题。
The design and application in Bloom filter
改进方案
布隆过滤器
添加地址
1亿 邮箱
0 0 0 0
16亿二进制
0
0
0
0
0
0
abc123@
abc123@
随机数生成器 F1-8
BCD123@
信息 指纹
误识别概率： 万分之一以下
信息指纹
一段文字中包含的信息是信息熵，理论上无损编码最短长度就是信息熵， 但如果仅仅区分几段文字或者图片，则不需要这么长的编码，任何一段 信息文字，都可以对应一个不太长的随机数，作为区别它和其它信息的 指纹（Fingerprint)。只要算法设计的好，任何两段信息的指纹都很难重 复，就如同人类的指纹一样。信息指纹在加密、信息压缩和处理中有着 广泛的应用。 目前常用的信息指纹算法为Mersenne Twister算法，译为马特赛特旋转 演算法，是伪随机数发生器之一，其主要作用是生成伪随机数。此算法 是Makoto Matsumoto （松本）和Takuji Nishimura （西村）于1997年开 发的，基于有限二进制字段上的矩阵线性再生。可以快速产生高质量的 伪随机数，修正了古老随机数产生算法的很多缺陷。
0
1
1
1
0
0
1
1
这样可以每天采用恒定的1个byte即可保存当天的考勤记录。
布隆过滤器
布隆过滤器（Bloom Filter），它结合了位图和Hash表 两者的优点. 位图的优点是节省空间，但是只能处理整型值一类的问题 ，无法处理字符串一类的问题. 而Hash表却恰巧解决了位图无法解决的问题，然而Hash太 浪费空间。
优点
布隆过滤器可以表示全集，其它任何数据结构都不能。 k和m相同，使用同一组散列函数的两个布隆过滤器的
交并差运算可以使用位操作进行。
优点
在增加了错误率这个因素之后，布隆过滤器通过允许少 量的错误来节省大量的存储空间。
缺点
有误判的概率，即存在假阳性（False Position），无法
获取集合中的元素数据。 随着存入的元素数量增加，误算率随之增加。但是如果 元素数量太少，则使用散列表足矣。（误判补救方法是：再
优点
可能元素范围不是很大，并且大多数都在集合中
比特数组
>>
布隆过滤器
忽略碰撞并且只存储元素是否在其中的二进制信息时
k=1的布隆过滤器
优点
使用k>1的布隆过滤器，即k个哈希函数将每个元素改 为对应于k个bits，因为误判度会降低很多，并且如果参数k 和m选取得好，一半的m可被置为1，这充分说明了布隆过 滤器的空间效率性。
The proof and calculation of error probability
误判概率
证明与计算
误判概率证明
假设
假设布隆过滤器中的散列函数满足简单均匀散列假设： 每个元素都等概率地散列到所有桶中的任何一个，与其它 元素被散列到哪个桶无关。
记号
k ：布隆过滤器中散列函数的个数； m：布隆过滤器中全部比特位个数； n ：布隆过滤器中存在比特位个数。
f‘1 = F‘1 = f1 f’2 = F’2 f‘3 = F’3 = m2 f’4 = F‘4 = m3 f‘5 = F’5 = m4 f’6 = F‘6 = m5 f‘7 = F’7 = m6 f’8 = F‘8 = m7
信息 指纹
1
0
g1 g'1
g'2
g2
g8
g3
g4
g5
g6
g7
查询地址
16亿二进制
The background of Bloom filter
背景介绍
布隆过滤器
背景介绍
比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断 它是否在已知的字典中）； 在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；
在网络爬虫里，一个网址是否被访问过等等。
Hash函数
一般来讲，计算机中的集合是用哈希表（hash table）来存储的。 Hash函数作用就是把要存的数据映射成hash表中的一个位置，这个位 置就是你要存放该数据的地方。一般把hash表的每个位置都叫做“槽 （slot）”。 它的好处是快速准确，缺点是浪费存储空间。当集合比较小时，这个问 题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来 了。