哈夫曼树和哈夫曼编码

2019-03-26

通常的编码方法有固定长度和不等长度编码。最优编码方案的目的是使总码长度最短。

如果采用等长的编码方案，假设所有字符的编码都等长，则表示n个不同的字符需要位，例如三个不同的字符abc，至少需要2位二进制数表示：a(00)、b(01)、c(10)。如果每个字符的使用频率相等的话，固定长度编码是空间效率最高的方法。

那么问题来了，等长编码方案，n个不同字符需要几位来表示呢？log2n取上限。

利用字符的使用频率来编码，是不等长编码方法，使得经常使用的字符编码较短，不常使用的字符编码较长。

不等长编码需要解决两个关键问题：

编码尽可能短

1 2	使用频率高的字符编码较短，使用频率低的编码较长，可提高压缩率，节省空间，也能提高运算和通信速度。即频率越高，编码越短。

不能有二义性

例如a(0)、b(1)、c(01)，那么传输的01001就不知道到底是什么了，开头的01，可以说是ab，也可以说是c。这就是二义性。

1
2
3

解决二义性：
任何一个字符的编码不能是另一个字符编码的前缀。
即**前缀码特性**。

1952年，数学家D.A.Huffman提出了用字符在文件中出现的频率来建议一个用0，1串表示各字符的最佳编码方式，成为Huffman编码。哈夫曼编码很好的解决了上述两个关键的问题，广泛地应用于数据压缩、尤其是远距离通信和大容量数据存储，常用的JPEG图片就是采用哈夫曼编码压缩的。

哈夫曼编码的基本思想就是以字符的使用频率来构建一棵哈夫曼树，然后利用哈夫曼树对字符进行编码。

哈夫曼树

构建哈夫曼树，是将所要编码的字符作为叶子结点，该字符在文件中使用的频率作为叶子结点的权值，自底向上的方式，通过n-1次的“合并”运算后构造出来的树。核心思想是让权值大的叶子离根最近。

哈夫曼算法采取的贪心策略是每次从树的集合中取出没有双亲且权值最小的两棵树作为左右子树(一般情况下有个约定，两棵树中权值最小的为左子树)，构建一棵新树，新树根结点的权值为其左右孩子结点权值之和，将新树插入到树的集合中。这也是构建哈夫曼树的步骤。

字符	a	b	c	d	e	f
频率	0.05	0.32	0.18	0.07	0.25	0.13

我们把频率扩大100倍，不会影响结果。

我们从T集合中选没有双亲且权值最小的两棵树作为左右子树，也就是a和d，那么ad构建的新树的根结点权值为5+7=12。将这个新树t1加入到T集合再进行比较，ad不再进行比较了。

选没有双亲且权值最小的两棵树作为左右子树，也就是t1,f。那么t1和f构建的新树的根结点权值为12+13=25。将这个新树t2加入到T集合再进行比较，t1和f不再进行比较了。

选没有双亲且权值最小的两棵树作为左右子树，c的权值18最小了，作为左子树，而t2和e权值都是25，选谁作为右子树呢？选e。理由就是选前面的，新构建的树在T集合的后面。那么c和e构建的新树的根结点权值为18+25=43。将这个新树t3加入到T集合再进行比较，t2和e不再进行比较了。

以此类推…

那么我们这里再说一个哈夫曼树带权路径长度。
WPL=每个叶子的权值*该叶子到根的路径长度之和。叶子到根的路径长度为路径分支数(边数)。例如结点c到根经过两个边，其到根的路径长度为2。所以上面这个哈夫曼树的带权路径为

1	182+252+54+74+13+322=237

当然了还有一种计算方法，哈夫曼树的带权路径长度之和等于各新生结点的权值之和。

1	100+43+12+25+57=237

注意的是我们这里是扩大了100倍的，也就是说相当于有100个字符。那么如果有10^6^个字符，其哈夫曼树编码的长度时多少呢？10^6^*237/100

哈夫曼编码

前言

确定合适的数据结构，顺序存储。
哈夫曼树中没有深度为1的结点，则一棵有n个叶子结点的哈夫曼树共有2n-1个结点。
构成哈夫曼树后，编码需从叶子结点出发走一条到根的路径。
译码需要从根出发走一条从根到叶子的路径。对每一个结点而言，需要知道它的权值、双亲、左孩子、有孩子和结点信息。

什么是哈夫曼编码

利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子结点都有一条路径，对路径上的各分支约定指向左子树的分支表示”0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为各个叶子结点对应的字符编码，即是哈夫曼编码。

带权路径长度可以看做最终编码的二进制长度。

a的编码为：1000

代码分析

构建哈夫曼树是一个填表的过程，哈夫曼编码是一个读表的过程。

下标	weight	parent	lchild	rchild	value
0	5	-1	-1	-1	a
1	32	-1	-1	-1	b
2	18	-1	-1	-1	c
3	7	-1	-1	-1	d
4	25	-1	-1	-1	e
5	13	-1	-1	-1	f
6	-1	-1	-1	-1
7	-1	-1	-1	-1
8	-1	-1	-1	-1
9	-1	-1	-1	-1
10	-1	-1	-1	-1

