可视化解释压缩算法的工作原理

正文

压缩技术在生活中无处不在，硬盘上存储数据、发送电视信号、网页传输、流媒体、电子游戏……现代计算几乎没有一个重要领域不使用压缩技术。

那么压缩技术到底是什么？

无论你使用过很多年的电脑压缩软件还是从没想过这个问题，本文将尝试解释，当你压缩一个文件或传输一段视频时，其中的数据到底发生了什么变化。我们将探寻这些重要问题的答案，在此过程中，也许会提出一些新的问题。

• 对被压缩对象进行压缩，意味着什么？
• 如何能将目标对象变得比原来更小？
• 如何具体实现压缩技术

让我们来一一解答吧！

via GIPHY

基础知识

在研究压缩技术和数字信息之前，这里有一段通俗易懂的压缩技术介绍。让我们来看看下方的英文字母：

看看我们用来表现这个单词（Tree）的字符，加起来一共是 4 个：

看起来还行。如果我们用汉字会发生什么？

天哪！只用了一个字符！我们有改变它要传达的意思和任何信息么？并没有。但是，我们降低了75%的网页空间，来表达“tree”的含义。那么我们到底做了什么？

没什么神奇的 —— 我们只是用另一种方式去表达了这个含义。我们选择了一种不同的、更加高效的信息表现方式。Spoiler：接下来是本文最重要的部分，请仔细阅读。

那么，如果是像素级的图片呢？

你肯定会觉得惊讶，如何将上面的例子应用于严谨的数字图像数据呢？让我们来看一下最近很流行的一类数据 —— 图片。现阶段，让我们先从简单的像素级图片入手，而不是一上来就尝试去压缩一张高分辨率的 Instagram 图片或其他类似的复杂图片。

不怎么好看对吗？因为这是我自己画的。上面是一个 10*10 的网格，每一种颜色都可以用‘B’、‘Y’和‘G’中的一个字符来表示。

我们怎么用数字化的方式表示上面的图像？以原始的方式存储这张图片的文件可能包含下面的内容：

我们所做的只是从左到右，从上到下，为每个像素写下了代表其颜色的字符。正如你预期的那样，总共会有 100 个字符。我们假设这 100 个字符会占用硬盘上的 100 个字节。这种存储方式，定义了一个合理的存储文件大小上限。任何其他存储方式，只要其文件大小大于上述方法，都是无意义的，或者尝试去存储除了图片数据之外的信息（比如元数据或其他数据）。我想你们应该能认同我的这种观点。

在你往下看之前，开动下你的大脑。如果我让你用少于 100 个字符来表示这张图片，你会怎么做呢？喝一杯茶，仔细想一想，我等着你。

想到什么方法了吗？很好，我也想到了一个。

我准备将我的方法命名为 行程长度压缩算法（RLE） 。开玩笑的啦，这个方法不是我想出来的，也不是我命名的。至少从六十年代起，它已经成为了一种基本的压缩技术。我打赌，你们之中有些人刚刚才想出这种方法。

我们将行程长度压缩算法应用于上面的图片。在上方，我们写了很多一连串的相同颜色字符。让我们从那些‘B’字符下手。那么我们能够压缩这些重复的字符么？

当然可以！抛弃下面这种方式：

取而代之：

看起来有戏。通过缩写这一长串相同字符，我们将 17 个字符减少到了 3 个。顺便说下，我们将这些重复的字符串称之为 runs 。所以 行程长度压缩算法 是通过记下 runs 的长度，而不是记下每一个字符，对数据进行压缩编码。这种压缩方式并没有信息丢失。能够解析前一个文件的程序，稍微修改下，就能解析我们的新文件格式。2 者解析出来的图片应该是一样的。

下面的实时 demo 展示了原始图像和它的 2 种存储编码方式：原始版本和行程长度压缩编码版。

通过点击任意像素点，你可以改变其颜色，下方的存储字符也会随之变化。

编注：英文原文此处有 Demo，本文无法再现，请在 https://unwttng.com/compression-decompressed 查看。

随着你不断改变原始图像的像素颜色，你会发现我们能够压缩的比例和图片本身有关。如果整张图片只有一种颜色，或者颜色的连续区域很长，我们可以得到很小的输出。使用行程长度压缩算法能够得到的最小存储大小是 4 字节：

当然，这个算法在某些场景下也会表现的十分糟糕。实际上，用这个算法压缩出来的文件，可以比原始一个像素一个像素表示的方式都要大。你会发现，当需要表示‘1B’或’1G’时，它会使用 2 个字符。如果在你的像素图片中，每个颜色的连续长度只有 1 ，会发生什么？

惊讶吧。

是时候学习些术语了。

压缩率

如何衡量我们的压缩算法到底使数据缩小了多少？你可能已经猜到了 —— 计算数据压缩前后的大小比。

比如，我们使用算法将 100 字节的像素图片压缩至 42 字节，那么我们计算出的压缩率为 (100 / 42) ≈ 2.38。最好的情况是只有一种颜色的图片，这种算法的压缩率高达 (100 / 4) = 25！然而，当该算法作用于每个颜色的连续长度只有 1 的图片上时，压缩率只有 (100 / 200) = 0.5。Protip：压缩率小于 1 简直是糟糕透了。

