数据结构与算法学习 (11)哈夫曼编码

哈夫曼树(Huffman Tree)

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
路径：在一棵树中，一个结点到另一个结点之间的通道，称为路径。上图中，从根结点到a之间的通路就是一条路径。
路径长度：在一条路径上，每经过一个结点，路径的长度就要加1。在一棵树中，规定根结点所在层数为1层，那么根结点到第i层结点的路径长度为i-1。
结点的权：给每一个结点赋予一个新的数值，称为结点的权。例如上图中a结点的权为7。
结点的带权路径长度：指的是从根结点到每一个结点的路径长度和该结点权值的乘积。上图中c结点的带权路径长度为2*3=6。
树的带权路径长度为树中所有叶子结点的带权路径长度之和。记做WPL。下图中这棵树的带权路径长度为：
WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3 = 30

。
树的构建基本思想：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
以2 4 5 7为例

哈夫曼编码

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

哈夫曼树的应用很广，哈夫曼编码就是其在电讯通信中的应用之一。广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。在电讯通信业务中，通常用二进制编码来表示字母或其他字符，并用这样的编码来表示字符序列。

例：如果需传送的电文为 ‘BADCADFEED’，它只用到6种字符，用两位二进制编码便可分辨。假设 A, B, C, D，E，F 的编码分别为 00, 01,10, 11，则上述电文便为 ‘001 000 011 010 000 011 101 100 100 011’（共 30 位），译码员按两位进行分组译码，便可恢复原来的电文。

A 01
B 1001
C 101
D 00
E 11
F 1001
BADCADFEED 编码
原编码⼆进制: 001 000 011 010 000 011 101 100 100 011(共30个字符)
新编码⼆进制: 1001 01 00 101 01 00 1001 11 11 00(共25个字符)
显然利用haffman coding 极大的缩短了字符个数

哈夫曼树的实现思路:

获取根据权值构建的哈夫曼树
循环遍历[0,n]个结点;
创建临时结点cd ,从根结点开始对⻬进⾏编码,左孩⼦为0,右孩⼦为1;
将编码后的结点存储haffCode[i]
设置HaffCode[i]的开始位置以及权值;

代码实现：

#include "string.h"
#include "stdio.h"
#include "stdlib.h"

const int MaxValue = 10000;//初始设定的权值最大值
const int MaxBit = 4;//初始设定的最大编码位数
const int MaxN = 10;//初始设定的最大结点个数

//节点
typedef struct HaffNode {
    int weight;//权重
    int flag;//是否插入过
    int parent;//父节点
    int leftChild;//左孩子
    int rightChild;//右孩子
}HaffNode;

//哈夫曼编码数据结构元素
typedef struct Code//存放哈夫曼编码的数据元素结构
{
    int bit[MaxBit];//数组
    int start;  //编码的起始下标
    int weight;//字符的权值
}Code;


//1.
//根据权重值,构建哈夫曼树;
//{2,4,5,7}
//n = 4;

void Haffman(int weight[], int n, HaffNode *haffTree) {
    int j,m1,m2,x1,x2;
    //1.哈夫曼树初始化，n个叶子节点，哈夫曼树总结点个数为2n-1
    //所有节点都赋初值
    for (int i = 0; i < 2*n-1; i++) {
        if (i<n) {
            haffTree[i].weight = weight[I];
        } else {
            haffTree[i].weight = 0;
        }
        
        haffTree[i].flag = 0;
        haffTree[i].parent = 0;
        haffTree[i].leftChild = -1;
        haffTree[i].rightChild = -1;
    }
    //2.构造haffTree的 n-1个非叶子节点，找到最小的两个子树合并
    
    for (int i = 0; i<n-1; i++) {//构建节点
        m1 = m2 = MaxValue;
        x1 = x2 = 0;
        //找最小值
        for (j = 0; j<n+i; j++) {
            //没插入过才找最小值，插入过的不取
            if (haffTree[j].weight<m1 && haffTree[j].flag == 0) {
                m2 = m1;
                x2 = x1;
                m1 = haffTree[j].weight;
                x1 = j;
            } else if (haffTree[j].weight<m2 && haffTree[j].flag == 0) {
                m2 = haffTree[j].weight;
                x2 = j;
            }
        }
        //3.将最小将找出的两棵权值最小的子树合并为一棵子树
        haffTree[x1].parent = I+n;
        haffTree[x2].parent = I+n;
        //4.将2个结点的flag 标记为1,表示已经加入到哈夫曼树中
        haffTree[x1].flag = 1;
        haffTree[x2].flag = 1;
        //5.修改n+i结点的权值
        haffTree[i+n].weight = haffTree[x1].weight + haffTree[x2].weight;
        //6.修改n+i左右孩子的值
        haffTree[i+n].leftChild = x1;
        haffTree[i+n].rightChild = x2;
    }
}


/*
9.2 哈夫曼编码
由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode
//{2,4,5,7}
*/
void HaffmanCode(HaffNode *haffTree, int n, Code HaffCode[]) {
    //1.创建临时节点cd
    Code *cd = (Code * )malloc(sizeof(Code));
    int child, parent;
    //2.求n个节点的哈夫曼编码
    for (int i = 0; i<n; i++) {
        cd->start = 0;
        cd->weight = haffTree[i].weight;
        //当前节点设为孩子节点
        child = I;
        //找到孩子节点的父节点
        parent = haffTree[child].parent;
        //由叶子节点向上遍历找到根节点
        while (parent != 0) {
            if (haffTree[parent].leftChild == child) {
                cd->bit[cd->start] = 0;
            } else {
                cd->bit[cd->start] = 1;
            }
            //编码加一
            cd->start++;
            //让当前的双亲节点成为孩子节点
            child = parent;
            //找双亲节点
            parent = haffTree[child].parent;
        }
        int temp = 0;
        //bit是反的，要反转过来
        for(int j = cd->start-1; j>=0; j--) {
            temp = cd->start-1-j;
            HaffCode[i].bit[temp] = cd->bit[j];
        }
        //把cd中的数据赋值到haffCode[I]中.
        //保存好haffCode 的起始位以及权值;
        HaffCode[i].weight = haffTree[i].weight;
         //保存编码对应的权值
        HaffCode[i].start = cd->start;

    }
   
}

int main(int argc, const char * argv[]) {
    printf("Hello, 哈夫曼编码!\n");
    int i, j, n = 4, m = 0;
    
    //权值
    int weight[] = {2,4,5,7};
    
    //初始化哈夫曼树, 哈夫曼编码
    HaffNode *myHaffTree = malloc(sizeof(HaffNode)*2*n-1);
    Code *myHaffCode = malloc(sizeof(Code)*n);
    
    //当前n > MaxN,表示超界. 无法处理.
    if (n>MaxN)
    {
        printf("定义的n越界，修改MaxN!");
        exit(0);
    }
    
    //1. 构建哈夫曼树
    Haffman(weight, n, myHaffTree);
    //2.根据哈夫曼树得到哈夫曼编码
    HaffmanCode(myHaffTree, n, myHaffCode);
    //3.
    for (i = 0; i<n; I++)
    {
        printf("Weight = %d\n",myHaffCode[i].weight);
        for (j = 0; j<myHaffCode[i].start; j++)
            printf("%d",myHaffCode[i].bit[j]);
        m = m + myHaffCode[i].weight*myHaffCode[i].start;
        printf("\n");
    }
    printf("Huffman's WPS is:%d\n",m);
    return 0;
}