[严题集 6.26③]假设用于通信的电文仅由 8 个字母组成,字母在电文中出现的频率分别为 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这 8 个字母设计哈夫曼编码。使用 0~7 的二进制表示形式是另一种编码方案。对于上述实例,比较两种方案的优缺点。

哈夫曼编码是一种基于字符频率的前缀编码方法，高频字符用短码，低频字符用长码，从而最小化总加权路径长度。本题需根据给定频率设计哈夫曼编码，并与固定长度二进制编码（3位）比较优劣。

关键点：

1. 构造哈夫曼树：通过反复合并最小频率节点生成二叉树。
2. 编码规则：左分支赋0，右分支赋1，路径组合即为码字。
3. 比较方案：哈夫曼编码压缩效率高但需编码表，固定编码简单但效率低。

步骤1：构造哈夫曼树

将频率放大100倍后排序：2, 3, 6, 7, 10, 19, 21, 32。合并过程如下：

1. 合并2和3 → 新节点5（左0，右1）。
2. 合并5和6 → 新节点11（左0，右1）。
3. 合并7和10 → 新节点17（左0，右1）。
4. 合并11和17 → 新节点28（左0，右1）。
5. 合并19和21 → 新节点40（左0，右1）。
6. 合并28和32 → 新节点60（左0，右1）。
7. 合并40和60 → 根节点100。

步骤2：生成哈夫曼编码

从根到叶子的路径组合：

• 2：10000（路径：根→60→28→11→5→左）
• 3：10001（路径：根→60→28→11→5→右）
• 6：1001（路径：根→60→28→11→右）
• 7：1010（路径：根→60→28→17→左）
• 10：1011（路径：根→60→28→17→右）
• 19：00（路径：根→40→左）
• 21：01（路径：根→40→右）
• 32：11（路径：根→60→右）

步骤3：比较两种编码方案

• 哈夫曼编码：
  • 优点：平均码长更短（2.35位），压缩效率高。
  • 缺点：需存储编码表，编码过程复杂。
• 固定长度编码（3位）：
  • 优点：简单，无需额外开销。
  • 缺点：平均码长固定为3位，效率低（总加权路径长300 > 哈夫曼的235）。