1952年，克劳德·香农在贝尔实验室的办公室里写下了这样一个公式：

$$H(X) = -\sum_{i=1}^{n} p_i \log_2 p_i$$

这个看似简洁的等式，定义了信息的数学本质，也为接下来七十年的压缩技术发展奠定了理论基础。当我们今天用gzip压缩文件、用PNG保存图片、用HTTP传输网页时，这些技术的根源都可以追溯到香农的信息论。

信息的度量：为什么随机数据无法压缩

理解压缩的第一步，是理解什么是"信息"。香农的天才之处在于，他将信息定义为一个概率问题：事件发生的概率越低，它所携带的信息量越大。

如果你生活在一个每天都是晴天的地方，有人告诉你"今天是晴天"，这句话几乎没有任何信息量——因为你早就知道了。但如果有人告诉你"今天下雪了"，这句话的信息量就非常大，因为这是一个极不可能发生的事件。用数学语言表达，一个概率为 $p$ 的事件所携带的信息量是：

$$I(p) = -\log_2 p$$

对数底数取2，意味着信息量的单位是比特。一个概率为1/2的事件（如抛硬币正面朝上）携带1比特信息；一个概率为1/256的事件（如从256个可能值中猜中某一个）携带8比特信息。

将所有可能事件的平均信息量加总，就得到了熵的概念。熵衡量的是一个信息源的"不确定程度"，也是对该信息源进行编码所需的平均最小比特数。一个信息源的熵越低，说明它越"可预测"，也就越容易被压缩。

这解释了一个根本性的问题：为什么已经压缩过的文件无法再压缩？ 当一个文件被完美压缩后，其字节分布会趋近于均匀——每个字节值出现的概率都接近1/256。此时文件的熵接近最大值8比特/字节，没有任何冗余可以被去除。试图再次压缩，就像试图从打乱后的扑克牌中找出规律一样徒劳。

这正是为什么加密文件和随机数无法被有效压缩——它们已经足够"随机"，熵已经接近最大值。而文本、代码、图像之所以能被压缩，正是因为它们存在统计规律和冗余。

霍夫曼编码：构建最优前缀码

1951年，麻省理工学院的学生大卫·霍夫曼在一门信息论课程上面临期末考试或学期论文的选择。他的导师Robert Fano给了他一个题目：找到一种能生成最优编码的方法。霍夫曼放弃了考试，埋头研究了几个月后，找到了答案——这个算法如此优雅，以至于Fano后来说：“我应该把这个问题作为考试题，而不是学期论文。”

霍夫曼编码的核心思想是变长编码：对高频出现的符号使用短码，对低频出现的符号使用长码。但这带来了一个问题：如何区分"短码的结束"和"长码的开始"？

霍夫曼的解决方案是前缀码：没有任何一个编码是另一个编码的前缀。这意味着在解码时，一旦读取到的比特序列匹配某个编码，就可以立即确定对应的符号，不存在歧义。

构建霍夫曼树的过程是一个经典的贪心算法：

flowchart TD
    A[统计每个符号的出现频率] --> B[将所有符号作为叶子节点放入优先队列]
    B --> C[取出频率最低的两个节点]
    C --> D[创建新节点，频率为两者之和]
    D --> E[新节点的左右子节点为取出的两个节点]
    E --> F{队列中剩余节点数 > 1?}
    F -->|是| C
    F -->|否| G[最后剩余的节点即为霍夫曼树的根]
    G --> H[从根到叶子的路径即为编码]

让我们用一个具体例子来理解。假设我们有五个字符及其频率：

字符 频率
A 45%
B 25%
C 15%
D 10%
E 5%

构建过程如下：首先将频率最低的D和E合并（15%），然后将这个新节点与C合并（30%），再与B合并（55%），最后与A合并（100%）。

最终得到的编码可能是：A=0, B=10, C=110, D=1110, E=1111。注意没有任何编码是另一个编码的前缀：看到"0"就知道是A，看到"10"就知道是B。

霍夫曼编码的平均编码长度为：

$$L_{avg} = \sum_{i=1}^{n} p_i \cdot l_i$$

对于上面的例子，平均长度为 $0.45 \times 1 + 0.25 \times 2 + 0.15 \times 3 + 0.10 \times 4 + 0.05 \times 4 = 1.85$ 比特/符号。如果使用固定长度编码，每个符号需要 $\lceil \log_2 5 \rceil = 3$ 比特。霍夫曼编码节省了约38%的空间。

霍夫曼证明了他的编码是最优的前缀编码——没有任何其他前缀编码能达到更短的平均长度。但这个"最优"有一个限定条件：每个符号必须编码为整数个比特。这个限制在某些情况下会带来显著的效率损失。

算术编码：打破整数比特的限制

