赫夫曼编码问题 — 编程爱好者社区

主题：赫夫曼编码问题

bai [专家分：70] 发布于 2006-04-12 18:30:00

假设A、B、C、D的编码分别为00、01、10、11 A B A C C D A则上述七个字符为
00010010101100 总长为14位。
如何使电文总长得到最短的二进制编码呢？假设每种字符在电文中出现的次数为Wi,其编码的长度为li，电文中只有n种字符，则电文总长为∑Wili
A(0) B(10) C(110) D(111) 我算的是（A）3*1+ （B）2*1+（C）2*3+（D）1*3=14
总长也为14位，并没有减少啊？

本帖地址： http://bbs.pfan.cn/post/156704.html

回复列表（共5个回复）

沙发

euc [专家分：4310] 发布于 2006-04-13 18:27:00

挺巧的，是一样长的。
那是因为w分配的不好，先看一下各字母出现的频率，a=3,b=1,c=2,d=1，然后按频率大小构造huffman树，先拼最小的两个，然后再拼...
     O
   O  a
O  c
b d
这样编码：a=0,c=10,b=111,d=110
总长度1*3+2*2+3*1+3*1=13，是不是减少了？虽然才减少了1~

板凳

rickone [专家分：15390] 发布于 2006-04-16 22:49:00

huffman编码的算法在《离散数学》里有证明，确实是最优树

3 楼

wohenry [专家分：30] 发布于 2006-04-17 15:33:00

我觉得二楼说的对，因为楼主你的那个编码不是最优的！！！因为A和C的权值最大，所以我觉得应该把他们放在上面，而把B和D放在最下面这层，也就是二楼的想法。

4 楼

自律自强 [专家分：0] 发布于 2006-10-16 19:42:00

各位高手，赫夫曼编码怎么用程序代码实现啊？请各位高手不吝赐教！
[em12]

5 楼

雨523 [专家分：200] 发布于 2006-10-22 15:02:00

我只能ＰＳ在严的书上有这个ＨＦＭ算法

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：赫夫曼编码问题

回复列表（共5个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：赫夫曼编码问题

回复列表 （共5个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共5个回复）