专栏首页木东居士的专栏Counting Bloom Filter 的原理和实现

Counting Bloom Filter 的原理和实现

0x00 前言

标准的 Bloom Filter 是一种比较简单的数据结构,只支持插入和查找两种操作。在所要表达的集合是静态集合的时候,标准 Bloom Filter 可以很好地工作,但是如果要表达的集合经常变动,标准Bloom Filter的弊端就显现出来了,因为它不支持删除操作。这就引出来了本文要谈的 Counting Bloom Filter,后文简写为 CBF。

0x01 原理

一、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 两页专门对其做了一番阐述。这里不再推导细节,只给出一个大概的说明,感兴趣的童鞋可以参考原论文。

0x03 简单的实现

还是实现一个简单的程序来熟悉 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"))

0xFF 总结

CBF 虽说解决了 BF 的不能删除元素的问题,但是自身仍有不少的缺陷有待完善,比如 Counter 的引入就会带来很大的资源浪费,CBF 的 FP 还有很大可以降低的空间, 因此在实际的使用场景中会有很多 CBF 的升级版。

比如 SBF(Spectral Bloom Filter)在 CBF 的基础上提出了元素出现频率查询的概念,将CBF的应用扩展到了 multi-set 的领域;dlCBF(d-Left Counting Bloom Filter)利用 d-left hashing 的方法存储 fingerprint,解决哈希表的负载平衡问题;ACBF(Accurate Counting Bloom Filter)通过 offset indexing 的方式将 Counter 数组划分成多个层级,来降低误判率。这些内容,有机会再分享。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Bloom Filter 的基本原理和实现

    Bloom Filter 是由 Burton H. Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是不是集...

    木东居士
  • Bloom Filter 的基本原理和实现

    木东居士
  • BitMap 的基本原理和实现

    本篇是大数据算法系列 第一篇《 BitMap 的原理和实现》,BitMap 的思想的和原理是很多算法的基础,因此我们以 BitMap 开篇。

    木东居士
  • BitMap 的基本原理和实现

    木东居士
  • 布隆过滤器(Bloom Filter)的原理和实现

    虽然上面描述的这几种数据结构配合常见的排序、二分搜索可以快速高效的处理绝大部分判断元素是否存在集合中的需求。但是当集合里面的元素数量足够大,如果有500万条记录...

    一个会写诗的程序员
  • 布隆过滤器redis缓存 顶

    Bloom Filter布隆过滤器 算法背景 如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表...

    须臾之余
  • 大数据量下的集合过滤—Bloom Filter

    欠扁的小篮子
  • 大数据量下的集合过滤—Bloom Filter

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

    王知无-import_bigdata
  • deepBF:使用学习型Bloom过滤器和进化式深度学习进行恶意URL检测(CS/AI)

    由于各种系统(例如边缘计算)的不断现代化,恶意URL检测是一个新兴的研究领域。在本文中,我们提出了一种新颖的恶意URL检测技术,称为deepBF(深度学习和Bl...

    用户8354439
  • 深度剖析各种BloomFilter的原理、改进、应用场景

      Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求1...

    sunsky
  • 详解大规模数据处理利器 BloomFilter 算法

    转自:heaad http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html Bloom Filt...

    企鹅号小编
  • Milvus数据管理:删除的实现原理

    本文将主要讲述 Milvus 是怎么实现删除功能的。删除是许多用户期待已久的功能,这次终于在 Milvus 0.7.0 版本中发布。区别于直接调用 FAISS ...

    Zilliz RDS
  • 理解BitMap算法的原理

    位图:一种常用的数据结构,代表了有限域中的稠集(dense set),每一个元素至少出现一次,没有其他的数据和元素相关联。在索引,数据压缩,海量数据处理等方面有...

    我是攻城师
  • 处理海量数据的10种常见方法

    本文将介绍10种处理海量数据问题的常见方法,也可以说是对海量数据的处理方法进行一个简单的总结,希望对你有帮助。

    挖掘大数据
  • 好玩的布隆过滤器

    本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 「...

    chengcheng222e
  • 布隆过滤器实战【防止缓存击穿】

    我们的业务中经常会遇到穿库的问题,通常可以通过缓存解决。 如果数据维度比较多,结果数据集合比较大时,缓存的效果就不明显了。 因此为了解决穿库的问题,我们引入Bl...

    老钱
  • 入门 | 海量数据处理算法总结【超详解】

    作者 | Angel_Kitty ➤1. Bloom Filter 【Bloom Filter】 Bloom Filter(BF)是一种空间效率很高的随机数据...

    AI科技大本营
  • 面试系列:十个海量数据处理方法大总结

    本文将简单总结下一些处理海量数据问题的常见方法。当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本...

    王知无-import_bigdata
  • 大数据计数原理1+0=1这你都不会算(一)No.47

    hello哈,大家是不是好久没见到我啦?我也是一直在摸索小伙伴们喜欢看到什么东西,不喜欢看什么东西,还请大家多多支持。为了表示感谢。小蕉在这给你们一鞠躬,二鞠躬...

    大蕉

扫码关注云+社区

领取腾讯云代金券