首页 > 代码库 > 布隆过滤器
布隆过滤器
通常,我们需要判断一个元素是否在一个集合中。比如在WPS字处理软件中,需要检查一个单词是否拼写正确;在FBI
中需要判断一个嫌疑犯的名字是否在嫌疑名单上;在网络爬虫里,判断一个网址是否被访问过。最简单的解决办法就是
采用HashTable的方法来存储,它的好处是快速且精确,缺点是耗费大量内存空间。
现在,来介绍一种数学工具,叫做布隆过滤器(Bloom Filter),是布隆在1970年提出的,它所需要的空间比传统
的Hash表的方法少很多(减少到Hash表所需内存的1/8或者1/4),而且并不会存储元素本身,所以数据安全性比较
高。但缺点是有一定的误识别率,并且无法删除元素。元素越多,误识别率越大,这里的误识别是指不在集合中的元素
可能被误识别为在集合中的元素,当然在集合中的元素一定能被识别到。
接下来介绍布隆过滤器的原理。
布隆过滤器是一个很长的二进制向量和一系列随机映射函数,以存储一亿个垃圾邮件的黑名单为例进行说明。
先建立一个16亿二进制向量,然后将这16亿个二进制位全部清零,对于每一个邮件地址,用8个不同的随机数产生器
产生8个信息指纹,使这8个信息指纹映射到1-16亿中的8个自然数,现在把这8个位置的二进制全部设置为1,对这1
亿个邮件地址都进行这样的操作后,一个针对这些电子邮件地址的布隆过滤器就建成了。
在设计布隆过滤器时,假设布隆过滤器有比特,里面有个元素,每个元素对应个信息指纹的哈希函数。接下来
会分析布隆过滤器中的误识别问题。
在布隆过滤器中插入一个元素,它的第一个哈希函数会把过滤器中的某个比特位置位1,因此任何一个比特位被置成1
的概率是,那么它依然是0的概率是,对于过滤器中一个特定的位置,如果这个元素的个哈希函数都
没有把它设置成1,其概率是
如果过滤器中插入了第二个元素,某个特定的比特位依然没有被设置成1的概率为
如果插入了个元素还没有把某个特定的比特位设置为1,其概率为
那么,反过来,一个特定的比特位在插入个元素后,被设置为1的概率则是
假定这个元素都放到布隆过滤器中了,新来一个不在集合中的元素,由于它的信息指纹的哈希函数都是随机的,因
此它的第一个哈希函数正好命中某个值为1的比特的概率就是
一个不在集合中的元素被误识别在集合中,需要所有的哈希函数对应的比特值均为1,其概率为
我们很容易知道如下结论
那么实际上就有
现在设
由于是常数,设,那么上述方程变为
两边取对数得到
两边再对求导数,得到
要求最值,那么令导数值为零,即
那么,最终会得到
也就是说,当
时,此时的误判率最低,其对应的最低值为
对于上述中垃圾邮件的例子,其中的值为16亿,的值为1亿,这样计算得到的误判率约为0.046%。也就是说万
分之五都不到,这样在大部分应用中都是可以忍受的。
上面我们解出
即得到
此概率为某一固定的比特位在插入个元素后还未被置为1的概率。所以可以看出,要想布隆过滤器的误判率最低,
那么它的空间使用率需为50%。
那么参数的值应该设置为多少最合适? 针对这个问题,根据上面的过程可以得到
有了这个结论,我们可以根据当前的想要达到指定的误判率来计算需要的比特位。
同样的判断垃圾邮件问题,现在通过传统哈希表的方法和布隆过滤器的方法来进行比较。
(1)传统哈希表方法
传统的哈希表的存储效率最多只有50%,即哈希表半满,由于每个元素占8字节,总空间计算如下
(2)布隆过滤器方法
上面我们说过,要使布隆过滤器的误判率最低,那么它的空间使用率需为50%,取的值为8,因为数据是1亿
条,那么就应该有被置位1,所以总空间计算如下
布隆过滤器