布隆过滤器的概述及Python实现方法

布隆过滤器

布隆过滤器是一种概率空间高效的数据结构。它与hashmap非常相似,用于检索一个元素是否在一个集合中。它在检索元素是否存在时,能很好地取舍空间使用率与误报比例。正是由于这个特性,它被称作概率性数据结构(probabilistic data structure)。

空间效率

我们来仔细地看看它的空间效率。如果你想在集合中存储一系列的元素,有很多种不同的做法。你可以把数据存储在hashmap,随后在hashmap中检索元素是否存在,hashmap的插入和查询的效率都非常高。但是,由于hashmap直接存储内容,所以空间利用率并不高。

如果希望提高空间利用率,我们可以在元素插入集合之前做一次哈希变换。还有其它方法呢?我们可以用位数组来存储元素的哈希值。还有吗,还有吗?我们也允许在位数组中存在哈希冲突。这正是布隆过滤器的工作原理,它们就是基于允许哈希冲突的位数组,可能会造成一些误报。在布隆过滤器的设计阶段就允许哈希冲突的存在,否则空间使用就不够紧凑了。

当使用列表或者集合时,空间效率都是重要且显著的,那么布隆过滤器就应当被考虑。

布隆过滤器基础

布隆过滤器是N位的位数组,其中N是位数组的大小。它还有另一个参数k,表示使用哈希函数的个数。这些哈希函数用来设置位数组的值。当往过滤器中插入元素x时,h1(x), h2(x), ..., hk(x)所对应索引位置的值被置“1”,索引值由各个哈希函数计算得到。注意,如果我们增加哈希函数的数量,误报的概率会趋近于0.但是,插入和查找的时间开销更大,布隆过滤器的容量也会减小。

为了用布隆过滤器检验元素是否存在,我们需要校验是否所有的位置都被置“1”,与我们插入元素的过程非常相似。如果所有位置都被置“1”,那也就意味着该元素很有可能存在于布隆过滤器中。若有位置未被置“1”,那该元素一定不存在。

单的python实现

如果想实现一个简单的布隆过滤器,我们可以这样做:

from bitarray import bitarray
# 3rd party
import mmh3
class BloomFilter(set):
 def __init__(self, size, hash_count):
  super(BloomFilter, self).__init__()
  self.bit_array = bitarray(size)
  self.bit_array.setall(0)
  self.size = size
  self.hash_count = hash_count
 def __len__(self):
  return self.size
 def __iter__(self):
  return iter(self.bit_array)
 def add(self, item):
  for ii in range(self.hash_count):
   index = mmh3.hash(item, ii) % self.size
   self.bit_array[index] = 1
  return self
 def __contains__(self, item):
  out = True
  for ii in range(self.hash_count):
   index = mmh3.hash(item, ii) % self.size
   if self.bit_array[index] == 0:
    out = False
  return out
def main():
 bloom = BloomFilter(100, 10)
 animals = ['dog', 'cat', 'giraffe', 'fly', 'mosquito', 'horse', 'eagle',
    'bird', 'bison', 'boar', 'butterfly', 'ant', 'anaconda', 'bear',
    'chicken', 'dolphin', 'donkey', 'crow', 'crocodile']
 # First insertion of animals into the bloom filter
 for animal in animals:
  bloom.add(animal)
 # Membership existence for already inserted animals
 # There should not be any false negatives
 for animal in animals:
  if animal in bloom:
   print('{} is in bloom filter as expected'.format(animal))
  else:
   print('Something is terribly went wrong for {}'.format(animal))
   print('FALSE NEGATIVE!')
 # Membership existence for not inserted animals
 # There could be false positives
 other_animals = ['badger', 'cow', 'pig', 'sheep', 'bee', 'wolf', 'fox',
      'whale', 'shark', 'fish', 'turkey', 'duck', 'dove',
      'deer', 'elephant', 'frog', 'falcon', 'goat', 'gorilla',
      'hawk' ]
 for other_animal in other_animals:
  if other_animal in bloom:
   print('{} is not in the bloom, but a false positive'.format(other_animal))
  else:
   print('{} is not in the bloom filter as expected'.format(other_animal))
