random - 为什么 ZIP 在 System.Random 生成的序列上如此高效 - Kolmogorov 复杂性在哪里？

Question

我正在生成随机数序列。序列仅包含 0 和 1。我将每个序列放入单独的文本文件中，然后尝试将该文件存档(为 .zip 格式)。我使用 System.Random 生成每个序列的元素。乍一看，这些序列似乎确实是随机的。

奇怪的是，无论生成的 .txt 文件的大小是多少，压缩的 .zip 文件的大小始终等于 .txt 文件大小的相同比例 ~17%。

但从理论上讲，对于真正随机的序列，压缩的 .zip 文件的大小应几乎等于 .txt 文件的大小 - 即，几乎不应该进行压缩。否则，序列至少是部分可预测的(这在这个类似“翻转硬币”的实验中是不可能的)。

所以这意味着我的“归档器”知道如何识别该序列是由 System.Random 中实现的特定伪随机生成器生成的。

我有两个问题:

1. 如何生成存档器无法压缩的伪随机序列？也许有一些已知的技巧？

2. 为什么 17% 的比例如此稳定，并且不依赖于序列的长度(即 .txt 文件的大小)。

感谢您的帮助!

Answer 1

您声明您只在文本文件中保存 0 和 1。因此，在二进制级别，您的文件完全由位序列 00110000 的出现组成。和00110001 (对应于字符 '0' 和 '1' 的 ASCII 值)。这是非常浪费的，一个好的压缩算法会意识到它可以用更少的位数来表示这些 8 位模式中的每一个:最好是 1，但可能是 1 和 2 位的组合以获得约 18% 的压缩比你引用的。

如果要创建无法压缩的序列，则需要生成随机无界值，并将它们作为二进制写入文件。例如:

byte[] buffer = new byte[1024 * 1024];   // for a 1 MB file
(new Random()).NextBytes(buffer);        // each byte gets a random value from 0 to 255
File.WriteAllBytes(target, buffer);