Huffman编码举例
时间: 2023-10-15 13:08:25 浏览: 40
假设有如下的字符集合和它们出现的频率:
| 字符 | 频率 |
|------|------|
| A | 10 |
| B | 15 |
| C | 20 |
| D | 35 |
| E | 20 |
步骤1:将字符集按照出现频率从小到大排序,得到如下顺序:
```
A, B, E, C, D
```
步骤2:取出频率最小的两个字符 A 和 B,创建一个新节点,它们的权重为它们的频率之和:
```
25
/ \
A B
```
步骤3:将新节点插入到集合中,重新排序:
```
E, C, D, AB
```
步骤4:重复步骤2和步骤3,直到只剩下一个节点:
```
100
/ \
/ \
/ \
AB ECD
/ \ / \
A B E CD
/ \
C D
```
步骤5:对每个节点进行编码,左子节点编码为 0,右子节点编码为 1。最终编码如下:
| 字符 | 频率 | 编码 |
|------|------|------|
| A | 10 | 00 |
| B | 15 | 01 |
| C | 20 | 11 |
| D | 35 | 10 |
| E | 20 | 10 |
因此,我们可以用 0 和 1 的组合来表示每个字符,使得编码后的长度最短。例如,字符串 "ACEDB" 的 Huffman 编码为 "0011011110"。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)