关于哈夫曼编码试题的计算假设某符号集X中包含7个符号:(s1,s2,s3,s4,s5,s6,s7),它们各自出现的概率分别为:(0.31,0.22,0.18,0.14,0.1,0.04,0.01).试求其哈夫曼编码、信息熵、平均码字长度和编码
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/30 04:48:18
![关于哈夫曼编码试题的计算假设某符号集X中包含7个符号:(s1,s2,s3,s4,s5,s6,s7),它们各自出现的概率分别为:(0.31,0.22,0.18,0.14,0.1,0.04,0.01).试求其哈夫曼编码、信息熵、平均码字长度和编码](/uploads/image/z/3358567-55-7.jpg?t=%E5%85%B3%E4%BA%8E%E5%93%88%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81%E8%AF%95%E9%A2%98%E7%9A%84%E8%AE%A1%E7%AE%97%E5%81%87%E8%AE%BE%E6%9F%90%E7%AC%A6%E5%8F%B7%E9%9B%86X%E4%B8%AD%E5%8C%85%E5%90%AB7%E4%B8%AA%E7%AC%A6%E5%8F%B7%EF%BC%9A%EF%BC%88s1%2Cs2%2Cs3%2Cs4%2Cs5%2Cs6%2Cs7%EF%BC%89%2C%E5%AE%83%E4%BB%AC%E5%90%84%E8%87%AA%E5%87%BA%E7%8E%B0%E7%9A%84%E6%A6%82%E7%8E%87%E5%88%86%E5%88%AB%E4%B8%BA%EF%BC%9A%EF%BC%880.31%2C0.22%2C0.18%2C0.14%2C0.1%2C0.04%2C0.01%EF%BC%89.%E8%AF%95%E6%B1%82%E5%85%B6%E5%93%88%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81%E3%80%81%E4%BF%A1%E6%81%AF%E7%86%B5%E3%80%81%E5%B9%B3%E5%9D%87%E7%A0%81%E5%AD%97%E9%95%BF%E5%BA%A6%E5%92%8C%E7%BC%96%E7%A0%81)
关于哈夫曼编码试题的计算假设某符号集X中包含7个符号:(s1,s2,s3,s4,s5,s6,s7),它们各自出现的概率分别为:(0.31,0.22,0.18,0.14,0.1,0.04,0.01).试求其哈夫曼编码、信息熵、平均码字长度和编码
关于哈夫曼编码试题的计算
假设某符号集X中包含7个符号:(s1,s2,s3,s4,s5,s6,s7),它们各自出现的概率分别为:(0.31,0.22,0.18,0.14,0.1,0.04,0.01).试求其哈夫曼编码、信息熵、平均码字长度和编码效率.能给出明确的解题过程么?
关于哈夫曼编码试题的计算假设某符号集X中包含7个符号:(s1,s2,s3,s4,s5,s6,s7),它们各自出现的概率分别为:(0.31,0.22,0.18,0.14,0.1,0.04,0.01).试求其哈夫曼编码、信息熵、平均码字长度和编码
太复杂了,楼主一会记得多给我点分!
先设权w=(31,22,18,14,10,4,1),n=7,则m=13,按照哈夫曼算法可以构造一棵哈夫曼树如下:
100
40 60
22 18 31 29
14 15
10 5
4 1
末端结点为22,18,31,14,10,4,1,你自己把上面的加上线连成一棵二叉树就行,记得左分支标0,右分支标1(为了得出后面的哈夫曼编码HC)
然后需要列出HT初态表和HT终态表,如下:
HT初态表 HT终态表
weight parent lchild rchild weight parent lchild rchild
1 31 0 0 0 31 12 0 0
2 22 0 0 0 22 11 0 0
3 18 0 0 0 18 11 0 0
4 14 0 0 0 14 10 0 0
5 10 0 0 0 10 9 0 0
6 4 0 0 0 4 8 0 0
7 1 0 0 0 1 8 0 0
8 - 0 0 0 5 9 6 7
9 - 0 0 0 15 10 5 8
10 - 0 0 0 29 12 4 9
11 - 0 0 0 40 13 2 3
12 - 0 0 0 60 13 1 10
13 - 0 0 0 100 0 11 12
最后得出哈夫曼编码HC:
1——>10
2——>00
3——>01
4——>110
5——>1110
6——>11110
7——>11111
平均码字长度为(0.31+0.22+0.18)×2+0.14×3+0.1×4
+(0.04+0.01)×5=2.47
编码效率为[(1-0.01)×3+0.01×2]/2.47=1.21
补充:对于其中的编码效率问题本人有点淡忘,我选择的是用
普通平均编码长度除上了哈夫曼平均编码长度得出,不知对否.
辛苦半天,望楼主能赐我分数,不胜感激!
注:提交后发现格式不太规整,对于哈夫曼树谁是谁的左孩子、右孩子比较容易分出(左右孩子结点相加可知父亲结点),对于HT初态表和HT终态表1列1列的看就行!其中数字第一列为序号,从第2列到第9列分别对应HT初态表的weight parent lchild rchild 和HT终态表的weight parent lchild rchild .