数据压缩详解

你加载的每个网页、每个 ZIP 文件和每张 PNG 图像都经过了压缩:在不丢失任何一个比特的情况下变小,到达后再解压还原。背后的方法简单得出人意料。它们寻找重复出现的东西,然后说一句“和前面一样”,而不是再说一遍。这个想法能走多远、又在哪里止步,是计算机科学中最精妙的故事之一。

一行文本,其中重复的片段被替换成指回其首次出现位置的箭头,旁边的条形显示原始大小和压缩后的大小
一行文本,其中重复的片段被替换成指回其首次出现位置的箭头,旁边的条形显示原始大小和压缩后的大小

无损与有损

压缩分为两类。无损压缩能精确还原原始数据,这对文本、程序、电子表格以及任何错一个比特就会出问题的东西都必不可少。有损压缩用于照片、音乐和视频,它丢弃人们几乎感知不到的细节,能达到小得多的大小,但原始数据就永远丢失了。本页和演示器讨论的是无损压缩,它的原理是找出并去除冗余,也就是数据中本可以预测出来的部分。

游程编码

最简单的方法是把一串相同的符号替换为一个计数和该符号:十二个白色像素变成 12W。传真机、早期的位图格式和 PCX 图像格式都用过它,因为扫描的页面和简单的图画里满是长长的游程。对普通文本来说它毫无用处,甚至有害:游程很少,而为每个单独的字母都写一个计数会让大小翻倍。游程编码至今仍存在于其他方法内部,用来处理第一步变换之后留下的连续的零。

LZ77:往回指

1977 年,以色列理工学院的两位研究者亚伯拉罕·伦佩尔和雅各布·齐夫发表了一种改变这一领域的方法。编码器保留一个刚处理过的文本窗口。如果接下来的字符已经在窗口中出现过,它就写下一对数:前面那份副本从多远之前开始,以及它有多长。否则就写出字符本身。解码器根本不需要字典,只需要它已经重建的文本。一个引用甚至可以与它所生成的文本重叠,所以由 100 个相同字母组成的游程只需一个字母加一个引用。

亚伯拉罕·莱姆佩尔。1977年,他与雅各布·齐夫在以色列理工学院发表了如今称为LZ77的窗口与引用方法。
亚伯拉罕·莱姆佩尔。1977年,他与雅各布·齐夫在以色列理工学院发表了如今称为LZ77的窗口与引用方法。

LZW:学习一个字典

伦佩尔和齐夫的第二种方法 LZ78 不再回看窗口,而是建立一个字典。Terry Welch 在 1984 年对它做了改进,即 LZW:它从全部 256 个字节值开始,每一步都发送它已知的最长字符串的编号,并把这个字符串加上下一个字符作为新条目加入字典。解码器仅凭这些编号就能重建同样的字典。LZW 快速而简单,被用于 Unix 的 compress 命令、GIF 图像格式和 TIFF 文件,直到 20 世纪 90 年代围绕它的专利引发了一场旷日持久的纠纷。

Deflate、ZIP 及其后

Phil Katz 的 deflate 方法于 1993 年随 PKZIP 2 推出,它把 LZ77 与霍夫曼编码结合起来:找出重复之后,再给最常见的字面量、长度和距离分配最短的比特编码。Deflate 用于 ZIP、gzip、PNG 图像和网页压缩,也是本演示器借助浏览器自带的压缩器来测量的方法。Zstandard、Brotli 和 xz 等较新的方法使用更大的窗口、更聪明的匹配和更精确的熵编码,能把典型文件再压缩 10% 到 30%。

为什么不是所有东西都能缩小

没有任何方法能让每个文件都变小。n 比特的文件有 2ⁿ 个,而比它短的文件只有 2ⁿ − 1 个,所以如果一种方法把它们全都缩小,必然有两个文件变得相同,无法同时还原:这就是鸽巢原理。因此,每个压缩器都会让某些输入变大,通常是看起来随机的数据,例如加密文件、已压缩的文件和噪声。这也可以用来检验随机性:任何压缩器都无法缩小的数据看起来就是随机的。

熵极限

克劳德·香农在 1948 年证明,信源的熵是任何无损编码每个符号平均所需比特数的最小可能值。逐个字母计算时,英语文本的熵约为每个字母 4 比特,是存储它所用的 8 比特的一半。LZ77 等利用上下文的方法,在重复性强的文本上可以低于这个单字母数值,因为一个引用一次就代表了一整段。最好的现代压缩器根据前面的全部内容来预测每个字母,能把英语压缩到每个字母不到 2 比特。

克劳德·香农于1948年在贝尔实验室精确刻画了一条消息所含的信息量,并以比特来度量。
克劳德·香农于1948年在贝尔实验室精确刻画了一条消息所含的信息量,并以比特来度量。

动手探索

打开压缩演示器,对一段文字、一首带副歌的歌、一行像素、一张数据表、随机字母或 DNA,或者你自己的文本运行 LZ77、LZW 和游程编码。点击任意 LZ77 引用,查看它复制的内容,观察 LZW 字典如何增长,并把所有方法与 ZIP 和熵极限进行比较。

常见问题

压缩比 3 : 1 是什么意思?

意思是原始数据是压缩后版本的三倍大,所以压缩后的文件只占三分之一的空间,节省了三分之二。用 ZIP 压缩文本通常能达到 2 : 1 到 4 : 1;重复很多的数据,例如日志文件,往往高得多。

为什么再次压缩 ZIP 文件没有用?

第一遍已经去除了重复,其输出看起来几乎是随机的。第二遍找不到任何可以指回的内容,只会增加自身的开销,所以文件大小不变或略有增大。

为什么 LZ77 的窗口越大越好?

更大的窗口让编码器能找到更靠前的重复,例如隔了好几段主歌才再次出现的副歌。代价是每个距离需要更多比特来写,搜索也更费时间,这就是为什么 deflate 止步于 32 KB,而较新的方法允许使用数兆字节。

压缩和加密是一回事吗?

不是。压缩让数据变小,任何人都能还原;加密让数据在没有密钥的情况下无法读取。两者经常结合使用,这时必须先压缩:加密后的数据看起来是随机的,再也无法压缩。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

打开压缩演示器