文件压缩如何工作

大多数压缩程序都使用LZ自适应词典算法收缩文件。“ LZ”是指Lempel和Ziv，算法的创建者和“字典”是指分类数据片。

安排词典的系统各不相同，但可能与编号列表一样简单。当我们浏览肯尼迪的著名单词时，我们挑选出重复的单词并将其放入编号的索引中。然后，我们简单地编写数字，而不是写出整个单词。

因此，如果这是我们的词典：

我们的句子现在读到：“ 1不是2 3 4 5 6 7 8-1 2 8 5 6 7 3 4”

如果您知道系统，则可以仅使用此词典和数字模式轻松地重建原始短语。这就是您的扩展计划电脑当它扩展下载的文件时。您可能还遇到了打开自己的压缩文件。为了创建此类文件，程序员在压缩文件中包括一个简单的扩展程序。下载后，它会自动重建原始文件。

但是，我们实际上为这个系统节省了多少空间？“ 1不是2 3 4 5 6 7 8-1 2 8 5 6 7 3 4”肯定比“不要问您的国家可以为您做什么；问您可以为您的国家做什么；”但是请记住，我们需要保存字典本身以及文件。

在实际的压缩方案中，弄清楚各种文件要求将相当复杂；但是，出于我们的目的，让我们回到一个想法，即每个角色和每个空间都占用一个单元的内存。我们已经看到整个短语占用了79个单位。我们的压缩句子（包括空间）占用37个单位，字典（单词和数字）也占用37个单位。这使我们的文件大小为74，因此我们没有将文件大小减少太多。

但这只是一句话！您可以想象，如果压缩程序通过肯尼迪的其余演讲工作，它将发现这些单词，而其他人则重复了很多次。而且，正如我们在下一部分中看到的那样，它也将重写词典以使最有效的组织成为可能。

在上一个示例中，我们挑选了所有重复的单词，然后将它们放在字典中。对我们来说，这是撰写词典的最明显方法。但是，压缩程序的看法很大：它没有任何单独单词的概念 - 它只寻找模式。为了尽可能减少文件大小，它仔细选择了字典中包含哪些模式。

如果我们从这个角度了解这个短语，我们最终会以完全不同的词典。

如果压缩程序扫描了肯尼迪的短语，那么它将遇到的第一个冗余将只有几个字母。在“问你什么”中，有一个重复的字母“ t”的模式，然后是一个空间 - 在“不是”和“什么”中。如果压缩程序将其写给字典，则每次a t thake thake a thake a thake a the a the a the the the the the space都可以写入“ 1”。但是，在这个简短的短语中，这种模式不足以使其成为值得进入的条件，因此该程序最终会覆盖它。

该程序可能会注意到的下一件事是“ OU”，它都出现在“您的”和“国家”中。如果这是一个更长的文档，则将此模式写入字典可以节省很多空间 - “ OU”是英语中相当普遍的组合。但是，随着压缩程序通过这句话运行，它将很快发现一个字典条目的更好选择：不仅重复了“ ou”，而且整个单词“您的”和“乡村”都重复了，实际上它们是重复的一起，作为“您的国家”一词。在这种情况下，该程序将覆盖“ OU”的字典条目，并在“您的国家 /地区”的条目中覆盖字典。

也重复了“可以做的”一词，一次是“您的”，然后是“您”，然后给我们一个重复的“可以为您做的”。这使我们能够编写具有一个数字值的15个字符（包括空格），而“您的国家”只能让我们编写具有一个数字值的13个字符（带空格），因此该程序将覆盖“您的国家”条目为“国家，“然后为“可以为您做的”编写一个单独的条目。该程序以这种方式进行，拾取所有重复的信息，然后计算其应写入字典的模式。这种重写字典的能力是LZ自适应词典算法。通过讨论可以看到，程序的实际执行方式非常复杂data-compression.com。

无论您使用哪种特定方法，此深度搜索系统都可以使您比仅挑选单词更有效地压缩文件。使用上面选择的模式，并为空格添加“ __”，我们提出了这个较大的词典：

这个较小的句子：“ 1NOT__2345 __--__ 12354”

该句子现在占据了18个单位的记忆，我们的字典占用41个单位。因此，我们将总文件大小从79个单位压缩到59个单位！这只是压缩短语的一种方法，而不一定是最有效的方法。（看看您是否可以找到更好的方法！）

那么这个系统有多好？这减少文件比率取决于许多因素，包括文件类型，文件大小和压缩方案。

在世界上大多数语言中，某些字母和单词通常以相同的模式出现在一起。由于这种冗余率很高，文本文件压缩很好。对于良好的文本文件而言，典型的减少50％或更多。最多编程语言之所以非常多余，是因为它们使用相对较小的命令集合，这些命令经常以设定的模式一起使用。包含许多独特信息的文件，例如图形或mp3文件，由于它们不重复多个模式（在下一节中详细介绍），因此无法对此系统进行太多压缩。

如果文件具有大量重复模式，则降低速率通常随文件大小而增加。您只需查看我们的示例即可看到这一点 - 如果我们有更多的肯尼迪演讲，我们将能够更频繁地参考字典中的模式，从而从每个条目的文件空间中获得更多信息。同样，在更长的工作中可能会出现更多普遍的模式，从而使我们能够创建一个更有效的词典。

这种效率也取决于特定算法由压缩程序使用。一些程序特别适合在某些类型的文件中拾取模式，因此可能会更简洁地压缩它们。其他人则在字典中有字典，可能会为较大的文件有效地压缩，但对于较小的文件而言，这可能不会有效。尽管这种类型的所有压缩程序都具有相同的基本想法，但执行方式实际上存在很大的差异。程序员一直在努力构建一个更好的系统。

我们在这里讨论的压缩类型称为无损压缩，因为它使您可以精确地重新创建原始文件。所有无损压缩都是基于将文件分解为“较小”形式进行传输或存储的想法，然后将其放回另一端，以便可以再次使用。

有损压缩工作方式有很大不同。这些程序只是消除了“不必要的”信息，从而量身定制文件，使其较小。这种类型的压缩被用于减少位图图片的文件大小，这往往相当笨重。要查看其工作原理，让我们考虑一下您的计算机如何压缩扫描照片。

无损压缩程序对这种类型的文件无法做得太多。尽管图片的大部分看起来可能相同 - 例如，整个天空是蓝色的 - 大多数单独的像素都有些不同。为了使这张图片较小而不损害分辨率，您必须更改某些像素的颜色值。如果图片有很多蓝天，该程序将选择一种可用于每个像素的蓝色。然后，程序重写文件，以使每个天空像素的值都回到此信息。如果压缩方案效果很好，您将不会注意到更改，但是文件大小将大大减少。

当然，通过有损耗的压缩，您无法在压缩后取回原始文件。您被压缩程序重新解释原始内容所困扰。因此，您不能将这种压缩使用用于需要精确复制的任何内容，包括软件应用程序，数据库和总统就职演讲。

有关文件压缩和相关主题的更多信息，请查看下一页上的链接。

最初出版：2001年1月18日