Bloom Filter 算法

发布于: 13 小时前

Bloom filter是由Burton Bloom 在1970年提出的,其后在P2P上得到了广泛的应用。Bloom filter 算法可用来查询某一数据是否在某一数据集合中。其优点是查询效率高、可节省空间,但其缺点是会存在一定的错误。因此Bloom filter 算法只能应用于那些允许有一定错误的场合。可使用Bloom filter 算法的场合包括字典软件、分布式缓存、P2P网络和资源路由等等。

使用Bloom Filter我们可以判断一个元素是否在某一个集合中。如果这个集合是使用线性结构存储的话,其查找的时间复杂度是O(N);使用像二叉树或B-tree这样的树形结构存储的话其查找的时间复杂度是O(logN);而使用Bloom Filter在可以容忍一定错误率的情况下,其时间复杂度是O(1)。因此,与传统的权衡空间或时间的算法不同,Bloom Filter 极其巧妙,通过引入一定的错误率来换取时间和空间,在某些应用大大提高了性能。

Bloom Filter 算法应用

使用Bloom Filter算法查找某个元素是否属于某个集合是常数时间,并且Bloom Filter使用的是位数组,大大减少了空间。虽然有一定的错误率,但对于那些允许有一定错误的场合则十分有效。

使用Bloom Filter还可以进行垃圾邮件过滤。由于垃圾邮件的数量是非常巨大的,如果将所有的垃圾邮件的地址都存到数据库再进行垃圾邮件过滤,则其性能会非常低下。此时如果通过垃圾邮件的地址创建Bloom Filter,并把Bloom Filter的位数组放到内存中,那么在进行垃圾邮件过滤时就非常高效了。

在HTTP缓存服务器中,可以使用Bloom Filter来加快判断Url是否在代理服务器的缓存中。在代理服务器中,首先用缓存页面的URL通过哈希算法创建一个Bloom Filter的位数组。如果有多个代理服务器,还可以将自己的位数组传送给其他代理服务器,以加快缓存查询速度。当有HTTP请求来时,就先在代理服务器中查看是否有此Url的缓存,如果没有,则查看是否在其它代理服务器中,再没有的话才会去主服务器提取页面。可以看出,使用Bloom Filter查询某URL是否在缓存中非常快,如果出现错误的情况则最多到主服务器提取页面。而且由于Bloom Filter大大减少了空间的使用,使其在网络上传输更加快速。

在Web爬虫中,也可使用Bloom Filter。当Web爬虫处理了一个页面时,首先会通过Bloom Filter判断这个页面是否已经处理过,如果没处理过就对其进行处理并将其加到Bloom Filter中。在web爬虫如果出现误判,则最多对同一个URL多处理几次,并不影响web爬虫的性能。通过Bloom Filter反而大大提高了Web爬虫的性能。

总而言之,Bloom Filter近些年来得到了广泛的应用,通过使用Bloom Filter可以加快对海量数据的查询,提高应用的性能。

Bloom Filter算法思想

Bloom Filter算法就是对于有n个元素的集合S={x1, x2,……,xn},我们用k个哈希函数(h1,h2,……,hk),分别将S中的每个元素映射到一个m位的位数组中。该位数组在初始化时全部置为0,每当用哈希函数映射到该位时则将该位置为1,对于已经置为1的位则不在重复置1。

例如,将S={x1,x2,x3}这个集合用3个哈希函数映射到一个14位的位数组中,如图所示:

可以看出,如果要查找一个元素是否在这个集合中,则只要将该元素进行k次哈希,如果其对应的位全部为1的话则说明该元素在这个集合中。否则,只要有其中一位为0,则说明该元素不在这个集合中。如图所示,x2在集合中,而x4不在集合中。

Bloom Filter会产生错误也就是因为对某个元素进行k次哈希后对应的位全部为1,因此错误地将这个元素判定为在这个集合中,但实际上这个元素并不在这个集合中。如图所示,x5实际并不是这个集合的元素:

要将一个元素加入这个集合很容易,只要将这个元素进行k次哈希后将对应的位置1就行了。但如果要从这个集合中删除一个元素,那么使用上面的位数组就不行了。因为如果只是简单地将k次哈希后对应的位置0,而其它在这个集合中的元素也可能会映射到该位,这样这个集合就出错了。因此,对于要进行删除的情况,则应该使用Bloom Filter的变体算法:计数Bloom Filter。计数Bloom Filter位数组的每个元素并不是只有1位,而可能是2位或更多位(视情况而定)。如图就是使用2位位数组的例子:

在这种情况下,如果要删除一个元素,则只要将对应位的计数减1就行了。删除了x2之后如图所示:

发布于: 13 小时前 阅读数: 7
用户头像

Chank

关注

还未添加个人签名 2019.02.06 加入

邮箱:fangliquan@qq.com

评论

发布
暂无评论
Bloom Filter算法