» 关于Bloom Filter 补充说几句

关于Bloom Filter 补充说几句

July 3, 2007 at 10:40 pm · Filed under CompSci

今天谷歌黑板报上吴军研究员深入浅出的讲解了Bloom Filter. 因为前段时间我在拼写检查器的一点注记当中也提到了Bloom Filter, 所以补充说几句.

1. 黑板报上说:

对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, …,F8）产生八个信息指纹（f1, f2, …, f8）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, …,g8。

其实这句话有点绕人, 本质上来说, 就是有8个不同的Hash 函数, 能把这个 X 映射到八个自然数. (实际上对于好的Hash 函数, 比如 MD5, 算一次, 截成八段, 就是八个很好的Hash 函数了, 不一定要8个随机数产生器.)

2. 黑板报上说:

布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是，它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，因为有可能某个好的邮件地址正巧对应个八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。在上面的例子中，误识概率在万分之一以下。

实际上, 这说的就是 Bloom filter 不会有Flase Negative, 可能有 False Positive. 我们来算一下概率. 假设Hash 函数是理想的, 也就是说, 函数值是均一分布的, Bloom Filter 长为 $m$ bits, 那么, 对于一个输入, 某一位没被设置的概率是 $1-\frac{1}{m}$ , 而我们一共有 $k$ 个独立不相关的 Hash 函数, 所以这一位保持为 $0$ 的概率应该是 $(1-\frac{1}{m})^k$ . 因此, 假如我们一直插入了 $n$ 个元素进来, 某一位是 $0$ 的概率就是 $(1-\frac{1}{m})^{kn}$ . 用 $1$ 减去它, 就是这一位是 $1$ 的概率了. 那么, 如果我们这时候开始测试元素是否在集合中而发生了错误, 就是说, 明明元素不在集合里面, 可是Hash 过后每一位都是 $1$ , 这个的概率就是 $\left(1-\left(1-\frac{1}{m}\right)^{kn}\right)^k \approx \left(1-e^{-kn/m}\right)^k$ . 这个题目中, $m$ =16G, $n$ =1G, $k$ =8, 我算出来的错误率是0.0005744 (Linux Bash: echo “(1-e(-8*1/16))^8″|bc -l), 大于万分之一了. [Wikipedia 和我的算法一样]

Permalink

7 Comments »

Solrex Yang said,

July 3, 2007 @ 11:21 pm

呵呵，你还仔细算了
我看的时候也觉得，为什么叫做随机数产生器？大概是翻译理解问题吧，如果让他写英文，肯定是 hash 了。
还有概率问题，嘿嘿，我潜意识里觉得这个概率应该更大(觉得比你算出来的还大 ^_^)，不过没算。看来还是动手比较好。
zeaster said,

July 5, 2007 @ 9:47 pm

我看了wikipedia上文章，有一点不明白：
“当k=mln2/n时，那个概率值最小”，这个是怎么解出来的？

我根据(1-e^(-kn/m))^k的一阶导数等于0，算出如果设b=e^(n/m)，则有
(b-1)^(b-1)=b^(b-2)，可是这个方程的解b=2是怎么解出来的？
像这种含有x^x的方程数学上有什么标准解法吗？
Eric said,

July 5, 2007 @ 10:58 pm

回复 zeaster:

我不太清楚您的求导过程是不是有问题, 用你的符号, 我求导数并且让一阶导数为0, 最后一步我能够得到:
$b^{-k} ln(b^{-k}) = (1-b^{-k}) ln (1-b^{-k})$ ,
两边的函数形式一样, 而且都是增函数, 比较一下就知道, 让 $b^{-k} = 1-b^{-k}$ 即可, 也就是 $b^{-x} = \frac{1}{2}$ . 下面的结论就和 wikipedia 一样了.
因此, 好像用不到你说的那个复杂的方程.
zeaster said,

July 6, 2007 @ 12:10 am

汗，是我推导错了

ps:
下面是我试试tex，看在评论中这么用对不
$b=e^{kn/m}$
jayven said,

October 11, 2007 @ 9:14 pm

我也有点不明白，其实上边公式算出来的应该是在k,m,n情况下，判断某个元素属于集合的概率吧？它不是应该等于正确判断概率加上误判概率才对吗？
Eric said,

October 11, 2007 @ 10:10 pm

Think about it again :) The equation here is correct.
jayven said,

October 12, 2007 @ 12:30 am

莫非是因为实际上有无穷个元素会碰撞在一起（映射到相同的8个为1的bit上），所谓正确只是其中的一个，因此正确判断概率可视为0？