考虑一个极端情况：假设我们要编码一个只有两个符号的信息源，符号A出现的概率是99%，符号B出现的概率是1%。使用霍夫曼编码，A会被编码为0，B会被编码为1——每个符号都用整整1比特，尽管它们的信息量截然不同。

按照信息论，A的自信息量是 $-\log_2 0.99 \approx 0.014$ 比特，B的自信息量是 $-\log_2 0.01 \approx 6.64$ 比特。理想的平均编码长度应该是 $0.99 \times 0.014 + 0.01 \times 6.64 \approx 0.08$ 比特/符号，但霍夫曼编码只能达到1比特/符号——效率损失超过十倍。

算术编码通过一种精巧的方法解决了这个问题：不再为每个符号单独编码，而是将整个消息编码为一个区间内的一个数值。

算法的核心是维护一个当前区间 $[low, high)$。初始时，区间是 $[0, 1)$。每当要编码一个符号时，根据符号的概率分布，将当前区间划分为若干子区间，每个子区间的大小与对应符号的概率成正比。选择当前符号对应的子区间作为新的当前区间，然后重复这个过程。

对于上面的例子，编码序列"AAB"的过程如下：

  1. 初始区间：$[0, 1)$
  2. 编码A：区间变为 $[0, 0.99)$（因为A占99%的概率）
  3. 编码A：区间变为 $[0, 0.9801)$
  4. 编码B：区间变为 $[0.970299, 0.9801)$

最终，我们只需要输出一个位于最终区间内的数值，比如0.975。解码器收到这个数值后，可以进行逆向操作：0.975落在A的子区间 $[0, 0.99)$ 内，所以第一个符号是A；然后在A的子区间内继续细分，0.975落在A的子区间内，所以第二个符号也是A；继续细分后，0.975落在B的子区间内，所以第三个符号是B。

算术编码的平均编码长度可以无限逼近香农熵，不存在整数比特的限制。但它的实现比霍夫曼编码复杂得多，主要挑战在于：

  • 精度问题：随着编码的进行，区间越来越小，需要高精度算术
  • 自适应概率估计：需要动态更新符号的概率分布
  • 专利限制：早期算术编码被IBM等公司申请了专利，限制了其普及

LZ77：从重复中寻找机会

霍夫曼和算术编码都依赖于对符号概率的准确估计。但现实中，很多数据的冗余并非来自符号频率的不均匀，而是来自数据的自相似性——相同或相似的模式反复出现。

1977年，以色列研究人员Abraham Lempel和Jacob Ziv提出了一种完全不同的压缩思路：不统计符号频率，而是直接利用数据中的重复模式。这就是著名的LZ77算法。

LZ77的核心是一个滑动窗口机制。窗口分为两部分：已经处理过的数据（称为字典或搜索缓冲区）和待处理的数据（称为前瞻缓冲区）。算法尝试在前瞻缓冲区中找到与字典中最长匹配的字符串，然后用一个"距离-长度"对来表示它。

graph LR
    subgraph 滑动窗口
        A[字典<br/>已处理数据] --> B[前瞻缓冲区<br/>待处理数据]
    end
    C[匹配指针] --> A
    C --> B

假设我们要压缩字符串 “ABABABCABAB”。处理过程如下：

  1. 字典为空，输出字面量 (0, 0, ‘A’)
  2. 字典为 “A”，输出字面量 (0, 0, ‘B’)
  3. 字典为 “AB”，在字典中找到匹配 “AB”，距离2，长度2，输出 (2, 2)
  4. 字典为 “ABAB”，在字典中找到匹配 “AB”，距离2，长度2，输出 (2, 2)
  5. 字典为 “ABABAB”，输出字面量 (0, 0, ‘C’)
  6. 字典为 “ABABABC”，在字典中找到匹配 “ABAB”，距离5，长度4，输出 (5, 4)

输出序列：(0,0,‘A’), (0,0,‘B’), (2,2), (2,2), (0,0,‘C’), (5,4)。原始字符串有11个字符，压缩后需要存储6个单元。

LZ77的优势在于它不需要预先知道数据的统计特性，而是自适应地建立字典。这使得它对各种类型的数据都有不错的效果。更重要的是，LZ77的解压过程非常简单：只需要根据距离和长度复制之前的数据，这使得它成为许多实际应用的首选。

但LZ77也有局限性：当字典中没有匹配时，输出单元比原始数据还要大。一个字面量输出需要存储距离(0)、长度(0)和字符本身，比直接存储字符占用更多空间。

DEFLATE：两大算法的联姻

1990年代，Phil Katz在开发PKZIP软件时，设计了一种新的压缩格式——DEFLATE。它巧妙地结合了LZ77和霍夫曼编码的优势，成为互联网上最广泛使用的压缩算法。

