CSP-J 2022 第一轮 第 7 题：哈夫曼编码求某字符编码长度

题目

假设字母表 $\{a,b,c,d,e\}$ 在字符串出现的频率分别为 $10\%$，$15\%$，$30\%$，$16\%$，$29\%$。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 $d$ 的编码长度（ ）位。

选项

• A. $1$
• B. $2$
• C. $2$ 或 $3$
• D. $3$

答案

B

题解

答案是 B，2 位。

哈夫曼编码的规则是：每次选出频率最小的两个节点合并，直到只剩一个节点。字符的编码长度等于它在哈夫曼树中到根节点的边数。

合并过程如下：

1. 将最小的 $a(10\%)$ 和 $b(15\%)$ 合并，得到 $25\%$。
2. 剩下 $16\%、25\%、29\%、30\%$，将 $d(16\%)$ 和 $25\%$ 合并，得到 $41\%$。
3. 将 $29\%$ 和 $30\%$ 合并，得到 $59\%$。
4. 将 $41\%$ 和 $59\%$ 合并，得到根节点 $100\%$。

因此，$d$ 到根节点的路径是：

$$ d(16\%) \rightarrow 41\% \rightarrow 100\% $$

共经过 2 条边，所以编码长度为 2 位。