数据结构作业-严蔚敏-5.2.(3)
一、题目说明
假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。
1）试为这8个字母设置哈夫曼编码
2）试设计另一种由二进制表示的等长编码方案
3）对于上述实例，比较两种方案的优缺点。
二、解答
1）可以将频率放大100倍，以方便计算，不影响哈夫曼树的构造。
w={7, 19, 2, 6, 32, 3, 21, 10},根据哈夫曼树的构造规则得出以下的哈夫曼树：
2）哈夫曼编码和定长编码如下表所示：
| 字母编号 | 出现频率 | 哈夫曼编码 | 等长编码 |
|---|---|---|---|
| 1 | 0.07 | 1010 | 000 |
| 2 | 0.19 | 00 | 001 |
| 3 | 0.02 | 10000 | 010 |
| 4 | 0.06 | 1001 | 011 |
| 5 | 0.32 | 11 | 100 |
| 6 | 0.03 | 10001 | 101 |
| 7 | 0.21 | 01 | 110 |
| 8 | 0.10 | 1011 | 111 |
3)对于上述的两种方案。定长编码明显比哈夫曼编码更加简单。但是，哈夫曼编码是最优前缀编码。对于n个字符的数据文件来说，分别以它们的出现次数为权值构造哈夫曼树，则该树对应的哈夫曼编码对文件进行编码，能够使得该文件压缩过后对应的二进制文件的长度最短。
哈夫曼编码对应二叉树的WPL为：
WPL=2*(0.19+0.32+0.21)+4*(0.07+0.06+0.10)+5*(0.02+0.03)=2.61
等长编码对应二叉树的WPL为：
WPL=3*(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3