布隆过滤器的误判率该如何计算?

news/2024/11/8 2:56:38/

作者:胡慢慢滚雪球
链接:https://www.zhihu.com/question/38573286/answer/507497251
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
 

在计算机中,判断一个元素是不是在一个集合中,通常是用hash来解决,这在数据量不大的时候是可以的,但是当数据量很大的时候存储空间就会爆炸。

一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件(email)提供商,总是需要过滤来自发送垃圾邮件的人(spamer)的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址,全世界少说也有几十亿个发垃圾邮件的地址,将他们都存起来则需要大量的网络服务器。如果用哈希表,每存储一亿个 email 地址, 就需要 1.6GB 的内存(用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹 googlechinablog.com/2006/08/blog-post.html,然后将这些信息指纹存入哈希表,由于哈希表的存储效率一般只有 50%,因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB, 即十六亿字节的内存)。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机,一般服务器是无法存储的。——吴军《数学之美》

解决的问题

大数据量的时候, 判断一个元素是否在一个集合中。

实现原理

布隆过滤器(Bloom Filter)的核心实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m,哈希函数的个数为k。

以上图为例,具体的操作流程:假设集合里面有3个元素{x, y, z},哈希函数的个数为3。首先将位数组进行初始化,将里面每个位都设置位0。

添加元素

对于集合里面的每一个元素,将元素依次通过3个哈希函数进行映射,每次映射都会产生一个哈希值,这个值对应位数组上面的一个点,然后将位数组对应的位置标记为1。

查询元素

查询W元素是否存在集合中的时候,同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1,则可以判断该元素一定不存在集合中。反之,如果3个点都为1,则该元素**可能**存在集合中。注意:此处不能判断该元素是否一定存在集合中,可能存在一定的误判率。可以从图中可以看到:假设某个元素通过映射对应下标为4,5,6这3个点。虽然这3个点都为1,但是很明显这3个点是不同元素经过哈希得到的位置,因此这种情况说明元素虽然不在集合中,也可能对应的都是1,这是误判率存在的原因。

移除集合中的元素

这个在布隆过滤器中是不允许的,理解原理我们就知道,如果将是1的位置重置成0会影响其他元素是不是在集合中的判断。对于关小黑屋再放出来这种需求,我们可以换一个思路,再加一个布隆过滤器————“被移除的元素”,当然现在公司都比较土豪,直接用redis存一个过期时间就可以,那就不在我们讨论之列了,布隆过滤器的初衷是用少许的误判来极大的节省空间。

错误率

假设 Hash 函数以等概率条件选择并设置 Bit Array 中的某一位,假定由每个 Hash 计算出需要设置的位(bit) 的位置是相互独立, m 是该位数组的大小,k 是 Hash 函数的个数.

  • 位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位的概率是:

 

  • 在所有 k 次 Hash 操作后该位都没有被置 "1" 的概率是:

 

  • 如果我们插入了 n 个元素,那么某一位仍然为 "0" 的概率是:

 

  • 该位为 "1"的概率是:

 

检测某一元素是否在该集合中。标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 "1",但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中(False Positives),该概率由以下公式确定:

 

如何使得错误率最小,对于给定的m和n,当 的时候取值最小。关系如下图所示:

应用

  • HBASE、Cassandra数据库中用来判断数据是不是在磁盘上

  • chrome用它来做钓鱼网站监测
  • 在比特币中用来判断是不是属于钱包
  • 垃圾邮件监测

实现

如果你是java开发者,可以看看google的guava包中有对Bloom Filter的实现,详细见参考资料。

参考资料

  • Bloom filter - Wikipedia
  • 布隆过滤器:Google Guava类库源码分析及基于Redis Bitmaps的重构 - 文章 - 伯乐在线
  • 布隆过滤器(Bloom Filter)、SPV和比特币

http://www.ppmy.cn/news/529348.html

相关文章

什么是布隆过滤器?如何使用?

欢迎搜索 文章目录 一、布隆过滤器简介二、布隆过滤器的结构三、布隆过滤器应用四、布隆过滤器的优缺点五、布隆过滤器实战六、总结 Redis缓存穿透可以通过布隆过滤器进行解决,那么什么是布隆过滤器呢?请往下看。 通常你判断某个元素是否存在用的是什么…

瑞尔集团通过上市聆讯:半年亏4.6亿 淡马锡与高瓴是股东

雷递网 雷建平 2月28日报道 口腔诊所——瑞尔集团有限公司(简称:“瑞尔集团”)日前通过聆讯,准备在香港上市。 半年期内亏损4.64亿 瑞尔集团是一家提供高端口腔医疗服务的企业。自1999年成立以来,在过往十年当中&#…

何为布隆过滤器

问题的提出 我们有一个不安全网页的黑名单,包含了100亿个黑名单网页的URL,每个网页URL最多占用64B.。 现在我们要设计一个网页过滤系统,这个系统要判断该网页是否在黑名单里,但是我们的空间有限,只有30GB. 允许有万分之一的判断…

神奇的利克瑞尔数:196 【大数加法】【回文数】

微信搜索:编程笔记本 微信搜索:编程笔记本 微信搜索:编程笔记本 点击上方蓝字关注我,我们一起学编程 欢迎小伙伴们分享、转载、私信、赞赏 今天要跟小伙伴们分享神奇的数字:196。 在介绍这个神奇的数字之前&#xff0c…

allure简介

allure介绍 allure是一个轻量级,灵活的,支持多语言的测试报告工具 多平台的,奢华的report框架 可以为dev/qa提供详尽的测试报告、测试步骤、log 也可以为管理层提供high level统计报告 java语言开发的,支持pytest,javaScript,PHP等…

布隆过滤器说明

本文参考:布隆过滤器详解__瞳孔的博客-CSDN博客_布隆过滤器 布隆过滤器以及python实现_追光的鲲的博客-CSDN博客_python布隆过滤器 目录 一、概述 二、布隆过滤器原理 2.1 原理 2.2 误判率 2.3 特性 2.4 添加元素步骤 2.5 查询元素步骤 2.6 布隆过滤器的使…

瑞尔齿科×UB Store | RPA破解医疗业务痛点

如今,医疗行业正经历剧变,无论是政策环境还是病患需求,都在快速变化。随着智能自动化技术的深入发展,医疗行业也掀起了应用RPA技术的热潮。 瑞尔齿科 瑞尔齿科,中国高端齿科服务行业领先品牌,成立于1999年&…

瑞尔集团再度冲刺港股:半年亏4.6亿 淡马锡与高瓴是股东

雷递网 雷建平 7月5日报道 口腔诊所——瑞尔集团有限公司日前再次向港交所递交招股书,准备在香港上市。 半年期内亏损4.64亿 瑞尔集团是一家提供高端口腔医疗服务的企业。自1999年成立以来,在过往十年当中,瑞尔集团号称已服务患者超过630万人…