哈夫曼树及应用

发表于 更新于 阅读次数： 本文字数： 2k 阅读时长 ≈ 7 分钟

在计算机和互联网技术中，文本压缩就是一个非常重要的技术。玩电脑的人几乎都会应用压缩和解压缩软件来处理文档。因为它除了可以减少文档在磁盘上的空间外，还有重要的一点， 就是我们可以在网络上以压缩的形式传输大量数据，使得保存和传递都更加高效。

那么压缩而不出错是如何做到的呢?简单说，就是把我们要压缩的文本进行重新编码，以减少不必要的空间。尽管现在最新技术在编码上已经很好很强大，但这一切都来自于曾经的技术积累，我们今天就来介绍一下最基本的压缩编码方法-赫夫曼编码。

在介绍赫夫曼编码前，我们必须得介绍赫夫曼树，而介绍赫夫曼树，我们不得不提这样一个人，美国数学家赫夫曼(David Huffman)， 也有的翻译为哈夫曼。他在1952年发明了赫夫曼编码，为了纪念他的成就，于是就把他在编码中用到的特殊的C叉树称之为赫夫曼树，他的编码方法称为赫夫曼编码。也就是说，我们现在介绍的知识全都来自于近60年前这位伟大科学家的研究成果，而我们平时所用的压缩和解压缩技术也都是基于赫夫曼的研究之上发展而来，我们应该要记住他。

部分显示问题，请参考

哈夫曼树的相关术语

路径

  • 从树中一个结点到另一个结点之间的分支构成这两个结点间的路径

路径长度

  • 路径上的分支数目

带权路径长度

  • 结点到根的路径长度与结点上权的乘积

树的带权路径长度(weighted path length)

  • 树中所有叶子结点的带权路径长度之和
WPL

定义

