数据结构-哈夫曼树

发表于 更新于 分类于 阅读次数： 本文字数： 2.9k 阅读时长 ≈ 3 分钟

本文写于 2020 年 3 月 31 日，2022 年 3 月 20 日重新整理

编码

考虑这样一种情形：在一篇若干字符组成的文章中，各个字符出现的频率一般是不同的。假如我们可以设计出一种不等长编码，让出现频率较高的字符使用更短的编码，出现频率较低的字符使用较长的编码，这样可以实现对文章的无损压缩。
哈夫曼编码就是这样一种压缩编码。

哈夫曼树(Huffman Tree)

考虑下面这种判定树：

1
2
3
4
5
6
7
8
9
10
11
if(num<60){
    return 1;
}else if(num <70){
    return 2;
}else if(num<80){
    return 3;
}else if(num<90){
    return 4;
}else{
    return 5;
}

如果对小规模的学生成绩进行 5 分制取整，可以使用上面这段愚蠢的程序。如果要处理的是较大规模的数据，那么上面的判断过程还有优化的空间。
根据上面的判断过程，对于 60 以下的数据，需要判断一次， 60-70 的数据，需要判断两次， 70-80 的数据，需要判断三次。假如要处理的数据集对不同分段的数据有个出现频率的信息，比如：

| 数据段 | <60 | 60-70 | 70-80 | 80-90 | >90 |
| ------ | ---- | ----- | ----- | ----- |
| 频率 | 0.05 | 0.15 | 0.4 | 0.3 | 0.1 |

那么上面的判断过程平均判断次数为：0.05∗1+0.15∗2+0.4∗3+0.3∗4+0.1∗4=3.150.05 * 1 + 0.15 * 2 + 0.4 * 3 + 0.3 * 4 + 0.1 * 4 = 3.15 次

根据上面的频率表可以查看出， 70-90 的占比较大，而他们需要判断 3,4 次。如果让占比较大的只判断一次，而让占比较小的 <60 分段判断 4 次，似乎可以减少平均判断次数，提高效率。例如改进为如下判断：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if(num<80){
    if(num<70){
        if(num<60){
            return 1;
        }else{
            return 2;
        }
    }else{
        return 3;
    }
}else{
    if(num<90){
        return 4;
    }else{
        return 5;
    }
}

则平均判断次数为：0.05∗3+0.15∗3+0.4∗2+0.3∗2+0.1∗2=2.20.05 * 3 + 0.15 * 3 + 0.4 * 2 + 0.3 * 2 + 0.1 * 2 = 2.2 次，优化了不少。
这就是哈夫曼树的思想：根据元素出现的频率构造搜索树。

带权路径长度(WPL)

假设二叉树有 nn 个叶子节点，每个叶子节点的权值为，从根节点到每个叶子节点的长度为，则每个叶子节点的带权路径和就是。哈夫曼树就是 WPL=∑WkLkWPL=\sum W_kL_k 最小的二叉树，又叫最优二叉树。

哈夫曼树的构造

哈夫曼树的构造过程很简单，从一个带权节点的序列中取出权值最小的两个节点 a 和 b ，将 a 和 b 合并，并且构造一个新节点作为 a 和 b 的父节点，父节点的权值为 a,b 权值之和。然后把父节点放回到序列中，再取出权值最小的两个节点合并。一直做到序列为空，哈夫曼树就形成了。

哈弗曼数结构上就是普通的二叉树，因此它的原型为：

1
2
3
4
5
6
typedef struct hafman
{
    WeightType weight;
    HuffmanTree *left;
    HuffmanTree *right;
} HuffmanTree;

构造的过程需要取出权值最小的元素，不妨用最小堆(MinHeap)储存节点，最小堆的实现与[[数据结构-堆]]类似。如果使用排好序的序列也可以实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
HuffmanTree *constructHuffmanTree(MinHeap *heap)
{
    HuffmanTree *huffman;
    for (int i = 1; i < heap->size; ++i) //size nodes need size-1 times insert
    {
        huffman = (HuffmanTree *)malloc(sizeof(HuffmanTree));
        huffman->left = deleteMin(heap);
        huffman->right = deleteMin(heap);
        huffman->weight = huffman->left->weight +
                          huffman->right->weight;
        insert(heap, huffman);
    }
    return deleteMin(heap);
}

哈夫曼树的特点

根据哈夫曼树构造的过程，可以看出哈夫曼树具有以下特点：

  • 没有度为 1 的节点: 哈夫曼树构造时总是两两合一，因此它的所有节点要么度为 2 ，要么度为 0
  • n 个叶节点的哈夫曼树总结点数为 2n-1: 二叉树的节点分为三类：度为 0，1，2 的三类节点。设度为 i 的节点数量为 nin_i ，同时满足关系：n2=n0−1n_2 = n_0 - 1 。因此在哈夫曼树中：叶节点数量n即为 n0n_0 ，由于没有度为 1 的点，所以节点总数是 n0+n2=2n−1n_0 + n_2 = 2n - 1 。
  • 哈夫曼树交换左右子树仍然是哈夫曼树: 对于同一组带权节点序列，可能存在不同构的两颗哈夫曼树，但是他们的 WPL 相同。

哈夫曼编码

是一种字符串的不等长编码方式，可以使字符串占用的空间最小。使用不等长编码有一个问题：给定一串编码，无法准确的把每个字符分割出来，不同的分割方式有不同的含义，即二义性问题。针对这个问题，又有聪明人提出了解决的方法：使用前缀码 (Prefix Code) 。
所谓前缀码，即满足：任何字符的编码都不是其他字符编码的前缀。例如给出下面的三个字母的非前缀编码：

1
2
3
a:  1
b:  0
c:  10

则字符 a 的编码 1 是字符 c 的编码 10 的前缀，当给出编码 10 时，无法分辨究竟是 ab 还是 c 。
哈夫曼编码是在一棵二叉树上进行的，规定 0 代表左子树， 1 代表右子树，同时字符只储存在叶节点上。这样每个字符的编码实际上描述了从根节点到该字符所在叶节点的路径，同时任何一个字符的编码都不可能是其他字符编码的前缀。

解决了二义性问题，哈夫曼编码下一个要解决的问题就是效率。结合哈夫曼树的思想，把字符串中每个字符的出现次数作为该字符的权值建立哈夫曼树，这样出现次数多的节点将位于较浅位置处的叶节点，其路径编码（ 0 代表左， 1 代表右）长度也较短。这样就实现了对一个字符串或者一篇文章的字符不等长编码，也就实现了对字符串的压缩。