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

Question

可以在文件上运行恩特程序以提供输出，如下所示：

熵=每字节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位对输入进行编码，即减少8倍。然而，gzip代表空格和空格的运行，并且生成一个文件，即使使用gzip头也要小208倍。