回复

先锋

2018年10月13日

构造哈弗曼树:

1、首先a(3)、b(2)、i(1)、l(1)分别单独构成一个树(节点),节点的权重是字符出现的频率;
2、先将权重最小的两个节点结合组成一个新的节点(新节点的权重为子节点的权重之和),然后依次这样进行,最终所有的节点组成一个树;
3、对于每个节点,其左边值为0,右边值为1;所有的叶节点均为文本中出现的字符。
   weight(2)                                     weight(4)                                         weight(7)                                 
                                                      0/            \1                                           0/    \1
     0 /   \ 1                ->    weight(2)                  b(2)     ->                   weight(4)    a(3)
                                       0 /   \1                                                            0/   \1
     l(1) i(1)                     l(1)    i(1)                                              weight(2)    b(2)
                                                                                                        0 /  \1
                                                                                                       l(1)   i(1)

所以,对于a/b/l/i 他们对应的霍夫曼编码
a:1;
b:01;
i :001;
L:000;

长度:1+3+3+2+1+2+1=13

0 0
回复
暂无回复
查看更多
我要回复