基于压缩文件是一个新的二进制文件的想法,为什么我不能通过反复压缩来减小 Zip 的大小 - 直到最终文件非常小?
答案1
基于压缩文件是一个新的二进制文件的想法,为什么我不能通过再次压缩并连续将其压缩为一个非常小的文件来减小它的大小?
因为压缩是基于寻找模式和减少相似数据的基础上进行的。
例如,放射线剂量率(游程编码)是一种简单的压缩方法,其中检查数据并将类似数据的运行压缩如下:
AAABCEEEJFFYYYYYYYYYYOOAAAAGGGGGAAA
becomes
3ABC3EJ2F10YOO4A5G3A
如您所见,通过用数据和出现次数的计数替换重复数据,您可以将此特定示例从 35 个字节减少到 20 个字节。这不是巨大的减少了,但仍然小了 42%。此外,这是一个小的、人为的例子;更大的、真实的示例可以有更好的压缩效果。(之所以OO
保留 ,是因为用 替换它2O
不会节省任何东西。)
文本文件通常压缩效果很好,因为它们往往有很多可以压缩的模式。例如,单词这在英语中非常常见,因此你可以删除每个单词的实例,这些单词的标识符只有单个字节(甚至更少)。你也可以使用以下方法压缩更多内容:部分类似的单词,如cAKE
,,,,等等。bAKE
shAKE
undertAKE
那么为什么不能压缩已经压缩过的文件呢?因为当你进行初始压缩时,你删除了图案。
看一下压缩的 RLE 示例。如何进一步压缩它?没有相同的数据运行需要压缩。事实上,当你尝试压缩已经压缩的文件时,你最终可能会得到一个更大文件。例如,如果你强制对上述示例进行重新编码,则可能会得到如下结果:
131A1B1C131E1J121F11101Y2O141A151G131A
现在,压缩数据(运行计数)本身被视为数据,因此最终得到的文件比开始时更大。
你可以尝试使用不同的压缩算法,因为一种压缩算法的输出可能是另一种算法的素数,但这种情况通常不太可能。
当然,这一切都是为了无损压缩解压后的数据必须与原始数据完全相同。有损压缩,通常可以删除更多数据,但质量会下降。此外,有损压缩通常使用某种基于模式的方案(它不仅有的如果你仔细研究一下数据(例如,丢弃数据),你会发现最终还是会到达一个根本没有模式可寻的地步。
答案2
如果所有压缩文件在再次压缩后都减小了大小(或大小不大于其父文件),那么在某个时候大小将变为 0,这不可能。如果这是真的,我们几乎根本不需要文件存储。
无损数据压缩算法无法保证所有输入数据集都压缩换句话说,对于任何无损数据压缩算法,都会有一个输入数据集在经过算法处理后不会变小,并且对于任何使至少一个文件变小的无损数据压缩算法,都会有至少一个文件变大。这可以通过初等数学中的计数论证轻松证明,如下所示:
- 假设每个文件都表示为某个任意长度的位串。
- 假设有一种压缩算法,可以将每个文件转换成不长于原始文件的输出文件,并且至少有一个文件将被压缩成比原始文件短的输出文件。
- 假设 M 为最小数,使得存在长度为 M 位的文件 F,该文件 F 可压缩为更短的文件。假设 N 为 F 压缩版本的长度(以位为单位)。
- 因为 N < M,所以每个长度为 N 的文件在压缩过程中都会保持其大小。有 2 N个这样的文件。加上 F,这就产生了 2 N +1 个文件,它们都压缩为长度为 N 的2 N个文件之一。
- 但是 2 N小于 2 N +1,因此根据鸽巢原理,一定存在某个长度为 N 的文件,它同时是压缩函数对两个不同输入的输出。该文件无法可靠地解压缩(应该产生两个原始文件中的一个?),这与算法无损的假设相矛盾。
- 因此,我们必须得出结论:我们最初的假设(压缩函数不会使文件变得更长)必然是不正确的。
https://en.wikipedia.org/wiki/Lossless_compression#Limitations
答案3
经过最佳压缩的文件将不包含任何模式或任何可以减少的内容。
让我们想象一个包含此内容的简单文件。
AAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBB
CCCCCCCCCCCCCCCCCCCC
如果我们压缩它,我们可以说它是 20 个 A,换行符,然后是 20 个 B,换行符,然后是 20 个 C。或者类似的东西20xA\n20xB\n20xC\n
。一旦我们完成了第一次压缩,就没有新的模式需要压缩了。每一位信息都是独一无二的。
答案4
我想说,你无法压缩随意的二进制文件在很大程度上——比如 JPEG 图像、x264 视频等等。特别是因为你想重建你的原始文件确切地(一点一点地)你需要一个无损压缩。1
这种有限压缩的原因在此说明维基百科关于熵的文章 它量化了消息中包含的信息的预期价值:
熵有效地限制了最强无损(或接近无损)压缩的性能,这可以在理论上通过使用典型集合来实现,或者在实践中使用 Huffman、Lempel-Ziv 或算术编码来实现。(...)
1 JPEG 图像之所以能够实现非常强的“压缩”,是因为有些信息被丢弃了(以人眼乍一看无法识别的方式);有损压缩)。