文档章节

布隆过滤器

tantexian
 tantexian
发布于 2017/02/15 00:12
字数 1973
阅读 22
收藏 1

本文主要参引了以下两篇文章,在此作出特别说明:

http://www.cnblogs.com/haippy/archive/2012/07/13/2590351.html

http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html

1.什么是布隆过滤器

布隆过滤器[1](Bloom Filter)是由布隆(Burton Howard Bloom)在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成,布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率(假正例False positives,即Bloom Filter报告某一元素存在于某集合中,但是实际上该元素并不在集合中)和删除困难,但是没有识别错误的情形(即假反例False negatives,如果某个元素确实没有在该集合中,那么Bloom Filter 是不会报告该元素存在于集合中的,所以不会漏报)。布隆过滤器的原理图如下:

2.布隆过滤器相关算法描述

 

一个empty bloom filter是一个有m bits的bit array,每一个bit位都初始化为0。并且定义有k个不同的hash function,每个都以uniform random distribution将元素hash到m个不同位置中的一个。在下面的介绍中n为元素数,m为布隆过滤器或哈希表的slot数,k为布隆过滤器重hash function数。

 

为了add一个元素,用k个hash function将它hash得到bloom filter中k个bit位,将这k个bit位置1。

 

为了query一个元素,即判断它是否在集合中,用k个hash function将它hash得到k个bit位。若这k bits全为1,则此元素在集合中;若其中任一位不为1,则此元素比不在集合中(因为如果在,则在add时已经把对应的k个bits位置为1)。

 

不允许remove元素,因为那样的话会把相应的k个bits位置为0,而其中很有可能有其他元素对应的位。因此remove会引入false negative,这是绝对不被允许的。

 

当k很大时,设计k个独立的hash function是不现实并且困难的。对于一个输出范围很大的hash function(例如MD5产生的128 bits数),如果不同bit位的相关性很小,则可把此输出分割为k份。或者可将k个不同的初始值(例如0,1,2, … ,k-1)结合元素,feed给一个hash function从而产生k个不同的数。

 

当add的元素过多时,即n/m过大时(n是元素数,m是bloom filter的bits数),会导致false positive过高,此时就需要重新组建filter,但这种情况相对少见。

3.应用领域举例

 

Google 著名的分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列,以减少磁盘查找的IO次数[3]。

Squid 网页代理缓存服务器在 cache digests 中使用了也布隆过滤器[4]。

Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据[5]。

SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间[6]。

Google Chrome浏览器使用了布隆过滤器加速安全浏览服务[7]。

上图一个典型的用例,在很多Key-Value系统中也使用了布隆过滤器来加快查询过程,如 Hbase,Accumulo,Leveldb,一般而言,Value 保存在磁盘中,访问磁盘需要花费大量时间,然而使用布隆过滤器可以快速判断某个Key对应的Value是否存在,因此可以避免很多不必要的磁盘IO操作,只是引入布隆过滤器会带来一定的内存消耗.

4.布隆过滤器相关推导

 

以垃圾邮件过滤中黑白名单为例:现有1亿个email的黑名单,每个都拥有8 bytes的指纹信息,则可能的元素范围为  clip_image002 ,对于bit array来说是根本不可能的范围,而且元素的数量(即email列表)为 clip_image002[6] ,相比于元素范围过于稀疏,而且还没有考虑到哈希表中的collision问题。

 

若采用哈希表,由于大多数采用open addressing来解决collision,而此时的search时间复杂度为 :

clip_image002[8]

即若哈希表半满(n/m = 1/2),则每次search需要probe 2次,因此在保证效率的情况下哈希表的存储效率最好不超过50%。此时每个元素占8 bytes,总空间为:

clip_image002[10]

若采用Perfect hashing(这里可以采用Perfect hashing是因为主要操作是search/query,而并不是add和remove),虽然保证worst-case也只有一次probe,但是空间利用率更低,一般情况下为50%,worst-case时有不到一半的概率为25%。

 

若采用布隆过滤器,取k=8。因为n为1亿,所以总共需要 clip_image002[12] 被置位为1,又因为在保证误判率低且k和m选取合适时,空间利用率为50%(后面会解释),所以总空间为:

clip_image002[14]

所需空间比上述哈希结构小得多,并且误判率在万分之一以下。

(PS:具体的推导过程请参见原文...)

http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html

5.布隆过滤器的优势

 