if __name__ == '__main__':
 main()
 

输出结果如下所示:

dog is in bloom filter as expected
cat is in bloom filter as expected
giraffe is in bloom filter as expected
fly is in bloom filter as expected
mosquito is in bloom filter as expected
horse is in bloom filter as expected
eagle is in bloom filter as expected
bird is in bloom filter as expected
bison is in bloom filter as expected
boar is in bloom filter as expected
butterfly is in bloom filter as expected
ant is in bloom filter as expected
anaconda is in bloom filter as expected
bear is in bloom filter as expected
chicken is in bloom filter as expected
dolphin is in bloom filter as expected
donkey is in bloom filter as expected
crow is in bloom filter as expected
crocodile is in bloom filter as expected

badger is not in the bloom filter as expected
cow is not in the bloom filter as expected
pig is not in the bloom filter as expected
sheep is not in the bloom, but a false positive
bee is not in the bloom filter as expected
wolf is not in the bloom filter as expected
fox is not in the bloom filter as expected
whale is not in the bloom filter as expected
shark is not in the bloom, but a false positive
fish is not in the bloom, but a false positive
turkey is not in the bloom filter as expected
duck is not in the bloom filter as expected
dove is not in the bloom误报 filter as expected
deer is not in the bloom filter as expected
elephant is not in the bloom, but a false positive
frog is not in the bloom filter as expected
falcon is not in the bloom filter as expected
goat is not in the bloom filter as expected
gorilla is not in the bloom filter as expected
hawk is not in the bloom filter as expected

从输出结果可以发现,存在不少误报样本,但是并不存在假阴性。

不同于这段布隆过滤器的实现代码,其它语言的多个实现版本并不提供哈希函数的参数。这是因为在实际应用中误报比例这个指标比哈希函数更重要,用户可以根据误报比例的需求来调整哈希函数的个数。通常来说,sizeerror_rate是布隆过滤器的真正误报比例。如果你在初始化阶段减小了error_rate,它们会调整哈希函数的数量。

误报

布隆过滤器能够拍着胸脯说某个元素“肯定不存在”,但是对于一些元素它们会说“可能存在”。针对不同的应用场景,这有可能会是一个巨大的缺陷,亦或是无关紧要的问题。如果在检索元素是否存在时不介意引入误报情况,那么你就应当考虑用布隆过滤器。

另外,如果随意地减小了误报比率,哈希函数的数量相应地就要增加,在插入和查询时的延时也会相应地增加。本节的另一个要点是,如果哈希函数是相互独立的,并且输入元素在空间中均匀的分布,那么理论上真实误报率就不会超过理论值。否则,由于哈希函数的相关性和更频繁的哈希冲突,布隆过滤器的真实误报比例会高于理论值。

在使用布隆过滤器时,需要考虑误报的潜在影响。

确定性

当你使用相同大小和数量的哈希函数时,某个元素通过布隆过滤器得到的是正反馈还是负反馈的结果是确定的。对于某个元素x,如果它现在可能存在,那五分钟之后、一小时之后、一天之后、甚至一周之后的状态都是可能存在。当我得知这一特性时有一点点惊讶。因为布隆过滤器是概率性的,那其结果显然应该存在某种随机因素,难道不是吗?确实不是。它的概率性体现在我们无法判断究竟哪些元素的状态是可能存在

换句话说,过滤器一旦做出可能存在的结论后,结论不会发生变化。

缺点

布隆过滤器并不十全十美。

布隆过滤器的容量

布隆过滤器需要事先知道将要插入的元素个数。如果你并不知道或者很难估计元素的个数,情况就不太好。你也可以随机指定一个很大的容量,但这样就会浪费许多存储空间,存储空间却是我们试图优化的首要任务,也是选择使用布隆过滤器的原因之一。一种解决方案是创建一个能够动态适应数据量的布隆过滤器,但是在某些应用场景下这个方案无效。有一种可扩展布隆过滤器,它能够调整容量来适应不同数量的元素。它能弥补一部分短板。

