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

Question

zip压缩背后的概念是什么？我可以理解删除空白空间等概念，但可能需要添加一些内容来说明在解压缩过程中需要添加多少/哪些空闲空间？

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

Answer 1

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

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

追问：

为了更好地回答原来的问题，背后无损压缩的想法是不是要删除空的空间，但除去redundent信息。

如果你创建了一个数据库来存储音乐歌词，你会发现很多空间被用来存储重复多次的合唱。你可以简单地将CHORUS放在合唱线的第一个实例之前，而不是使用所有这些空间，然后每次重复合唱时，只需使用CHORUS作为占位符（实际上，这几乎是主意在LZW压缩之后 - 在LZW中，歌曲的每一行将显示一个前面的数字，如果一首歌曲在歌曲后面重复，而不是在整行后面写出数字）

Answer 2

压缩之间的概念是基本上是统计学的。如果你有一系列的字节，实际上字节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位。

Answer 3

基本概念是，不是使用八位来表示每个字节，而是使用更短的表示来更频繁地发生字节或字节序列。

例如，如果文件仅仅由字节的0x41的（A）重复16次，然后代替表示它作为8位的序列01000001缩短到1比特序列0。然后该文件可以由0000000000000000（十六个0 s）表示。那么重复十六次的字节0x41的文件可以由重复两次的由字节0x00组成的文件来表示。

所以我们在这里是这个文件（0x41重复十六次）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 

现在，我们可以通过00000101 00111001 01110111表示上述字节图案（这是三字节图案0x05 0x39 0x77）重复2048次。

但更好的方法是由单个位0代表字节模式

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

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

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

和字节模式0x00重复256次，我们的压缩文件从16,384字节（模字典）256个字节。

简而言之，压缩是如何工作的。整个业务归结为寻找给定文件中字节和字节序列的简短高效表示。这是一个简单的想法，但细节（找到代表）可能会非常具有挑战性。

见例如：

1. Data compression
2. Run length encoding
3. Huffman compression
4. Shannon-Fano coding
5. LZW