1.设7个字母在通信中出现的频率为: a:30%,b:20%,c:15%,d: 15%,e:10%,f:5%,g:3% 使用huffman算法求传输它们的最佳前缀编码,画出最优树,指出每 个字母的编码,并指出传输1000 个按上述频率出现的字母需要多少 个二进制数码。(10分)
时间: 2024-02-07 17:02:16 浏览: 31
首先,根据Huffman算法,我们可以将出现频率较低的字母放在树的底层,出现频率较高的字母放在树的上层。因此,我们按照出现频率从小到大的顺序,依次将每个字母看做一个节点,并为每个节点赋上对应的权值。然后,我们将这些节点放在一个集合中,并按照权值从小到大的顺序排序。
接下来,我们每次从集合中选出权值最小的两个节点,将它们合并成一个新的节点,并将新节点的权值设置为两个原始节点的权值之和。这个新节点就代表了两个原始节点的父节点。我们将新节点加入集合中,并重复执行上述操作,直到集合中只剩下一个节点为止。这个节点就是Huffman树的根节点。
根据题目中给出的字母出现频率,我们可以依次按照频率从小到大的顺序,将节点放入集合中并排序:
g (3%) -> f (5%) -> e (10%) -> d (15%) -> c (15%) -> b (20%) -> a (30%)
然后,我们依次选出权值最小的两个节点进行合并,得到新的节点:
1. g+f (3%+5% = 8%)
2. e+d (10%+15% = 25%)
3. c+b (15%+20% = 35%)
4. a+(c+b) (30%+35% = 65%)
最终,我们得到了一棵Huffman树,其中叶子节点为字母节点,非叶子节点为合并节点。树的结构如下图所示:
```
65%
/ \
/ \
/ \
35% a
/ \
/ \
/ \
15% b
/ \
/ \
c d
|
15%
|
e
|
10%
|
f
|
3%
|
g
```
根据Huffman树的构造原理,我们可以得到每个字母的编码,即从根节点到对应字母节点的路径上的边的编号,左边为0,右边为1。编码如下:
a: 0
b: 11
c: 100
d: 101
e: 1100
f: 1101
g: 1110
传输1000个按照上述频率出现的字母,我们需要传输1000个字符的编码。根据上面的编码,每个字符需要的二进制位数为:
a: 1 * 0.3 = 0.3
b: 2 * 0.2 = 0.4
c: 3 * 0.15 = 0.45
d: 3 * 0.15 = 0.45
e: 4 * 0.1 = 0.4
f: 4 * 0.05 = 0.2
g: 4 * 0.03 = 0.12
因此,传输1000个按照上述频率出现的字母需要的二进制数码总位数为:
0.3 * 1000 + 0.4 * 1000 + 0.45 * 1000 + 0.45 * 1000 + 0.4 * 1000 + 0.2 * 1000 + 0.12 * 1000 = 2320
因此,需要2320个二进制数码。