【离散数学】树（一）哈夫曼编码基本原理

正文之前

霍夫曼编码(Huffman Coding)，又译为哈夫曼编码、赫夫曼编码，是一种用于无损数据压缩的熵编码（权编码）算法。由大卫*霍夫曼在1952年发明                  ——Wikipedia

---

本节我们将介绍以下内容：

1. 哈夫曼树
2. 哈夫曼编码

正文

哈夫曼树

1. 简介
2. 构造
3. 特点

1. 简介

给定 n 个叶子结点，每个结点带权值，构造一棵二叉树，如果带权路径长度最短，则称为哈夫曼树（最优二叉树），权值最大的结点最接近根结点

2. 构造

给定一组符号S及其权值W（出现的概率）

根据这张表格，我们来构造一棵哈夫曼树

1. 选取权值最小结点：G, F，构成一棵树，并从表格中移除，根结点为两结点权值之和：2 + 3 = 5

2. 将上一棵树的根结点作为子结点，并选择权值最小结点：E，和 1 中的树构成一棵新树，根结点为两结点权值之和：5 + 7 = 12

3. 将上一棵树的根结点作为子结点，并选择权值最小结点：D，和 2中的树构成一棵新树，根结点为两结点权值之和：12 + 8 = 20

4. 将上一棵树的根结点作为子结点，并选择权值最小结点：C，和 3中的树构成一棵新树，根结点为两结点权值之和：20 + 12 = 32

5. 将上一棵树的根结点作为子结点，并选择权值最小结点：B，和 4中的树构成一棵新树，根结点为两结点权值之和：32 + 16 = 48

6. 将上一棵树的根结点作为子结点，并选择权值最小结点：A，和 5中的树构成一棵新树，根结点为两结点权值之和：48 + 20 = 68

3. 特点

哈夫曼压缩是一种能够大幅度压缩自然语言文件空间的数据压缩技术，不再使用8位二进制数表示每一个字符，而是用较少的比特表示出现频率高的字符，而用较多的比特表示出现频率低的字符

2. 哈夫曼编码

在我们构造出哈夫曼树后，将所有的权值删去，并给每条边赋值0或1
在此我们定义 左 0 右 1

据此，我们尝试解码一个短串：

011011111

从根结点开始，遇到0，向左下移动一次，得到字符 A

开始解码下一个字符，从根结点开始，遇到2个1，向右下移动2次，遇到0，向左下移动一次，得到字符 C

开始解码下一个字符，从根结点开始，遇到5个1，向右下移动5次，得到字符 E

所以我们解码得到的字符为 ACE

关于哈夫曼编码的基本原理就介绍到此了，谢谢大家！