美文网首页
数据结构与算法-哈夫曼编码

数据结构与算法-哈夫曼编码

作者: 恍然如梦_b700 | 来源:发表于2020-04-29 00:51 被阅读0次

    哈夫曼树(Huffman Tree)

    给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。


    2ef074ac551810a6f4248641 (3).jpeg [图片上传中...(2ef074ac551810a6f4248641.jpeg-46188d-1588090650382-0)] 2ef074ac551810a6f4248641.jpeg

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


    122.006.jpeg

    哈夫曼编码

    哈夫曼编码(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 极大的缩短了字符个数

    哈夫曼树的实现思路:

    1. 获取根据权值构建的哈夫曼树
    2. 循环遍历[0,n]个结点;
    3. 创建临时结点cd ,从根结点开始对⻬进⾏编码,左孩⼦为0,右孩⼦为1;
    4. 将编码后的结点存储haffCode[i]
    5. 设置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;
    }
    
    

    相关文章

      网友评论

          本文标题:数据结构与算法-哈夫曼编码

          本文链接:https://www.haomeiwen.com/subject/zlxwwhtx.html