怎样才能将文件压缩到小于其熵？

Question

我创建了一个包含100,000个数字的文件，这些数字是从集合{1,2,3,4,5,6,7,8}中均匀绘制的(概率为1/8)。

当看一下我硬盘上这个文件的大小时，它是293KB(千字节)，这是有意义的，因为一个人需要3位来“识别”一个介于1和8之间的数字，3*100,000 =300KB。

接下来，我使用Win-zip压缩文件，发现文件被压缩到只有57KB！这怎么可能呢?因为我希望我在抽奖时使用的随机数生成器是理想的。这意味着序列应该是真正随机的，因此文件的大小应该由它的熵(即300KB)给定。

Answer 1

我担心你对某些概念感到困惑。

3位乘以100,000得到300,000 位，字节有8位，大约相当于37.5KB。这与300KB相去甚远。

(在任何情况下，如果您要创建“一个包含100,000个数字的文件”，那么您的硬盘上没有魔法仙女，它会计算出您的数字的最小和最大范围，并使用表示所有数字所需的最小位数将它们存储在文件中。)

因此，让300KB与10万个一位数的熵完全无关，这一点非常重要。

您完全没有告诉我们您是如何创建该文件的，所以它的文件格式是一个谜，但我们可以进行一些简单的计算和猜测: 293 KB乘以1024等于300,000，所以您拥有的是一个300,000字节的文件。这意味着您将为每个数字写入3个字节。这意味着您已经将这些数字作为文本写入文本文件中，每个数字后面跟着一个逗号，然后跟着一个空格，或者每个数字后面跟着一个回车符和换行符，或者类似的东西。

文本文件格式在存储空间方面非常浪费。

所以，是的，这是一个高度可压缩的文件，大部分由相同的字节组成，甚至不相同的字节(数字)都映射到每个字节只有3位，所以难怪整个文件压缩得如此好。

在这个问题的提出过程中，没有任何自然规律受到损害。