文档章节

布隆过滤器

tantexian
 tantexian
发布于 2017/02/15 00:12
字数 1973
阅读 20
收藏 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
粉丝 198
博文 491
码字总数 721387
作品 0
成都
架构师
布隆过滤器(Bloom Filter)

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

行者PHPer
2014/04/12
0
0
网络爬虫之url等高效率去重原理

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

小湘西
2015/11/12
0
0
海量数据判重——布隆过滤器(Bloom filter)与Bitmap对比

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

tick_tock97
2017/12/01
0
0
如何实现大数据集查询?Bloom Filter或许是你想要的

1、什么情况下需要布隆过滤器? 先来看几个比较常见的例子 字处理软件中,需要检查一个英语单词是否拼写正确 在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上 在网络爬虫里,一个网址是否被访...

流川枫AI
2017/06/18
0
0
HBase列族高级配置

HBase有几个高级特性,在你设计表时可以使用。这些特性不一定联系到模式或行键设计,但是它们定义了某些方面的表行为。本节我们讨论这些配置参数,以及你可以如何使用它们。 1 可配置的数据块...

八戒_o
2016/01/03
143
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java IO类库之PrintStreamWriter

* A <code>PrintStream</code> adds functionality to another output stream, * namely the ability to print representations of various data values * conveniently. Two other fea......

老韭菜
54分钟前
0
0
qduoj~前端~二次开发~笔记

青岛大学qdu的onlinejudge是js的写的前端,框架是vue.js,在nodejs上部署运行,其实整体运行还是建立在docker的容器虚拟环境里,这里暂时不需要docker。安装环境是Ubuntu14-64bit 1.安装一大...

虚拟世界的懒猫
58分钟前
6
0
ConcurrentHashMap源码解读

部分内容转自:http://jiabinyuan.xyz/#/app/archive/detail/25 内部结构 内部采用了segment结构,每一个segment相当于一个hashtable。看下面的结构图: 从图的结构我们可以了解到,Concurr...

edwardGe
今天
1
0
Ubuntu终端Tab键自动补全

打开 /etc/bash.bashrc,找到下列代码,取消注释。 #enable bash completion in interactive shells#if ! shopt -oq posix; then# if [-f /usr/share/bash-completion/bash_compl......

大熊猫
今天
0
0
polipo socks5代理转http代理

天朝的网络,哎~ 装个 yarn 都时而会卡 假设在SSlocal 已经装好运行的前提下,来安装设置 polipo sudo apt-get install polipo sudo vim /etc/polipo/config 追加下列配置内容,并保存 socksP...

纯洁徐
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部