我们可以看出，这种基础 RLE 算法的压缩率对于输入的数据结构十分敏感。对于这类简单的算法，这种现象很常见。该算法对于数据的结构做了若干假设，如果要使该算法能够输出理想结果，原始输入数据中必须存在重复相邻的相同字节。一个更智能的 RLE 算法实现可能会尝试使用重复的子串来对数据进行压缩编码。

甚至我直接用英语文字描述这张图片，压缩率都比 2 要大！运用这种方法，可以将数据压缩存储成一种友好、简洁的文件格式，相比第一次尝试我们又迈出了一小步。

数据到底能被压缩到多小？

这是一个很大很宽泛的问题。当然，人们认为，对于任何输入数据，一个合理设计的压缩算法，应该至少能将数据压缩那么一点（这里的一点点，既指口语上的，也表示学术上的）。

不幸的是，事情并没有那么简单。假设我们有一个算法 A，对于任何的输入，能够使压缩率始终严格大于 1。对于某些输入，压缩率可以为 2.5；对于另一些输入，压缩率可能为 1.000000002。

如果这种算法存在，我们可以无限迭代调用它。对于某个输入，我们计算 A(A(A(data)))，对每一次的输出不断调用 A()。我们每调用一次，数据的大小至少会被压缩一点点。不难看出，到最后，我们能将数据压缩至 1 字节，甚至 0 字节？

这看起来不太现实。事实也确实如此。我们甚至不需要使用递归法去证明该算法的可行性，试想下这种情况：有 9 个不同的文件，没有任何方法能够在不丢失数据的情况下，将这 9 个文件都压缩至 3 字节。

3 个字节一共只能表示 8 种不同的数据：000、001、010、100、011、101、110、111。即使我们有某个十分强大的压缩算法，能够将前 8 个文件分别压缩成前面这 8 种字节表示，第 9 个文件也只能压缩为其中之一。对于该算法，任意 8 个以上的未压缩数据片段，都无法找到更多不同的 3 个字节来表示。

这里有一条重要的原则： 对常见数据的压缩，任何算法的压缩率都有严格的限制 。你可以不断地使用某个算法对数据进行压缩，直到无法将数据压缩得更小，然后换种算法继续尝试。这种做法也许会将数据压缩得更小（实际上，很多线上的软件都是这么做的），但最终，你会遇到你永远无法再次压缩的数据。其实，你对不同的算法的重复调用，到头来又变成了另一种压缩算法。这条规则现在仍然适用。

柯氏复杂性

看到下面你也许会更加失望。对于压缩率的大小，不仅仅在算法上有着理论的限制 —— 数据本身的复杂度对其也会有很大的影响

让我们来看下下面的 2 个字符串：

和：

2 者是完全相同的长度，但是，你可以很轻易地看出来，后者明显要更加复杂。说的更具体点，使用 RLE 压缩算法，我们可以将第一个字符串压缩至最多 3 个字符（“24a”）。

柯氏复杂性 （一位苏联数学家 Andrey Nikolaevich Kolmogorov 的伟大发明）将上述内容阐述地很好。当然，一个事物的度量方式有很多种，柯氏复杂性是一种比较不错的度量方式。 数据的柯氏复杂性是指，通过计算机程序输出的，能够描述这个字符串的最短长度 。

显然，对于柯氏复杂性，任何字符串‘S’的长度上界就是其本身。上述说法将算法进行了一定的简化，其实数据的柯氏复杂性还需加上整个程序的长度 —— 包括解释器或编译后的代码。但是就本文讨论的范围来说，没有必要。直接把它认为是你能生成的该数据的最短长度。

柯氏复杂性对于你选择什么编程语言并不是很敏感。程序语言的选择只会对复杂度的一个常数因子产生影响。下面这句话很重要： 无论你选择什么语言来描述数据，所带来的长度变化是有限的 。有些数据就是需要比一百万个绿色像素点更多的空间来表示，怎么也减少不了。

数据丢失

但是，别放弃希望。我们之前讨论的都是 无损压缩 。无损压缩是指， 通过压缩之后的数据，能够完全还原压缩之前的原始数据 。也就是说，如果 C 是我们的压缩算法，D 是相应的解压缩算法，D(C(x)) = x 对于任何输入数据 x 永远成立。

无损压缩是十分有用的！当压缩一些文献或博文、税收档案、低分辨率的像素图片等类似的文本数据时，你肯定想要做到无损压缩。对于这些数据，保证数据的精确和每个字符的顺序，是很重要的。

但是也有其他选择。有损压缩是指，不保证压缩的数据解压之后与压缩之前的数据完全一致。这种压缩算法十分常见。

有损压缩应用十分广泛。人类的感官对于一些微小错误或瑕疵是比较有容忍度的。数据丢失主要体现在压缩图片、音频（或视频）文件时。

需要例子吗？请看下面 2 张奥巴马的图片。

第一张图片是大小约为 335 千字节的 PNG 文件（PNG 是一种无损图片压缩格式）。这将作为我们的参照物。

第二张图片，是第一张图片保存为 JPEG 格式的结果，这是一种会丢失许多数据的有损压缩。第二张图片的大小约为 22 千字节，相比原始图片，压缩率约为 15，这么大的压缩率并不表示数据丢失会很严重。

请到「今天看啥」查看全文