规范霍夫曼编码原理:一张码表如何写进压缩包再被还原

压缩包里的文件不会原样存放,它要先变成一串更短的比特。这一步靠熵编码,最经典的实现是霍夫曼编码。霍夫曼编码的产物是一棵二叉树:符号挂在叶子上,从根走到叶子时每一步往左还是往右,就构成了这个符号的编码。想补齐熵编码的整体框架,可以先看熵编码与霍夫曼编码的基本思路。

码表为什么不直接写进文件

一棵霍夫曼树要向解码端交代两件事:每个符号对应哪一串比特,以及符号之间是什么从属关系。最直白的做法,是把"符号到完整码字"的映射逐条写进压缩包。这条路走不通,低频符号的码字往往很长,一个符号就可能占用几十个比特,写一遍、存一遍都很亏。

更省的办法是只写"每个符号占几位",也就是码长。所有符号的码长加起来,通常远小于逐条展开完整码字的总长度。

关键问题随即出现:只传码长,解码端真能把那棵树还原出来吗?能,但需要一条明确的规则,否则两端会各自造出不同的树。

规范霍夫曼编码如何让两端对同一棵树达成一致

这条规则就叫规范霍夫曼编码。它的思路是给整棵树定一个统一排序:先按码长从短到长排,码长相同的再按符号本身的先后排,然后依次发放码字,排在最前面的符号拿最短的码。

排好序之后,发码字这件事其实没有自由度了。头一个码字取全零或全一,后面每一个码字,都是在同长度里挑一个还没用过的数,同时要落在前一个码字之下、同长度的其他码字之上。长度相同的码字互为兄弟,谁也不能成为谁的前缀。

这套规则的妙处在于:码长集合和符号顺序一旦相同,重建出来的树就是唯一的。编码端和解压端不必在文件里额外商量"我们用的是哪一棵树",各自按同一条规则算一遍,结果必然一致。

不做规范化当然也行,只是编码端得把整棵树的形状描述一遍:每个内部节点连着哪两个孩子,每个叶子对应哪个符号。树有分叉就有组合余地,描述起来又长又容易出错。规范化把"描述树"降级成"描述长度",信息量小得多。

码长表自己也需要被压缩

码长表不是免费的。符号一多,这张表也会明显占空间。

DEFLATE 的处理办法很典型。它先对码长序列做一轮游程编码,把连续相同的码长合并成"这个码长连续出现了多少次",再对压缩后的结果做熵编码。前一步消灭冗余,后一步榨干统计规律,两步下来,码长表本身也被压到了很小的体量。

所以在真实格式里,规范霍夫曼编码和游程编码经常是搭配着出现的,它们解决的是同一类问题的两个不同侧面:前者压缩"码字怎么分配",后者压缩"长度怎么重复"。

这套设计在真实格式里的位置

DEFLATE 是理解这套机制的好例子,它的两阶段流水线里的熵编码环节就按这个思路做。它的动态块会在压缩数据之前先写一段码长描述,解压端先按规范规则把树建好,再去解后面的主体数据。ZIP、PNG、gzip 都建立在 DEFLATE 之上,所以同一套码表逻辑被无数文件格式共用。

把视角再拉高一点。字典编码与熵编码的分工讲的是两个阶段如何接力,而码表传输是熵编码这一环必须自己解决的前置问题。搞不定它,前面省下的比特就可能被码表重新吃回去。这也是为什么压缩格式每次演进,码表这一块都会被重新设计一遍。

对普通用户意味着什么

这套机制最终以"解压时不需要额外说明"的形式呈现。解压工具知道该按哪套规则重建码表,因为规则是写死在格式里的,不是包作者临时决定的。

这也解释了为什么同一套工具既能解开很老的包,也能解开很新的包:格式变了,解码器跟着升级就行,包之间不需要互相知道对方的私有约定。

想亲手感受一下压缩流程,可以打开闪压主窗口左侧的"文件压缩"模块,把文件拖进去,选好输出格式后点"开始压缩"。进度条走完会弹出"压缩完成"提示,里面直接告诉你省下了多少体积;更多格式与打包需求,可以看看闪压文件压缩这个功能页。