1948年，贝尔实验室的Claude Shannon在《Bell System Technical Journal》上发表了一篇论文——“A Mathematical Theory of Communication”。这篇论文定义了一个被称为"熵"的量：

$$H(X) = -\sum_{i} p(x_i) \log_2 p(x_i)$$

这个公式看起来平淡无奇，但它划定了一道任何无损压缩算法都无法逾越的边界：对于任何概率分布的信源，其无损编码的平均码长不可能低于该信源的熵。

这是一个令人震撼的结论。它意味着，无论算法多么精妙、无论硬件多么强大，我们都无法突破这个数学极限。你可以无限逼近它，但永远无法超越。

更令人意想不到的是，这个极限还隐含着另一个更底层的约束：不存在任何压缩算法，能够压缩所有文件。这不是技术上的限制，而是数学上的不可能。

一个反直觉的数学事实

假设有人声称发明了一款名为"Ultrazip"的压缩软件，可以将任何文件压缩到原大小的80%。你给它一个100字节的文件，它返回80字节。再压缩一次，得到64字节。如此反复，任何文件最终都能被压缩到几个字节。

这听起来很美好，但数学告诉我们：这样的软件不可能存在。

证明非常简洁。考虑所有长度为n比特的文件，共有$2^n$个。如果Ultrazip能将每个文件压缩到原来的p倍（p < 1），那么压缩后的文件长度为$\lfloor pn \rfloor$比特。长度为$\lfloor pn \rfloor$比特的文件共有$2^{\lfloor pn \rfloor}$个。

由于$2^n > 2^{\lfloor pn \rfloor}$（因为$n > pn$），根据抽屉原理（pigeonhole principle），至少有两个不同的n比特文件会被压缩成同一个$\lfloor pn \rfloor$比特文件。一旦压缩，这两个文件就再也无法区分——信息已经丢失。

这就是著名的压缩不可能定理：任何无损压缩算法，如果它能让某些文件变小，就必然会让另一些文件变大。

这不是算法设计者的无能，而是组合数学的铁律。

一个具体的例子

考虑所有3比特长的文件：

000  001  010  011  100  101  110  111

共有8个。如果压缩算法声称能达到66%的压缩率，那么所有文件都会被压缩成2比特：

00  01  10  11

只有4个可能的输出。8个输入映射到4个输出，必然有碰撞。一旦发生碰撞，就无法无损还原。

香农第一定理：压缩的数学边界

既然不可能压缩所有文件，那么对于特定的数据，压缩的极限在哪里？

Shannon在1948年的论文中给出了答案。**香农第一定理（信源编码定理）**指出：

对于熵为$H(X)$的信源，任何无损编码的平均码长$L$满足：

$$H(X) \leq L < H(X) + 1$$

熵$H(X)$就是压缩的下限。理解这个公式，需要理解什么是"熵"。

熵：信息的度量

熵是对不确定性的度量。考虑一个简单的例子：抛一枚硬币。

  • 如果是普通硬币，正反面概率各50%，熵为1比特。你需要1比特来记录结果（0=正面，1=反面）。
  • 如果这枚硬币两面都是正面，概率是100%和0%，熵为0比特。结果完全确定，不需要任何信息来记录。

熵的公式$H = -\sum p_i \log_2 p_i$精确地量化了这种"不确定性"。

对于英文字母，Shannon在1951年通过实验测得其熵约为1.0-1.5比特/字符（取决于上下文预测）。而如果26个字母等概率出现，熵应为$\log_2 26 \approx 4.7$比特/字符。

这个差距意味着：英文文本中存在大量的冗余。正是这些冗余，让压缩成为可能。

熵的直观理解

想象你要发送一条消息，内容是明天的天气预报。如果你在撒哈拉沙漠，“晴天"几乎是确定的，你几乎不需要发送任何信息。但如果你在多雨的伦敦，天气高度不确定，你需要更多比特来传达信息。

