Python Counting Bloom Filter原理与实现详细介绍
作者:木东居士 发布时间:2021-04-04 19:01:54
前言
标准的 Bloom Filter 是一种比较简单的数据结构,只支持插入和查找两种操作。在所要表达的集合是静态集合的时候,标准 Bloom Filter 可以很好地工作,但是如果要表达的集合经常变动,标准Bloom Filter的弊端就显现出来了,因为它不支持删除操作。这就引出来了本文要谈的 Counting Bloom Filter,后文简写为 CBF。
原理
一、BF 为什么不支持删除
BF 为什么不能删除元素?我们可以举一个例子来说明。
比如要删除集合中的成员 dantezhao,那么就会先用 k 个哈希函数对其计算,因为 dantezhao 已经是集合成员,那么在位数组的对应位置一定是 1,我们如要要删除这个成员 dantezhao,就需要把计算出来的所有位置上的 1 置为 0,即将 5 和 16 两位置为 0 即可。
问题来了!现在,先假设 yyj 本身是属于集合的元素,如果需要查询 yyj 是否在集合中,通过哈希函数计算后,我们会去判断第 16 和 第 26 位是否为 1, 这时候就得到了第 16 位为 0 的结果,即 yyj 不属于集合。 显然这里是误判的。
二、什么是 Counting Bloom Filter
Counting Bloom Filter 的出现,解决了上述问题,它将标准 Bloom Filter 位数组的每一位扩展为一个小的计数器(Counter),在插入元素时给对应的 k (k 为哈希函数个数)个 Counter 的值分别加 1,删除元素时给对应的 k 个 Counter 的值分别减 1。Counting Bloom Filter 通过多占用几倍的存储空间的代价, 给 Bloom Filter 增加了删除操作。基本原理是不是很简单?看下图就能明白它和 Bloom Filter 的区别在哪。
三、Counter 大小的选择
CBF 和 BF 的一个主要的不同就是 CBF 用一个 Counter 取代了 BF 中的一位,那么 Counter 到底取多大才比较合适呢?这里就要考虑到空间利用率的问题了,从使用的角度来看,当然是越大越好,因为 Counter 越大就能表示越多的信息。但是越大的 Counter 就意味着更多的资源占用,而且在很多时候会造成极大的空间浪费。
因此,我们在选择 Counter 的时候,可以看 Counter 取值的范围多小就可以满足需求。
根据论文中描述,某一个 Counter 的值大于或等于 i 的概率可以通过如下公式描述,其中 n 为集合的大小,m 为 Counter 的数量,k 为 哈希函数的个数。
在之前的文章《Bloom Filter 的数学背景》中已经得出,k 的最佳取值为 k = m/n * ln2
,将其带入公式后可得。
如果每个 Counter 分配 4 位,那么当 Counter 的值达到 16 时就会溢出。这个概率如下,这个值足够小,因此对于大多数应用程序来说,4位就足够了。
关于 CBF 中 Counter 大小的选择,主要参考这篇论文:《Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol》,在论文的第 6、7 两页专门对其做了一番阐述。这里不再推导细节,只给出一个大概的说明,感兴趣的童鞋可以参考原论文。
简单的实现
还是实现一个简单的程序来熟悉 CBF 的原理,这里和 BF 的区别有两个:
一个是我们没有用 bitarray 提供的位数组,而是使用了 bytearray 提供的一个 byte数组,因此每一个 Counter 的取值范围在 0~255。
另一个是多了一个 remove 方法来删除集合中的元素。
代码很简单,只是为了理解概念,实际中使用的库会有很大差别。
import mmh3
class CountingBloomFilter:
def __init__(self, size, hash_num):
self.size = size
self.hash_num = hash_num
self.byte_array = bytearray(size)
def add(self, s):
for seed in range(self.hash_num):
result = mmh3.hash(s, seed) % self.size
if self.bit_array[result] < 256:
self.bit_array[result] += 1
def lookup(self, s):
for seed in range(self.hash_num):
result = mmh3.hash(s, seed) % self.size
if self.bit_array[result] == 0:
return "Nope"
return "Probably"
def remove(self, s):
for seed in range(self.hash_num):
result = mmh3.hash(s, seed) % self.size
if self.bit_array[result] > 0:
self.bit_array[result] -= 1
cbf = CountingBloomFilter(500000, 7)
cbf.add("dantezhao")
cbf.add("yyj")
cbf.remove("dantezhao")
print (cbf.lookup("dantezhao"))
print (cbf.lookup("yyj"))
来源:https://cloud.tencent.com/developer/article/1136056
猜你喜欢
- 在asp中调用sql server的存储过程可以加快程序运行速度,本文介绍了asp使用存储过程的方法。1.调用存储过程的一般方法 先假设在s
- 继续Mootools的扩展,适用于Mootools 1.1及1.2,这次在Element扩展了两个非常简单的方法,一个用来获取
- 如何用Response.Write调用代替内嵌表达式?我们可以利用下面的代码,注意:代码的每一行对响应流有一次写操作,所有的代码都包含在一个
- 不知不觉大半年没更新了...前面小二介绍过使用Typora+MinIO+Java代码打造舒适写作环境,然后有很多大佬啊,说用Java来实现简
- 笔者小白在收集印刷体汉字的深度学习训练集的时候,一开始就遇到的了一个十分棘手的问题,就是如何获取神经网络的训练集数据。通过上网搜素,笔者没有
- Python写入Excel有时需要合并单元格、或者改变文字内容的颜色首先导入xlwt模块import xlwt创建文件名创建Excel工作簿
- 最近用Python写了个 * ,需要部署到Linux环境的服务器上,由于之前本地开发时使用virtualenv,使用这个虚拟环境有个好处是项目
- 安装数据可视化模块matplotlib:pip install matplotlib导入matplotlib模块下的pyplot1 折线图f
- 1、显式等待它指定要查找的节点,然后指定一个最长的等待时间,如果规定时间内加载出来了这个节点,就返回查找的节点;如果规定时间内没有加载出该节
- 问题背景调试脚本时,遇到一个问题:ImportError: cannot import name 'A' from '
- 前言还记得这个九九乘法表吗,这次课后相信你可以用代码给你的小弟弟妹妹们变出这份“葵花宝典”。循环如果要把循环翻译成机器语言,那他对应的可以是
- 本文实例讲述了PHP实现二维数组中的查找算法。分享给大家供大家参考,具体如下:方法1:silu从左下角最后一行的第一个元素开始,遍历。如果小
- 要将身份证的正反面图片合并为一张图片,你可以使用PHP的GD库来完成。演示了如何合并两张图片下面是一个示例代码,演示了如何合并两张图片://
- 1. NumPy安装使用pip包管理工具进行安装$ sudo pip install numpy使用pip包管理工具安装ipython(交互
- 一、功能说明:1. 多线程方式抓取代理服务器,并多线程验证代理服务器ps 代理服务器是从http://www.cnproxy.com/ (测
- 安装pip install requests发送网络请求import requestsr=requests.get('http://
- 网易最近出的一款自动化UI测试工具:Airtest 挺火的,还受到谷歌的推荐。我试着用了一下,感觉优缺点还是蛮明显的。对初学者来说,能用到的
- 第一个:神奇的字典键some_dict = {}some_dict[5.5] = "Ruby"some_dict[5.0
- pytorch forwod函数在父类中的调用问题背景最近在研究Detetron2的代码结构时,发现有些网络代码里面没有forward函数,
- Django中集成jquery首先,静态的资源通常放入static文件夹中:static/ css/