zip压缩背后的概念是什么？

Question

压缩文件的概念是什么？我可以理解去除空格等操作的概念，但在解压缩过程中需要添加多少/在哪里添加这些空格呢？

字节流压缩的基本过程是什么？

- Neil Barnwell

---

听起来你需要去维基百科阅读一些内容。 - skaffman

简单！将其转换成二进制并去除零。 - Johnno Nolan

http://www.howstuffworks.com/file-compression.htm - Johnno Nolan

@skaffman 是的，但 Spolsky 希望 Stack Overflow 成为编程问题的规范解答网站，因此在这里提问很合适。我不打算写压缩算法，我只是对它的基本原理感兴趣。现在我明白了。其他对此感兴趣并在 Stack Overflow 上询问的人也会明白。 - Neil Barnwell

只是谷歌一下，阅读维基百科，RTFM答案从来不是SO上正确的答案（或评论）。 - EBGreen

@John Nolan - 如果您删除数字“1”，那么您可以获得更好的压缩比率。但是请保留数字“2”，因为它们很重要。 - David

Answer 1

一个很好的起点是查找哈夫曼压缩方案。哈夫曼背后的基本思想是，在给定文件中，一些字节比其他字节更频繁地出现（在明文文件中，许多字节根本不会出现）。与其花费8位来编码每个字节，为什么不使用较短的位序列来编码最常见的字符，并使用较长的序列来编码不常见的字符（这些序列是通过创建哈夫曼树确定的）。

一旦你掌握了使用这些树根据字符频率对文件进行编码/解码的方法，那么想象一下，你开始处理单词频率——而不是将"they"编码为4个字符的序列，为什么不考虑它由于频率而被视为单个字符，允许它在哈夫曼树中被分配自己的叶子。这或多或少是ZIP和其他无损类型压缩的基础——它们在文件中寻找常见的“单词”（字节序列）（包括仅由1个字节组成的序列，如果足够常见），并使用树来对它们进行编码。然后zip文件只需要包含树信息（每个序列的副本和它出现的次数）即可允许树进行重构并解码文件的其余部分。

跟进：

为了更好地回答最初的问题，无损压缩的思想不是去除空白空间，而是去除冗余信息。

如果你创建了一个用于存储音乐歌词的数据库，你会发现大量的空间被用来存储重复出现多次的副歌。为了节省这些空间，你可以在第一次出现副歌前面加上“CHORUS”这个词，然后每次副歌需要重复时，只需使用“CHORUS”作为占位符（事实上，这基本上就是LZW压缩的思想——在LZW中，每行歌词前都有一个数字。如果某行歌词在歌曲的其他地方重复出现，只需显示其数字即可，而不必写出整行歌词）。

- David

---

提供答案摘要并附上进一步阅读链接，而不仅仅是将OP发送到维基/谷歌，这是提供优秀答案的好方法。 - EBGreen

更基本的压缩可能是RLE压缩，但它并不能解释更高级的压缩方式。 - Paul de Vrieze

作为额外的资源，您可以添加一个链接或提到Security Now！播客。在第205集中，Steve Gibson讨论了压缩理论及其随时间演变的情况。这是转录链接：http://www.grc.com/sn/sn-205.txt - EBGreen

实际上，如果您使用动态哈夫曼压缩，甚至不需要存储树。在编码时，您从一些默认树开始。然后，您使用它对单个字符/单词进行编码，基于已经读取的字符/单词的频率更新树，并处理下一个字符/单词，直到达到输入的末尾。在解码时，您从相同的初始树开始，并根据输入更新它。 - Filip Navara

为了准确起见，zip通常不是基于LZW的，而是基于LZ77 +（非动态）哈夫曼编码。 LZ77是压缩算法，它消除了字母重复序列（例如“oh baby baby”中的一个冗余“baby”），而Huffman则是对LZ77输出的有效编码。 - r0u1i

Answer 2

基本概念是，不使用8位来表示每个字节，而是对于更常出现的字节或字节序列使用较短的表示方法。

例如，如果文件只由0x41（A）字节重复16次组成，则不要将其表示为8位序列01000001，而应缩短为1位序列0。然后文件可以通过0000000000000000（十六个0）来表示。因此，由0x41字节重复16次组成的文件可以通过由0x00字节重复两次组成的文件来表示。

所以这里的情况是，对于这个文件（0x41重复16次），位01000001与位0相比没有提供任何额外信息。因此，在这种情况下，我们丢弃多余的位，以获得更短的表示方法。

这就是压缩的核心思想。

再举一个例子，考虑八个字节的模式。

0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48

现在请把它重复2048次。按照上述方法的一种是使用三位表示字节。

000 0x41
001 0x42
010 0x43
011 0x44
100 0x45
101 0x46
110 0x47
111 0x48

现在，我们可以通过重复2048次三字节模式0x05 0x39 0x77，将以上字节模式表示为00000101 00111001 01110111。

但更好的方法是表示字节模式。

0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48

通过单个比特0的方式。然后，我们可以通过重复2048次0来表示上述字节模式，这将成为重复256次的字节0x00。现在我们只需要存储字典。

0 -> 0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48

我们使用字节模式0x00重复256次，并将文件从16,384字节压缩到（取决于字典）256字节。

简而言之，这就是压缩的工作原理。整个过程就是在给定文件中找到短小高效的字节和字节序列的表示方法。这是一个简单的想法，但细节（即找到表示方法）可能会非常具有挑战性。

例如，请参见：

1. 数据压缩
2. 行程长度编码
3. 霍夫曼压缩
4. 香农-费诺编码
5. LZW

- jason

Answer 3

压缩的概念基本上是统计学的。如果你有一系列字节，字节N实际上是X的机会取决于前面的字节0..N-1的值分布。没有压缩，你为每个可能的值X分配8位。有了压缩，分配给每个值X的字节数量取决于估计的概率p(N,X)。

例如，给定一个序列"aaaa"，压缩算法可以将高值分配给p(5,a)，将较低的值分配给p(5,b)。当p(X)高时，分配给X的比特串将很短，当p(X)低时，使用长比特串。通过这种方式，如果p(N,X)是一个好的估计，那么平均比特串将比8位短。

- MSalters