在bloom filter的错误率f最小时，也就是最优的情况下，位数组的任意概率为0.5，在这种情况下，如果根据Claude Shannon编码原理，位数组将无法得到任何压缩效果，因为Claude Shannon编码原理的基本思想为：

    假设符号 Fn 在整条信息中重复出现的概率为 Pn，则该符号的熵也即表示该符号所需的位数位为：En = - log2(Pn)，整条信息的熵也即表示整条信息所需的位数为：E = ∑En。如果每个位的取值只有0,1两种情况，那么E0 = - log2(0.5) = 1，E1 = - log2(0.5) = 1，整个长度为m的位数组需要的位数为：E = E0*m*0.5+E1*m*0.5 = m，其中m*0.5代表0和1出现的次数。

    然而，事实并非如此，因为我们之前是在已知位数组大小m和集合元素个数n的情况下，求出最优的Hash函数个数k = (m/n)ln2，进而得到最小的错误率p = 0.5。所以该p得出的背景是把Bloom filter看成是没有压缩的，在位数组固定的情况下的到的最优Hash函数数目和最低错误率.

    所以压缩之前，Bloom filter有四个重要的参数，错误率f，hash函数个数k，位数组大小m，集合元素个数n。在对位数组进行压缩之后Bloom filter有五个重要的参数，错误率f，hash函数个数k，压缩前位数组大小m，压缩后的位数组大小z，集合元素个数n。在引入压缩的概念之后，我们考虑的问题变成在给定的压缩后位数组大小z，以及集合元素个数m的前提下，如何确定最优的Hash数目以及压缩前的位数组大小m，使得f最小。

    假设我们有一个很好的压缩算法使得z = mH(p)，其中的H(p) = -∑ pi*log2(pi)是信息熵函数，其中的pi是位数组中可能出现的数值的概率，取以2为底的对数是因为如果2^n =X，那么logX = n，所以信息熵就是二进制字符集在去掉冗余度后的二进制编码的位数，冗余度是通过统计每个字符出现的概率获得。

    所以这里的H(p) = -plog2p – (1-p)log2(1-p)，p ≈ e-kn/m是位数组某一位为0的概率，进而得到错误率的函数f = (1 - p)k = (1 - p)(-lnp) (m/n)，再将m=z/H(p)代入得到:

    由于z和n固定，所以要得到最小的错误率f，假设β = fn/z，那么求得β的最小值时，f也同样为最小的，所以将H(p) = -plog2p – (1-p)log2(1-p)代入β = fn/z中可得：

    将上式中的括号2内部的式子化简，可以的大β的最小值等价于求下式的最大值：

     对上式求导，得

    令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值，不仅可以获得好的传输压缩率同时还能获得更小的错误率。

    参考文献：Michael Mitzenmacher, Member, IEEE, 2002Compressed Bloom Filters，IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 10, NO. 5, OCTOBER