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

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

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

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

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

让我们来一一解答吧!

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,本文无法再现,请在 http://www.cswhw.com.cn/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,这么大的压缩率并不表示数据丢失会很严重。

你能看出这 2 张图片的区别么?也许能看出一点点。如果你尽可能靠近你的屏幕,眯起眼睛,转头环视下这张图片。接着你去看他的头发细节,一根一根地数头发,在没有头发的地方你会发现一些模糊。关键点不在于第二张图是不是一个完美的复制品,而在于它是不是足够好用。当你通过互联网传输数据时,十五倍的压缩率比起一张毫无损失的 PNG 图片更有价值。

但这并不是说在任何情况下,它都如此出色。为了达到这种压缩效果,JPEG 必须丢掉很多数据,尽管同时它尽力避免丢失太多数据,但是你可以尝试探索下它的极限。通过下面的实时 demo,你可以看出 JPEG 格式的图片质量下限能到多少。同时在图片清晰度变得无法容忍之前,注意看下图片质量是多少。像我之前说的那样,人类的视觉容忍度是很高的。

编注:英文原文此处有一个 Demo,本文无法再现,请在?http://www.cswhw.com.cn/compression-decompressed 查看

像 Netflix 和 YouTube 上的视频流服务,以及 Spotify 和 Soundcloud 上的音频流服务,都是使用的有损压缩?;撼寤蜓映偈且桓鲇没薹ㄈ淌艿?,所以在保证音视频质量的同时,这些服务尽可能地去压缩数据。你经?;峥吹绞莸亩顾?, 一开始视频会比较模糊,当检测到你的网络速度可以接受更小的压缩率时,视频的清晰度会随之提高。

看到下面这张来自 Giphy 网站上的动图了么?数据的动态压缩在这里同样适用??纯此鞘侨绾未硗俾那榭鱿碌亩技釉兀淮?,我在 Giphy 网站上将这个加载过程做成了一张动图,并将它嵌入了进来,看出什么问题了么?):

via GIPHY

看起来很奇怪对么?首先,他们加载了这张动图的第一帧低清晰度图片。接着,当更大的数据传输过来后,出现了动图。但是还不完全,只有仅仅几帧。然后,越来越多帧图片被传输了过来,直到最后完全加载整张动图。

这就是现代的流媒体压缩技术:混合的压缩策略几乎完全是为了,以尽可能少的字节(大小越小,时间也越短),提供给用户流畅的内容。针对文件的无损压缩技术,比如上面说到的 RLE,也有用武之地,而且它仍然是很多最好的桌面文件压缩工具的核心???。但是,多亏了有损压缩,你才能在电视上流畅地观看《权利的游戏》。

数据压缩无处不在

关于压缩技术本文我们就先介绍到这里,但这只是冰山一角。

我们学习了压缩技术的基本思想,从这些技术中得出了一条很重要的哲学道理:

图像,文字,视频,音乐 —— 任何数据都没有唯一正确的表现形式。区别只是在于有多少种表现数据的有效方式。

压缩技术就是不断寻找更加有效的方式来存储你的数据,最强大的压缩算法,对于任何数据,它都能找到一种高效的方法对其进行压缩。

感谢阅读,如果你认可我在文中制作的那些实时 demo,请随时与你的朋友分享。

2 1 收藏 1 评论

关于作者:nEoYe

喜欢唱歌和游戏的程序员 个人主页 · 我的文章 · 11 ·   

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部