设A、B、C、D、E、F六个字母出现的概率分别为7,19,2,6,32,3。试写出为这六个字母设计的HUFFMAN编码, 并画出对应的HUFFMAN树
时间: 2024-02-06 17:04:13 浏览: 72
统计英文文本每个字母出现概率(不分大小写)并进行哈夫曼,香农编码
首先,按照出现概率从小到大的顺序排列这些字母,得到:C(2), F(3), D(6), A(7), B(19), E(32)。
然后,按照哈夫曼编码的构造方法,从小到大依次取出两个概率最小的字符,构造一个新节点,其权值为这两个字符的概率之和,然后把这个新节点放回原序列中,重复以上步骤,直到只剩下一个节点为止。构造出的树如下所示:
```
74
/ \
/ \
34 E(32)
/ \
/ \
15 B(19)
/ \
/ \
F(3) 12
/ \
/ \
C(2) DA(10)
/ \
/ \
D(6) A(7)
```
根据哈夫曼树,可以给每个字符赋予一个二进制编码,从根节点开始,往左走编码为0,往右走编码为1,得到以下编码:
C: 0000
F: 0001
D: 001
A: 010
B: 11
E: 10
因此,对应字符的编码为:C-0000,F-0001,D-001,A-010,B-11,E-10。
阅读全文