星河拾贝录星河拾贝录
文章 分类 标签 专栏 关于
简体中文
星河拾贝录星河拾贝录

目录

目录

BloomFilter中的数学推导

liubang  收录于  类别 存储与分布式
     约 478 字   预计阅读 3 分钟 

mm: 表示 Bloom Filter bit array 的长度;
kk: 表示 hash 函数个数;
nn: 表示插入元素的个数;

假设 hash 函数以等概率选择 bit array 的下标，那么某次 hash 后，某个特定 bit 位未被设置为 1 的概率为 1−1m1 - \frac{1}{m}。经过 kk 个 hash 函数之后，该 bit 位仍未被设置为 1 的概率为:

(1−1m)k \left(1 - \frac{1}{m}\right)^k

在插入 nn 个元素之后，某个 bit 位仍然没有被设置为 1 的概率为:

(1−1m)kn \left(1 - \frac{1}{m}\right)^{kn}

因此在插入 nn 个元素之后，某个 bit 位被设置为 1 的概率为:

p=1−(1−1m)kn p = 1 - \left(1 - \frac{1}{m}\right)^{kn}

对于一个不存在于集合中的元素，如果要出现误判（false positive），意味着经过 kk 个 hash 函数之后，生成的 kk 个下标所对应的 bit 位全部为 1，其概率为:

ε=pk=(1−(1−1m)kn)k \varepsilon = p^k = \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k

接下来利用自然常数 ee 的极限定义对上式进行简化。已知:

lim⁡m→∞(1+zm)m=ez \lim_{m \to \infty}\left(1 + \frac{z}{m}\right)^m = e^z

令 z=−1z = -1:

lim⁡m→∞(1−1m)m=e−1 \lim_{m \to \infty}\left(1 - \frac{1}{m}\right)^m = e^{-1}

当 mm 足够大时，有:

(1−1m)kn=((1−1m)m)knm≈e−knm \left(1 - \frac{1}{m}\right)^{kn} = \left(\left(1 - \frac{1}{m}\right)^m\right)^{\frac{kn}{m}} \approx e^{-\frac{kn}{m}}

代入 ε\varepsilon 可得:

ε≈(1−e−knm)k \varepsilon \approx \left(1 - e^{-\frac{kn}{m}}\right)^k

当 ε\varepsilon 最小时，kk 为最优。因此需要对 ε\varepsilon 关于 kk 求导，找到极小值点。

令 f=(1−e−knm)kf = \left(1 - e^{-\frac{kn}{m}}\right)^k，对等式两边取对数:

g=ln⁡f=k⋅ln⁡(1−e−knm) g = \ln f = k \cdot \ln\left(1 - e^{-\frac{kn}{m}}\right)

对 gg 关于 kk 求导（利用乘积法则）:

dgdk=ln⁡(1−e−knm)+k⋅ddkln⁡(1−e−knm) \frac{dg}{dk} = \ln\left(1 - e^{-\frac{kn}{m}}\right) + k \cdot \frac{d}{dk}\ln\left(1 - e^{-\frac{kn}{m}}\right)

对第二项应用链式法则:

ddkln⁡(1−e−knm)=nm⋅e−knm1−e−knm \frac{d}{dk}\ln\left(1 - e^{-\frac{kn}{m}}\right) = \frac{\frac{n}{m} \cdot e^{-\frac{kn}{m}}}{1 - e^{-\frac{kn}{m}}}

因此:

dgdk=ln⁡(1−e−knm)+knm⋅e−knm1−e−knm \frac{dg}{dk} = \ln\left(1 - e^{-\frac{kn}{m}}\right) + \frac{kn}{m} \cdot \frac{e^{-\frac{kn}{m}}}{1 - e^{-\frac{kn}{m}}}

令 dgdk=0\frac{dg}{dk} = 0（在不考虑 kk 为整数的约束下寻找极值点）:

ln⁡(1−e−knm)+knm⋅e−knm1−e−knm=0 \ln\left(1 - e^{-\frac{kn}{m}}\right) + \frac{kn}{m} \cdot \frac{e^{-\frac{kn}{m}}}{1 - e^{-\frac{kn}{m}}} = 0

整理得:

