压缩文件多少次？

Question

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

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

• 它没有变小？
• 文件变坏了？

这两点是相同还是不同？

收益递减点在哪里出现？

如何找到这些要点？

我不是在谈论任何特定的算法或特定文件.

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个字节时,我们将开始增长两个字节.随着文件变大,增长将变得更糟.

对压缩程序有一个逆风 - 元数据.而且,对于真正的压缩器,标题会添加到文件的开头.这意味着最终文件将随着每次额外压缩而开始增长.

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

以下是我可以想到多个压缩工作的一些情况.

1. 我曾在一张装有磁盘的Amiga杂志上工作过.当然,我们把磁盘装到鳃上.我们使用的工具之一允许您打包可执行文件,以便在运行时,它可以解压缩并自行运行.因为解压缩算法必须在每个可执行文件中,所以它必须小而简单.我们经常通过压缩两次得到额外的收益.解压缩在RAM中完成.由于读取软盘的速度很慢,我们通常也会提速!
2. Microsoft支持bmp文件上的RLE压缩.此外,许多文字处理器都进行了RLE编码.RLE文件几乎总是由更好的压缩器可压缩.
3. 我工作的很多游戏都使用了一个小巧,快速的LZ77解压缩器.如果压缩一个大的矩形像素(特别是如果它有很多背景颜色,或者它是一个动画),你可以经常压缩两次,效果很好.(原因？你只有很多位来指定回溯距离和长度,所以一个大的重复模式被编码成几个部分,而那些部分是高度可压缩的.)

Answer 2

通常,限制是一次压缩.一些算法导致更高的压缩比,并且使用差的算法,然后使用良好的算法通常会导致改进.但是首先使用好的算法是正确的做法.

理论上限制了一组给定数据的压缩程度.要了解更多相关信息,您必须学习信息理论.

Answer 3

通常,对于大多数算法,压缩不止一次是没有用的.但是有一个特例.

如果您有大量重复文件,则zip格式将单独压缩,然后您可以压缩第一个zip文件以删除重复的zip信息.具体来说,对于7个大小为108kb的相同Excel文件,使用7-zip压缩它们会产生120kb的存档.再次压缩导致18kb存档.过去你会得到递减的回报.

Answer 4

假设我们有一个N位长的文件,我们想要无损压缩它,以便我们可以恢复原始文件.有2 ^ N个可能的文件N位长,因此我们的压缩算法必须将这些文件中的一个更改为2 ^ N个可能的其中一个.但是,我们不能在少于N位的情况下表达2 ^ N个不同的文件.

因此,如果我们可以获取一些文件并压缩它们,我们必须有一些长度处于压缩状态的文件,以平衡那些缩短的文件.

这意味着压缩算法只能压缩某些文件,实际上它必须延长一些文件.这意味着,平均而言,压缩随机文件不能缩短它,但可能会延长它.

实用的压缩算法有效,因为我们通常不使用随机文件.我们使用的大多数文件都有某种结构或其他属性,无论它们是文本还是程序可执行文件还是有意义的图像.通过使用良好的压缩算法,我们可以大大缩短我们通常使用的类型的文件.

但是,压缩文件不是这些类型之一.如果压缩算法很好,大部分结构和冗余都被挤掉了,剩下的就像随机性一样.

正如我们所见,没有压缩算法可以有效地压缩随机文件,这也适用于随机文件.因此,尝试重新压缩压缩文件不会显着缩短它,并且可能会将其延长一些.

因此,压缩算法可以有效运行的正常次数是一次.

腐败只发生在我们谈论有损压缩的时候.例如,您无法从JPEG文件中精确恢复图像.这意味着JPEG压缩器可以可靠地缩短图像文件,但这样做的代价是无法完全恢复它.我们经常愿意为图像而不是文本,特别是不是可执行文件.

在这种情况下,没有腐败开始的阶段.它会在您开始压缩它时开始,并在您压缩它时变得更糟.这就是为什么优秀的图像处理程序可以让您指定制作JPEG时所需的压缩程度:这样您就可以平衡图像质量与文件大小.您可以通过考虑文件大小的成本来找到停止点(对于网络连接而言,这通常比存储更重要)与降低质量的成本.没有明显正确的答案.

Answer 5

如果算法很好,通常压缩一次就足够了.
_{事实上,多次压缩可能会导致尺寸增加}

你的两点不同.

• 反复进行压缩并且在尺寸减小方面没有改善
  是预期的理论条件
• 重复压缩导致损坏
  可能是实现中的错误(或者算法本身)

现在让我们看一些例外或变体,

• 为了提高安全性,可以重复应用加密而不减小尺寸
  (实际上有时会增加尺寸)
• 越来越压缩的图像,视频或音频文件
  将丢失数据(在某种意义上有效地"损坏")