软考易错知识点——哈夫曼编码
最近总有人问我哈夫曼编码的问题,因此博主决定写一篇文章为大家捋一捋。
我们直接通过一个例子来了解一下哈夫曼编码,如下:
已知一个文件中各个字符及其对应的频率如下所示:
字符 a b c d e f
频率 45 13 12 16 9 5
若采用哈夫曼编码,则字符序列“face”对应的编码为:
要求得哈夫曼编码我们首先需要画出哈夫曼树
1) 将字符按照频率从小到大进行排序:
f 5 e 9 c12 b 13 d 16 a 45
此时最小的两个为 f、e,我们将最小的作为左孩子,另一个作为右孩子,形成一个新的结点p1此时p1频率为14
2) 我们将新形成的结点和剩余的结点再次按照频率从小到大进行排序:
c 12 b13 p1 14 d 16 a 45
此时将c、b形成新结点p2,p2的频率为25
3) 继续将新旧结点排序:
P1 14 d16 p2 25 a 45
将p1、d 形成新结点p3,p3的频率为30
4) 继续排序:
P2 25 p3 30 a 45
由p2、p3得到p4,p4的频率为55
5) 剩下p4和a合成p5
6) 此时该题的哈夫曼树就已经画出来了,左分支为0,右分支为1,如图:
此时就可以得到“face”的哈夫曼编码为:110001001101