文档章节

布隆过滤器

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

精选30+云产品,助力企业轻松上云!>>>

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

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
粉丝 233
博文 527
码字总数 758009
作品 0
成都
架构师
私信 提问
加载中
请先登录后再评论。
Google布隆过滤器与Redis布隆过滤器详解

一、什么是布隆过滤器? 布隆过滤器可以用来判断一个元素是否在一个集合中。它的优势是只需要占用很小的内存空间以及有着高效的查询效率。 对于布隆过滤器而言,它的本质是一个位数组:位数组...

osc_hyhwtzyu
2019/11/25
1
0
Google布隆过滤器与Redis布隆过滤器详解

一、什么是布隆过滤器? 布隆过滤器可以用来判断一个元素是否在一个集合中。它的优势是只需要占用很小的内存空间以及有着高效的查询效率。 对于布隆过滤器而言,它的本质是一个位数组:位数组...

王知无
2019/12/15
16
0
Google布隆过滤器与Redis布隆过滤器详解

一、什么是布隆过滤器? 布隆过滤器可以用来判断一个元素是否在一个集合中。它的优势是只需要占用很小的内存空间以及有着高效的查询效率。 对于布隆过滤器而言,它的本质是一个位数组:位数组...

王知无
2019/11/25
8
0
Redis 中的布隆过滤器

一、什么是『布隆过滤器』 布隆过滤器是一个神奇的数据结构,可以用来判断一个元素是否在一个集合中。很常用的一个功能是用来去重。在爬虫中常见的一个需求:目标网站 URL 千千万,怎么判断某...

IT--小哥
04/20
0
0
Redis中的布隆过滤器及其应用

一、什么是布隆过滤器 布隆过滤器(Bloom Filter)是由Howard Bloom在1970年提出的一种比较巧妙的概率型数据结构,它可以告诉你某种东西一定不存在或者可能存在。当布隆过滤器说,某种东西存...

RainTa
06/02
14
0

没有更多内容

加载失败,请刷新页面

加载更多

跨越了6个阶段,我仍然是生物信息学初学者

首先非常欢迎大家分享自己与生物信息学/生信技能树的故事! 上一期是:我如何从生物科学到生物信息 这一期是我在朋友圈看到了我们单细胞天地常驻编辑周运来的真情流露,邀请他投稿的我们生信...

biotrainee
前天
17
0
网飞是如何运用心理学来完善其客户体验的

原文地址:https://36kr.com/p/5289228 译者:俊一 占据全球网站流量 15%的奈飞,其用户体验设计背后有哪些秘密? 神译局是 36 氪旗下编译团队,关注科技、商业、职场、生活等领域,重点介绍...

高行
02/08
23
0
shell编程中的循环脚本

本文中的部分脚本来源于网络,就不申明原创了,如果这些东西自己学会了,那就是属于自己的了。 求从1加到100的和 使用for循环求和: #!/bin/bash declare -i sum=0 for ((i=1;i<=100;i++));...

Double_冬
2018/08/16
14
0
智能合约:介绍、geth、Ethereum Wallet

从看雪论坛换了一本《智能合约安全分析和审计指南》,看了一些智能合约相关的内容,因为我之前对于区块链的了解仅仅是只知道世界上有一种叫做比特币的东西,所以对于这些概念的理解还是比较困...

yichen115
04/26
9
0
Vue和React技术风格上的不同

在主流框架中,Vue和React都属于全球热门,各自有着大量用户,两者之间的优缺点便带来了众多讨论。 那么这两者之间的关键区别在于哪些方面?为何熟练掌握Vue成为越来越多公司的岗位要求? Vu...

若川
07/02
24
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部