随机数据的实用压缩技术

Question

所以昨天我在压缩整数序列的问题上提出了一个问题（链接），大多数评论都有一个相似的观点：如果顺序是随机的（或者更糟，数据完全随机），那么一个值k需要log2(k)位。我也在这个网站的其他问题中看到了类似的回复。现在，我希望这不是一个愚蠢的问题，如果我将该序列序列化到文件中，然后运行gzip，那么我确实可以实现压缩（并且根据我允许gzip运行的时间，我可能会得到高压缩）。能有人解释一下这个事实吗？

提前感谢。

- jplot

---

对于给定的压缩器，存在一组将被压缩和一组不会被压缩的输入；这对于任何压缩程序（包括gzip）都是正确的。不存在完美的压缩器，可以为任何输入产生压缩输出（很容易证明）。假设我们有一个随机序列生成器，它可以产生n次相同的数字，甚至基于RLE的压缩器也可以有效地压缩这个序列。 - Kwariz

你写了_serialized_，如果你写了一个只包含字符'0'到'9'（10个不同字符）的文件，任何实际的压缩程序都能够将其压缩，至少可以压缩一半吧。 - Kwariz

点赞你的问题，因为它不是愚蠢的，而是一个合法的问题。你对无限压缩随机数据的犹豫显然表明你已经尝试理解问题，足以注意到并关注矛盾之处。 - Cory Klein

Answer 1

我的猜测是，你在随机文件上实现压缩是因为你没有使用最优的序列化技术，但是没有更多细节就不可能回答你的问题。压缩后的文件中是否有n个在[0，k)范围内的数字，小于n*log2(k)位？（也就是说，n*log256(k)字节）。如果是这样，gzip是否能够为您生成的所有随机文件都做到这一点，还是仅仅偶尔做到？

让我注意一件事：假设你对我说，“我使用mt19937 prng [1]和uniform_int_distribution(0, 255)生成了一个随机八位字节文件。我的文件的最优压缩是什么？”现在，我的答案可以合理地是：“大约80位”。我需要复制你的文件只需要：

种子prng使用的值，很可能是32位整数[2]；和

文件的长度，可能适合48位。

如果我可以用80位数据再现文件，那就是最佳压缩。不幸的是，这不是一种通用的压缩策略。gzip几乎不可能能够找出您使用了特定的prng来生成文件，更不用说它将能够反向工程种子（尽管这些事情在理论上至少是可行的；Mersenne twister不是一个加密安全的prng）。

另一个例子是，通常建议在加密之前压缩文本；结果会比加密后压缩要短得多。但事实上，加密增加的熵非常小；最多只增加加密密钥中的位数。尽管如此，生成的输出很难与随机数据区分开来，gzip将难以对其进行压缩（尽管它经常设法挤出几个位）。

---

注意1：注意：这里都是关于C++11/Boost的术语。mt19937是梅森旋转算法伪随机数生成器（PRNG）的一个实例，其周期为2^19937-1。

注意2：梅森旋转算法的状态实际上是624个字（19968位），但大多数程序使用较少的位数进行种子初始化。也许您使用了64位整数而不是32位整数，但它并没有太大的影响。

- rici

---

如果您使用/dev/random，则数据是真正的随机数。它不是由伪随机过程生成的，因此没有压缩的种子。它通过从操作系统中的随机事件收集熵来工作。 - Mark Adler

@MarkAdler，好的。我否认了吗？我只是提到“最优压缩”的概念有一些有趣的特殊情况，其中伪随机数生成器就是其中之一。确实，你可以使用/dev/random，但你可能会发现它作为gzip测试数据源相当昂贵。（熵不便宜。）如果你使用/dev/urandom，那么它并不是“真正”的随机数。如果你使用/dev/random来产生种子（更常见的情况），那么就有一个种子，我们又回到了最优压缩是种子大小的问题，最大值为19968位（对于mt19937）。 - rici

我只是为这个问题的读者提供信息。这个问题是关于随机数据而不是伪随机数据的，我指出许多系统都有这样的数据来源。顺便说一下，我经常使用 /dev/random 进行测试，它看起来并不昂贵。对于我生成的数据量，它似乎从未用尽随机数据池中的随机数据。我从未见过 /dev/random 和 /dev/urandom 之间的速度差异。（/dev/urandom 会从熵池中获取数据直到用尽，然后才切换到伪随机生成器。）我一次提取数百万字节的数据。 - Mark Adler

@MarkAdler，我猜你的机器比我的小笔记本有更多的熵。我刚试着从/dev/random中提取160个字节（使用dd），结果命令锁住了，直到我把鼠标摇了10秒钟才恢复。我曾看到很多Apache实例因为初始化SSL时缺乏熵而阻塞在启动状态，当设置使用/dev/random。显然你的情况可能不同（也适用于阅读此评论的其他人）。 - rici

我错误地认为Mac OS X使用相同的要求来实现这些设备，但事实并非如此。我从未看到过随机和urandom之间的区别，因为在Mac OS X中，它们是同一物的不同名称。它们是伪随机生成器，经常从内核的随机抖动测量中获得熵重新种植。感谢您提供的性能信息，促使我阅读我的文档。 - Mark Adler

Answer 2

如果我把这个序列序列化到文件上，然后运行gzip压缩这个文件，那么我确实可以实现压缩。所谓的"it"是指随机选择的字节（每个字节在0..255中均匀分布），如果将它们输入到gzip或任何压缩器中，则极少数情况下可能会获得一些压缩，但大多数时候会获得一些扩展。

- Mark Adler

Answer 3

如果数据是真正的随机数据，平均而言，没有任何压缩算法能够对其进行压缩。但是，如果数据具有某些可预测的模式（例如，如果符号的概率取决于先前出现在数据中的k个符号），许多（基于预测的）压缩算法将会成功。

- krjampani

---

我不这么认为，除非你是在暗示这种模式是由于伪随机性引起的。但是这样的模式非常难以检测（至少我不认为有任何压缩算法可以利用这一点）。 - krjampani

@amit 再次强调，显然会有一些重复（如果禁止重复，那就不是随机的了），但需要更多的重复才能抵消压缩开销。在总共100位中，一个6位模式的三次重复（其中只能省略2次）最多可以为您节省12位存储空间。而且，每生成100位中这个特定模式再重复三次，比任何出现超过一次的模式都要少得多。 - user395760

任何压缩算法在完全随机数据上的预期压缩比不能小于1。但是，个别示例可能会压缩得很好。问题在于对于完全随机的数据，任何算法更有可能扩展而不是压缩。 - Keith Randall

@amit：你的测试不正确。你的FileWriter正在使用默认字符编码，因此你没有为每个16位char写入的文件写入16位数据。你只写了2000000字节的随机数据，但是你的未压缩文件大小约为4.8M字节。 - Keith Randall

gzip 可以压缩随机生成的比特串，这有什么问题吗？gzip 的设计是用于某种输入，但并不限于此...随机比特串生成器产生可压缩的比特串的概率不为0。 - Kwariz