哈夫曼编码

哈夫曼编码是一种编码方式，该方法依据字符出现概率来构造异字头的平均长度最短的码字，一般就叫做Huffman编码。

哈夫曼思想就是依据使用的频率来最大化的节省字符存储空间。

图1.png

图1是我们求一个分数属于那个阶段的流程判断图

图2.png

图2是利用哈夫曼思想来画出的流程图

我们通过两种方式去求D节点的路程长度值：

图3.png 图4.png

图3和图4是两种方式求的路程值的示意图，从两图中可以很好的得出两种方式哪一种更好。

下面我们通过代码的方式来实现哈夫曼。

1、首先先进行一些基本的变量和结构体设置

const int MaxValue = 10000;//初始设定的权值最大值
const int MaxBit = 4;//初始设定的最大编码位数
const int MaxPoint = 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;

2、根据权重值，构建哈夫曼树
构建哈夫曼树，先对哈夫曼树进行初始化，由于一些值是由后面两个值相加而存在的节点；因此，我们可以知道数组中拥有的权重值都是叶子节点，根据二叉树原理，可以得到总节点数。
对权重数组进行遍历，找出最小的两个节点，并用一个变量标记值是否有被使用，来得到哈夫曼树

void Haffman(int weight[],int n,HaffNode *haffTree){
    int m1,m2,x1,x2;
    //哈夫曼树初始化
    //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].parent = 0;
        haffTree[i].flag = 0;
        haffTree[i].leftChild = -1;
        haffTree[i].rightChild = -1;
    }
    

    //构造哈夫曼树的n-1个非叶子节点
    for (int i = 0; i<n-1; i++) {
        m1 = m2 = MaxValue;
        x1=x2=0;
        for (int 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;
            }
        }
        //找出两颗权值最小的子树合并为一颗子树
        haffTree[x1].parent = n+i;
        haffTree[x2].parent = n+i;
        //将两个节点的flag标记为1，表示已经加入到哈夫曼树中
        haffTree[x1].flag = 1;
        haffTree[x2].flag = 1;
        //修改节点n+i节点的权值
        haffTree[n+i].weight = haffTree[x1].weight + haffTree[x2].weight;
        //修改n+i的左右孩子值
        haffTree[n+i].leftChild = x1;
        haffTree[n+i].rightChild = x2;
    }
}

3、创建哈夫曼编码元素结构，记录每个节点字符的权重值和编码下标值
由于得到的下标值是逆序的，所有需要对下标值进行逆序置换。

//2、哈夫曼编码
//由n个节点的哈夫曼树haffTree构造的哈夫曼编码haffCode
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++) {
        //从0开始计数
        cd->start = 0;
        //取得编码对应权值的字符
        cd->weight = haffTree[i].weight;
        //当叶子节点i为孩子节点
        child = i;
        //找到child的双亲节点
        parent = haffTree[child].parent;
        //由叶节点向上直到根节点
        while (parent!=0) {
            if(haffTree[parent].leftChild == child){
                cd->bit[cd->start] = 0;//左孩子节点编码0
            }else{
                cd->bit[cd->start] = 1;//右孩子节点编码1
            }
            //编码自增
            cd->start++;
            //当前双亲节点成为孩子节点
            child = parent;
            //找到双亲节点
            parent = haffTree[child].parent;
        }
        int temp = 0;
        for (int j = cd->start-1; j>=0; j--) {
            temp = cd->start-j-1;
            haffCode[i].bit[temp] = cd->bit[j];
        }
        //把cd中的数据赋值到haffCode[i]中
        //保存好haffCode的起始位以及权重值
        haffCode[i].start = cd->start;
        //保存编码对应的权值
        haffCode[i].weight = cd->weight;

    }
}

main函数

printf("哈夫曼编码!\n");
    int n=6,m = 0;
    //权值
    //
    int weight[] = {2,4,6,8,1,9};
    //初始化哈夫曼树，哈夫曼编码
    HaffNode *haffTree = malloc(sizeof(HaffNode)*2*n-1);
    Code *haffCode = malloc(sizeof(Code)*n);
    
    //当前n>MaxN越界，无法处理
    if(n>MaxPoint){
        printf("定义的n越界，修改MaxPoint");
        exit(0);
    }
    //1、构建哈夫曼树
    Haffman(weight, n, haffTree);
    //2、根据哈夫曼树得到哈夫曼编码
    HaffmanCode(haffTree, n, haffCode);
    //3、打印权值
    for (int i = 0; i<n; i++) {
        printf("weight = %d\n",haffCode[i].weight);
        for (int j = 0; j<haffCode[i].start; j++) {
            printf("%d",haffCode[i].bit[j]);
        }
        m = m+haffCode[i].weight*haffCode[i].start;
        printf("\n");
    }
    printf("总哈夫曼值为:%d\n",m);

打印结果:

15880592087214.png