compression - 一个文件可以压缩多少次？

Question

我正在考虑压缩，似乎必须对可以应用于它的压缩进行某种限制，否则它将是单个字节。

所以我的问题是，我之前可以压缩文件多少次:

• 它不会变小吗？
• 文件已损坏？

这两点是相同还是不同？

yield 递减点出现在哪里？

如何找到这些点？

我不是在谈论任何特定的算法或特定文件，只是一般性的。

Answer 1

对于无损压缩，您知道通过重新压缩文件可以获得多少次效果的唯一方法就是尝试。这将取决于压缩算法和您要压缩的文件。

两个文件永远无法压缩到相同的输出，因此您无法压缩到一个字节。一个字节怎么能代表你能解压到的所有文件呢？

二次压缩有时有效的原因是压缩算法无法做到无所不知的完美压缩。在它必须完成的工作和完成它所需的时间之间需要进行权衡。您的文件正在从所有数据更改为有关您的数据和数据本身的数据组合。

示例

以游程编码(可能是最简单有用的压缩)为例。

04 04 04 04 43 43 43 43 51 52 11 字节

这一系列字节可以压缩为:

[4] 04 [4] 43 [-2] 51 52 7 字节(我将元数据放在括号中)

其中括号中的正数是重复计数，括号中的负数是发出找到的下一个 -n 字符的命令。

在这种情况下，我们可以再尝试一种压缩:

[3] 04 [-4] 43 fe 51 52 7 个字节(fe 是 -2，被视为二进制补码数据)

我们什么也没得到，我们将在下一次迭代中开始成长:

[-7] 03 04 fc 43 fe 51 52 8 字节

一段时间内，每次迭代我们都会增加一个字节，但实际上会变得更糟。一个字节只能容纳负数到-128。当文件长度超过 128 字节时，我们将开始增加两个字节。随着文件变大，增长会变得更糟。

压缩程序面临着逆风——元数据。而且，对于真正的压缩器， header 附加在文件的开头。这意味着最终文件将随着每次额外的压缩而开始增长。

<小时/>

RLE 是一个起点。如果想了解更多请查看LZ77 (它会回顾文件以查找模式)和 LZ78 (构建字典)。像 zip 这样的压缩器经常尝试多种算法并使用最好的一种。

以下是我能想到的多重压缩发挥作用的一些情况。

1. 我在一家附带光盘的 Amiga 杂志工作。自然地，我们将磁盘包装得严严实实。我们使用的工具之一可让您打包可执行文件，以便在运行时解压并自行运行。由于解压缩算法必须存在于每个可执行文件中，因此它必须小而简单。我们经常通过两次压缩获得额外的增益。解压是在 RAM 中完成的。由于读取软盘的速度很慢，因此我们的速度也经常得到提高!
2. Microsoft 支持对 bmp 文件进行 RLE 压缩。此外，许多文字处理器都进行 RLE 编码。 RLE 文件几乎总是可以通过更好的压缩器进行显着压缩。
3. 我制作的许多游戏都使用了小型、快速的 LZ77 解压缩器。如果您压缩一个大的像素矩形(特别是如果它有很多背景颜色，或者它是一个动画)，您通常可以压缩两次以获得良好的结果。 (原因？您只有这么多位来指定回溯距离和长度，因此单个大型重复模式被编码为多个片段，并且这些片段是高度可压缩的。)