海量数据处理专题(二)——Bloom Filter

【什么是Bloom Filter】

Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,采用Bloom Filter的数据结构,可以通过极少的错误换取了存储空间的极大节省。 这里有一篇关于Bloom Filter的详细介绍,不太懂的博友可以看看。

【适用范围】

可以用来实现数据字典,进行数据的判重,或者集合求交集

【基本原理及要点】

对于原理来说很简单,位数组外加k个独立hash函数。Bloom filter提供两种基本的操作,将元素加入集合和判断某一元素是否属于该集合,一下说明如何操作:

将一个元素加入集合:首先将要加入集合的元素用k个hash函数进行hash,得到k个hash index,然后在集合的位数组中将这k个hash index的位置置1,下面用两幅图来描述这个过程。

bloom filter位数组(集合)的初始状态

bloom filter位数组(集合)的初始状态

插入两个个元素,X1,X2:

bloom-filter-插入元素

bloom-filter-插入元素

查找元素是否属于该集合:首先同样用定义的hash函数对该元素进行hash得到hash index,然后查位数组中对应的hash index是否都是1,如果是,则表明该元素属于该集合,反之不属于【当然不全是了,请继续看后面】,如图,判断元素Y1,Y2是否属于该集合。

bloom-filter-判断元素是否属于集合

bloom-filter-判断元素是否属于集合

如上图,由于y1的三个hash index有一个不为1,因此不属于该集合,而y2所有的hash index的位置上都为1,因此属于该集合。

【Bloom Filter的不足】

很明显上面这个查找过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个counter数组代替位数组,就可以支持删除了。

还有一个比较重要的问题,如何根据输入元素个数n,确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况 下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应 该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。

举个例子我们假设错误率为0.01,则此时m应大概是n的13倍。这样k大概是8个。

注意这里m与n的单位不同,m是bit为单位,而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。

【扩展】

Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter,从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

【问题实例】

给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?

根据这个问题我们来计算下内存的占用,4G=2^32大概是40亿*8大概是340亿,n=50亿,如果按出错率0.01算需要的大概是650亿个bit。 现在可用的是340亿,相差并不多,这样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大大简单了。

做人好厚道,转载请注明出处:http://diducoder.com/mass-data-topic-2-bloom-filter.html

海量数据处理专题(二)——Bloom Filter》上有8条评论

  1. hash函数的选择是很重要的,直接关系到后面要维护的白表大小。哈希函数的选择很多,比如取摸法,MD5,SHA1.。。

  2. 错误率为0.01的话,log(1/0.01) * 1.44好像不等于13吧,我算了下应该是9点几,怎么是13呢?

    • 我算出来的结果跟你的结果一样的,也是9.1怎么可能是13呢?求高人指点啊

  3. Pingback引用通告: 海量数据处理专题(二)——Bloom Filter » NoName

  4. Pingback引用通告: 海量数据处理zz | Faster!Higher!Stronger!

  5. Pingback引用通告: 海量数据处理专题(一)——开篇 | 帝都码农

发表评论

电子邮件地址不会被公开。 必填项已用*标注