当可以承受一些误报时,布隆过滤器比其它表示集合的数据结构有着很大的空间优势。例如self-balance BST, tries, hash table或者array, chain,它们中大多数至少都要存储元素本身,对于小整数需要少量的bits,对于字符串则需要任意多的bits(tries是个例外,因为对于有相同prefixes的元素可以共享存储空间);而chain结构还需要为存储指针付出额外的代价。对于一个有1%误报率和一个最优k值的布隆过滤器来说,无论元素的类型及大小,每个元素只需要9.6 bits来存储。这个优点一部分继承自array的紧凑性,一部分来源于它的概率性。如果你认为1%的误报率太高,那么对每个元素每增加4.8 bits,我们就可将误报率降低为原来的1/10。add和query的时间复杂度都为O(k),与集合中元素的多少无关,这是其他数据结构都不能完成的。

 

如果可能元素范围不是很大,并且大多数都在集合中,则使用确定性的bit array远远胜过使用布隆过滤器。因为bit array对于每个可能的元素空间上只需要1 bit,add和query的时间复杂度只有O(1)。注意到这样一个哈希表(bit array)只有在忽略collision并且只存储元素是否在其中的二进制信息时,才会获得空间和时间上的优势,而在此情况下,它就有效地称为了k=1的布隆过滤器。

 

而当考虑到collision时,对于有m个slot的bit array或者其他哈希表(即k=1的布隆过滤器),如果想要保证1%的误判率,则这个bit array只能存储m/100个元素,因而有大量的空间被浪费,同时也会使得空间复杂度急剧上升,这显然不是space efficient的。解决的方法很简单,使用k>1的布隆过滤器,即k个hash function将每个元素改为对应于k个bits,因为误判度会降低很多,并且如果参数k和m选取得好,一半的m可被置为为1,这充分说明了布隆过滤器的space efficient性。

© 著作权归作者所有

共有 人打赏支持
tantexian
粉丝 207
博文 513
码字总数 733413
作品 0
成都
架构师
私信 提问
Google Guava 中的布隆过滤

在 Guava 项目的11.0版中,一个新的类添加了进来—— BloomFilter(布隆过滤器)类。布隆过滤器是一种独特的数据结构,用以表明元素是否被保存在一个集合(Set)中。有趣的是,布隆过滤器能够...

可观
2013/01/25
6.1K
1
详解布隆过滤器的原理、使用场景和注意事项

今天碰到个业务,他的 Redis 集群有个大 Value 用途是作为布隆过滤器,但沟通的时候被小怼了一下,意思大概是 “布隆过滤器原理都不懂,还要我优化?”。技术菜被人怼认了、怪不得别人,自己...

YoungChen__
08/30
0
0
网络爬虫之url等高效率去重原理

布隆过滤器用于字符串去重复,比如网络爬虫抓取时URL去重、邮件提供商反垃圾黑名单Email地址去重。等等。用哈希表也可以用于元素去重,但是占用空间比较大,而且空间使用率只有50%。   布隆...

小湘西
2015/11/12
0
0
布隆过滤器(Bloom Filter)

基本概念 如果想判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合...

行者PHPer
2014/04/12
0
0
海量数据判重——布隆过滤器(Bloom filter)与Bitmap对比

前言 之前写过一篇Bitmap在海量整数排序中应用的博客,在看过布隆过滤器之后,感觉两个有些相似,但是又有区别,在查阅了很多资料之后,这里决定稍作总结。 关于布隆过滤器(Bloom filter)的...

tick_tock97
2017/12/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

easyui tree

<tr> <th><spring:message code="wf.borrow.examiner"/></th> <td> <input id="inp-examiner1" type="text" name="examiner1" style="width:197px;height:20px;" data-options="required:tru......

小兵胖胖
15分钟前
1
0
内存性能的正确解读

一台服务器,不管是物理机还是虚拟机,必不可少的就是内存,内存的性能又是如何来衡量呢。 1. 内存与缓存 现在比较新的CPU一般都有三级缓存,L1 Cache(32KB-256KB),L2 Cache(128KB-2MB)...

阿里云云栖社区
18分钟前
1
0
微服务架构:Zuul 1.0 和 2.0 我们该如何选择?

在今年5月中,Netflix终于开源了它的支持异步调用模式的Zuul网关2.0版本,真可谓千呼万唤始出来。从Netflix的官方博文[附录1]中,我们获得的信息也比较令人振奋: The Cloud Gateway team a...

大木老师故事的小黄花
18分钟前
1
0
基础掌握

哪些是基础功呢?我觉得包括: 数据结构和算法:链表、队列、栈、堆、树(RBT, B/B+)、跳表、哈希、图;查找(二分、bst)、排序(冒泡、插入、快排、归并、堆排、希尔)、递归、归并、回溯、...

边鹏_尛爺鑫
20分钟前
1
0
Android APP的安装路径

一. Android应用安装路径有两种情况: system/app 系统自带的应用程序,无法删除。root后可以删除,注意可能造成系统崩溃,不过有的垃圾捆绑软件只能这么删除了 data/app 用户程序安装的目录,...

天王盖地虎626
23分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部