5

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

提前致谢。

4

3 回答 3

7

我的猜测是您正在对随机文件进行压缩，因为您没有使用最佳的序列化技术，但是如果没有更多细节，就不可能回答您的问题。[0, k) 范围内的 n 个数字的压缩文件是否小于 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 是Mersenne twister伪随机数生成器 (prng) 的一个实例，其周期为 2^19937 - 1。

注 2：Mersenne twister 的状态实际上是 624 个字（19968 位），但大多数程序使用较少的位来播种它。也许您使用了 64 位整数而不是 32 位整数，但这并没有太大改变答案。

于 2012-09-21T21:07:02.197 回答
4

如果我采用该序列并将其序列化为一个文件，然后在该文件上运行 gzip，那么我确实实现了压缩

它是什么”？如果您获取随机字节（每个字节均匀分布在 0..255 中）并将它们提供给 gzip 或任何压缩器，您可能会在极少数情况下获得少量压缩，但大多数时候您会获得少量扩展.

于 2012-09-21T20:20:25.117 回答
3

如果数据真的是随机的，平均来说没有压缩算法可以压缩它。但是，如果数据具有一些可预测的模式（例如，如果一个符号的概率取决于数据中出现的先前 k 个符号），许多（基于预测的）压缩算法将成功。

于 2012-09-21T17:20:11.753 回答