霍夫曼编码

简介

在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现几率的方法得到的，出现几率高的字母使用较短的编码，反之出现几率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
例如，在英文中，e的出现几率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。
霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明霍夫曼树的WPL是最小的。

历史

1951年，霍夫曼在麻省理工学院（MIT）攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。导师罗伯特·法诺（Robert Fano）出的学期报告题目是：查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树。
1952年，于论文《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）中发表了这个编码方法。

示例

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

数据解压缩

简单来说，霍夫曼码树的解压缩就是将得到的前置码（Prefix Huffman code）转换回符号，通常借由树的追踪（Traversal），将接收到的比特串（Bits stream）一步一步还原。但是要追踪树之前，必须要先重建霍夫曼树；某些情况下，如果每个符号的权重可以被事先预测，那么霍夫曼树就可以预先重建，并且存储并重复使用，否则，发送端必须预先发送霍夫曼树的相关信息给接收端。
最简单的方式，就是预先统计各符号的权重并加入至压缩之比特串，但是此法的运算量花费相当大，并不适合实际的应用。若是使用Canonical encoding，则可精准得知树重建的数据量只占B2^B比特（其中B为每个符号的比特数（bits））。如果简单将接收到的比特串一个比特一个比特的重建，例如：'0'表示父节点，'1'表示终端节点，若每次读取到1时，下8个比特则会被解读是终端节点（假设数据为8-bit字母），则霍夫曼树则可被重建，以此方法，数据量的大小可能为2~320字节不等。虽然还有很多方法可以重建霍夫曼树，但因为压缩的数据串包含"traling bits"，所以还原时一定要考虑何时停止，不要还原到错误的值，如在数据压缩时时加上每笔数据的长度等。

基本性质

考量到不同的应用领域以及该领域的平均性质，将会使用不同的通用几率，又或者，这个几率是可以从被压缩文本中的实际频率所获取。

最优化

原始的霍夫曼算法是一个符号与符号间已知输入几率分布的最佳编码方式，也就是说将不相关的符号个别编码为如此的数据流。然而，当符号间的限制被舍弃或是质量几率函数是未知的时候，如此方式则并非最优化。此外，当这些符号之间不是互相独立，且分布不相同的时候，单一一个符号可能不足以实现最优化。在这种情况之下，算术编码可能比起霍夫曼编码会有更佳的压缩能力。
虽然上述两种方法都可以组合任意数量的符号以实现更高效的编码效果，并且通常适应于实际的输入统计层面，但尽管最简单的版本比霍夫曼编码更慢且更复杂，算术编码不会显著增加其计算或算法复杂度。当输入概率不是精确已知或在流内显著变化时，这种灵活性特别有用。然而，霍夫曼编码通常更快，并且算术编码在历史上是专利问题的一些主题。因此，许多技术历来避免使用有利于霍夫曼和其他前缀编码技术的算术编码。截至2010年中期，随着早期专利的到期，这种替代霍夫曼编码的最常用技术已经进入公有领域。
对于具有均匀概率分布的一组符号，以及作为2的幂之成员，霍夫曼编码等同于简单的二进位制编码，例如 ASCII 编码。这反映了如此的事实：无论压缩方法是什么，这种输入都不可能进行压缩，或只是说对数据无所作为，比起压缩才是才是最佳选择。
在任何情况下，霍夫曼编码在所有方法中是最佳的方式，其中每个输入符号是具有二元几率的已知独立且相同分布的随机变量。前缀码，特别是霍夫曼编码，往往在小字母表上产生较差的效率，其中概率通常落在这些最佳（二元）点之间。当最可能符号的概率远超过0.5时，可能发生霍夫曼编码的最坏情况，使低效率的上限无限制。
在使用霍夫曼编码的同时，有两种相关的方法可以解决这种特定的低效问题。将固定数量的符号组合在一起（阻塞）通常会增加（并且永不减少）压缩。随着块的大小接近无穷大，霍夫曼编码理论上接近熵限制，即最佳压缩。然而，阻塞任意大的符号组是不切实际的，因为霍夫曼代码的复杂性在要编码的可能性的数量上是线性的，这是在块的大小中呈指数的数字。这限制了在实践中完成的阻塞量。
广泛使用的实际替代方案是行程编码。该技术在熵编码之前增加一步，特别是对重复符号进行运行次数的计数，然后对其进行编码。对于伯努力（Bernoulli）过程的简单情况，哥伦（Golomb）编码在编码游程长度的前缀码中是最佳的，这是通过霍夫曼编码技术证明的事实。使用改进的霍夫曼编码的传真机采用类似的方法。但是，游程编码并不像其他压缩技术那样适应许多输入类型。

变化

霍夫曼编码有派生出许多的许多变化，其中一些使用类似霍夫曼的算法，而其他一些算法找到最佳前缀码（例如，对输出施加不同的限制）。注意，在后一种情况下，该方法不需要像霍夫曼那样，实际上甚至不需要到多项式复杂度。

多元树霍夫曼编码

