61

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

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

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

这两点是相同的还是不同的？

收益递减点出现在哪里？

如何找到这些点？

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

4

15 回答 15

74

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

两个文件永远不能压缩到相同的输出，所以你不能缩小到一个字节。一个字节怎么能代表你可以解压到的所有文件呢？

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

例子

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

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 解压器。如果你压缩一个大的像素矩形（特别是如果它有很多背景颜色，或者如果它是一个动画），你经常可以压缩两次，效果很好。（原因？你只有这么多位来指定回溯距离和长度，所以一个大的重复模式被编码成几个片段，这些片段是高度可压缩的。）
于 2009-07-22T16:11:31.230 回答
17

通常限制是一次压缩。一些算法会导致更高的压缩比，使用一个糟糕的算法然后使用一个好的算法通常会导致改进。但是首先使用好的算法是正确的做法。

对于一组给定的数据可以压缩多少，存在理论上的限制。要了解有关此的更多信息，您必须学习信息论。

于 2009-07-22T16:16:22.483 回答
16

一般来说，对于大多数算法，多次压缩是没有用的。不过有一个特殊情况。

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

于 2009-07-22T16:50:25.003 回答
9

假设我们有一个 N 位长的文件，我们想无损压缩它，这样我们就可以恢复原始文件。有 2^N 个可能的文件 N 位长，因此我们的压缩算法必须将这些文件之一更改为 2^N 个可能的其他文件之一。但是，我们不能用少于 N 位来表示 2^N 个不同的文件。

因此，如果我们可以获取一些文件并对其进行压缩，我们必须让一些文件的长度处于压缩状态，以平衡那些缩短的文件。

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

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

但是，压缩文件不是这些类型之一。如果压缩算法好的话，大部分结构和冗余都被挤出了，剩下的看起来很像随机性。

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

因此，压缩算法正常运行的次数是 1。

只有当我们谈论有损压缩时才会发生损坏。例如，您不一定能从 JPEG 文件中精确地恢复图像。这意味着 JPEG 压缩器可以可靠地缩短图像文件，但代价是无法准确恢复。我们通常愿意为图像执行此操作，但不是为文本，尤其是可执行文件。

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

于 2009-07-22T17:07:43.863 回答
5

如果算法很好，通常压缩一次就足够了。
实际上，多次压缩可能会导致大小增加

你的两点不一样。

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

现在让我们看看一些例外或变化，

  • 为了提高安全性，可以重复应用加密而不减小大小
    （实际上有时会增加大小）
  • 越来越压缩的图像、视频或音频文件
    会丢失数据（在某种意义上实际上是“损坏”）
于 2009-07-22T16:11:23.540 回答
3

您可以无限次压缩。但是，第二次和进一步压缩通常只会产生比前一次更大的文件。因此，多次压缩是没有意义的。

于 2009-07-22T16:13:30.197 回答
3

您可以根据需要多次压缩文件。但是对于大多数压缩算法，从第二次开始的压缩结果可以忽略不计。

于 2009-07-22T16:13:39.243 回答
3

我可以压缩文件多少次才不会变小？

一般来说，一个也没有。无论您使用哪种压缩算法，都必须始终存在一个根本不被压缩的文件，否则您总是可以通过相同的参数重复压缩直到达到 1 个字节。

在文件损坏之前我可以压缩多少次？

如果您用来压缩文件的程序完成了它的工作，那么文件将永远不会损坏（当然我正在考虑无损压缩）。

于 2009-07-22T16:22:17.433 回答
3

压缩（我认为是无损的）基本上意味着更简洁地表达一些东西。例如

111111111111111

可以更简洁地表示为

15 X '1'

这称为游程编码。计算机可以使用的另一种方法是查找文件中定期重复的模式。

这些技术的使用量显然是有限制的，例如游程编码不会影响

15 X '1'

因为没有重复的模式。类似地，如果模式替换方法将长模式转换为 3 字符模式，重新应用它几乎没有效果，因为唯一剩余的重复模式将是 3 长度或更短。由于各种开销，通常对已压缩的文件应用压缩会使其稍大一些。对压缩效果不佳的文件应用良好的压缩通常不如仅应用良好的压缩效果。

于 2009-07-22T16:39:23.687 回答
2

这是一个很好的问题。您可以从不同的角度查看文件。也许您先验地知道该文件包含算术级数。让我们将其视为“字节”、“符号”或“样本”的数据流。

一些答案可以给你“信息论”和“数理统计”请查看该研究人员的专着以获得全面深入的理解：

A.科尔莫哥洛夫

S.库尔贝克

