c - 对于任何真实数据集，数据压缩比的最小可能值是多少

Question

我正在ZLIB为嵌入式硬件压缩器编写 API，它使用 deflate 算法来压缩给定的输入流。

在继续之前，我想解释一下数据压缩率。数据压缩率定义为未压缩大小与压缩大小之间的比率。

压缩比通常大于一。这意味着压缩数据通常小于未压缩数据，这是压缩的重点。但情况并非总是如此。例如使用ZLIB在某些 Linux 机器上生成的库和伪随机数据，压缩比大致为 0.996。这意味着 9960 字节压缩成 10000 字节。

我知道ZLIB通过使用类型 0 块来处理这种情况，它只返回具有大约 5 字节标头的原始未压缩数据，因此它只提供 5 字节开销，最多 64KB 数据块。这是这个问题的智能解决方案，但由于某种原因，我不能在我的 API 中使用它。我必须提前提供额外的安全空间来处理这种情况。

现在，如果我知道已知的最小数据压缩率，那么我很容易计算出我必须提供的额外空间。否则为了安全起见，我必须提供超出需要的额外空间，这在嵌入式系统中可能至关重要。

在计算数据压缩率时，我不关心页眉、页脚、极小的数据集和系统特定的细节，因为我是单独处理的。我特别感兴趣的是，是否存在任何最小大小为 1K 并且可以提供比0.99使用 deflate 算法更低的压缩比的真实数据集。在这种情况下，计算将是：
压缩率 = 未压缩大小/（使用 deflate 的压缩大小，不包括页眉、页脚和系统特定开销）

请提供反馈。任何帮助，将不胜感激。如果可以提供对此类数据集的引用，那就太好了。

编辑：
@MSalters 评论表明硬件压缩器没有正确遵循 deflate 规范，这可能是微码中的错误。

Answer 1

因为鸽子原则

http://en.wikipedia.org/wiki/Pigeonhole_principle

您将始终拥有被压缩的字符串和被扩展的字符串

http://matt.might.net/articles/why-infinite-or-guaranteed-file-compression-is-impossible/

从理论上讲，您可以使用 0 熵数据（无限压缩比）实现最佳压缩，使用无限熵数据（AWGN 噪声，因此压缩比为 0）实现最差压缩。

Answer 2

我无法从您的问题中判断您是否使用 zlib。如果您使用的是 zlib，它提供了一个函数 ，deflateBound()它完全符合您的要求，采用未压缩大小并返回最大压缩大小。它考虑了 deflate 流是如何使用deflateInit()或deflateInit2()计算正确的标头和尾标大小进行初始化的。

如果您正在编写自己的 deflate，那么您将根据允许它使用存储块的频率知道最大压缩大小是多少。

更新： 确定硬件压缩器的最大数据扩展的唯一方法是获取使用的算法。然后通过检查，您可以确定它多久会为随机数据发出存储块。

唯一的选择是经验的和不可靠的。您可以向硬件压缩器提供随机数据，并检查结果。您可以使用infgen反汇编 deflate 输出并查看存储的块及其大小。然后你可以为展开写一个线性边界公式。然后为加法和乘法项添加一些余量，以涵盖您在测试中未观察到的情况。

这仅在硬件放气算法表现良好时才有效，这意味着如果存储的块更小，它将不会写入固定或动态的放气块。如果表现不佳，则所有赌注都将取消。

Answer 3

放气算法具有与 ZLIB 算法类似的方法。它使用 3 位标头，低两位00是存储以下块时以长度为前缀但未压缩。

这意味着最坏的情况是一个字节的输入会爆炸到 6 个字节（3 位标头，32 位长度，8 位数据，5 位填充），因此最差的比率是 1/6 = 0.16。

这当然是假设一个最佳编码器。次优编码器会为该字节传输 Huffman 表。