Data Compression Explained 深度解读

背景

本文源自 Matt Mahoney 所著的《Data Compression Explained》（数据压缩详解），该书由 Dell, Inc. 于 2010-2012 年间发布版权，并在 2013 年进行了最后更新。这是一本面向希望理解数据压缩原理或致力于编写数据压缩软件的读者的技术著作。

该书预设读者具备基本的编程能力和一定的数学基础。其内容结构严谨，涵盖了从信息论基础到具体算法实现的各个层面，包括基准测试、编码技术、建模、变换（如 RLE、LZ77 系列、LZW、BWT 等）、预测滤波以及有损压缩等专题。

本书的核心宗旨是“自包含”（self-contained），即读者无需点击外部链接即可理解所有内容。它旨在揭示数据压缩的本质：即通过减少存储或传输数据所需的比特数，来实现效率的提升。

核心内容

数据压缩分为无损压缩（Lossless）和有损压缩（Lossy）两大类，其底层逻辑均建立在概率模型与编码理论的结合之上。

1. 压缩的基本构成

所有数据压缩算法至少包含两个部分：模型（Model）和编码器（Coder），并可选地包含预处理变换。

• 模型：负责估计输入数据的概率分布。例如，模型需要判断字母 "E" 出现的概率高于 "Z"。
• 编码器：根据模型提供的概率，为高概率符号分配较短的代码，为低概率符号分配较长的代码。
• 难点：虽然存在高效且最优的编码解决方案，但“最优建模”已被证明在计算上是不可行的（uncomputable）。因此，建模（或预测）既是一个人工智能（AI）问题，也是一门艺术。

2. 无损压缩与信息论极限

无损压缩确保数据解压后能精确还原为原始值。经典的例子是 1848 年的摩尔斯电码，其中常见的字母（如 E, T）使用最短的代码，罕见的字母（如 J, Q, X, Z）使用最长的代码。

信息论为无损压缩设定了硬性限制：

• 不存在“通用”压缩算法：没有任何算法能保证压缩任意输入，甚至不能保证压缩超过特定大小的输入。特别是，随机数据无法被压缩，且压缩过程不能递归进行。
• 香农极限：给定输入数据的概率分布模型，最优的编码长度是 $\log_2(1/p)$ 比特，其中 $p$ 是符号的概率。
• 通用但不可计算的分布：数据具有一个通用的概率分布，即字符串 $x$ 的概率约为 $2^{-|M|}$，其中 $M$ 是 $x$ 的最短描述，$|M|$ 是其比特长度。然而，不存在通用程序能找到 $M$ 或估计 $|M|$，也没有算法能测试随机性或判断字符串是否还能进一步压缩。

**计数论证（Counting Argument）**证明了上述观点： 假设存在一个能压缩所有至少为 $n$ 比特的字符串的算法。长度为 $n$ 的二进制字符串共有 $2^n$ 个。如果算法是通用的，每个输入必须映射到不同的输出。然而，长度小于 $n$ 的二进制字符串只有 $2^n - 1$ 个。根据鸽巢原理，必然有两个不同的输入映射到同一个输出，导致解压时无法区分，从而产生错误。因此，绝大多数字符串无法被大幅压缩。具体来说，能从 $n$ 比特压缩到 $m$ 比特的字符串比例最多为 $2^{m-n}$。例如，少于 0.4% 的字符串能被压缩一个字节。任何能压缩某些输入的压缩器，必然也会扩展（expand）某些输入，但扩展量通常不超过一个符号。

3. 编码效率案例分析

以圆周率 $\pi$ 的数字序列为例，假设每个数字出现的概率均为 0.1 且相互独立：

• BCD 编码：每个数字用 4 位表示，压缩率为 4.0 bpc（bits per character）。
• Huffman 编码：根据概率分配变长代码，压缩率为 3.4 bpc。Huffman 码是前缀码（prefix code），即没有任何代码是其他代码的前缀，从而保证唯一可解码性。
• 二进制直接映射：非唯一可解码，例如 "111" 可能被解码为 7，也可能被解码为 3 和 1，或 1 和 3 等，导致歧义。
• 分组编码优化：通过为数字对（100 种组合，概率各 0.01）分配 Huffman 码，平均码长可降至 3.36 bpc。若对三位数字组进行编码，可进一步降至 3.3253 bpc。

4. 熵（Entropy）的定义

Shannon 和 Weaver (1949) 证明，对于概率为 $p$ 的符号，最优码长为 $\log_2(1/p)$。 随机变量 $X$ 的熵 $H(X)$ 定义为期望码长： $$ H(X) = \sum p(i) \log_2(1/p(i)) $$ 在上述 $\pi$ 的例子中，熵为 $10 \times (0.1 \log_2(1/0.1)) \approx 3.3219$ bpc。这是基于该模型可实现的最小平均码长。

此外，联合熵 $H(X,Y)$ 满足 $H(X,Y) \le H(X) + H(Y)$。等号成立当且仅当 $X$ 和 $Y$ 相互独立。条件熵 $H(X|Y) = H(X,Y) - H(Y)$ 表示在已知 $Y$ 的情况下 $X$ 的信息量。

5. 有损压缩

有损压缩通过丢弃人眼或人耳无法感知的“不重要”数据来减小体积。例如，1953 年的 NTSC 彩色电视标准利用人眼对亮度（黑白）比色度（红绿等）细节更敏感的特性，以较低的分辨率传输色度信号。

有损压缩的流程通常包括：

1. 变换：将数据分离为重要和不重要部分（这是一个 AI 问题，需理解人类感知机制）。
2. 无损压缩：对重要部分进行无损压缩。
3. 丢弃：移除不重要部分。

关键要点

• 压缩的核心是概率建模：压缩算法由“模型”（估计概率）和“编码器”（分配码长）组成。建模是压缩中最困难的部分，因为它本质上是一个不可计算的最优预测问题。
• 不存在万能压缩算法：信息论证明，无法压缩所有数据，特别是随机数据。任何压缩算法必然会导致某些数据膨胀。
• 香农熵是理论极限：对于给定的概率分布，最优压缩率由熵 $H(X) = \sum p(i) \log_2(1/p(i))$ 决定。Huffman 编码等算法可以逼近这一极限，但无法超越。
• 唯一可解码性至关重要：编码方案（如 Huffman 码）必须确保没有代码是其他代码的前缀，否则解码器无法正确还原数据。
• 分组编码可提高效率：通过对多个符号进行联合编码（如数字对、数字组），可以更接近香农极限，减少平均码长。
• 有损压缩依赖感知模型：有损压缩的有效性取决于对“人类感知”的理解，通过变换分离重要信息并丢弃冗余细节。

意义与影响

《Data Compression Explained》不仅是一本技术手册，更是对信息本质的哲学性探讨。它揭示了数据压缩并非简单的技巧，而是建立在严格的数学基础（信息论）和人工智能（建模/预测）之上的科学。

1. 理论指导实践：通过明确“计数论证”和“香农极限”，该书为开发者提供了理论边界，避免了在不可行方向上的无效尝试，并指导了如 LZ77、BWT 等高效算法的设计思路。
2. **AI