python zlib - 压缩字符串vs香农熵的大小

我想更好地理解压缩算法（如zlib）的输出如何与理论预期进行比较。所以我有几个问题。（1）首先我想检查一下，我是否正确计算了压缩率。说我希望压缩的1000对那些阵列，我可以做以下python zlib - 压缩字符串vs香农熵的大小

# encode the array such that len(s) == 1000 bytes 
s = np.ones(1000, dtype='uint8').tostring() 

# compress using the python zlib (deflate) 
comp_s = zlib.compress(s, 9) 
# giving comp_s = 'x\xdacd\x1c\x05\xa3`\x14\x0cw\x00\x00\xa7e\x03\xe9' 

comp_ratio = len(comp_s)/len(s) 
# giving 17/1000

因此我的第一个问题：被comp_s编码，使得其长度对应于字节数？我无法弄清楚这个字符串是如何编码的。如果我做sys.getsizeof(comp_s)我发现它的大小是54字节而不是17字节？由于getsizeof返回python对象的大小，所以它肯定高估了字符串的大小，我是否正确假设sys.getsizeof(s) - sys.getsizeof('')是正确的方式？至少可以得到与len()相同的结果。（2）压缩序列的大小应大于（或等于）其香农熵。对于以50:50概率出现的1和0的随机二进制序列，每个数字的信息数量是1位（根据定义h = - p log p - (1-p)log(1-p)）。由于一个真正的随机序列是不可压缩的，如果我生成一个长度为n的随机二进制序列，我期望通过增加一个随机数字，得到的长序列在压缩后平均大1位。

当我做了以下

rawsize = range(1, 100000, 1000) 
compsize = [] 
for l in rawsize: 
    s = np.random.randint(0, 2, l, dtype='uint8').tostring() 
    comp_s = zlib.compress(s, 9) 
    # note: I compress again to achieve better compression when l is large 
    comp_s = zlib.compress(comp_s, 9) 
    compsize.append(len(comp_s))

如果我绘制compsize/rawsize我发现弯道0.155意思接近恒定值（如果我理解正确地）由0.155增加一个数字的信息量增大-Bits。我不明白这一点，因为压缩似乎比理论预期好得多。

为了进一步理解这一点，我还比较了1和0的二进制序列情况下的压缩字符串大小，其中1的出现概率为0<p<1。然后，字符串（每个数字）的压缩大小应跟踪香农熵，并且在p=0.5处最大为(=1)。我发现压缩字符串大小（每个数字）的曲线远低于香农熵，并且如果我将香农熵乘以0.155，它们大致位于彼此之上。

显然有一些规范化因素我没有考虑，但我无法弄清楚它的基本原理。我还试图以编码使用16，32和64位无符号整数的原始序列，发现比compsize/rawsize变得大致0.176，0.2，0.23分别所以看起来，通过在1和0表示加入一个字节我们贡献了大约0.25位的额外信息，这也是好奇。

任何建议将非常有用！

来源

2017-05-23 stefano

我把这个作为'1'位长音的说明，正如你所说的那样，对于真正的随机序列，这不是常见的情况。 – Uriel

zlib引入了6个字节的开销，而deflate又增加了几个字节。当你双重压缩时，你会得到两次开销字节。 –

的开销不大（根据文件，最高为0.03％）。我所报告的问题是，我似乎压缩得比我应该的效率高得多 - 约6倍。作为一个旁注，在这种情况下，我试图对'np.random.bytes（N）'和'compsize/rawsize'接近'1'做同样的处理，也许它会给出一些有用的提示。 – stefano

当调用np.random.randint(0, 2, l, dtype='uint8').tostring()，你是不是获得的0和1的随机序列，但随机序列的8位二进制表示0和1的：10000000和00000000。每8位差不多有1个是随机的，其他7个都是0。我想最佳比例应该是1/8左右，加上一些开销。

事实上，如果使用np.random.randint(0, 256, 100000, dtype='uint8').tostring()代替，comp_ratio是〜1。

来源

2017-05-24 16:35:09 user1620443

谢谢你，这是我得出的结论，当我认为比率大致为log2（k）/ 8，其中k是字典大小（在这种情况下最大的整数，对于k = 256，那么我得到1）。那么正确的做法是采用长度为N的1s和0s的序列's1'并将每个8的块转换为相应的整数，从而获得长度为N/8的序列's2'？然后通过压缩's2'，zlib应该尝试压缩对应于's1'的位数组。 – stefano

是的，这将是一个很好的解决方案。 – user1620443

你会发现，当你添加熵的一位，输入要添加0.155 字节压缩的输出，这是1.24 位。

来源

2017-05-25 08:23:16

python zlib - 压缩字符串vs香农熵的大小

回答

相关问题