首页 > C/C++ > Bloom Filter算法简介

Bloom Filter算法简介

Bloom Filter的中文翻译叫做布隆过滤器,是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。如文章标题所述,本文只是做简单介绍,属于科普文章。

一、应用场景
在正式介绍Bloom Filter算法之前,先来看看什么时候需要用到Bloom Filter算法。
1. HTTP缓存服务器、Web爬虫等
主要工作是判断一条URL是否在现有的URL集合之中(可以认为这里的数据量级上亿)。
对于HTTP缓存服务器,当本地局域网中的PC发起一条HTTP请求时,缓存服务器会先查看一下这个URL是否已经存在于缓存之中,如果存在的话就没有必要去原始的服务器拉取数据了(为了简单起见,我们假设数据没有发生变化),这样既能节省流量,还能加快访问速度,以提高用户体验。
对于Web爬虫,要判断当前正在处理的网页是否已经处理过了,同样需要当前URL是否存在于已经处理过的URL列表之中。

2. 垃圾邮件过滤
假设邮件服务器通过发送方的邮件域或者IP地址对垃圾邮件进行过滤,那么就需要判断当前的邮件域或者IP地址是否处于黑名单之中。如果邮件服务器的通信邮件数量非常大(也可以认为数据量级上亿),那么也可以使用Bloom Filter算法。

二、几个专业术语
这里有必要介绍一下False Positive和False Negative的概念(更形象的描述可以阅读第4条参考)。
False Positive中文可以理解为“假阳性”,形象的一点说就是“误报”,后面将会说道Bloom Filter存在误报的情况,现实生活中也有误报,比如说去体检的时候,医生告诉你XXX检测是阳性,而实际上是阴性,也就是说误报了,是假阳性,杀毒软件误报也是同样的概念。
False Negative,中文可以理解为“假阴性”,形象的一点说是“漏报”。医生告诉你XXX检测为阴性,实际上你是阳性,你是有病的(Sorry, it’s just a joke),那就是漏报了。同样杀毒软件也存在漏报的情况。

三、Bloom Filter算法
好了,终于要正式介绍Bloom Filter算法了。
初始状态下,Bloom Filter是一个m位的位数组,且数组被0所填充。同时,我们需要定义k个不同的hash函数,每一个hash函数都随机的将每一个输入元素映射到位数组中的一个位上。那么对于一个确定的输入,我们会得到k个索引。

插入元素:经过k个hash函数的映射,我们会得到k个索引,我们把位数组中这k个位置全部置1(不管其中的位之前是0还是1)

查询元素:输入元素经过k个hash函数的映射会得到k个索引,如果位数组中这k个索引任意一处是0,那么就说明这个元素不在集合之中;如果元素处于集合之中,那么当插入元素的时候这k个位都是1。但如果这k个索引处的位都是1,被查询的元素就一定在集合之中吗?答案是不一定,也就是说出现了False Positive的情况(但Bloom Filter不会出现False Negative的情况)
Bloom filter算法false positive
在上图中,当插入x、y、z这三个元素之后,再来查询w,会发现w不在集合之中,而如果w经过三个hash函数计算得出的结果所得索引处的位全是1,那么Bloom Filter就会告诉你,w在集合之中,实际上这里是误报,w并不在集合之中。

四、Bloom Filter算法的False Positive Rate
Bloom Filter的误报率到底有多大?下面在数学上进行一番推敲。假设HASH函数输出的索引值落在m位的数组上的每一位上都是等可能的。那么,对于一个给定的HASH函数,在进行某一个运算的时候,一个特定的位没有被设置为1的概率是
bloom filter pr1
那么,对于所有的k个HASH函数,都没有把这个位设置为1的概率是
bloom filter pr2
如果我们已经插入了n个元素,那么对于一个给定的位,这个位仍然是0的概率是
bloom filter pr3
那么,如果插入n个元素之后,这个位是1的概率是
bloom filter pr4
如果对一个特定的元素存在误报,那么这个元素的经过HASH函数所得到的k个索引全部都是1,概率也就是
bloom filter pr5
根据常数e的定义,可以近似的表示为:
bloom filter pr6

五、关于误报
有时候误报对实际操作并不会带来太大的影响,比如对于HTTP缓存服务器,如果一条URL被误以为存在与缓存服务器之中,那么当取数据的时候自然会无法取到,最终还是要从原始服务器当中获取,之后再把记录插入缓存服务器,几乎没有什么不可以接受的。
对于安全软件,有着“另可错报,不可误报”的说法,如果你把一个正常软件误判为病毒,对使用者来说不会有什么影响(如果用户相信是病毒,那么就是删除这个文件罢了,如果用户执意要执行,那么后果也只能由用户来承担);如果你把一个病毒漏判了,那么对用户造成的后果是不可设想的……更有甚者,误报在某种程度上能让部分用户觉得你很专业……

六、参考文档
1. 布隆过滤器 http://zh.wikipedia.org/wiki/Bloom_filter
2. Bloom filter http://en.wikipedia.org/wiki/Bloom_filter
3. Bloom Filter算法 http://www.cnblogs.com/yuyijq/archive/2012/02/08/2343374.html
4. 什么是False Positive和False Negative http://simon.blog.51cto.com/80/73395/


觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> Bloom Filter算法简介
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 2012年10月16日07:39 | #1

    关键是这些技术在我们所看到的哪些产品中应用到呢?

    技术只有商业化才能体现其价值。。

    [回复]

    代码疯子 回复:

    @TekTea, 上面都举了例子,缓存服务器、垃圾邮件判断等。在谷歌黑板报上,吴军的数学之美就有介绍。
    http://www.google.com.hk/ggblog/googlechinablog/2007/07/bloom-filter_7469.html
    很多东西你就在用,但你并不一定知道背后的实现。
    算法改变计算机科学,呵呵

    [回复]

  2. 2012年11月1日19:09 | #2

    为啥不可能出现false negative?

    [回复]

    代码疯子 回复:

    @tanglei, 一定不会漏报。一个元素经过k个HASH函数之后,映射到的k个位都是1啊。如果一个元素确定存在,那么去检查这个元素存在的时候检查对应的k个位是不是全部都是1. 既然存在,肯定都是1,所以不会漏报

    [回复]

    timcho 回复:

    @tanglei, 换句话说,数组的值不会被赋予0,那么也就不会存在这样的case:一个元素经过HASH之后,所映射的那K个位被设定为1,不会有其他的情况将这K个位中的某一位改成0,下一次这个元素来检查的时候,这些位还是1.

    [回复]

    代码疯子 回复:

    @timcho, [em022] 正解

    [回复]

  1. 2012年10月14日18:37 | #1