随机数据的实际压缩

Question

所以昨天我问了一个关于压缩整数序列的问题(链接),大多数评论都有类似的观点:如果顺序是随机的(或者最差的,数据是完全随机的)那么就必须用log2(k)来解决值为k的位.我也在本网站的其他问题中阅读了类似的回复.现在,我希望这不是一个愚蠢的问题,如果我采取该序列并将其序列化为文件然后我在此文件上运行gzip然后我实现压缩(并且根据我允许gzip运行的时间我可能会得到高压缩).有人可以解释这个事实吗？

提前致谢.

Answer 1

我的猜测是你在随机文件上实现压缩,因为你没有使用最佳的序列化技术,但没有更多的细节,你就无法回答你的问题.n个数字在[0,k]范围内的压缩文件是否小于n*log2(k)位？(即,n*log256(k)字节).如果是这样,gzip是否设法为您生成的所有随机文件执行此操作,或偶尔执行此操作？

让我注意一件事:假设你对我说,"我通过使用uniform_int_distribution(0,255)和mt19937 prng [1]生成了一个随机八位字节的文件.我文件的最佳压缩是什么？" 现在,我的答案可能是合理的:"大约80位".我需要重现你的文件

• 你用来为prng播种的值,很可能是一个32位整数[2]; 和

• 文件的长度,可能适合48位.

如果我可以重现给定80位数据的文件,那就是最佳压缩.不幸的是,这不是通用的压缩策略.gzip极不可能发现你使用特定的prng来生成文件,更不用说能够对种子进行逆向工程了(尽管这些事情至少在理论上是可以实现的; Mersenne twister不是一个加密安全的prng.)

再举一个例子,通常建议在加密前压缩文本; 结果将比加密后的压缩要短得多.但事实是加密增加了很少的熵; 最多,它会添加加密密钥中的位数.尽管如此,结果输出很难与随机数据区分开来,而gzip很难压缩它(尽管它经常设法挤出几个比特).

注1:注意:这都是c ++ 11/boost术语.mt19937是Mersenne twister伪随机数生成器(prng)的一个实例,其周期为2 ^ 19937 - 1.

注2:梅森捻线机的状态实际上是624个字(19968位),但大多数程序使用较少的位来播种它.也许您使用了64位整数而不是32位整数,但它并没有多少改变答案.