哈夫曼编码是一种变长码编码方式，该编码方式是数学家D.A.Huffman于1952年提出，其完全依据字符出现频率来构造平均长度最短的码字。简言之，哈夫曼编码算法是用字符出现的频率来建立一个用0-1串表示各字符的最优表示方式，有时称之为最佳编码，一般就叫作Huffman编码。

01、问题分析——贪心策略

首先，仔细研究编码方案的二叉树结构，不难发现以下4点。

(1) 树的叶子节点为字符。

(2) 从根到叶子的路径经过的01串为相应字符的编码。

(3) 编码长度为该字符在二叉树中的深度。

(4) 编码方案满足前缀码性质。

其次，研究编码方案优劣的衡量标准。平均每个字符的码长，引入平均码长的概念。所谓平均码长指的是编码方案中平均每个字符的码长。

设字符集C，任意一个字符c∈C，出现的频率为f(c)，在二叉树T中的深度为dT(c)(即字符编码的长度)，二叉树T表示的编码方案平均码长为B(T)，则：

哈夫曼编码是使平均码长为最短的编码方式。哈夫曼以字符的使用频率做权构建一棵哈夫曼树，然后利用哈夫曼树对字符进行编码。核心思想是：频率越大的字符离树根越近。

算法的贪心策略是：从树的集合中选取两个频率最低的字符，使其作为左右子树构造一棵新树，父节点的频率为左右节点频率之和，然后将新树插入到树的集合中。

02、算法设计

1●设计思想

输入：字符集C={c1,c2,…,cn}及字符出现的频率f(ci)，i=1,2,…,n。

输出：哈夫曼树Q。

首先将字符集中的每个字符看作一棵只含有根节点的树，构造一个n棵树构成的树的集合Q；然后做n-1次贪心选择，每次都选择两个出现频率最小的节点，让其作为左右子树构造一棵新树，将新树插入到树的集合Q中。直到Q中只含有一棵树为止。
从树根深度优先遍历，左子树输出0、右子树输出1，搜索到叶子节点就得到了叶子字符的编码。

2●算法伪码

算法：Huffman(C)

3●正确性证明

设C是字符集，任意一个字符c的频率为f(c)；x、y是C中具有最小频率的两个字符。

(1) 贪心选择性质——存在从贪心选择开始的最优解。

需证明存在字符集C的一个最优前缀码方案T，使得x、y具有相同的码长，且最后一位编码不同。

如果T中，x、y是最深的叶子且互为兄弟，那么T就是贪心选择开始的最优前缀码；

如果T中，x、y不是最深的叶子，也不是兄弟，那么设T中字符b、c是最深的叶子且互为兄弟，如图2-7所示。

由于x,y是字符集C中频率最小的两个字符，所以有f(x)≤f(b)、f(x)≤f(c)、f(y)≤f(b)、f(y)≤f(c)，交换树T中的字符x和字符b得到树T′，如图2-8所示。

■ 图2-7树T结构示意图 ■ 2-8树T′结构示意

在树T和T′中，只有x、b两个字符深度发生变化，其他字符深度都没有变，所以：

又由于dT(x)=dT′(b)，dT(b)=dT′(x)，所以：

又f(x)-f(b)≤0，dT(x)-dT(b)≤0，

故B(T)-B(T′)≥0，B(T)≥B(T′)。

再交换字符y和字符a，得到树T″，如图2-9所示。

■ 图2-9 树T″结构示意

同理可以证明B(T′)≥B(T″)，由此B(T)≥B(T″)。

又因为T是字符集C的最优前缀码，所以B(T)≤B(T″)。所以B(T)=B(T″)，T″中，x、y字符处于最深处且互为兄弟，是从贪心选择开始的最优解。

（2) 最优子结构性质——整体最优解一定包含子问题的最优解。

设T是字符集C的最优前缀码，令f(z)=f(x)+f(y)，则T′是字符集C′=C-{x,y}+{z}的最优前缀码。

需要证明T′是字符集C′=C-{x,y}+{z}的最优前缀码。

证明： 假设T′不是字符集C′的最优前缀码，则设T″是字符集C′的最优前缀码，B(T′)>B(T″)。
将字符x、y加入到T″中，作为字符z的孩子，构成的树为T"'，则有T"'是字符集C的一种编码方案。

对任意字符c∈C-{x,y}，有dT(c)=dT′(c)，故f(c)dT(c)=f(c)dT′(c)，另一方面dT(x)=dT(y)=dT(z)+1。

则

由此，可以知道，B(T)=B(T′)+f(x)+f(y)，同理有B(T'″)=B(T″)+f(x)+f(y)。

由于B(T′)>B(T″)，所以B(T)>B(T'″)。

这说明T不是字符集C的最优前缀码，这与T是字符集C的最优前缀码矛盾，假设不真，得证。