对于任何真实数据集,数据压缩比的最小可能值是什么

我正在为嵌入式硬件压缩器编写ZLIB就像使用deflate算法压缩给定输入流一样。

在进一步说明之前,我想解释数据压缩率。 数据压缩比定义为未压缩大小和压缩大小之间的比率。

在此处输入图像描述

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

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

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

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

请提供反馈。 任何帮助,将不胜感激。 如果可以提供对这样的数据集的引用,那将是很好的。

编辑:
@MSalters评论指出硬件压缩器没有正确地遵循deflate规范,这可能是微代码中的一个错误。

deflate算法具有与ZLIB算法类似的方法。 它使用3位标头,当后面的块存储长度为前缀但未压缩时,低两位为00

这意味着最坏的情况是一个字节输入,最多可以吹6个字节(3位报头,32位长度,8位数据,5位填充),因此最差比率为1/6 = 0.16。

这当然是假设最佳编码器。 次优编码器将为该一个字节发送霍夫曼表。

我无法从你的问题中判断出你是否正在使用zlib。 如果您正在使用zlib,它会提供一个函数deflateBound() ,它可以完全满足您的要求,采用未压缩的大小并返回最大压缩大小。 它考虑了如何在计算正确的标题和尾部大小时使用deflateInit()deflateInit2()初始化deflate流。

如果您正在编写自己的deflate,那么您将已经知道最大压缩大小取决于您允许它使用存储块的频率。

更新:确定硬件平减器的最大数据扩展的唯一方法是获得所使用的算法。 然后通过检查,您可以确定它为随机数据发出存储块的频率。

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

这仅在硬件收缩算法表现良好时才有效,这意味着如果存储的块较小,它将不会写入固定或动态的收缩块。 如果表现不佳,那么所有的赌注都会被取消。

因为鸽子的原则

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

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

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

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