为什么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(其对应于字符的ASCII值'0'和'1').这是非常浪费的,并且一个好的压缩算法会意识到它可以用较少的位数表示这些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);