设有n个权值{w1,w2,…,wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi，则wpl最小的二叉树叫哈夫曼树。

哈夫曼树的构造过程

(1). 初始化：根据给定的n个权值{w1,w2,…,wn}，构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti只有一个带权为wi的根结点，其左右子树均空。

(2). 选取与合并：在 F 中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。

(3). 删除与加入：在 F 中删除这两棵树，同时将新得到的二叉树加入 F 中。

(4). 重复(2)和(3)，直到 F 只含一棵树为止。这棵树便是所求的哈夫曼树。

例：

w={5, 29, 7, 8, 14, 23, 3, 11}的构造过程

w1 w2 w3 w4 w5 w6 w7 w8

哈夫曼编码

一般地， 设需要编码的字符集为{ d1,d2,···,dn }，各个字符在电文中出现的次数或频率集合为{ W1,W2,···,Wn},以d1,d2,···,dn作为叶子结点，以W1,W,···,Wn作为相应叶子结点的权值来构造一棵哈夫曼树。规定哈夫曼树的左分支代表0，右分支代表1,则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是哈夫曼编码。

哈夫曼树及编码存储结构

1
2
3
4
5
6
7
typedef struct
{
    char data;
    int weight;
    int parent, lchild, rchild;
}HTNode, * HuffmanTree;
typedef char** HuffmanCode;//动态分配数组存储哈夫曼编码

哈夫曼树建立

返回两个双亲域为0且权值最小的点的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void Select(HuffmanTree HT, int n, int& s1, int& s2)
{
    /*n代表HT数组的长度*/
    //前两个for循环找所有结点中权值最小的点（字符）
    for (int i = 1; i <= n; i++)
    {
        if (HT[i].parent == 0)//利用for循环找出一个双亲为0的结点
        {
            s1 = i;//s1初始化为i
            break;//找到一个后立即退出循环
        }
    }
    for (int i = 1; i <= n; i++)
    {
        /*利用for循环找到所有结点（字符）权值最小的一个并且保证该结点的双亲为0*/
        if (HT[i].weight < HT[s1].weight && HT[i].parent == 0)
            s1 = i;
    }
    //后两个for循环所有结点中权值第二小的点（字符）
    for (int i = 1; i <= n; i++)
    {
        if (HT[i].parent == 0 && i != s1)//利用for循环找出一个双亲为0的结点，并且不能是s1
        {
            s2 = i;//s2初始化为i
            break;//找到一个后立即退出循环
        }
    }
    for (int i = 1; i <= n; i++)
    {
        /*利用for循环找到所有结点（字符）权值第二小的一个，该结点满足不能是s1且双亲是0*/
        if (HT[i].weight < HT[s2].weight && HT[i].parent == 0 && i != s1)
            s2 = i;
    }
}

建树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void CreateHuffmanTree(HuffmanTree& HT, int n)
{
    if (n <= 1)
        return;
    int m = 2 * n - 1;  //总结点数2n-1
    HT = new HTNode[m + 1];
    for (int i = 1; i <= m; i++)
    {
        //将1~m号单元中的双亲，左孩子，右孩子的下标都初始化为0
        HT[i].data = '\0';
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    cout << "输入结点信息和权值：";
    for (int i = 1; i <= n; i++)
    {
        cin >> HT[i].data >> HT[i].weight; //输入前n个单元中叶子结点的信息和权值
    }
    /*-----------初始化工作结束，下面建树---------------------------*/
    int s1, s2;
    for (int i = n + 1; i <= m; i++)
    {
        Select(HT, i - 1, s1, s2);
        HT[s1].parent = i;
        HT[s2].parent = i;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}

哈夫曼编码

根据树对每个元素编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void CreateHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n)
{
    HC = new char* [n + 1]; //分配储存n个字符编码的编码表空间
    char* cd = new char[n]; //分配临时存储字符编码的动态空间
    cd[n - 1] = '\0';       //编码结束符
    for (int i = 1; i <= n; i++)//逐个求字符编码
    {
        int start = n - 1; //start 开始指向最后，即编码结束符位置
        int c = i;
        int f = HT[c].parent;//f指向结点c的双亲
        while (f != 0)//从叶子结点开始回溯，直到根结点
        {
            --start;//回溯一次，start向前指向一个位置
            if (HT[f].lchild == c)
                cd[start] = '0';
            else
                cd[start] = '1';
            c = f;
            f = HT[c].parent;
        }
        HC[i] = new char[n - start];//为第i个字符编码分配空间
        strcpy(HC[i], &cd[start]);//把求得编码的首地址从cd[start]复制到HC的当前行中
    }
    delete[] cd;
}

哈夫曼解码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void DeCode(HuffmanTree HT, string a, string& b, int n)
{
    b = "";
    int q = 2 * n - 1;//q初始化为根结点的下标
    for (int i = 0; i < a.length(); i++)
    {
        //for循环结束条件是读入的字符是结束符（二进制编码）
        //此代码块用来判断读入的二进制字符是0还是1
        if (a[i] == '0')
        {
            /*读入0，把根结点(HT[q])的左孩子的下标值赋给q下次循环的时候把HT[q]的左孩子作为新的根结点*/
            q = HT[q].lchild;
        }
        else if (a[i] == '1')
        {
            q = HT[q].rchild;
        }
        //此代码块用来判断HT[q]是否为叶子结点
        if (HT[q].lchild == 0 && HT[q].rchild == 0)
        {
            /*是叶子结点，说明已经译出一个字符该字符的下标就是找到的叶子结点的下标*/
            b += HT[q].data;//把下标为q的字符赋给字符数组b[] q = 2 * n - 1;//初始化q为根结点的下标
            q = 2 * n - 1;//继续译下一个字符的时候从哈夫曼树的根结点开始
        }
    }
}

哈夫曼译码

1
2
3
4
5
6
7
8
9
10
11
12
void Code(HuffmanTree HT, HuffmanCode HC, string c, string& d, int n)
{
    d = "";
    for (int i = 0; i < c.length(); i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (c[i] == HT[j].data)  //找到字符后再d后追加编码
                d.append(HC[j]);
        }
    }
}

总结

学习哈夫曼树和哈夫曼编码有助于初步理解数据压缩原理。

部分显示问题，请参考