布隆过滤器的构造和检索

在使用布隆过滤器时,我们不仅要接受少量的误报率,还要接受速度方面的额外时间开销。相比于hashmap,对元素做哈希映射和构建布隆过滤器时必然存在一些额外的时间开销。

无法返回元素本身

布隆过滤器并不会保存插入元素的内容,只能检索某个元素是否存在,因为存在哈希函数和哈希冲突我们无法得到完整的元素列表。这是它相对于其它数据结构的最显著优势,空间的使用率也造成了这块短板。

删除某个元素

想从布隆过滤器中删除某个元素可不是一件容易的事情,你无法撤回某次插入操作,因为不同项目的哈希结果可以被索引在同一位置。如果想撤消插入,你只能记录每个索引位置被置位的次数,或是重新创建一次。两种方法都有额外的开销。基于不同的应用场景,若要删除一些元素,我们更倾向于重建布隆过滤器。

在不同语言中的实现

在产品中,你肯定不想自己去实现布隆过滤器。有两个原因,其中之一是选择好的哈希函数和实现方法能有效改善错误率的分布。其次,它需要通过实战测试,错误率和容量大小都要经得起实战检验。各种语言都有开源实现的版本,以我自己的经验,下面的Node.js和Python版本实现非常好用:

NodePython

还有更快版本的pybloomfilter(插入和检索速度都比上面的python库快10倍),但它需要运行在PyPy环境下,并不支持Python3。

总结

以上所述是小编给大家介绍的布隆过滤器的概述及Python实现方法,希望对大家有所帮助,如果大家有任何疑问欢迎给我留言,小编会及时回复大家的!

(0)

