在《什么是布隆过滤器(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),请勿用于任何商业用途---