首页 > 代码库 > 布隆过滤器

布隆过滤器

通常,我们需要判断一个元素是否在一个集合中。比如在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,所以总空间计算如下

 

   

 

 

 

布隆过滤器