BloomFilter原理学习

BloomFilter简单介绍

BloomFilter我们可能经常听到也在使用, 它的特点是如果判断结果为"不存在", 则一定不存在; 如果判断为存在, 则可能存在. 如下图示例说明当我们判断z元素存在时, 其实是不存在的, 即存在有概率性.

如上图, 长为m=16的二进制向量, 初始全为0; k=3(即添加一个元素需要将3个bit设置为1), 对n=3个元素进行添加操作.

BloomFilter几个关键量定义:
m: 二进制向量大小(多少个二进制位)
n: 要存放的元素个数
k: 哈希函数的个数, 或者说每添加一个元素都要进行k次计算
fpp或者简写为p: 误判率(false positive rate), 即 使用bloomfilter判断为存在时, 但实际不存在的概率

BloomFilter中的数学知识

fpp(误判率/假阳性)的计算

BloomFilter主要的数学原理是: 在某一范围内($1<=x<=m)$(x为整数, m通常是很大的, 如$10^6级别$), 任意选取两个整数$i,j,i和j可重复选取$, 则其相等的概率是非常小的: $\frac{m}{m^2}=\frac{1}{m}$

我们假定hash计算是均匀的, 即每次hash会随机地将m位中的一位设置为1. 那么:

• 一次hash计算(如$h1(x)$)后, 任一位被 置为1 的概率为: $\frac{1}{m}$
• 一次hash计算(如$h1(x)$)后, 任一位 还是0(即未被置为1) 的概率为: $1-\frac{1}{m}$
• 添加一个元素(如bloomFilter.Add(x), 即执行k次hash)后, 任一位还是0的概率为: $(1-\frac{1}{m}{)}^k$
• 添加n个元素后(如上图中的n=3个元素:x,y,z), 任一位还是0的概率为: $(1-\frac{1}{m}{)}^{kn}$ , 任一位为1的概率为 $1-(1-\frac{1}{m}{)}^{kn}$
• 如果将1个新的元素，添加到已存在n个元素的BloomFilter中，则任一位已经为1的概率与上面相同，为：$1-(1-\frac{1}{m}{)}^{kn}$ .
  那么添加这个新元素时, k个比特都为1(相当于新元素和已有元素已经分不清了)的概率(此即为新插入元素的误识别率)为：
  $$p=[1-(1-\frac{1}{m}{)}^{kn}{]}^k$$

通常来说, m是一个非常大的数(1MiB内存就有$2^{20}\times 8\approx 800万$个bit), 并且我们有: $\underset{x\to \infty }{\lim }(1+x{)}^{\frac{1}{x}}=e$
那么在工程实践中, 可以认为p的近似值为:
$$\begin{array}{rl}p& =[1-(1-\frac{1}{m}{)}^{kn}{]}^k\\ & =[1-(1-\frac{1}{m}{)}^{-m\times \frac{-kn}{m}}{]}^k\\ & \approx (1-e^{-\frac{kn}{m}}{)}^k(当m很大时,将-\frac{1}{m}看作x)\end{array}$$

k的最小值

计算过程参考: https://cs.stackexchange.com/questions/132088/how-is-the-optimal-number-of-hashes-is-derived-in-bloom-filter

已经遗忘的知识:

1. 求导公式: $(\ln x{)}^{{}^{\prime }}=\frac{1}{x}$
2. 求导公式: $({\mathbf{e}}^{nx}{)}^{{}^{\prime }}=n{\mathbf{e}}^{nx}$

在某些情况下, 我们对n, m, 的值可以给一个估算值, 以此来获得最小的p(即尽可能准确判断), 那么k就是一个变量了, 问题就变为求 $(1-e^{-\frac{kn}{m}}{)}^k$的最小值.
令$f(k)=(1-e^{-\frac{kn}{m}}{)}^k$, 那么
$$\begin{array}{rl}& 两边取对数有:\\ & \ln f(k)=\ln (1-e^{-\frac{kn}{m}}{)}^k=k\ln (1-e^{-\frac{kn}{m}})\\ & 设g(k)=k\ln (1-e^{-\frac{kn}{m}}),那么:\\ & g{}^{\prime }(k)=\ln (1-e^{-\frac{kn}{m}})+k\frac{\frac{n}{m}{e}^{-\frac{kn}{m}}}{1-e^{-\frac{kn}{m}}}\\ & 令x=e^{-\frac{kn}{m}},x\in (0,1),那么有\\ & h(x)=\ln (1-x)-\frac{x}{1-x}\ln x(注意k用-\frac{m}{n}lnx替换)\\ & =\frac{(1-x)\ln (1-x)-x\ln x}{1-x}(x\in 0,1)\end{array}$$

对 $h(x)=\frac{(1-x)\ln (1-x)-x\ln x}{1-x}(x\in 0,1)$, 不难看出:

1. 当$x=\frac{1}{2}时,h(x)=0$
2. 当$x>\frac{1}{2}时,h(x)<0$
3. 当$x<\frac{1}{2}时,h(x)>0$

站在巨人的肩膀上, 我们可以直接在这里看:
显然在$x\in (0,1)范围内,当x=0.5时,h(x)最小$, 此时$k=\frac{m}{n}ln2$

也就是说:
当$k<\frac{m}{n}ln2$时(想象k非常接近0), $x=e^{-\frac{kn}{m}}$会非常接近1, 此时$x>\frac{1}{2}$,
$h(x)<0$ ⇒ f(k)在变小;
当$k>\frac{m}{n}ln2$时(想象k非常接近0), $x=e^{-\frac{kn}{m}}$会非常接近0, 此时$x<\frac{1}{2}$,
$h(x)>0$ ⇒ f(k)在变大;
所以$k=\frac{m}{n}ln2$时会使得$f(k)$最小, 即此时p最小.

公式总结

1. 误判率公式: $p=[1-(1-\frac{1}{m}{)}^{kn}{]}^k$
2. 误判率近似公式(当m很大时): $p\approx (1-e^{-\frac{kn}{m}}{)}^k$
3. 已知m, n, k的最小值(近似)为: $k=\frac{m}{n}\ln 2\approx 0.7\frac{m}{n}$
4. 已知n, p, 且k取最小时, $m=-\frac{n\ln p}{(ln2{)}^2}$

编程语言实现

golang的实现

https://github.com/bits-and-blooms/bloom

已知n, p求m和k

func EstimateParameters(n uint, p float64) (m uint, k uint) {m = uint(math.Ceil(-1 * float64(n) * math.Log(p) / math.Pow(math.Log(2), 2)))k = uint(math.Ceil(math.Log(2) * float64(m) / float64(n)))return
}

参考

1. https://en.wikipedia.org/wiki/Bloom_filter
2. https://cs.stackexchange.com/questions/132088/how-is-the-optimal-number-of-hashes-is-derived-in-bloom-filter

(完)