假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的频度分别为

假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的频度分别为{0.31,0.16,0.10,0.08,0.11,0.20,0.04},

1）为这7个字母设计哈夫曼编码；
2）为这7个字母设计等长编码，至少需要几位二进制数？
3）哈夫曼编码比等长编码使电文总长压缩多少？

一

对左子树路径赋为0，右子树赋为1,该数据序列相应的编码分别为
a=01 b=001 c=101 d=0000 e=100 f=11 g=0001

二

Log2 >= 7 的最小值为3，所以等长编码至少需要3位二进制数
a=001 b=010 c=011 d=100 e=101 f=110 g=111

哈夫曼编码：231+316+310+48+311+220+4*4=254
等长编码平均长度：（100）*3 = 300
哈夫曼编码比等长编码压缩了 = 1 - （254/300）/100 = 15.33%

假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的频度分别为

假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的频度分别为{0.31,0.16,0.10,0.08,0.11,0.20,0.04},

1）为这7个字母设计哈夫曼编码；
2）为这7个字母设计等长编码，至少需要几位二进制数？
3）哈夫曼编码比等长编码使电文总长压缩多少？

一

对左子树路径赋为0，右子树赋为1,该数据序列相应的编码分别为
a=01 b=001 c=101 d=0000 e=100 f=11 g=0001

二

Log2 >= 7 的最小值为3，所以等长编码至少需要3位二进制数
a=001 b=010 c=011 d=100 e=101 f=110 g=111

哈夫曼编码：231+316+310+48+311+220+4*4=254
等长编码平均长度：（100）*3 = 300
哈夫曼编码比等长编码压缩了 = 1 - （254/300）/100 = 15.33%