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

Question

zip 压缩背后的概念是什么？我可以理解删除空白空间等的概念，但大概必须添加一些东西来说明在解压过程中需要添加多少/哪里可用空间？

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

Answer 1

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

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

跟进:

为了更好地回答最初的问题，无损压缩背后的想法与其说是删除空白，不如说是删除冗余信息。

如果您创建一个数据库来存储音乐歌词，您会发现大量空间被用来存储重复多次的合唱。您可以简单地将 CHORUS 一词放在合唱线的第一个实例之前，而不是使用所有空间，然后每次重复合唱时，只需使用 CHORUS 作为占位符(事实上，这几乎就是这个想法LZW 压缩之后 - 在 LZW 中，歌曲的每一行前面都会显示一个数字。如果一行在歌曲中稍后重复，则不要写出整行，只显示数字)