已知字符集{a,b,c,d,e,f,g,h},重复频率集{0.05,0.25,0.03,0.06,0.1,0.11,0.36,0.04},画出对应的haffman树,求每个字符对应的haffman编码,并给出该哈夫曼树的WPL值。
时间: 2023-10-25 16:06:59 浏览: 181
哈夫曼树及其编码
首先根据重复频率从小到大排序,得到字符集和频率分别为:
```
a: 0.05
c: 0.03
d: 0.06
b: 0.25
e: 0.1
f: 0.11
h: 0.04
g: 0.36
```
接下来按照哈夫曼树的构建规则,不断选择权值最小的两个节点合并,直到只剩下一个根节点。具体步骤如下:
1. a和c合并,得到一个新节点ac,权值为0.08
2. d和ac合并,得到一个新节点acd,权值为0.14
3. e和f合并,得到一个新节点ef,权值为0.21
4. h和g合并,得到一个新节点hg,权值为0.4
5. b和ef合并,得到一个新节点bef,权值为0.46
6. bef和acd合并,得到根节点,权值为0.6
得到的哈夫曼树如下所示:
```
o
|
+----+----+
| |
o o
| |
+---+---+ o
| | |
o o o
| | |
a c d
|
+---+---+
| |
e f
|
+---+---+
| |
h g
```
根据哈夫曼树,我们可以求出每个字符的哈夫曼编码:
```
a: 0000
c: 0001
d: 001
b: 01
e: 10
f: 11
h: 00000
g: 00001
```
WPL值为每个叶节点的权值乘以其深度的和,即:
```
WPL = 0.05*4 + 0.03*4 + 0.06*3 + 0.25*2 + 0.1*2 + 0.11*2 + 0.04*5 + 0.36*5
= 2.75
```
因此,该哈夫曼树的WPL值为2.75。
阅读全文