2.2.2 如何设计哈夫曼编码
保证编码的长度最短，这是一个最优问题，如果没有条件（2）的限制，那么我们可以将所有字符都编码成0，这样肯定是最短的，每个字符只需要一个数字即可，编码长度就是字符的长度，但是由于“异前置码字”要求，所以不能这样编码。我们已经意识到在保证条件（2）的情况下出现次数越多的字符编码应该越短，出现次数越少的字符编码应该越长，这样构造的编码长度应该是最短的，这里已经蕴含了贪心的思想。那么如何构造异前置码字呢？这里我们引入二叉树，如图2.1所示。
图2.1 构造异前置码字二叉树
该二叉树由左右子树组成，并且左子树的路径被编码成0，右子树的路径被编码成1，叶子结点是我们要编码的字符，那么从根到叶子结点组成的编码就是异前置码字，图2.1中ABCDE的编码如下：
A:000;B:001;C:01;D:10;E:11
我们可以发现，通过二叉树进行编码后的ABCDE字符是异前置码字。现在我们已经学会了异前置码字的构造，接下来我们思考如何使构造的编码长度最短？出现次数越多的字符编码应该越短，出现次数越少的字符编码应该越长，我们首先统计一下“i want to learn algorithm”出现的频率，如表2.1所示。
表2.1 字符频率统计（1）
首先我们给上面的字符按频率从低到高排序，如表2.2所示。
表2.2 字符频率统计（2）
出现次数越多的字符编码长度越短，叶子离根越近，出现次数越少的字符编码长度越长，叶子离根越远。我们使用如下贪心思想，每次选取权重最低的两个字符组成新的子树，不断让树长高，那么就可以保证权重越低的字符，离根越远，编码长度越长，权重越高的字符，离根越近，编码长度越短。我们通过图例进行仔细讲解。
（1）首先选取表2.2中频率最低的两个字符w和e组成一个二叉树，如图2.2所示。
图2.2 选取频率最低的w和e组成二叉树
字符w和e组成的二叉树权重为2，我们使用新的字符t1表示，我们将新的字符列表重新按频率从低到高进行排序，如表2.3所示。
表2.3 字符频率统计（3）
（2）选取表2.3中频率最低的两个字符g和h组成一个二叉树，如图2.3所示。
图2.3 选取频率最低的g和h组成二叉树
字符g和h组成的二叉树权重为2，我们使用新的字符t2表示，我们将新的字符列表重新按频率从低到高进行排序，如表2.4所示。
表2.4 字符频率统计（4）
（3）选取表2.4中频率最低的两个字符m和i组成一个二叉树，如图2.4所示。
图2.4 选取频率最低的m和i组成二叉树
字符m和i组成的二叉树权重为3，我们使用新的字符t3表示，我们将新的字符列表重新按频率从低到高进行排序，如表2.5所示。
表2.5 字符频率统计（5）
（4）选取表2.5中频率最低的两个字符n和o组成一个二叉树，如图2.5所示。
图2.5 选取频率最低的n和o组成二叉树
字符n和o组成的二叉树权重为4，我们使用新的字符t4表示，我们将新的字符列表重新按频率从低到高进行排序，如表2.6所示。
表2.6 字符频率统计（6）
（5）选取表2.6中频率最低的两个字符l和r组成一个二叉树，如图2.6所示。
图2.6 选取频率最低的l和r组成二叉树
字符l和r组成的二叉树权重为4，我们使用新的字符t5表示，我们将新的字符列表重新按频率从低到高进行排序，如表2.7所示。
表2.7 字符频率统计（7）
（6）选取表2.7中频率最低的两个字符t1和t2组成一个二叉树，如图2.7所示。
图2.7 选取频率最低的t1和t2组成二叉树
字符t1和t2组成的二叉树权重为4，我们使用新的字符t6表示，我们将新的字符列表重新按频率从低到高进行排序，如表2.8所示。
表2.8 字符频率统计（8）
（7）选取表2.8中频率最低的两个字符a和t组成一个二叉树，如图2.8所示。
图2.8 选取频率最低的a和t组成二叉树
字符a和t组成的二叉树权重为6，我们使用新的字符t7表示，我们将新的字符列表重新按频率从低到高进行排序，如表2.9所示。
表2.9 字符频率统计（9）
（8）选取表2.9中频率最低的两个字符t3和t4组成一个二叉树，如图2.9所示。
图2.9 选取频率最低的t3和t4组成二叉树
字符t3和t4组成的二叉树权重为7，我们使用新的字符t8表示，我们将新的字符列表重新按频率从低到高进行排序，如表2.10所示。
表2.10 字符频率统计（10）
（9）选取表2.10中频率最低的两个字符t5和t6组成一个二叉树，如图2.10所示。
图2.10 选取频率最低的t5和t6组成二叉树
字符t5和t6组成的二叉树权重为8，我们使用新的字符t9表示，我们将新的字符列表重新按频率从低到高进行排序，如表2.11所示。
表2.11 字符频率统计（11）
（10）选取表2.11中频率最低的两个字符t7和t8组成一个二叉树，如图2.11所示。
图2.11 选取频率最低的t7和t8组成二叉树
字符t7和t8组成的二叉树权重为13，我们使用新的字符t10表示，我们将新的字符列表重新按频率从低到高进行排序，如表2.12所示。
表2.12 字符频率统计（12）
（11）最后选取表2.12中剩下的最后两个字符t9和t10组成一个二叉树，如图2.12所示。
图2.12 选取频率最低的t9和t10组成二叉树
字符t9和t10组成的二叉树权重为21，我们使用新的字符t11表示，最终的结果如表2.13所示。
表2.13 字符频率统计（13）
根据图2.12，从根到叶子结点的路径就是该字符的编码，我们可以得到字符串“i want to learn algorithm”的哈夫曼编码，如表2.14所示。
表2.14 字符串的哈夫曼编码