−ln⁡(1−e−knm)=knm⋅e−knm1−e−knm -\ln\left(1 - e^{-\frac{kn}{m}}\right) = \frac{kn}{m} \cdot \frac{e^{-\frac{kn}{m}}}{1 - e^{-\frac{kn}{m}}}

对等式两边取指数:

11−e−knm=eknm⋅e−knm1−e−knm \frac{1}{1 - e^{-\frac{kn}{m}}} = e^{\frac{kn}{m} \cdot \frac{e^{-\frac{kn}{m}}}{1 - e^{-\frac{kn}{m}}}}

为简化表达，令 x=e−knmx = e^{-\frac{kn}{m}}（其中 0<x<10 < x < 1），可得:

11−x=(1x)x1−x \frac{1}{1 - x} = \left(\frac{1}{x}\right)^{\frac{x}{1 - x}}   ⟺  (1−x)−1=x−x1−x  ⟺  (1−x)=xx1−x \iff (1 - x)^{-1} = x^{-\frac{x}{1-x}} \iff (1 - x) = x^{\frac{x}{1 - x}}

对等式两边取对数:

ln⁡(1−x)=x1−x⋅ln⁡x \ln(1 - x) = \frac{x}{1 - x} \cdot \ln x   ⟺  (1−x)⋅ln⁡(1−x)=x⋅ln⁡x \iff (1 - x) \cdot \ln(1 - x) = x \cdot \ln x

设 h(t)=t⋅ln⁡th(t) = t \cdot \ln t，上式即 h(1−x)=h(x)h(1 - x) = h(x)。由于 h(t)h(t) 在 (0,1)(0, 1) 上先递减后递增，且关于 t=12t = \frac{1}{2} 对称（即 h(t)=h(1−t)h(t) = h(1-t) 当且仅当 t=12t = \frac{1}{2}），可得 x=12x = \frac{1}{2}。

又因为 x=e−knmx = e^{-\frac{kn}{m}}，所以:

e−knm=12  ⟺  −knm=ln⁡12=−ln⁡2  ⟺  k=mnln⁡2 e^{-\frac{kn}{m}} = \frac{1}{2} \iff -\frac{kn}{m} = \ln\frac{1}{2} = -\ln 2 \iff k = \frac{m}{n} \ln 2

已知 ε≈(1−e−knm)k\varepsilon \approx \left(1 - e^{-\frac{kn}{m}}\right)^k，将 k=mnln⁡2k = \frac{m}{n}\ln 2 代入。

由前面的推导，当 kk 取最优值时 e−knm=12e^{-\frac{kn}{m}} = \frac{1}{2}，因此:

ε≈(1−12)mnln⁡2=(12)mnln⁡2 \varepsilon \approx \left(1 - \frac{1}{2}\right)^{\frac{m}{n}\ln 2} = \left(\frac{1}{2}\right)^{\frac{m}{n}\ln 2}

对两边取自然对数:

ln⁡ε≈mnln⁡2⋅ln⁡12=−mn(ln⁡2)2 \ln \varepsilon \approx \frac{m}{n} \ln 2 \cdot \ln\frac{1}{2} = -\frac{m}{n} (\ln 2)^2

解出 mm:

m≈−nln⁡ε(ln⁡2)2≈−1.44 nlog⁡2ε m \approx -\frac{n \ln \varepsilon}{(\ln 2)^2} \approx -1.44 \, n \log_2 \varepsilon

其中 1(ln⁡2)2≈2.08\frac{1}{(\ln 2)^2} \approx 2.08，所以也可以写成 m≈−2.08 nln⁡εm \approx -2.08 \, n \ln \varepsilon。

给定预期插入元素数 nn 和可接受的误判率 ε\varepsilon:

  • 最优 bit array 长度: m≈−nln⁡ε(ln⁡2)2m \approx -\frac{n \ln \varepsilon}{(\ln 2)^2}
  • 最优 hash 函数个数: k=mnln⁡2≈−log⁡2εk = \frac{m}{n} \ln 2 \approx -\log_2 \varepsilon

例如，若期望误判率为 1%（ε=0.01\varepsilon = 0.01），则每个元素约需 9.6 bits，最优 hash 函数个数约为 7。

更新于 2025-01-01
 Storage
 | 主页