1.设7个字母在通信中出现的频率为: a:30%,b:20%,c:15%,d: 15%,e:10%,f:5%,g:3% 使用huffman算法求传输它们的最佳前缀编码,画出最优树,指出每 个字母的编码,并指出传输1000 个按上述频率出现的字母需要多少 个二进制数码
时间: 2024-02-07 09:02:19 浏览: 21
根据Huffman算法,我们可以先将频率从小到大排序,得到:
g:3% -> f:5% -> e:10% -> d:15% -> c:15% -> b:20% -> a:30%
然后我们将频率最小的两个字母进行合并,构建一棵树。合并后的频率为两者之和,即3%+5%=8%。得到以下树状图:
```
100%
-----------
| |
30% 70%
| |
a -----
| |
40% 30%
| |
b -----
| |
20% 15%
| |
d c
|
15%
|
e
|
10%
|
f
|
3%
|
g
```
从根节点到每个叶子节点的路径上的编码即为该字母的编码,向左为0,向右为1。因此:
a: 0
b: 10
c: 111
d: 110
e: 101
f: 1001
g: 1000
传输1000个字母,其中a出现的频率为30%,即出现300次,其编码为一个0,因此传输a需要300个二进制数码。同理,传输b需要200个二进制数码,传输c需要150个二进制数码,传输d需要150个二进制数码,传输e需要100个二进制数码,传输f需要50个二进制数码,传输g需要30个二进制数码。因此,传输1000个按上述频率出现的字母需要:
300*1 + 200*2 + 150*3 + 150*3 + 100*3 + 50*4 + 30*4 = 1730个二进制数码。