已知字符A,B,C,D,E,F的概率分别是0.16,0.05,0.08,0.12,0.41,0.18,构造哈夫曼树,求其WPL,并写出每个字符的编码。
时间: 2023-10-08 20:12:27 浏览: 39
构造哈夫曼树的过程如下:
1. 将6个字符按照概率从小到大排序,得到B,C,D,A,F,E
2. 选取概率最小的两个字符B,C,构造一个新节点BC,概率为0.05+0.08=0.13
3. 将新节点BC插入到原来的序列中,得到BC,D,A,F,E
4. 选取概率最小的两个字符BC,D,构造一个新节点BCD,概率为0.13+0.12=0.25
5. 将新节点BCD插入到原来的序列中,得到BCD,A,F,E
6. 选取概率最小的两个字符BCD,A,构造一个新节点ABC,概率为0.25+0.16=0.41
7. 将新节点ABC插入到原来的序列中,得到ABC,F,E
8. 选取概率最小的两个字符ABC,F,构造一个新节点ABCF,概率为0.41+0.18=0.59
9. 将新节点ABCF插入到原来的序列中,得到ABCF,E
10. 最后剩下两个节点ABCF和E,构造一个新节点,概率为0.59+0.41=1,得到哈夫曼树如下图所示:
```
1
/ \
/ \
0.59 0.41
/ \
/ \
0.41 ABCF
/ \
/ \
0.25 / \
/ \
0.16 F E
/ \
/ \
BC D
/ \
/ \
0.05 0.08
B C
```
WPL(Weighted Path Length)=0.05×2+0.08×2+0.16×3+0.25×2+0.18×2+0.41×1=2.49
每个字符的编码为:
A: 1
B: 000
C: 001
D: 01
E: 11
F: 10