ent 程序如何计算“最佳压缩”？

Question

的ENT程序可以在一个文件中运行以得到输出如下面的：

熵 = 每字节 4.731183 位。

最佳压缩将把这个 15731 字节文件的大小减少 40%。

15731 个样本的卡方分布为 235086.62，随机超过该值的次数少于 0.01%。

数据字节的算术平均值为 87.3796（127.5 = 随机）。Pi 的蒙特卡罗值为 4.000000000（误差 27.32%）。序列相关系数为 0.140065（完全不相关 = 0.0）。

程序如何确定“最佳压缩”可以实现什么？

我注意到这个估计通常甚至被 gzip 击败。

Answer 1

熵给出了文件中包含的各种信息，即文件中存在的不同值的数量的表示；最佳压缩，或者更准确地说，最佳编码，将使用完全相同的存储量。

在您的情况下，文件当前的长度为 15,731 字节，但每字节存储 4.731183 位；因此，它总共包含 4.731183 × 15,731 位信息，即74,426.24 位信息，或 9,303.28 字节。最佳压缩将产生 9,304 字节的文件，这是原始文件的 59.14%。不参考文件长度也可以做同样的计算：4.733183是8的59.16%。表示为减少，(8 - 4.733183)是8的40.84%，也就是在 中进行的计算ent，将百分比截断为整数：

           printf("Entropy = %f bits per %s.\n", ent, samp);
           printf("\nOptimum compression would reduce the size\n");
           printf("of this %lld %s file by %d percent.\n\n", totalc, samp,
            (short) ((100 * ((binary ? 1 : 8) - ent) /
                  (binary ? 1.0 : 8.0))));

现实世界的压缩工具通过以更简洁的方式表示重复来解决这个问题。比较结果

$ (printf %5000s; printf %5000s | tr ' ' '1') | ent
Entropy = 1.000000 bits per byte.

Optimum compression would reduce the size
of this 10000 byte file by 87 percent.

$ (printf %5000s; printf %5000s | tr ' ' '1') | gzip | wc -c
48

输入由大量字节组成，但只有两个不同的值，数量相等，因此熵为每字节 1 位。ent认为可以使用每字节 1 位对输入进行编码，即少八倍。gzip然而，代表空格和空格的运行，并生成一个即使带有gzip标题也小 208 倍的文件。