Bloom Filter 的数学背景

0x00 前言

程序员应该无所畏惧,所以,一起来推导数学公式吧!

上文我们分享了 Bloom Filter 的基本原理和代码实现,在文章的结尾提到了 BF 的误判率以及几个重要参数的选取,我们只给出了最后的公式,而没有具体的推导过程。 这是会被狠狠地挑战的,本着追根刨底的精神,我们推导一下 BF 相关的数学公式。

文章结构

本文会分享关于 BF 的三个知识点:

  1. 错误率公式的推导
  2. 最佳哈希函数个数的推导
  3. BF 的基数估计公式,即如何计算 BF 中的元素个数

0x01 背景补充

错误率

错误率有两种:

  • FP = A false positive error, or in short a false positive, commonly called a “false alarm”, is a result that indicates a given condition exists, when it does not.
  • FN = A false negative error, or in short a false negative, is a test result that indicates that a condition does not hold, while in fact it does.

对应 BF 的情况下,FP 就是「集合里没有某元素,查找结果是有该元素」,FN 就是「集合里有某元素,查找结果是没有该元素」。

FN 显然总是0,只要集合中有某元素,那么肯定能查到。FP 会随着 BF 中插入元素的数量而增加——极限情况就是所有 bit 都为 1,这时任何元素都会被认为在集合里。

0x02 数学推导

一、误判率怎么来?

假设哈希函数以相等的概率选择位数组中的位置。如果 m 是位数组中的比特数,则在插入元素期间某一特定比特位不被某个哈希函数设置为 1 的概率是:

1-\frac{1}{m}

如果哈希函数的数量是 k,则通过 k 个哈希函数都未将该位设置为 1 的概率是:

(1-\frac{1}{m})^k

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

(1-\frac{1}{m})^{kn}

因此这一位的值为 1 的概率就是:

1-(1-\frac{1}{m})^{kn}

那么,BF 的误判率是怎么得出的?前面提到,我们主要关注 FP,即集合里没有某元素,查找结果是有该元素。

现在我们要判断一个元素是否在集合中,假设这个元素本不在集合中,理论上来讲,经过 k 个哈希函数计算后得到的位数组的 k 个位置的值都应该是 0,如果发生了误判,即这 k 个位置的值都为 1,这个概率如下:

p=(1-[1-\frac{1}{m}]^{kn})^k\approx (1-e^{-\frac{kn}{m}})^k

上面的公式就是 BF 的误判率。

注意,上面的证明并不是不是严格正确的,因为它假定每个位的概率被设置为独立性。不过,并不太影响我们对误判率的理解。

二、哈希函数个数该怎么选?

首先,哈希函数的数目 k 必须是正整数。对于给定值的 m 和 n,该如何选择 k 的取值才能使能使误判率 p 最小?这就要用到前面的公式,令 p 的取值为零,即可得到如下表达式:

k=\frac{m}{n}ln2

将 k 的最佳取值带入概率公式,就可以得到误判率 p 和 哈希函数个数 k 的关系:

p\approx(1-e^{-\frac{kn}{m}})^k=(1-e^{-(\frac{m}{n}ln2)\frac{n}{m}})^k=(1-\frac{1}{2})^k

上述公式也可以表述为如下形式:

m=-\frac{nlnp}{(ln2)^2}

或者

k = -log_2p

以上就是关于哈希函数个数 k 的最优化取值的数学推导。

三、如何估计 BF 的元素数量?

下面是维基百科给出公式,这里照搬过来,先不做推导了,感兴趣的可以自己来一遍。

n = -\frac{m}{k}ln(1-\frac{t}{m})

其中 n 是估计 BF 中的元素个数,t 是位数组中被置为 1 的位的个数。

有了能够估计 BF 中元素数量的方式,BF 就可以应用到基数估计的场景中了,这在后面提到 Hyperloglog 等算法的时候会有一些对比。

0xFF 总结

本文参考 BF 的维基百科和几篇经典论文。自己学习并推导一遍还是很能加深印象,公式是自己在 Markdown 中用 LaTeX 敲出来的,十分方便。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

每周学点大数据 | No.7大数据规模的算法分析

No.7期 大数据规模的算法分析 Mr. 王:这样的时间界限记为O(1),我们称之为常数时间算法,这样的算法一般来说是最快的,因为它与输入规模完全无关,不论输...

2024
来自专栏Java 源码分析

平衡搜索树

2-3树 ​ 其实仔细来看2-3树好像是 B 树的一个特例,它规定了一个节点要么有一个 key 要么有两个 key。 如果有一个 key 那么他就有两个子...

3159
来自专栏Leetcode名企之路

【Leetcode】64. 最小路径和

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

2161
来自专栏量化投资与机器学习

从Encoder到Decoder实现Seq2Seq模型(算法+代码)

知乎专栏:机器不学习 作者:天雨栗 | 蚂蚁金服 | 数据算法 已授权刊登 前言 好久没有更新专栏,今天我们来看一个简单的Seq2Seq实现,我们将使用Tens...

8296
来自专栏余林丰

12.高斯消去法(1)——矩阵编程基础

对于一阶线性方程的求解有多种方式,这里将介绍利用高斯消去法解一阶线性方程组。在介绍高斯消去法前需要对《线性代数》做一下温习,同时在代码中对于矩阵的存储做一个简...

2457
来自专栏ATYUN订阅号

如何在Python和numpy中生成随机数

随机性的使用是机器学习算法配置和评估的重要部分。从神经网络中的权重的随机初始化,到将数据分成随机的训练和测试集,再到随机梯度下降中的训练数据集的随机混洗(ran...

3073
来自专栏AI研习社

从 Encoder 到 Decoder 实现 Seq2Seq 模型

前言 好久没有更新专栏,今天我们来看一个简单的Seq2Seq实现,我们将使用TensorFlow来实现一个基础版本的Seq2Seq,主要帮助理解Seq2Se...

61313
来自专栏李智的专栏

Deep learning基于theano的keras学习笔记(2)-泛型模型(含各层的方法)

  我们希望预测Twitter上一条新闻会被转发和点赞多少次。模型的主要输入是新闻本身(一个词语序列)。但我们还可以拥有额外的输入(如新闻发布的日期等)。这个模...

941
来自专栏专知

【Keras教程】用Encoder-Decoder模型自动撰写文本摘要

【导读】这篇博文介绍了如何在深度学习框架Keras上实现文本摘要问题,探讨了如何使用编码器-解码器递归神经网络体系结构来解决文本摘要问题,如何实现文本摘要问题的...

9185
来自专栏CreateAMind

keras doc 5 泛型与常用层

2974

扫码关注云+社区

领取腾讯云代金券