Question

3．假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为

3．假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为：
A
B
C
D
E
F
G
H

0.09
0.15
0.04
0.07
0.28
0.08
0.2l
0.18

（1）试构造关于w的一棵哈夫曼树，并具此写出每个字符的编码。
（2）求该编码方案的平均码长

Answer 1

平均码长=(4*0.09+3*0.15+4*0.04+4*0.07+2*0.28+4*0.08+2*0.21+3*0.18)/1.1=2.81

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

所求的哈夫曼树不是唯一的，但是其加权路径长度是唯一的。

扩展资料：

赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。

例如a7从左至右，由U至U″″，其码字为1000；

a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为1001…

用赫夫曼编码所得的平均比特率为：Σ码长×出现概率

上例为：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit

可以算出本例的信源熵为2.61bit，二者已经是很接近了。

参考资料来源：百度百科-哈夫曼编码

Answer 2

平均码长=(4*0.09+3*0.15+4*0.04+4*0.07+2*0.28+4*0.08+2*0.21+3*0.18)/1.1=2.81

哈夫曼树及每个字符的编码如图：

追答

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
所求的哈夫曼树不是唯一的，但是其加权路径长度是唯一的。