相关推荐

  • Python+Redis实现布隆过滤器

    布隆过滤器是什么 布隆过滤器(Bloom Filter)是1970年由布隆提出的.它实际上是一个很长的二进制向量和一系列随机映射函数.布隆过滤器可以用于检索一个元素是否在一个集合中.它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难. 布隆过滤器的基本思想 通过一种叫作散列表(又叫哈希表,Hash table)的数据结构.它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit array)中的一个点.这样一来,我们只要看看这个点是不是1就可以知道集合中有没

  • python实现布隆过滤器及原理解析

    在学习redis过程中提到一个缓存击穿的问题, 书中参考的解决方案之一是使用布隆过滤器, 那么就有必要来了解一下什么是布隆过滤器.在参考了许多博客之后, 写个总结记录一下. 一.布隆过滤器简介 什么是布隆过滤器? 本质上布隆过滤器( BloomFilter )是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 "某样东西一定不存在或者可能存在". 相比于传统的 Set.Map 等数据结构,它更高效

  • 布隆过滤器的概述及Python实现方法

    布隆过滤器 布隆过滤器是一种概率空间高效的数据结构.它与hashmap非常相似,用于检索一个元素是否在一个集合中.它在检索元素是否存在时,能很好地取舍空间使用率与误报比例.正是由于这个特性,它被称作概率性数据结构(probabilistic data structure). 空间效率 我们来仔细地看看它的空间效率.如果你想在集合中存储一系列的元素,有很多种不同的做法.你可以把数据存储在hashmap,随后在hashmap中检索元素是否存在,hashmap的插入和查询的效率都非常高.但是,由于ha

  • 布隆过滤器(Bloom Filter)的Java实现方法

    布隆过滤器原理很简单:就是把一个字符串哈希成一个整数key,然后选取一个很长的比特序列,开始都是0,在key把此位置的0变为1:下次进来一个字符串,哈希之后的值key,如果在此比特位上的值也是1,那么就说明这个字符串存在了. 如果按照上面的做法,那就和哈希算法没有什么区别了,哈希算法还有重复的呢. 布隆过滤器是将一个字符串哈希成多个key,我还是按照书上的说吧. 先建立一个16亿二进制常量,然后将这16亿个二进制位全部置0.对于每个字符串,用8个不同的随机产生器(F1,F2,.....,F8)产

  • 浅析python实现布隆过滤器及Redis中的缓存穿透原理

    目录 布隆过滤器的原理 在 Python 中使用布隆过滤器 1.标准布隆过滤器. 2.计数布隆过滤器. 3.标准扩容布隆过滤器. 4.计数扩容布隆过滤器. Redis 中使用布隆过滤器 最后的话 在开发软件时,我们经常需要判断一个元素是否在一个集合中,比如,如何判断单词的拼写是否错误(判断单词是否在已知的字典中):在网络爬虫里,如何确认一个网址是否已经爬取过:反垃圾邮件系统中,如何判断一个邮件地址是否为垃圾邮件地址等等. 如果这些作为面试题那就很有区分度了,初级工程师就会说,把全部的元素都存在

  • Java实现布隆过滤器的方法步骤

    前言 记得前段时间的文章么?redis使用位图法记录在线用户的状态,还是需要自己实现一个IM在线用户状态的记录,今天来讲讲另一方案,布隆过滤器 布隆过滤器的作用是加快判定一个元素是否在集合中出现的方法.因为其主要是过滤掉了大部分元素间的精确匹配,故称为过滤器. 布隆过滤器 在日常生活工作,我们会经常遇到这的场景,从一个Excel里面检索一个信息在不在Excel表中,还记得被CTRL+F支配的恐惧么,不扯了,软件开发中,一般会使用散列表来实现,Hash Table也叫哈希表,哈希表的优点是快速准确

  • Redis实现布隆过滤器的方法及原理

    布隆过滤器(Bloom Filter)是1970年由布隆提出的.它实际上是一个很长的二进制向量和一系列随机映射函数.布隆过滤器可以用于检索一个元素是否在一个集合中.它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难. 本文将介绍布隆过滤器的原理以及Redis如何实现布隆过滤器. 应用场景 1.50亿个电话号码,现有10万个电话号码,如何判断这10万个是否已经存在在50亿个之中?(可能方案:数据库,set, hyperloglog) 2.新闻客户端看新闻时,它会不

  • 布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法

    引言 在介绍布隆过滤器之前我们首先引入几个场景. 场景一 在一个高并发的计数系统中,如果一个key没有计数,此时我们应该返回0,但是访问的key不存在,相当于每次访问缓存都不起作用了.那么如何避免频繁访问数量为0的key而导致的缓存被击穿? 有人说, 将这个key的值置为0存入缓存不就行了吗?确实,这是一个好的方案.大部分情况我们都是这样做的,当访问一个不存在的key的时候,设置一个带有过期时间的标志,然后放入缓存.不过这样做的缺点也很明显,浪费内存和无法抵御随机key攻击. 场景二 在一个黑名

  • python使用布隆过滤器的实现示例

    使用库pybloom_live from pybloom_live import ScalableBloomFilter,BloomFilter # 可自动伸缩的布隆过滤器 bloom = ScalableBloomFilter(initial_capacity=100,error_rate=0.001) # 添加内容 bloom.add('daqi') print('daqi'in bloom) # 定长的布隆过滤器 bloom1 = BloomFilter(capacity=10000) b

  • C++详细讲解模拟实现位图和布隆过滤器的方法

    目录 位图 引论 概念 解决引论 位图的模拟实现 铺垫 结构 构造函数 存储 set,reset,test flip,size,count any,none,all 重载流运算符 测试 位图简单应用 位图代码汇总 布隆过滤器 引论 要点 代码实现 效率 解决方法 位图 引论 四十亿个无符号整数,现在给你一个无符号整数,判断这个数是否在这四十亿个数中. 路人甲:简单,快排+二分. 可是存储这四十亿个整数需要多少空间? 简单算一下,1G=1024M=1024 * 1024KB=1024 * 1024

随机推荐