[科普中国]-霍夫曼编码

霍夫曼编码（Huffman Coding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1

霍夫曼编码（英语：Huffman Coding），又译为哈夫曼编码、赫夫曼编码，是一种用于无损数据压缩的熵编码（权编码）算法。由大卫·霍夫曼在1952年发明。

在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和。

霍夫曼编码（Huffman Encoding）

历史1951年，霍夫曼和他在MIT信息论的同学得选择是完成学期报告还是期末考试。导师罗伯特·法诺出的学期报告题目是，查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码的最大弊端──自顶向下构建树。

1952年，于论文《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）中发表了这个编码方法。

Huffman在1952年根据香农（Shannon）在1948年和范若（Fano）在1949年阐述的这种编码思想提出了一种不定长编码的方法，也称霍夫曼（Huffman）编码。霍夫曼编码的基本方法是先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字，由此得到一张该图像的霍夫曼码表。编码后的图像数据记录的是每个像素的码字，而码字与实际像素值的对应关系记录在码表中。

霍夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就称Huffman编码。下面引证一个定理，该定理保证了按字符出现概率分配码长，可使平均码长最短。

? 定理：在变字长编码中，如果码字长度严格按照对应符号出现的概率大小逆序排列，则其平 均码字长度为最小。

? 现在通过一个实例来说明上述定理的实现过程。设将信源符号按出现的概率大小顺序排列为 ： ?

U： ( a1 a2 a3 a4 a5 a6 a7 ) 1

0.20 0.19 0.18 0.17 0.15 0.10 0.01

? 给概率最小的两个符号a6与a7分别指定为“1”与“0”，然后将它们的概率相加再与原来的 a1~a5组合并重新排序成新的原为：

U′： ( a1 a2 a3 a4 a5 a6′ )

0.20 0.19 0.18 0.17 0.15 0.11

? 对a5与a′6分别指定“1”与“0”后，再作概率相加并重新按概率排序得

U″：（0.26 0.20 0.19 0.18 0.17）…

? 直到最后得 U″″：（0.61 0.39）

? 霍夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码。

例如a7从左至右，由U至U″″，其码字为0000；

? a6按践线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为0001…

? 用霍夫曼编码所得的平均比特率为：Σ码长×出现概率

? 上例为：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit

? 可以算出本例的信源熵为2.61bit，二者已经是很接近了。

Huffman方法构造出来的码并不是唯一的。但对于同一信源而言，其平均码字长是相同的，编码效率是一样的。

Huffman编码对不同信源的编码的编码效率是不同的。只有当信源概率分布不均匀时，Huffman才会收到显著效果。

问题定义与解法广义[编辑]给定

一组符号（Symbol）和其对应的权重值（weight），其权重通常表示成概率（%）。

欲知

一组二元的前置码，其二元码的长度为最短。

狭义[编辑]输入

符号集合{\displaystyle S=\left\{s_{1},s_{2},\cdots ,s_{n}\right\}}，其S集合的大小为{\displaystyle n}。

权重集合{\displaystyle W=\left\{w_{1},w_{2},\cdots ,w_{n}\right\}}，其W集合不为负数且{\displaystyle w_{i}=\mathrm {weight} \left(s_{i}\right),1\leq i\leq n}。

输出

一组编码{\displaystyle C\left(S,W\right)=\left\{c_{1},c_{2},\cdots ,c_{n}\right\}}，其C集合是一组二进制编码且{\displaystyle c_{i}}为{\displaystyle s_{i}}相对应的编码，{\displaystyle 1\leq i\leq n}。

目标

设{\displaystyle L\left(C\right)=\sum _{i=1}^{n}{w_{i}\times \mathrm {length} \left(c_{i}\right)}}为{\displaystyle C}的加权的路径长，对所有编码{\displaystyle T\left(S,W\right)}，则{\displaystyle L\left(C\right)\leq L\left(T\right)}

示例[编辑]霍夫曼树常处理符号编写工作。根据整组数据中符号出现的频率高低，决定如何给符号编码。如果符号出现的频率越高，则给符号的码越短，相反符号的号码越长。假设我们要给一个英文单字**"F O R G E T"**进行霍夫曼编码，而每个英文字母出现的频率分别列在Fig.1。

演算过程[编辑]

（一）进行霍夫曼编码前，我们先创建一个霍夫曼树。

⒈将每个英文字母依照出现频率由小排到大，最小在左，如Fig.1。

⒉每个字母都代表一个终端节点（叶节点），比较F.O.R.G.E.T六个字母中每个字母的出现频率，将最小的两个字母频率相加合成一个新的节点。如Fig.2所示，发现F与O的频率最小，故相加2+3=5。

⒊比较5.R.G.E.T，发现R与G的频率最小，故相加4+4=8。

⒋比较5.8.E.T，发现5与E的频率最小，故相加5+5=10。