С. 香农

N.维纳

信息论中的主要概念之一是熵。如果你有一个“字节”流......那个字节的熵不取决于你的“字节”或“样本”的值......如果仅由字节检索不同值的频率定义。最大熵用于完全随机数据流。当您的“字节”具有相同的值时，最小熵（等于零）必须存在。

它不会变小吗？

所以熵是每个“字节”的最小位数，在将信息写入磁盘时需要使用它。如果你使用上帝的算法，当然是这样。现实生活中的压缩无损启发式算法并非如此。

文件损坏？

我不明白这个问题的意义。您不能向磁盘写入任何位，并且您会将损坏的文件写入磁盘，其大小等于 0 位。当然它已损坏，但他的大小是零位。

于 2015-08-06T20:30:12.520 回答
1

这是最终的压缩算法（在 Python 中），通过重复使用它将任何数字字符串压缩到大小为 0（留给读者如何将其应用于字节串作为练习）。


def compress(digitString):
    if digitString=="":
        raise "already as small as possible"
    currentLen=len(digitString)
    if digitString=="0"*currentLen:
        return "9"*(currentLen-1)
    n=str(long(digitString)-1); #convert to number and decrement
    newLen=len(n);
    return ("0"*(currentLen-newLen))+n; # add zeros to keep same length

#test it
x="12";
while not x=="":
    print x;
    x=compress(x)

程序输出 12 11 10 09 08 07 06 05 04 03 02 01 00 9 8 7 6 5 4 3 2 1 0 然后是空字符串。它不会在每次传递时压缩字符串，但它会通过足够多的传递将任何数字字符串压缩到零长度字符串。确保写下通过压缩器发送它的次数，否则您将无法取回它。

于 2009-12-18T00:07:44.023 回答
1

我想说的是，压缩本身的限制并没有真正适应最大的限制。由于每个像素或书面语言都是黑色或书写轮廓。人们可以编写一个程序，可以完美地反编译成它本来的样子，比如一本书，但可以将像素模式和单词压缩成一个更好的压缩系统。含义它可能需要更长的时间来压缩，但是随着系统文件变得越来越大，P 和 R 和 q 的重复字母以及黑白偏差可以以指数方式压缩成一个复杂的自动公式。mhcien 不需要数据来理解，它只是可以让游戏制作出高度压缩的模式。这反过来又允许我们人类创建一个定制的压缩阅读引擎。这意味着现在我们拥有真正的压缩能力。设计一个完整的引擎，可以还原用户端的信息。该引擎有自己的最佳语言，没有空格，只需填充最小集合的黑白像素框，甚至编写自己的模式语言。Nad 因此它可以同时为最优化的性能，在它关闭时给出一个唯一的密码或解压缩公式，因此文件被最佳压缩并具有唯一的密码，以便引擎稍后解压缩它。机器可以进行无限次迭代以进一步压缩文件。这就像有一本打开的书，将当前所有的人类书面故事都放在一张 A4 纸上。我不知道，但这是另一个理论。所以发生的是拆分体积，因为去压缩的公式会有自己的大小，文件夹的命名和/或图标信息都具有大小，因此可以进一步将每种形式的数据放入信息字符串中。唔..

于 2019-10-01T03:19:17.490 回答
0

这完全取决于算法。换句话说，问题可能是首先使用此算法可以压缩文件多少次，然后是下一个...

于 2010-08-16T19:42:44.750 回答
0

使用“双表或交叉矩阵”的更高级压缩技术的示例还消除了算法中多余的不重要符号

[上一个例子] 以游程编码（可能是最简单有用的压缩）为例。

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

该系列字节可以压缩为：

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

[变成] 04.43.51.52 值 4.4.**-2 压缩

使用附加符号作为替代值的进一步压缩

04.ABC 值 4.4.**-2 压缩

于 2013-05-14T19:44:03.963 回答
0

理论上，我们永远不会知道，这是一个永无止境的事情：

在计算机科学和数学中，术语充分就业定理被用来指代一个定理，表明没有算法可以最佳地执行某些专业人士完成的特定任务。这个名字的出现是因为这样的定理确保有无限的空间来不断发现新技术来改进至少某些特定任务的完成方式。例如，编译器编写者的充分就业定理指出，不存在可证明完美的大小优化编译器，因为编译器的这种证明必须检测非终止计算并将它们减少到单指令无限环形。因此，一个可证明完美的大小优化编译器的存在将意味着停止问题的解决方案，这是不存在的，使证明本身成为一个不可判定的问题。

（来源）

于 2014-01-30T05:01:00.880 回答