DEFLATE的工作流程分为两步：

  1. LZ77阶段：将输入数据转换为字面量、长度-距离对序列
  2. 霍夫曼阶段：对LZ77的输出进行霍夫曼编码

但DEFLATE的设计远比这复杂。它引入了几个关键优化：

动态霍夫曼树：不是使用预定义的编码，而是在压缩时根据数据的实际统计特性构建霍夫曼树，并将树的描述信息存储在压缩输出中。这使得编码可以适应不同类型的数据。

分离的字面量/长度编码和距离编码：字面量和长度值使用一套霍夫曼编码，距离值使用另一套霍夫曼编码。这是因为它们的统计特性差异很大。

块结构：数据被分成多个块，每个块可以选择不同的压缩策略（不压缩、固定霍夫曼、动态霍夫曼）。这允许在压缩率和速度之间灵活权衡。

flowchart TD
    A[原始数据] --> B[LZ77编码]
    B --> C[字面量/长度流]
    B --> D[距离流]
    C --> E[霍夫曼编码]
    D --> F[霍夫曼编码]
    E --> G[压缩输出]
    F --> G

DEFLATE的成功不仅仅在于算法设计，更在于它的工程实现。zlib库提供了稳定、高效、跨平台的实现，被集成到无数软件中。gzip文件格式、PNG图像格式、HTTP压缩都使用DEFLATE作为核心压缩算法。

现代压缩算法：效率与速度的博弈

DEFLATE在1990年代是一个优秀的设计，但随着硬件性能的提升和应用场景的变化，它的局限性逐渐显现。压缩率不够高、压缩速度不够快，催生了新一代压缩算法。

Zstandard：速度与压缩率的最佳平衡

2015年，Facebook的Yann Collet发布了Zstandard（zstd）。它的设计目标是：在压缩率和压缩速度上都超越DEFLATE。

Zstd的核心创新是有限状态熵编码（FSE）。这是一种介于霍夫曼编码和算术编码之间的技术：

  • 像霍夫曼编码一样，使用整数比特表示符号
  • 像算术编码一样，可以处理非2的幂次的概率

FSE基于一个精巧的状态机。每个状态对应一个输出比特和一个转移目标状态。编码时，根据当前状态和要编码的符号，输出一个比特并转移到新状态。解码时，根据当前状态和输入比特，转移到新状态并输出对应符号。

Zstd的另一个创新是可训练字典。对于特定类型的数据（如JSON日志、HTML文件），可以预先训练一个字典，显著提升小文件的压缩率。这对于实时压缩场景非常有价值。

graph TD
    A[训练数据集] --> B[字典训练算法]
    B --> C[预定义字典]
    C --> D[压缩时使用]
    D --> E[显著提升小文件压缩率]

Brotli：为Web而生的压缩

2013年，Google开始开发Brotli压缩算法，专门针对Web内容优化。Brotli最引人注目的特点是它的预定义字典。

传统压缩算法需要从数据中学习模式。但对于小文件（如网页的HTML、CSS、JavaScript），数据量不足以建立有效的统计模型。Brotli内置了一个2MB的预定义字典，包含了大量HTML标签、CSS属性、JavaScript关键词等Web常见模式。

当你压缩一个HTML文件时，Brotli可以直接引用字典中的内容，而不需要从数据中学习。这使得即使是很小的HTML文件也能获得很高的压缩率。

Brotli在压缩率上通常比gzip高15-25%，但代价是压缩速度较慢。这使得它更适合静态资源的预压缩，而不是实时压缩。

LZMA：追求极致压缩率

当压缩率是唯一目标时，LZMA（Lempel-Ziv-Markov chain Algorithm）是一个选择。它使用大窗口（高达数GB）、复杂的上下文建模和范围编码，在压缩率上达到了通用压缩算法的巅峰。

LZMA的核心是一个马尔可夫链模型。它不仅利用直接的字符串匹配，还利用上下文信息来预测下一个符号的概率。更复杂的模型意味着更好的预测，但也意味着更高的计算和内存开销。

LZMA的压缩速度非常慢——比DEFLATE慢10-100倍。但对于软件分发、数据归档等场景，压缩只需要进行一次，解压需要进行很多次，这种权衡是合理的。

压缩的权衡：没有免费的午餐

所有的压缩算法都面临一个基本问题：在压缩率、压缩速度、解压速度、内存占用之间权衡。没有算法能在所有维度上同时最优。

graph TD
    subgraph 压缩算法权衡三角
        A[压缩率] --- B[压缩速度]
        B --- C[解压速度/内存]
        C --- A
    end
算法 压缩率 压缩速度 解压速度 内存占用
LZ4 低 极快 极快 低
Zstd 中高 快 快 中
Brotli 高 慢 中 高
LZMA 极高 极慢 中 高