这就是熵的本质：熵越高，消息携带的信息越多；熵越低，消息越可预测，需要的比特越少。

压缩的本质，就是利用数据的可预测性，用更少的比特表示同样的信息。

柯尔莫哥洛夫复杂度：更深层的不可能

香农熵考虑的是概率分布，但现实中的数据往往是一个确定的字符串。对于单个字符串，我们如何定义其"可压缩性”？

1965年，苏联数学家Andrey Kolmogorov提出了另一个视角：一个字符串的复杂度，定义为能够生成该字符串的最短程序的长度。

用形式化的语言：字符串$x$的柯尔莫哥洛夫复杂度$K(x)$是在通用图灵机上输出$x$的最短程序的比特长度。

这个定义揭示了一个深刻的事实：绝大多数字符串是不可压缩的。

随机字符串不可压缩

考虑一个长度为n的随机比特串。有多少比例的字符串可以被压缩至少c比特？

答案是：不超过$2^{-c}$。

原因很简单。能被压缩至少c比特的字符串，意味着存在一个长度不超过$n-c$的程序能生成它。长度不超过$n-c$的程序最多有$2^{n-c+1}$个（考虑不同长度）。而长度为n的字符串有$2^n$个。比例就是$2^{n-c+1}/2^n = 2^{-c+1}$。

换句话说：如果压缩c比特，最多只有$1/2^{c-1}$的字符串能被压缩。对于c=10，这个比例只有约0.1%。

这意味着，压缩算法的有效性，完全依赖于数据本身的规律性。真正随机的数据，几乎不可能被压缩。

一个不可计算的事实

柯尔莫哥洛夫复杂度还有一个令人沮丧的性质：它是不可计算的。

给定任意字符串，不存在通用算法能计算其柯尔莫哥洛夫复杂度。这是由于停机问题——判断一个程序是否会停机是不可判定的。如果存在算法能计算任意字符串的复杂度，我们就能解决停机问题。

所以，虽然柯尔莫哥洛夫复杂度给出了压缩的理论极限，但我们永远无法精确知道某个数据离这个极限有多远。

压缩算法的三代演进

理论归理论，实践归实践。虽然我们无法突破数学极限，但可以无限逼近它。过去五十年，压缩算法经历了三代演进。

第一代：熵编码

Huffman编码（1952年）是最早被广泛应用的熵编码方法。其核心思想非常直观：出现频率高的符号用短码，出现频率低的符号用长码。

假设一段英文文本中，字母’e’出现概率为12.7%，‘z’为0.07%。Huffman编码会给’e’分配较短的码字（如"00"），而给’z’分配较长的码字（如"11010"）。

Huffman编码是最优前缀码——在所有满足前缀性质（没有任何码字是另一个码字的前缀）的编码方案中，Huffman编码的平均码长最短。

但它有一个关键限制：每个码字必须是整数比特。如果某个符号的概率是0.99，其最优码长应为$-\log_2(0.99) \approx 0.014$比特，但Huffman编码至少需要1比特。这导致Huffman编码在某些情况下会浪费空间。

算术编码（1979年）解决了这个问题。它不再为每个符号分配独立的码字，而是将整个消息编码为一个[0, 1)区间内的实数。

例如，消息"ABB"可能被编码为区间[0.25, 0.3125)内的某个数。解码器只需要这个数和原始概率表，就能还原出完整消息。算术编码可以达到理论最优——无限逼近香农极限。

代价是计算复杂度。每次编码一个符号，都需要进行乘法和除法运算，速度远慢于Huffman编码。

2014年，Jarek Duda提出的**ANS（Asymmetric Numeral Systems）**找到了一个绝妙的平衡点。它像算术编码一样精确，又像Huffman编码一样只需要整数运算和查表。Facebook的Zstandard压缩算法就是基于ANS构建的。

第二代：字典编码

