algorithm - 如何计算布隆过滤器百分比

我正在经历Hadoop In Action并碰到了Bloom Filter的解释，其中说:

(1 – exp(-kn/m))k

k = ln(2) * (m/n) ≈ 0.7 * (m/n)

因此，在这里它说误报率是0.6185 * 8，即4.948，但是文件怎么说呢，大约是2％？有人可以帮我计算百分比吗？

基于David的回复的详细说明:

根据书中的解释:

n = 10,000,000 = 1e7

m/n = 8 which means m = 8*n

k = ln(2) * (m/n), Value of ln(2) is 0.693 = 0.7, so value of k = 0.7 * (m/n)

现在来到我的表情:

 (1 – exp^(-kn/m))^k = (1 - exp^(-0.7))^(0.7*8) = (1 - 0.4965)^(5.6) = (0.5034)^(5.6) = 0.0214 (Here ^ represents power)

要计算百分比，我们必须乘以100。

所以百分比是0.0214*100 = 2%

最佳答案

正确的公式是

                k
(1 – exp(-kn/m)) ,

将带括号的表达式取幂k而不是乘以k。近似值主要是假设布隆过滤器的每个单元格的值是独立的(由于写入exp会产生一些误差，而不是真正的单单元格概率)；假阳性率是k个细胞都被标记的概率。

对于给定的示例，这是如何计算误报概率。

>>> from math import *
>>> n = 1e7
>>> m = 8*n
>>> k = log(2) * (m/n)
>>> (1 - exp(-k*n/m)) ** k
0.021415847120683718

要将概率转换为百分比，请乘以100。

>>> 100*_
2.1415847120683718

关于algorithm - 如何计算布隆过滤器百分比，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27228043/