字典编码 vs 熵编码：压缩流水线的双引擎如何分工

为什么压缩要分两步走

打开任何主流压缩格式的说明书,你会发现里面从来只有两种编码:字典编码负责把数据里的重复模式"找出来",熵编码负责把已经整理过的符号"压紧"。这两件事单做都不算完整:字典编码再厉害,也只能把一串字符替换成"距离+长度"的指针;熵编码再聪明,如果输入还是原始字节流,它也无从下手。

打个比方,压缩流水线更像搬家。字典编码是先把同类物品归箱,熵编码是再把箱子按体积摆进货车。前一步减少"项目种类",后一步压紧"占用体积"。两步都做,文件才能真正变短。

这也是为什么单独讲"霍夫曼编码"或"算术编码"的文章,总会让人觉得还缺点什么——它们必须搭配前面的"整理"步骤,才能在真实压缩格式里发挥威力。

字典编码:从原始字节到指针串

字典编码的核心思想一句话讲完:用已经出现过的内容,描述还没出现的内容。LZ77 是这一脉最经典的实现:它在数据流里维护一个滑动窗口,把当前位置之前若干范围内的字节当作"字典";遇到一段新内容,就在字典里找最长匹配,然后用"距离+长度"两个数代替这段原文。

打个简单的比方:你抄一段长文本时,如果发现上一页就有几乎一样的一段,你不会逐字再抄,而是写"见上页第几行,抄几字"。字典编码做的就是这件事——它把文本里的重复结构压缩成"指针"。识别重复的能力越强,字典编码的收益越大;反之,如果数据本身没什么重复(比如已经随机化过的密文),字典编码几乎帮不上忙,只能把数据原样吐给下一步。

字典编码不会自己输出最终字节流,它只是把"原始字节"换成了"指针+字面量"的中间表示。真正把这种表示压成最终文件的,是后面接的熵编码。

熵编码:按概率压紧符号

熵编码的工作对象是符号。它关心的是:每个符号出现的概率不一样,那就给常见符号短码、生僻符号长码,这样平均下来每符号用掉的比特就会变少。霍夫曼编码和算术编码是这一脉最常见的两条路。

霍夫曼编码用一棵二叉树,自底向上把概率最低的两个符号先合并,合并后作为一个"伪符号"继续往上合。树的叶子就是最终码字。算术编码走得更远一点,它不再给每个符号发独立的码字,而是给整段消息算一个小数,用这个数本身的位数表示总信息量。

要注意的是:熵编码的输入必须先经过"概率建模"——也就是先估算每个符号出现的可能性。如果前面的字典编码没把重复结构提取出来,熵编码面对的还是一串无规律的字节,概率分布接近均匀,这时无论哪种熵编码都压不动。所以熵编码强不强,取决于前面给它的输入"整不整齐"。

为什么现代格式都是"字典 + 熵"组合拳

理解了前面三节,DEFLATE 这条经典组合就一目了然了:字典编码用 LZ77 找重复、输出指针串,熵编码用霍夫曼把指针串和字面量再压紧。ZIP、gzip、PNG 内核里的 zlib 都是这条路。新一代格式如 Zstandard、LZ4,虽然字典匹配的具体策略不一样(比如用更大的窗口、更快的哈希),但后端依然挂着熵编码,只是细节做了替换。

另一支 PPM 流派则把两步合并得更紧:它直接根据上下文估算下一个字节的概率,然后用算术编码把整段压紧。算术编码在这里既是后端,又吸收了一部分字典的角色。两路流派各有强项,谁也替代不了谁,这也是为什么今天的压缩工具几乎都给了用户两种模式可选。

写在最后:对普通用户意味着什么

回到日常使用,理解"字典在前、熵在后"的分工,有两条直接好处。第一,重复越多,压缩收益越大——文档、图片素材、工程源码这类文件,天然含有大量重复结构,压缩收益通常很可观;而已经加密过的随机数据,再压一遍基本等于浪费电。第二,分块压缩的策略其实就建立在这条规律上:对大文件按内容切成块,块内做字典,块间共享字典信息,可以同时拿到高吞吐和不错的压缩比。

闪压的文件压缩功能,在底层就是把这两步工程化:先按文件类型选用合适的字典策略,再用熵编码后端把指针串压紧。如果想再深入一层,推荐阅读文件压缩算法演进、熵编码原理与 PPM 预测模型,这三篇合在一起,基本把现代无损压缩的主干脉络过了一遍。