哈夫曼编码
某电文由8个字母组成,字母出现的频率如下表所示,请写出字母的哈夫曼编码。
字母 | 频率 | 哈夫曼编码 |
A | 22 | |
B | 15 | |
C | 4 | |
D | 3 | |
E | 37 | |
F | 10 | |
G | 7 | |
H | 2 |
因为有着八个元素,所以要预留2*n-1(n=8)即15个空位置
如下图所示求哈夫曼编码即使要把给填满
name | weight | parent | lchild | rchild |
A | 22 | 0 | ||
B | 15 | 0 | ||
C | 0 | |||
D | 0 | |||
E | 37 | 0 | ||
F | 0 | |||
G | 0 | |||
H | 0 | |||
I | ||||
J | ||||
K | ||||
L | ||||
M | ||||
N | ||||
O |
怎么求I?
首先在I的上方选取两个weight(权重)最小的点,I的值即为他们的和
由上图分析可知
I(weight)=H(weight)+D(weight)
画成图就是:
由此图可知
I的权重为5,父母为0(无父母),左子树为H,右子树为D
I | 5 | 0 | H | D |
H,D的父母也要修改为(I)
H | 2 | I |
D | 3 | I |
然后再从J的上方挑选两个子树合成新的树
选出 C和H分别作为J的左右子树,(C<H即是4<5)
即需要修改:
C | 4 | J | 0 | 0 |
I | 5 | J | H | D |
J | 9 | 0 | C | I |
依次类推将所有的元素补全构建成完整的树:
即是:
求编码只求编码区 (ABCDEFGH)
E从根开始向下查找 0
A从根开始向下查找 1 0
B从根开始向下查找 1 1 0
由图可知各个字符的哈夫曼编码
电文总长度(WPL)为
所有红节点的和
即5+9+16+26+41+63+100=260
2 分文章来源:https://www.toymoban.com/news/detail-475470.html
位。文章来源地址https://www.toymoban.com/news/detail-475470.html
到了这里,关于填空 哈夫曼编码的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!