讲解哈夫曼编码算法的贪心策略及正确性证明。
哈夫曼编码是一种变长码编码方法，该编码方法是数学家D.A.Huffman于1952年提出哈夫曼编码贪心算法时间复杂度，其完全根据字符出现频度来构造平均宽度最短的码字。简言之，哈夫曼编码算法是用字符出现的频度来构建一个用0-1串表示各字符的最优表示方法，有时称之为最佳编码，一般就叫作Huffman编码。
01
问题剖析——贪心策略
首先，仔细研究编码方案的二叉树结构，不难发觉以下4点。
(1) 树的叶子节点为字符。
(2) 从根到叶子的路径经过的01串为相应字符的编码。
(3) 编码宽度为该字符在二叉树中的深度。
(4) 编码方案满足前缀码性质。
其次，研究编码方案好坏的评判标准。平均每位字符的码长，引入平均码长的概念。所谓平均码长指的是编码方案中平均每位字符的码长。
设字符集C，任意一个字符c∈C，出现的频度为f(c)，在二叉树T中的深度为d T(c) (即字符编码的宽度)，二叉树T表示的编码方案平均码长为B(T)，则：
哈夫曼编码是使平均码长为最短的编码方法。哈夫曼以字符的使用频度做权建立一棵哈夫曼树，然后借助哈夫曼树对字符进行编码。核心思想是：频率越大的字符离树枝越近。
算法的贪心策略是：从树的集合中选定两个频率最低的字符，使其作为左右子树构造一棵新树，父节点的频度为左右节点频度之和，然后将新树插入到树的集合中。
02
算法设计
●
设计思想
输入：字符集C={c 1 ,c 2 ,…,c n }及字符出现的频度f(c i )，i=1,2,…,n。
输出：哈夫曼树Q。
首先将字符集中的每位字符看作一棵只富含根节点的树，构造一个n棵树构成的树的集合Q；然后做n-1次贪心选择，每次都选择两个出现频度最小的节点，让其作为左右子树构造一棵新树，将新树插入到树的集合Q中。直到Q中只富含一棵树为止。
从树枝深度优先遍历，左子树输出0、右子树输出1，搜索到叶子节点就得到了叶子字符的编码。
●
算法伪码
算法：Huffman(C)
●
正确性证明
设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两个字符深度发生变化，其他字符深度都没有变，所以：
又因为d T(x) =d T′(b) ，d T(b) =d T′(x) ，所以：
又f(x)-f(b)≤0，d T(x) -d T(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}，有d T(c) =d T′(c) ，故f(c)d T(c) =f(c)d T′(c)哈夫曼编码贪心算法时间复杂度，另一方面d T(x) =d T(y) =d T(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的最优前缀码矛盾，假设不真，得证。
实例讲解
算法设计与分析（Python版）
精彩回顾
秒懂算法
算法设计的通常过程
递推多项式求解方式
活动安排问题贪心算法
下期预告
秒懂算法
Prim算法
Kruskal算法
选第二大元素的分治算法
快速排序算法中的分治思想
动态规划算法的基本思想
矩阵连乘问题
0-1背包问题的动态规划改进算法——跳跃点算法
子集树模型——0-1背包问题的回溯算法
满m叉树模型——图的m可着色问题的回溯算法
排列树模型——旅行商问题的分支限界法
最大网络流的增广路算法
蒙特卡罗算法
03
参考书籍
《算法设计与分析》