ad构建的新树t1的根结点权值为5+7=12。保存在下标为6。对应下标为6的weight为12，lchild就是a，所以保存a的下标0，同理rchild保存的是d的下标3。同时a和d的parent就知道了，也就是下标6。所以每次构建一个新树，需要改动表里5个地方。
以此类推…

下标	weight	parent	lchild	rchild	value
0	5	6	-1	-1	a
1	32	9	-1	-1	b
2	18	8	-1	-1	c
3	7	6	-1	-1	d
4	25	8	-1	-1	e
5	13	7	-1	-1	f
6	12	7	0	3
7	25	9	6	5
8	43	10	2	4
9	57	10	7	1
10	100	-1	8	9

读表怎么读呢？比如我们想知道a的编码，我们读表知道a的parent是6，6的lchild为0正好是a的下标，也就是说a是左分支，所以这个分支编码为0。接着找6的parent，以此类推，直到parent为-1。这也是从叶子a到根的过程，保存路径各分支的编码，从根到叶子a的编码序列即为a的编码。(找是从叶子到根，但是找完了读还是从根到叶子。)

typedef struct
{
    int bit[MAXBIT];//存储编码的数组
    int start;//编码开始的下标
} HCodeType;        /* 编码结构体 */

这里每个叶子结点都使用了一个定长数组，是比较浪费空间的，可以动态创建。

全部代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXBIT    100
#define MAXVALUE  10000
#define MAXLEAF   30
#define MAXNODE   MAXLEAF*2 -1

typedef struct
{
    double weight;
    int parent;
    int lchild;
    int rchild;
    char value;
} HNodeType;        /* 结点结构体 */

typedef struct
{
    int bit[MAXBIT];
    int start;
} HCodeType;        /* 编码结构体 */
HNodeType HuffNode[MAXNODE]; /* 定义一个结点结构体数组 */
HCodeType HuffCode[MAXLEAF];/* 定义一个编码结构体数组*/
/* 构造哈夫曼树 */
void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n){
    /* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
       x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
    int i, j, x1, x2;
    double m1,m2;
    /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
    for (i=0; i<2*n-1;i++)
    {
        HuffNode[i].weight=0;//权值
        HuffNode[i].parent=-1;
        HuffNode[i].lchild=-1;
        HuffNode[i].rchild=-1;
    }
    /* 输入 n 个叶子结点的权值 */
    for (i=0; i<n; i++)
    {
        cout<<"Please input value and weight of leaf node "<<i+1<<endl;
        cin>>HuffNode[i].value>>HuffNode[i].weight;
    }
    /* 构造 Huffman 树 */
    for (i=0; i<n-1; i++)
    {//执行n-1次合并
         m1=m2=MAXVALUE;
         /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
        x1=x2=0;
        /* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一棵二叉树 */
        for (j=0;j<n+i;j++)
        {
            if (HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
            {
                m2 = m1;
                x2 = x1;
                m1 = HuffNode[j].weight;
                x1 = j;
            }
            else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
            {
                m2=HuffNode[j].weight;
                x2=j;
            }
        }
        /* 设置找到的两个子结点 x1、x2 的父结点信息 */
        HuffNode[x1].parent  = n+i;
        HuffNode[x2].parent  = n+i;
        HuffNode[n+i].weight = m1+m2;
        HuffNode[n+i].lchild = x1;
        HuffNode[n+i].rchild = x2;
        cout<<"x1.weight and x2.weight in round "<<i+1<<"\t"<<HuffNode[x1].weight<<"\t"<<HuffNode[x2].weight<<endl; /* 用于测试 */
    }
}
/* 哈夫曼树编码 */
void HuffmanCode(HCodeType HuffCode[MAXLEAF],  int n){
    HCodeType cd;       /* 定义一个临时变量来存放求解编码时的信息 */
    int i,j,c,p;
    for(i=0;i<n;i++)
    {
        cd.start=n-1;
        c=i;
        p=HuffNode[c].parent;
        while(p!=-1)
        {
            if(HuffNode[p].lchild==c)
                cd.bit[cd.start]=0;
            else
                cd.bit[cd.start]=1;
            cd.start--;        /*前移一位 */
            c=p;
            p=HuffNode[c].parent;    /* 设置下一循环条件 */
        }
        /* 把叶子结点的编码信息从临时编码cd中复制出来，放入编码结构体数组 */
        for (j=cd.start+1; j<n; j++)
           HuffCode[i].bit[j]=cd.bit[j];
        HuffCode[i].start=cd.start;
    }
}
int main()
{
    int i,j,n;
    cout<<"Please input n:"<<endl;
    cin>>n;
    HuffmanTree(HuffNode,n);  //构造哈夫曼树
    HuffmanCode(HuffCode,n);  // 哈夫曼树编码
    //输出已保存好的所有存在编码的哈夫曼编码
    for(i=0;i<n;i++)
    {
        cout<<HuffNode[i].value<<": Huffman code is: ";
        for(j=HuffCode[i].start+1;j<n;j++)
            cout<<HuffCode[i].bit[j];
        cout<<endl;
    }
    return 0;
}