假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的频度分别为{0.31, 0.16, 0.10, 0.08, 0.11, 0.20, 0.04}, (1)为这7个字母设计哈夫曼编码； (2)为这7个字母设计等长编码，至少需要几位二进制数？ (3)哈夫曼编码比等长编码使电文总长压缩多少？ (4)画出哈夫曼树的构造过程

(1) 哈夫曼编码的构造过程如下：

首先将出现频率从小到大排序，得到：

字母 | 频率
----|-----
d | 0.08
c | 0.10
e | 0.11
b | 0.16
a | 0.31
g | 0.04
f | 0.20

然后将频率最小的两个字母d和c合并，得到dc。此时dc的频率为0.18。然后将频率最小的两个字母dc和e合并，得到dce。此时dce的频率为0.29。以此类推，直到合并到所有字母都在同一棵树上为止。最后得到的哈夫曼编码如下：

字母 | 频率 | 编码
----|------|-----
a | 0.31 | 0
f | 0.20 | 10
b | 0.16 | 110
e | 0.11 | 1110
dc | 0.18 | 11110
g | 0.04 | 111110
dce | 0.29 | 111111

(2) 等长编码需要至少3位二进制数才能表示7个字母，因为 $2^2 < 7 < 2^3$。

(3) 哈夫曼编码比等长编码使电文总长压缩了6.5%。具体计算方法为：

等长编码每个字母需要3位二进制数，而哈夫曼编码则需要：

a: 1位

f: 2位

b: 3位

e: 4位

dc: 5位

g: 6位

dce: 6位

因此，如果电文中出现了n个字母，则等长编码需要3n位二进制数，而哈夫曼编码需要：

$$1\times0.31n + 2\times0.20n + 3\times0.16n + 4\times0.11n + 5\times0.18n + 6\times0.04n + 6\times0.29n = 3.35n$$

因此，哈夫曼编码比等长编码压缩了 $(3.35-3)/3.35 \times 100\% \approx 6.5\%$。

(4) 哈夫曼树的构造过程如下图所示：

其中，每个节点的权值表示该节点对应的字母的频率。在构造哈夫曼树时，每次选择频率最小的两个节点合并成一个新节点，直到所有节点都在同一棵树上。最后的根节点就对应整个字母集合的哈夫曼编码。