熵编码处理的是符号的统计规律，但数据中还存在另一种规律：重复出现的字符串。

1977年，Abraham Lempel和Jacob Ziv发表了划时代的LZ77算法。其核心思想是：不要重复编码已经出现过的内容，用一个指针指回去。

LZ77维护一个"滑动窗口"（通常32KB或更大）。当编码器遇到一个新的字符串时，它在窗口中搜索最长匹配，然后输出一个三元组：(偏移量, 长度, 下一个字符)。

例如，对于字符串"ABABABAB…"：

  • 编码前两个字符"A"和"B"，得到"A", “B”
  • 第三个字符开始匹配：在位置0找到了"AB"，长度为2
  • 输出(偏移=2, 长度=2)，继续…

这种方法的压缩比取决于窗口大小和数据中的重复模式。对于源代码、日志文件等具有大量重复结构的文本，效果极佳。

DEFLATE（1993年）将LZ77和Huffman编码结合起来：先用LZ77替换重复字符串，再用Huffman编码压缩输出。这个组合统治了压缩领域二十年——gzip、zip、PNG都在使用DEFLATE。

第三代：速度与压缩比的重新平衡

进入21世纪，存储成本下降、网络带宽提升，但数据量爆炸式增长。传统的权衡被重新审视。

2016年，Facebook发布了Zstandard (zstd)。它基于LZ77和FSE（Finite State Entropy，ANS的变体），但针对现代CPU架构进行了深度优化。

Zstd的关键创新在于适应现代硬件的设计：

  1. 更大的窗口：不再局限于32KB，可以访问TB级别的上下文
  2. 分支less设计：避免CPU分支预测失败导致的流水线清空
  3. 并行解码：将数据分割成多个独立流，利用多核CPU

测试结果令人瞩目：在相同压缩比下，zstd比gzip快3-5倍；在相同速度下，压缩比提升10-15%。解压速度接近550 MB/s，是gzip的两倍。

另一个极端是LZ4，它将速度做到极致：压缩速度超过500 MB/s，解压速度超过1000 MB/s。代价是压缩比较低——通常只有2:1左右。对于实时数据传输，这个权衡往往是值得的。

不可能三角：压缩比、速度与内存

压缩算法面临一个经典的工程困境：你不可能同时拥有高压缩比、快速压缩和低内存占用。

这是一个三选二的权衡：

         高压缩比
            /\
           /  \
          /    \
    快速压缩 ──── 低内存

为什么高压缩比需要时间？

更高的压缩比意味着更深入地挖掘数据中的规律。LZ77需要搜索更大的滑动窗口，匹配算法需要比较更多的候选位置。算术编码需要更高精度的计算。

如果你想要最好的压缩比，可以选择xz（LZMA2算法）在最高压缩级别。但压缩一个1GB的文件可能需要几分钟。反过来，LZ4可以在几百毫秒内完成，但压缩比可能差一倍。

为什么压缩比和内存相关？

更大的窗口意味着更多的内存。zstd在最高压缩级别可能使用几百MB内存。对于服务器，这通常可以接受；但对于嵌入式设备，可能需要使用轻量级的压缩方案。

解压速度的特殊地位

有一个有趣的不对称性：解压速度通常远快于压缩速度。

原因是压缩是一个"搜索"过程：需要在窗口中寻找最佳匹配，尝试多种编码方案，比较不同策略的结果。而解压只是"查表"：根据编码规范，逐个还原符号。

这也是为什么许多系统选择"压缩一次，解压多次"的策略。例如，Web服务器预先用高压缩比算法压缩静态资源，用户下载时只需要快速解压。

实战：如何选择压缩算法？

了解理论之后，如何在实践中做出选择？以下是基于场景的建议。

场景一：实时数据传输

要求：压缩和解压都要快，CPU资源有限

推荐：LZ4 或 Snappy