⒌比较8.10.T，发现8与T的频率最小，故相加8+7=15。

⒍最后剩10.15，没有可以比较的对象，相加10+15=25。

最后产生的树状图就是霍夫曼树，参考Fig.2。
（二）进行编码

1.给霍夫曼树的所有左链接'0'与右链接'1'。

2.从树根至树叶依序记录所有字母的编码，如Fig.3。

实现方法数据压缩[编辑]实现霍夫曼编码的方式主要是创建一个二叉树和其节点。这些树的节点可以存储在数组里，数组的大小为符号（symbols）数的大小n，而节点分别是终端节点（叶节点）与非终端节点（内部节点）。

一开始，所有的节点都是终端节点，节点内有三个字段：

1.符号（Symbol）

2.权重（Weight、Probabilities、Frequency）

3.指向父节点的链接（Link to its parent node）

而非终端节点内有四个字段：

1.权重（Weight、Probabilities、Frequency）

2.指向两个子节点的链接（Links to two child node）

3.指向父节点的链接（Link to its parent node）

基本上，我们用'0'与'1'分别代表指向左子节点与右子节点，最后为完成的二叉树共有n个终端节点与n-1个非终端节点，去除了不必要的符号并产生最佳的编码长度。

过程中，每个终端节点都包含着一个权重（Weight、Probabilities、Frequency），两两终端节点结合会产生一个新节点，新节点的权重是由两个权重最小的终端节点权重之总和，并持续进行此过程直到只剩下一个节点为止。

实现霍夫曼树的方式有很多种，可以使用优先队列（Priority Queue）简单达成这个过程，给与权重较低的符号较高的优先级（Priority），算法如下：

⒈把n个终端节点加入优先队列，则n个节点都有一个优先权Pi，1 ≤ i ≤ n

⒉如果队列内的节点数>1，则：

⑴从队列中移除两个最小的Pi节点，即连续做两次remove（min（Pi）, Priority_Queue)

⑵产生一个新节点，此节点为（1）之移除节点之父节点，而此节点的权重值为（1）两节点之权重和

⑶把（2）产生之节点加入优先队列中

⒊最后在优先队列里的点为树的根节点（root）

而此算法的时间复杂度（Time Complexity）为O（nlogn）；因为有n个终端节点，所以树总共有2n-1个节点，使用优先队列每个循环须O（logn）。

此外，有一个更快的方式使时间复杂度降至线性时间（Linear Time）O（n），就是使用两个队列（Queue）创件霍夫曼树。第一个队列用来存储n个符号（即n个终端节点）的权重，第二个队列用来存储两两权重的合（即非终端节点）。此法可保证第二个队列的前端（Front）权重永远都是最小值，且方法如下：

⒈把n个终端节点加入第一个队列（依照权重大小排列，最小在前端）

⒉如果队列内的节点数>1，则：

⑴从队列前端移除两个最低权重的节点

⑵将（1）中移除的两个节点权重相加合成一个新节点

⑶加入第二个队列

⒊最后在第一个队列的节点为根节点

虽然使用此方法比使用优先队列的时间复杂度还低，但是注意此法的第1项，节点必须依照权重大小加入队列中，如果节点加入顺序不按大小，则需要经过排序，则至少花了O（nlogn）的时间复杂度计算。

但是在不同的状况考量下，时间复杂度并非是最重要的，如果我们今天考虑英文字母的出现频率，变量n就是英文字母的26个字母，则使用哪一种算法时间复杂度都不会影响很大，因为n不是一笔庞大的数字。2

数据解压缩[编辑]简单来说，霍夫曼码树的解压缩就是将得到的前置码（Prefix Huffman code）转换回符号，通常借由树的追踪（Traversal），将接收到的比特串（Bits stream）一步一步还原。但是要追踪树之前，必须要先重建霍夫曼树 ；某些情况下，如果每个符号的权重可以被事先预测，那么霍夫曼树就可以预先重建，并且存储并重复使用，否则，发送端必须预先发送霍夫曼树的相关信息给接收端。

最简单的方式，就是预先统计各符号的权重并加入至压缩之比特串，但是此法的运算量花费相当大，并不适合实际的应用。若是使用Canonical encoding，则可精准得知树重建的数据量只占B2^B比特（其中B为每个符号的比特数（bits））。如果简单将接收到的比特串一个比特一个比特的重建，例如：'0'表示父节点，'1'表示终端节点，若每次读取到1时，下8个比特则会被解读是终端节点（假设数据为8-bit字母），则霍夫曼树则可被重建，以此方法，数据量的大小可能为2~320字节不等。虽然还有很多方法可以重建霍夫曼树，但因为压缩的数据串包含"traling bits"，所以还原时一定要考虑何时停止，不要还原到错误的值，如在数据压缩时时加上每笔数据的长度等。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所