Compressed Bloom Filter - Bloom Filter - CSDN...

Compressed Bloom Filter
焦萌 2007年2月8日 在前面的讨论中，我们都只将Bloom Filter作为一种表示集合的数据结构。但在网络应用中，Bloom Filter经常被当作节点之间交换信息时传递的消息。从这个角度考虑，我们自然希望消息在传递之前能够被压缩。 那么Bloom Filter到底能不能被压缩？在Bloom Filter概念和原理一文中，我们知道当Bloom Filter的错误率最低时，位数组中任意一位是0的概率p = 1/2。也就是说，在错误率最低时位数组中0和1的概率各占一半。根据Claude Shannon 编码原理，位数组将不可能获得任何压缩的效果。 然而事实并不是这样，因为p = 1/2的结论是这样作出的：在已知位数组大小m和集合元素个数n的情况下，我们求出最优的哈希函数个数k，使得错误率降到最低。这样求出的k = (m/n) ln2，位数组中任意一位是0的概率p = 1/2。这个分析思路没有考虑压缩，而是把Bloom Filter作为一种内存中的数据结构，在分配的位数组大小固定的情况下求哈希函数个数的最优值。 从上面的分析可以看出，在不考虑压缩的情况下，Bloom Filter有三个重要的性能参数：错误率f、哈希函数个数k和位数组大小m。在引入压缩之后，性能参数变成了四个：错误率f、哈希函数个数k、未压缩的位数组大小m和压缩后的位数组大小z。在多了一个因素之后，整个分析的思路会大不一样，因此不能简单地延续前面的结论继续分析。 下面我们就分析一下引入压缩之后，如何选择各个性能参数以达到最优的结果。在不考虑压缩的情况下，我们考虑的问题是：给定m和n，求最优的k，使得f最小。在考虑压缩的情况下，压缩后的位数组大小z比压缩前的大小m更重要，因为它是我们实际在网络上传输的消息大小。基于这个原因，我们考虑的问题就变成了：给定z和n，求最优的k和m，使得f最小。 首先假设我们有一个最优的压缩算法，使得z = m H(p)，其中H(p) = -plog2p – (1-p)log2(1-p)是信息熵函数（p是位数组某一位为0的概率）。在Bloom Filter概念和原理一文中，我们知道p ≈ e-kn/m，从而有k ≈ (-lnp) (m/n)。于是错误率f就可以写成p的函数f = (1 - p)k = (1 - p)(-lnp) (m/n)再将m = z / H(p)带入上式，可得f = (1 - p)-(zlnp/nH(p))由于z和n固定，且z ≥ n，要求f的最小值，即求β = fn/z的最小值。将H(p) = -plog2p – (1-p)log2(1-p)代入可得 
要求β的最小值，即求指数的最小值，也等于求 
的最大值。对上式求导，得 
令dγ/dp = 0，得p = 1/2。并且可以发现当p < 1/2时dγ/dp小于0，当p > 1/2时dγ/dp大于0。因此当p = 1/2时γ取得最小值，即β和f取得最大值。这个结论非常有意思：当p = 1/2，即k = (ln2) (m/n)时，在不考虑压缩的情况下错误率最低，而在考虑压缩的情况下错误率反而最高。换句话说，压缩总是能够降低错误率。 由于压缩总能降低错误率，因此对比标准的Bloom Filter，Compressed Bloom Filter性能更加出色。而且由于Compressed Bloom Filter增加了一个性能参数，它在各个性能参数的权衡上更加灵活。例如，用同样的位数表示集合元素，Compressed Bloom Filter的错误率更低，所用的哈希函数个数更少： 
上表中的第一列就是标准的Bloom Filter，没有压缩（m/n = z/n），每一个元素用8位表示。后两列是经过压缩的Bloom Filter，同样每一个元素用接近8位表示，但用的哈希函数个数更少，错误率更低。又例如，达到同样的错误率，Compressed Bloom Filter每一个元素所占位数更少，哈希函数个数也更少： 
 总之，在网络应用环境下，按( m/ n) ln2选择最优k 值不会获得任何的传输压缩率。相反，若增大本地节点表示信息的位数和选择较小的k值，不仅可以获得好的传输压缩率同时还能获得更小的错误率。 参考论文：Compressed Bloom Filters 本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/jiaomeng/archive/2007/02/08/1505299.aspx