这两个算法都设计用于高吞吐场景。压缩速度接近内存带宽，解压速度更快。虽然压缩比不高（通常1.5-2.5:1），但避免了压缩成为瓶颈。

适用场景：实时日志收集、流式数据处理、RPC通信

场景二：离线存储和归档

要求：最大化压缩比，时间可以接受

推荐：xz（LZMA2）或 zstd最高级别

xz可以达到非常高的压缩比（对于文本数据，往往能达到5:1甚至10:1），但压缩速度很慢。zstd在最高级别（–level=19）也能达到类似效果，解压速度更快。

适用场景：软件发布包、数据库备份、长期归档

场景三：Web资源压缩

要求：平衡压缩比和解压速度

推荐：Brotli 或 zstd

Brotli专为Web优化，内置了针对HTML/CSS/JS的预定义字典。zstd则在通用场景表现优异，解压速度更快。

适用场景：HTTP响应压缩、前端静态资源

场景四：数据库列存储

要求：随机访问友好，列级别压缩

推荐：Parquet/ORC内置压缩

列式存储天然有利于压缩（同列数据类型相同，规律性强）。Parquet和ORC都支持多种压缩算法（snappy、gzip、zstd），可以根据查询模式和存储成本权衡。

适用场景：数据仓库、OLAP查询

一个实用的基准测试

以下是在Silesia语料库上的典型性能（具体数值因硬件而异）：

算法 压缩比 压缩速度 解压速度
LZ4 2.1:1 500 MB/s 1000 MB/s
Snappy 2.1:1 250 MB/s 500 MB/s
zstd-1 2.8:1 300 MB/s 550 MB/s
zstd-3 3.0:1 150 MB/s 550 MB/s
zstd-19 3.6:1 3 MB/s 550 MB/s
gzip-6 2.7:1 40 MB/s 120 MB/s
xz-6 3.5:1 3 MB/s 50 MB/s

注意：zstd在所有压缩级别下解压速度几乎不变，这是其独特优势。

理论与实践的交汇

回到Shannon在1948年定义的熵。今天，当你在命令行输入zstd -19 large_file.txt时，算法正在做的事情，本质上是在逼近这个七十六年前定义的数学极限。

它永远不会到达那个极限——柯尔莫哥洛夫复杂度是不可计算的——但它可以无限接近。

同时，压缩不可能定理时刻提醒我们：没有免费的午餐。你选择让某些文件变小，就必须接受另一些文件可能变大。你选择高压缩比，就必须付出时间或内存的代价。

这就是数据压缩的数学真相：在理论和工程之间，永远存在着一条由权衡构成的鸿沟。而我们能做的，就是在给定的约束下，找到最优的平衡点。

参考文献

  1. Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal, 27(3), 379-423.
  2. Shannon, C. E. (1951). Prediction and Entropy of Printed English. Bell System Technical Journal, 30(1), 50-64.
  3. Huffman, D. A. (1952). A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the IRE, 40(9), 1098-1101.
  4. Ziv, J., & Lempel, A. (1977). A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory, 23(3), 337-343.
  5. Collet, Y. (2016). Smaller and Faster Data Compression with Zstandard. Facebook Engineering Blog.
  6. Duda, J. (2014). Asymmetric Numeral Systems: Entropy Coding Combining Speed of Huffman Coding with Compression Rate of Arithmetic Coding. arXiv:1311.2540.
  7. Mahoney, M. (2012). Adaptive Weighing of Context Models for Lossless Data Compression. Florida Tech Technical Report.
  8. Li, M., & Vitányi, P. (2008). An Introduction to Kolmogorov Complexity and Its Applications (3rd ed.). Springer.
  9. Cover, T. M., & Thomas, J. A. (2006). Elements of Information Theory (2nd ed.). Wiley.
  10. Matt Might. Why Guaranteed File Compression is Impossible. https://matt.might.net/articles/why-infinite-or-guaranteed-file-compression-is-impossible/