一个容易被忽视的问题是：压缩后的文件有时会比原文件更大。这发生在几种情况下：

  • 文件已经被压缩过（如JPEG、MP4）
  • 文件太小，压缩开销超过节省的空间
  • 文件本身熵很高（如加密数据）

压缩算法需要在输出中存储元数据：霍夫曼树、字典、块头等。对于小文件，这些开销可能超过压缩节省的空间。因此，大多数压缩算法会在压缩效率不高时自动切换到"存储模式"，直接存储原始数据而不压缩。

Web压缩的实践

HTTP压缩是Web性能优化的关键环节。当浏览器请求一个资源时，会在Accept-Encoding头中声明支持的压缩算法：

Accept-Encoding: gzip, deflate, br, zstd

服务器选择一种支持的算法进行压缩，并在Content-Encoding头中告知浏览器：

Content-Encoding: br

sequenceDiagram
    participant Browser as 浏览器
    participant Server as 服务器
    
    Browser->>Server: GET /index.html<br/>Accept-Encoding: gzip, br, zstd
    Server->>Server: 选择压缩算法
    Server->>Server: 压缩响应内容
    Server->>Browser: 200 OK<br/>Content-Encoding: br<br/>[压缩后的内容]
    Browser->>Browser: 解压缩
    Browser->>Browser: 渲染页面

在实践中，静态资源（CSS、JavaScript、字体）通常预先用Brotli最高压缩级别压缩，动态内容则用Zstd或gzip实时压缩。这种策略兼顾了压缩率和响应速度。

七十年的演进：从理论到实践

回顾压缩算法七十年的发展，可以看到几条清晰的主线：

从理论到实践：香农的信息论定义了压缩的理论极限，但如何高效地逼近这个极限，需要几十年的算法创新。霍夫曼编码在1952年就达到了前缀编码的最优，但直到算术编码和FSE的出现，我们才突破了整数比特的限制。

从统计到结构：早期的压缩算法（霍夫曼、算术）依赖于统计模型，后来LZ77开创了基于结构的方法。现代算法往往是两者的结合：先用结构化方法去除重复，再用统计方法优化编码。

从通用到专用：通用压缩算法追求对任意数据的压缩能力，而专用压缩算法利用特定领域知识获得更好的效果。Brotli的预定义字典、zstd的可训练字典，都是专用化趋势的体现。

从单一指标到多维权衡：早期的压缩研究主要关注压缩率，现代压缩算法需要平衡压缩率、速度、内存占用、随机访问能力等多个维度。zstd的出现，正是因为它在多个维度上都达到了不错的平衡。

未来，压缩算法的发展可能会沿着几个方向继续：

硬件加速：苹果的M系列芯片已经集成了专用的压缩/解压单元，AMD的EPYC处理器也支持实时内存压缩。当压缩成为硬件能力的一部分，算法的设计空间会发生根本变化。

机器学习驱动的压缩：语言模型本质上是在学习数据的概率分布。理论上，一个足够好的语言模型可以用于压缩。一些研究已经证明，使用GPT-2等模型进行压缩，在某些文本上可以超越传统的压缩算法。但计算成本仍然是一个障碍。

语义压缩：对于某些应用，我们可能不需要精确恢复原始数据。图像和视频的"感知无损"压缩已经广泛应用，未来可能会有更多"语义无损"的压缩方案出现。

当我们用一个简单的gzip file.txt命令压缩文件时，背后是七十年数学和工程智慧的结晶。从香农的公式到zstd的状态机，从霍夫曼的树到Brotli的字典，每一代研究者都在回答同一个问题：如何用最少的比特，承载最多的信息。

参考文献

  1. Shannon, C. E. (1948). A mathematical theory of communication. Bell System Technical Journal, 27(3), 379-423.

  2. Huffman, D. A. (1952). A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9), 1098-1101.

  3. Ziv, J., & Lempel, A. (1977). A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3), 337-343.

  4. Deutsch, P. (1996). DEFLATE Compressed Data Format Specification version 1.3. RFC 1951.

  5. Collet, Y., & Turner, A. (2016). Smaller and faster data compression with Zstandard. Facebook Engineering Blog.

  6. Alakuijala, J., & Szabadka, Z. (2016). Brotli compressed data format. RFC 7932.

  7. Pavlov, I. (2018). LZMA SDK. 7-Zip Project Documentation.

  8. Gailly, J. L., & Adler, M. (1996). gzip manual page. GNU Project.

  9. Witten, I. H., Neal, R. M., & Cleary, J. G. (1987). Arithmetic coding for data compression. Communications of the ACM, 30(6), 520-540.

  10. Bloom, C. (2018). Understanding LZMA compression. cbloomrants blog.

  11. W3Techs. (2024). Usage statistics of data compression for websites. Web Technology Surveys.

  12. Moffat, A. (2019). Huffman coding. ACM Computing Surveys, 52(4), 1-35.