在《什么是布隆过滤器（Bloom Filter）？》一文中，多次提到了误识别率（FPP，false positive probabilistic）。
那么误识别率到底是多大，应该如何计算呢？
假设布隆过滤器大小为m比特，存储了n个元素，使用k次散列函数来计算元素的存储位置。
- 添加1个元素，则任一比特为1的概率为：
1/m，任一比特为0的概率：1-1/m； - 添加1个元素，执行k次散列之后，则任一比特为0的概率：
(1-1/m)^k，任一比特为1的概率：1-(1-1/m)^k； - 如果添加n个元素，那么任一比特为0的概率：
(1-1/m)^kn，任一比特为1的概率：1-(1-1/m)^kn； - 如果将1个新的元素，添加到已存在n个元素的布隆过滤器中，则任一比特已经为1的概率与上面相同，概率为：
1-(1-1/m)^kn。因此，k个比特都为1的概率为：(1-(1-1/m)^kn)^k，此即为新插入元素的误识别率。
当n值比较大时，(1-(1-1/m)kn)k约等于：(1-e-kn/m)k
其中，e是一个数学常数，是自然对数函数的底数。有时被称为欧拉数（Euler’s number），以瑞士数学家欧拉命名。它是一个无限不循环小数，数值约为2.71828182846。
假定布隆过滤器大小m为16比特，k为8，存储元素n为1，那么误识别（假阳性）的概率是万分之五（5/10000）。
此时，m/n=16，事实上这表示1个元素使用16个比特的空间来存储。
因此，当k相同时，m/n为16/1、32/2、64/4等值时具有相同的误识别率。
将数值代入公式，计算一下万分之五的概率是怎么来的：
kn=8*1=8
kn/m=8/16=1/2
e的-1次方转换为倒数：1/e=0.36787944117
再计算1/e的1/2次方，即对0.36787944117进行开方，得到：0.60653065971144443045693327628786
计算括号内的值：1-0.60653065971144443045693327628786=0.39346934028855556954306672371214
最后再计算k次方：0.39346934028855556954306672371214的8次方=5.7449622219356465294987619912758e-4
计算得到的误识别率为 5.7449622219356465294987619912758e-4 ，即万分之五。
下面是来自http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html的一个误识别率表，可以很方便的查询出在m、n和k分别取不同值时的误识别率。
| m/n | k | k=1 | k=2 | k=3 | k=4 | k=5 | k=6 | k=7 | k=8 |
| 2 | 1.39 | 0.393 | 0.400 | ||||||
| 3 | 2.08 | 0.283 | 0.237 | 0.253 | |||||
| 4 | 2.77 | 0.221 | 0.155 | 0.147 | 0.160 | ||||
| 5 | 3.46 | 0.181 | 0.109 | 0.092 | 0.092 | 0.101 | |||
| 6 | 4.16 | 0.154 | 0.0804 | 0.0609 | 0.0561 | 0.0578 | 0.0638 | ||
| 7 | 4.85 | 0.133 | 0.0618 | 0.0423 | 0.0359 | 0.0347 | 0.0364 | ||
| 8 | 5.55 | 0.118 | 0.0489 | 0.0306 | 0.024 | 0.0217 | 0.0216 | 0.0229 | |
| 9 | 6.24 | 0.105 | 0.0397 | 0.0228 | 0.0166 | 0.0141 | 0.0133 | 0.0135 | 0.0145 |
| 10 | 6.93 | 0.0952 | 0.0329 | 0.0174 | 0.0118 | 0.00943 | 0.00844 | 0.00819 | 0.00846 |
| 11 | 7.62 | 0.0869 | 0.0276 | 0.0136 | 0.00864 | 0.0065 | 0.00552 | 0.00513 | 0.00509 |
| 12 | 8.32 | 0.08 | 0.0236 | 0.0108 | 0.00646 | 0.00459 | 0.00371 | 0.00329 | 0.00314 |
| 13 | 9.01 | 0.074 | 0.0203 | 0.00875 | 0.00492 | 0.00332 | 0.00255 | 0.00217 | 0.00199 |
| 14 | 9.7 | 0.0689 | 0.0177 | 0.00718 | 0.00381 | 0.00244 | 0.00179 | 0.00146 | 0.00129 |
| 15 | 10.4 | 0.0645 | 0.0156 | 0.00596 | 0.003 | 0.00183 | 0.00128 | 0.001 | 0.000852 |
| 16 | 11.1 | 0.0606 | 0.0138 | 0.005 | 0.00239 | 0.00139 | 0.000935 | 0.000702 | 0.000574 |
| 17 | 11.8 | 0.0571 | 0.0123 | 0.00423 | 0.00193 | 0.00107 | 0.000692 | 0.000499 | 0.000394 |
| 18 | 12.5 | 0.054 | 0.0111 | 0.00362 | 0.00158 | 0.000839 | 0.000519 | 0.00036 | 0.000275 |
| 19 | 13.2 | 0.0513 | 0.00998 | 0.00312 | 0.0013 | 0.000663 | 0.000394 | 0.000264 | 0.000194 |
| 20 | 13.9 | 0.0488 | 0.00906 | 0.0027 | 0.00108 | 0.00053 | 0.000303 | 0.000196 | 0.00014 |
| 21 | 14.6 | 0.0465 | 0.00825 | 0.00236 | 0.000905 | 0.000427 | 0.000236 | 0.000147 | 0.000101 |
| 22 | 15.2 | 0.0444 | 0.00755 | 0.00207 | 0.000764 | 0.000347 | 0.000185 | 0.000112 | 7.46e-05 |
| 23 | 15.9 | 0.0425 | 0.00694 | 0.00183 | 0.000649 | 0.000285 | 0.000147 | 8.56e-05 | 5.55e-05 |
| 24 | 16.6 | 0.0408 | 0.00639 | 0.00162 | 0.000555 | 0.000235 | 0.000117 | 6.63e-05 | 4.17e-05 |
| 25 | 17.3 | 0.0392 | 0.00591 | 0.00145 | 0.000478 | 0.000196 | 9.44e-05 | 5.18e-05 | 3.16e-05 |
| 26 | 18 | 0.0377 | 0.00548 | 0.00129 | 0.000413 | 0.000164 | 7.66e-05 | 4.08e-05 | 2.42e-05 |
| 27 | 18.7 | 0.0364 | 0.0051 | 0.00116 | 0.000359 | 0.000138 | 6.26e-05 | 3.24e-05 | 1.87e-05 |
| 28 | 19.4 | 0.0351 | 0.00475 | 0.00105 | 0.000314 | 0.000117 | 5.15e-05 | 2.59e-05 | 1.46e-05 |
| 29 | 20.1 | 0.0339 | 0.00444 | 0.000949 | 0.000276 | 9.96e-05 | 4.26e-05 | 2.09e-05 | 1.14e-05 |
| 30 | 20.8 | 0.0328 | 0.00416 | 0.000862 | 0.000243 | 8.53e-05 | 3.55e-05 | 1.69e-05 | 9.01e-06 |
| 31 | 21.5 | 0.0317 | 0.0039 | 0.000785 | 0.000215 | 7.33e-05 | 2.97e-05 | 1.38e-05 | 7.16e-06 |
| 32 | 22.2 | 0.0308 | 0.00367 | 0.000717 | 0.000191 | 6.33e-05 | 2.5e-05 | 1.13e-05 | 5.73e-06 |
参考
《数学之美》
http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html
https://zh.wikipedia.org/zh-cn/E_(%E6%95%B0%E5%AD%A6%E5%B8%B8%E6%95%B0)
https://en.wikipedia.org/wiki/Bloom_filter
---转载本站文章请注明作者和出处 二进制之路（binarylife.icu），请勿用于任何商业用途---