Zstandard 压缩算法原理:从字典阶段到 FSE 熵编码

Zstandard 是近几年被广泛使用的现代无损压缩算法,Linux 内核、文件系统、数据库备份、容器镜像压缩都在用它。它并非从零开始的天才发明,而是把两件"压缩流水线里的老工具"重新组合,再替换其中一个关键模块。下面从它的工作原理和设计取舍说起,顺便和经典的 DEFLATE 做个对比,帮你建立直觉。

什么是 Zstandard

Zstandard(社区习惯简称 Zstd)是一种无损压缩算法,目标是"在大多数真实数据上拿到接近当前最优的压缩率,同时保持非常高的解压速度"。它由 Facebook 开源,实现采用 C 语言,既是压缩器也是解压器,同一份代码既负责压也负责解。

把它放回压缩流水线的语境里看,Zstandard 走的依然是经典的"两阶段"路子:先把重复的结构找出来,再对剩余的统计冗余做编码。这与已经存在多年的 DEFLATE 在结构上是同一条思路,但具体每一阶段都换上了更新的实现细节,这也是它在现代场景里更受欢迎的根本原因。

两阶段流水线的老骨架

任何"无损压缩"基本都可以拆成两步理解:

第一步是字典阶段,负责找出输入里重复出现的字节片段。具体方法是设一个滑动窗口,在窗口里查找当前位置之后的若干字节是否出现过;一旦找到匹配,就用"距离 + 长度"这一对短引用把那段重复内容替换掉,从而避免了"第二次出现时还得再写一遍"的浪费。

第二步是熵编码阶段,负责把第一步替换后剩下的字节流转换成更紧凑的表示。我们已经知道每个位置上各符号出现的概率不同,因此可以用更短的码给高频符号、长码给低频符号,从而在统计意义上再砍掉一截冗余。两阶段合起来,组成了几乎所有现代通用压缩器的骨架。

Zstandard 也不例外。两阶段它都有,而且两阶段都比 DEFLATE 做得更激进一些。

与 DEFLATE 相同的那一段:字典阶段

在字典阶段,Zstandard 用的是和 DEFLATE 相近的滑动窗口 + 字符串匹配思路:为输入的每一段在窗口里寻找最长匹配,匹配上了就用"距离多少、长度多少"这两个数来表示。这与 LZ77 系列一脉相承,数学上没有本质差别。

不同之处在于搜索策略。DEFLATE 受限于上世纪九十年代的硬件,它的匹配搜索在实现上较保守;而 Zstandard 借助更先进的哈希策略和二叉树搜索,可以在更长的窗口里、用更少的比较找到更长的匹配。直观结果是:在文本、源代码、二进制日志等典型负载上,Zstandard 第一阶段获得的匹配更长、更密集,留下的"未匹配字面量"更少,从而给第二阶段减负。

与 DEFLATE 不同的一段:熵编码阶段

真正的差异化在第二阶段。DEFLATE 用的是霍夫曼编码,这是上世纪五十年代提出的经典方案,稳定可靠,实现简单,但它有一个先天限制:每个符号的码长必须是整数比特。当某个符号的出现概率落在"既不够高也不够低"的中间地带时,霍夫曼编码不得不把码长向上取整,留下一点统计冗余没被榨干。

Zstandard 把这一段换成了更现代的方案 — 有限状态熵编码(FSE, Finite State Entropy),也可以理解为非对称数字系统(ANS)家族的一种工程实现。FSE/ANS 的核心思想是:用一个有限状态机在两个数制(常规整数进制 和 压缩后的"虚拟"进制)之间做双向转换。每个符号被编码时,根据当前状态查表得到要"吐出多少比特",从而可以在亚比特精度上逼近最优编码长度,从霍夫曼无法压榨的最后那一丝冗余里继续抠出空间。

这就是 Zstandard "压缩率更高、解压速度却没掉"的关键:第一阶段在减少冗余上做到位了,第二阶段又把残留的统计冗余榨到接近理论极限。

为什么解压速度还快

一个新读者常有的疑问是:既然 Zstandard 比 DEFLATE 多了 FSE 这种"看起来更复杂"的编码方式,为什么解压速度反而更快?

答案藏在 FSE 的一个工程特性里:FSE 解码本质上是一连串查表与状态转移,绝大多数时候每解出一个符号只需要若干次内存访问和整数加减,而不需要复杂的算术运算;同时它对分支预测友好,可以流水线化。相比之下,算术编码虽然压缩率也能逼近最优,但每解一个符号都要做乘法,在硬件上跑起来就比 FSE 慢一些。

换句话说,FSE 在"接近最优压缩率"和"非常快的解码"之间找到了一个很舒服的工程平衡点。

在哪些场景里选 Zstandard

从公开应用看,Zstandard 适合几类典型负载:

• 结构化文本:日志、源代码、JSON、CSV 等 — 字符串匹配能抓到大量重复,Zstandard 的优势最明显。
• 备份和归档:数据库快照、容器镜像、虚拟机镜像 — 这类负载里字典收益大,且解压速度影响恢复时间。
• 实时传输:网络传输中解压速度直接影响端到端延迟,而 Zstandard 在中低压缩等级下解压速度非常可观。

反过来,已经高度压缩过的数据(例如 JPEG、MP4、ZIP 包)再压一遍收益很小,这时 Zstandard 与 DEFLATE 表现相近 — 这并不是 Zstandard 的失败,而是"信号已经被前一轮算法去掉得差不多了"。

与 LZ4 的取舍对照

同一时期还有另一个常被拿来比较的算法 — LZ4。LZ4 在工程上和 Zstandard 思路接近,但做出了一个明显不同的取舍:牺牲压缩率换取更极致的压缩/解压速度。LZ4 不做熵编码,只用最简单的"距离-长度"对的紧凑表示,然后直接输出。带来的结果是 LZ4 的压缩速度和解压速度都非常夸张,但压缩率低于 Zstandard。

所以"用 LZ4 还是 Zstandard"本质上是在回答一个取舍问题:实时写入、对延迟敏感、压缩比可以稍逊的场景偏向 LZ4;对压缩率有要求、解压速度也希望保持高水平的场景偏向 Zstandard。

结语

Zstandard 的工程价值在于把"经典两阶段骨架 + 现代 FSE 熵编码 + 更聪明的匹配搜索"这三件事干净地拼在一起。它不是某种颠覆式发明,而是把已有思路在工程层面打磨到接近当前硬件能达到的极限。这也是它能在短短几年内被 Linux 内核、文件系统、容器生态广泛接纳的原因。

想进一步了解压缩算法的整体脉络,可以读读 字典编码与熵编码的分工、LZ77 滑动窗口原理,以及 熵编码与霍夫曼/算术编码原理。若关心容器与系统级应用,可参考 分块压缩原理。要做桌面端压缩,可使用 闪压文件压缩 一键调用本地压缩流水线。