algorithm - 随机数据的实用压缩

Question

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

提前致谢。

Answer 1

我的猜测是，您正在对随机文件进行压缩，因为您没有使用最佳序列化技术，但如果没有更多详细信息，就不可能回答您的问题。 [0, k) 范围内的 n 个数字的压缩文件是否小于 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。)

再比如，一般建议在加密前对文本进行压缩；结果将比加密后压缩短很多。但事实是加密增加的熵很少；最多，它添加加密 key 中的位数。尽管如此，生成的输出很难与随机数据区分开来，并且 gzip 将难以压缩它(尽管它通常设法挤出一些位)。

---

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

注意 2:梅森扭曲器的状态实际上是 624 个字(19968 位)，但大多数程序使用较少的位来播种。也许您使用了 64 位整数而不是 32 位整数，但这并没有太大改变答案。