首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

huffman节点权值有关问题

2012-04-02 
huffman节点权值问题!字母A,B,C,D,E已被编码,相应的出现概率如下:p(A)0.16, p(B)0.51, p(C)0.09, p(D)

huffman节点权值问题!
字母A,B,C,D,E已被编码,相应的出现概率如下:
p(A)=0.16, p(B)=0.51, p(C)=0.09, p(D)=0.13, p(E)=0.11
原始权值为 w(A)=001, w(B)=1, w(C)=011, w(D)=000, w(E)=010


怎样设计每一个字符的权值才能使经huffman编码的权值最小?

权值的设计原则是不是将出现概率最高的字符权值设计为最小?

上面有5个字符那么最少需要3bit,我设置ABCDE权值的时候能不能如下设计是否合理?
W(A) = 010 实际用10
W(B) = 001 实际用1
W(C) = 101 实际用101
W(D) = 011 实际用11
W(E) = 100 实际用100

权值的设计目的就是使整棵树的权值最小达到最大压缩的目的。

[解决办法]
哈夫曼的思想简单来说有两点,一是权值大的点编码短,二是不会有前缀码

你的设计不合理,如果C是101表示的话,接收方如何知道它是C(101)而不是AB(101)?
[解决办法]
难看哈夫曼编码的原理,依次选择权值最小的2个节点,讲它们的权值和作为1个节点,该节点的两棵子树就是刚才权值最小的2个节点,然后再次选择权值最小的2个节点,依次循环
最后形成一颗树
[解决办法]
LZ去看看哈弗曼算法的习题

看看如何利用权值构造一颗合理的哈弗曼树。

先不要看算法,就看习题集上面的解题过程。有图的那种。。。

[解决办法]
出现频率最高的字符,编码长度越短。
另外,构造哈弗曼树要注意带权路径最小,并且在编码时后注意0、1的一致性。
比如左子树带权标0,那么右子树就是1。规则要一致,否则就乱了。

热点排行