文档章节

布隆过滤器

tantexian
 tantexian
发布于 2017/02/15 00:12
字数 1973
阅读 17
收藏 1
点赞 0
评论 0

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

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
粉丝 191
博文 467
码字总数 717645
作品 0
成都
架构师
布隆过滤器(Bloom Filter)

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

行者PHPer ⋅ 2014/04/12 ⋅ 0

网络爬虫之url等高效率去重原理

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

小湘西 ⋅ 2015/11/12 ⋅ 0

海量数据判重——布隆过滤器(Bloom filter)与Bitmap对比

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

tick_tock97 ⋅ 2017/12/01 ⋅ 0

如何实现大数据集查询?Bloom Filter或许是你想要的

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

流川枫AI ⋅ 2017/06/18 ⋅ 0

HBase列族高级配置

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

八戒_o ⋅ 2016/01/03 ⋅ 0

[转载]HBase列族高级配置

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

2k10 ⋅ 2016/02/03 ⋅ 1

关于布隆过滤器使用的请教

@CrawlScript 你好,想跟你请教个问题: 感谢您的分享,学习了,我有以下的疑问,想看下您布隆过滤器是怎么用的: 针对BreadthCrawler使用2^24的布隆过滤器进行URL管理这个的实现, 这个是在...

364599827 ⋅ 2014/11/29 ⋅ 2

一个简单的布隆过滤器

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都...

alex_wei ⋅ 2013/07/03 ⋅ 0

算法分析:使用布隆过滤器(Bloom Filter)进行大数据量排序

题目大意:移动公司需要对已经发放的所有139段的号码进行统计排序,已经发放的139号码段的文件都存放在一个文本文件中(原题是放在两个文件中),一个号码一行,现在需要将文件里的所有号码进...

苗哥 ⋅ 2014/03/20 ⋅ 3

布隆过滤器实现JAVA

概述 布隆过滤器的作用是加快判定一个元素是否在集合中出现的方法。因为其主要是过滤掉了大部分元素间的精确匹配,故称为过滤器。 其应用场景为需要频繁在一个海量的集合中查找某个元素是否存...

dugangabc ⋅ 2016/04/14 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周日乱弹 —— 这么好的姑娘都不要了啊

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @TigaPile :分享曾惜的单曲《讲真的》 《讲真的》- 曾惜 手机党少年们想听歌,请使劲儿戳(这里) @首席搬砖工程师 :怎样约女孩子出来吃饭,...

小小编辑 ⋅ 22分钟前 ⋅ 1

Jenkins实践3 之脚本

#!/bin/sh# export PROJ_PATH=项目路径# export TOMCAT_PATH=tomcat路径killTomcat(){pid=`ps -ef | grep tomcat | grep java|awk '{print $2}'`echo "tom...

晨猫 ⋅ 今天 ⋅ 0

Spring Bean的生命周期

前言 Spring Bean 的生命周期在整个 Spring 中占有很重要的位置,掌握这些可以加深对 Spring 的理解。 首先看下生命周期图: 再谈生命周期之前有一点需要先明确: Spring 只帮我们管理单例模...

素雷 ⋅ 今天 ⋅ 0

zblog2.3版本的asp系统是否可以超越卢松松博客的流量[图]

最近访问zblog官网,发现zlbog-asp2.3版本已经进入测试阶段了,虽然正式版还没有发布,想必也不久了。那么作为aps纵横江湖十多年的今天,blog2.2版本应该已经成熟了,为什么还要发布这个2.3...

原创小博客 ⋅ 今天 ⋅ 0

聊聊spring cloud的HystrixCircuitBreakerConfiguration

序 本文主要研究一下spring cloud的HystrixCircuitBreakerConfiguration HystrixCircuitBreakerConfiguration spring-cloud-netflix-core-2.0.0.RELEASE-sources.jar!/org/springframework/......

go4it ⋅ 今天 ⋅ 0

二分查找

二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于...

人觉非常君 ⋅ 今天 ⋅ 0

VS中使用X64汇编

需要注意的是,在X86项目中,可以使用__asm{}来嵌入汇编代码,但是在X64项目中,再也不能使用__asm{}来编写嵌入式汇编程序了,必须使用专门的.asm汇编文件来编写相应的汇编代码,然后在其它地...

simpower ⋅ 今天 ⋅ 0

ThreadPoolExecutor

ThreadPoolExecutor public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, ......

4rnold ⋅ 昨天 ⋅ 0

Java正无穷大、负无穷大以及NaN

问题来源:用Java代码写了一个计算公式,包含除法和对数和取反,在页面上出现了-infinity,不知道这是什么问题,网上找答案才明白意思是负的无穷大。 思考:为什么会出现这种情况呢?这是哪里...

young_chen ⋅ 昨天 ⋅ 0

前台对中文编码,后台解码

前台:encodeURI(sbzt) 后台:String param = URLDecoder.decode(sbzt,"UTF-8");

west_coast ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部