多元树霍夫曼编码算法使用{0, 1, ... , n − 1} 字母来编码消息并构建一个多元树。霍夫曼在他的原始论文中考虑了这种方法。对于二进制（n=2）代码应用相同的算法，除了n个最不可能的符号被一起使用，而不是仅2个最不可能的符号。注意，对于大于2的n，并非所有源字集都可以正确地形成用于霍夫曼编码的多元树。在这些情况下，必须添加额外的0概率占位符。这是因为树必须形成一个n到1的承包商;对于二进制编码，这是一个2比1的承包商，任何大小的集合都可以形成这样的承包商。如果源字的数量与1模n-1一致，则源字集将形成适当的霍夫曼树。

自适应霍夫曼编码

自适应霍夫曼编码的变化，涉及基于源符号序列中的最近实际频率动态地计算概率，以及改变编码树结构以匹配更新的概率估计。它在实践中很少使用，因为更新树的成本使其比优化的自适应算术编码慢，后者更灵活并且具有更好的压缩。

霍夫曼模板算法

在霍夫曼编码的实现中，通常会使用权重表示数值概率，但是上面给出的算法不需要这样;它只需要权重形成一个完全有序的可交换幺半群，这意味着一种订购权重和添加权重的方法。霍夫曼模板算法使人们能够使用任何类型的权重（成本，频率，权重对，非数字权重）和许多组合方法之一（不仅仅是加法），这个问题首先应用于电路设计。

长度限制霍夫曼编码

长度受限的霍夫曼编码是一种变体，其目标仍然是实现最小加权路径长度，但是存在另外的限制，即每个码字的长度必须小于给定常量。包合并算法通过一种与霍夫曼算法非常相似的简单贪婪方法解决了这个问题。

不相等成本霍夫曼编码

在标准的霍夫曼编码问题中，假设集合中构成码字的每个符号具有相同的传输成本：长度为N位的码字总是具有N的成本，无论多少这些数字是0，有多少是1，等等。在这个假设下工作时，最小化消息的总成本和最小化数字总数是相同的。
具有不等字母成本的霍夫曼编码是没有这种假设的概括：由于传输介质的特性，编码字母表的字母可能具有不均匀的长度。一个例子是摩尔斯电码的编码字母表，其中'破折号'比'点'需要更长的发送时间，因此传输时间中破折号的成本更高。目标仍然是最小化加权平均码字长度，但仅仅最小化消息使用的符号数量已经不够了。没有算法以与传统霍夫曼编码相同的方式或相同的效率来解决这个问题，尽管它已经由卡普（Karp）解决，其解决方案已经针对哥林（Golin）的整数成本的情况进行了改进。

最佳字母二叉树

在标准霍夫曼编码问题中，假设任何码字可以对应于任何输入符号。在字母表中，输入和输出的字母顺序必须相同。

规范霍夫曼编码

如果对应于按字母顺序排列的输入的权重是按数字顺序排列的，则霍夫曼代码具有与最佳字母代码相同的长度，这可以从计算这些长度中找到，从而不需要使用胡- 塔克（Hu-Tucker）编码。由数字（重新）有序输入产生的代码有时被称为规范霍夫曼代码，并且由于易于编码/解码，通常是实践中使用的代码。用于找到该代码的技术有时被称为霍夫曼- 香农 - 法诺编码，因为它像霍夫曼编码一样是最优的，但是在重量概率上是字母的，例如香农- 法诺编码。

示范程序

1 // 以下為C++程式碼，在G++下編譯通過 2 // 僅用於示範如何根據權值建構霍夫曼樹， 3 // 沒有經過性能上的優化及加上完善的異常處理。 4 #include <cstdlib> 5 #include <iostream> 6 #include <deque> 7 #include <algorithm> 8  9 using namespace std;10 11 const int size = 10;12 struct node {                               // 霍夫曼樹節點結構13     unsigned key;                           // 保存權值14     node *lchild;                           // 左孩子指針15     node *rchild;                           // 右孩子指針16 };17 deque<node *> forest;18 deque<bool> code;                           // 此處也可使用bitset19 node *ptr;20 int frequency[size] = {0};21 22 void printCode(deque<bool> ptr);            // 用於輸出霍夫曼編碼23 24 bool compare( node *a, node *b) {25     return a->key < b->key;26 }27 int main(int argc, char *argv[]) {28     for (int i = 0; i < size; i++) {29         cin >> frequency[i];                // 輸入10個權值30         ptr = new node;31         ptr->key = frequency[i];32         ptr->lchild = NULL;33         ptr->rchild = NULL;34         forest.push_back(ptr);35     } // 形成森林，森林中的每一棵樹都是一個節點36     // 從森林構建霍夫曼樹37     for (int i = 0; i < size - 1; i++) {38         sort(forest.begin(), forest.end(), compare);39         ptr = new node;40         // 以下代碼使用下標索引隊列元素，具有潛在危險，使用時請注意41         ptr->key = forest[0]->key + forest[1]->key;42         ptr->lchild = forest[0];43         ptr->rchild = forest[1];44         forest.pop_front();45         forest.pop_front();46         forest.push_back(ptr);47     }48     ptr = forest.front(); // ptr是一個指向根的指針49     system("PAUSE");50     return EXIT_SUCCESS;51 }52 53 void printCode(deque<bool> ptr) {54     // deque<bool>55     for (int i = 0; i < ptr.size(); i++) {56         if (ptr[i])57             cout << "1";58         else59             cout << "0";60     }61 }