搜狗做题网关于哈夫曼编码试题的计算
来源：学生作业帮 编辑：搜狗做题网作业帮 分类：数学作业 时间：2024/05/01 18:06:05
关于哈夫曼编码试题的计算
假设某符号集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 .
先设权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 .