霍夫曼编码

定义

霍夫曼编码是一种用于无损数据压缩的熵编码方法，属于可变字长编码(VLC)的一类。^[2] 它把待压缩数据看成由若干源符号组成的序列，为每个符号指定一个由 0 和 1 构成、长度不等的码字，使高频符号用短码、低频符号用长码，从而缩短整段数据的平均码长。^[1]

这样得到的码字集合满足前缀性质，即任何码字都不构成另一个码字的前缀，因此各码字直接首尾相接就能被唯一地逐符号译码，传输和存放时无需插入分隔标记。^[2] 描述这种码的树形结构通常称为霍夫曼树，也称最优二叉树，它是带权路径长度最短的二叉树。^[2]

原理

构造霍夫曼码的出发点是各符号的出现概率或频次表。算法把每个符号视为一个带权的叶子结点，反复从当前集合中取出权值最小的两个结点，合并为一个新的父结点，其权值为两个子结点之和，再把父结点放回集合并重新比较；这一过程持续到只剩一个根结点为止。^[1] 随后从根出发向叶子遍历，左右分支分别记 0 和 1，到达叶子时途经的分支序列就是该符号的码字。^[1]

由于每次合并都发生在权值最小的结点之间，出现最频繁的符号离根最近、码长最短，最不频繁的两个符号总是位于最深的一层且只在最后一位上不同。^[1] 用最小堆维护候选结点时，n 个符号的建树过程复杂度为 $O(n \log n)$。^[1]

算法给出的平均码长 $L$ 满足 $H(S) \le L < H(S)+1$，其中 $H(S)$ 是信源的熵，单位为比特每符号；这一界说明在给定概率分布的二进制前缀码中，霍夫曼编码的期望码长最短。^[1] 下图给出 4 个符号、频次分别为 5、3、1、1 时的合并过程。

flowchart BT

A["a:5"] --> P1["10"]

B["b:3"] --> P1

C["c:1"] --> P2["2"]

D["d:1"] --> P2

P2 --> P1

译码是编码的逆过程：从根结点开始按位读入，读到 0 走左分支、读到 1 走右分支，落到叶子即输出对应符号并回到根结点继续。^[3] 实际系统中还常用规范霍夫曼码，约定同长度码字按符号顺序连续编号、长码的数值总大于短码，这样只需传送各符号的码长即可复原码表，显著减小码表开销。^[1]

发展历程

霍夫曼编码出自大卫·霍夫曼 1951 年在麻省理工学院完成的一份学期报告选题。当时他的导师罗伯特·法诺(Robert M. Fano)给出的题目是寻找最有效的二进制编码；已有的香农-范诺编码采用自顶向下的分拆方式，不总能得到最优结果，霍夫曼转而尝试自底向上合并概率最小的符号，并证明了所得方案的最优性。^[2]

1952 年，霍夫曼在《Proceedings of the Institute of Radio Engineers》上发表论文《一种构建极小冗余编码的方法》(A Method for the Construction of Minimum-Redundancy Codes)，系统给出了这一编码方法，该文此后成为信息论领域被引用最多的文献之一。^[1]

20 世纪 70 年代，牛顿·法勒(Newton Faller)与罗伯特·加拉格(Robert Gallager)分别提出自适应霍夫曼编码，使编码树随符号流实时更新，收发两端各自维护同步的树，因而无需单独传送码表，适用于流式与实时传输场合。^[1] 1993 年前后，菲尔·卡茨(Phil Katz)将 LZ77 字典压缩与霍夫曼编码组合成 DEFLATE，用于 PKZIP 第二版，该格式后来由 IETF 以 RFC 1951 标准化，并被 gzip、PNG、ZIP 等格式沿用。^[4]

应用

通用无损文件压缩是霍夫曼编码最主要的落地场景。DEFLATE 先用 LZ77 把重复出现的字符串替换为长度-距离对，再对字面量和长度、距离符号分别建立霍夫曼表进行熵编码，gzip、zlib、ZIP 与 PNG 都建立在这一组合之上。^[4] DEFLATE 提供固定与动态两种模式：前者使用规范中预先定义的码表、无需在数据流中传送树结构，后者针对每个数据块重新建树并随块传送码长信息，压缩率通常更高但带有额外开销。^[5]

在多媒体领域，JPEG 用霍夫曼编码压缩量化后的离散余弦变换系数，MP3 用它压缩量化后的频谱系数，MPEG 与 H.26x 系列视频标准也包含霍夫曼或与之相关的熵编码环节。^[1] 此外，霍夫曼编码还用于传真、数字存档等需要完整保留原始数据的场合，黑白传真信源常把不同长度的游程扩展成更大的符号集合后再编码，以改善统计匹配。^[2]

局限

霍夫曼编码的码长只能是整数比特，当符号概率不是 2 的负整数次幂时无法贴合熵的下界，最优性与理论极限之间存在固定差距；当某个符号的概率超过 0.5 时，冗余可能明显增大，低熵信源上的效率尤其不理想。^[6] 把连续多个符号组成块再编码可以减小这一损失并利用符号间的相关性，但块长增大后建树与查表的复杂度迅速上升，实用性受限。^[7]

静态霍夫曼编码需要事先统计符号频率，并把码表或树结构随数据一起保存或传送，码表本身构成额外开销；数据统计分布变化较快时，固定码表还会失效。^[1] 自适应霍夫曼编码虽然免去传送码表，但压缩性能通常低于使用准确统计的静态方案，且译码端需同步执行建树算法，实现更为复杂。^[7]

算术编码按分数比特分配码长，可以更接近信源熵，在长序列上的压缩效果一般优于霍夫曼编码，但计算量和实现复杂度更高。^[6] 在 H.264、HEVC 等较新的视频标准中，上下文自适应二进制算术编码等方案取代了霍夫曼编码，以获得更高的压缩效率。^[1] 霍夫曼编码本身也不利用符号之间的依赖关系，对文本、图像这类存在强相关性的数据，需要先由 LZ 类算法或上下文建模处理冗余，它更多承担最后一级的熵编码角色。^[1]

参见

• DEFLATE —— 把 LZ77 与霍夫曼编码结合起来的无损压缩算法，ZIP、PNG、gzip 均以其为核心。

• LZ77 —— 基于滑动窗口字典的压缩算法，常在霍夫曼编码之前用于消除重复字符串。

• 算术编码 —— 按分数比特分配码长的熵编码方法，压缩效果可更接近信源熵。

• 香农-范诺编码 —— 自顶向下构造前缀码的早期方法，霍夫曼编码克服了其不总最优的缺陷。

• 前缀码 —— 任何码字都不作为其他码字前缀的编码集合，是霍夫曼码可唯一译码的基础。

• 熵编码 —— 依据符号统计特性进行编码的一类无损压缩技术的统称。