精华内容
下载资源
问答
  • 利用哈夫曼编码压缩文本

    千次阅读 多人点赞 2020-04-12 16:27:21
    文章目录使用哈夫曼编码进行压缩文本文本内容读取文件内容至内存中遍历文本内容,获取每个字符对应出现概率值建立哈夫曼树获取哈夫曼编码将转换后的编码写入新文件检测压缩率利用编码文件进行还原文本完整code ...

    使用哈夫曼编码进行压缩文本

    文本内容

    Even though neural network-based models have achieved
    a lot, there are several important things that have not been
    taken into consideration. Firstly, as shown in Figure 1, each
    block is represented as a low-dimensional embedding with
    manually selected features, which will cause the loss of
    much semantic information. Secondly, the order of the nodes
    plays an important role in representing binary functions,
    while previous approaches did not design methods to extract
    it. To solve these two problems, we propose an overall
    framework with three components: semantic-aware modeling,
    structural-aware modeling, and order-aware modeling.

    读取文件内容至内存中

    char *read_file(const char *filename)     ///从文件中读取字符串
    {
        FILE *fp = NULL;
        char buf[256];
        int len = 0;
        char *x = new char [10000];
        *x = '\0';
    
        if((fp = fopen(filename, "r"))==NULL)
        {
            perror("can't open the file");
            exit(1);
        }
        while(fgets(buf, 255, fp) != NULL)
        {
            len = strlen(buf);
            //printf("%d", len);
            if(buf[len-1] == '\n')
            {
                buf[len-1] = '\0';
            }
            //printf("%s\n", buf);
            strcat(x, buf);
        }
        //printf("%s\n", x);
        fclose(fp);
        return x;
    }
    
    

    遍历文本内容,获取每个字符对应出现概率值

    int samechar(char *x)     ///该函数将不同字符出现的次数记录下来
    {
        int flag;
        int n=0;
        tree_huffman[n].c = x[0];
        tree_huffman[n].w = 1.0;
        int l=strlen(x);
        for(int i=1;i<l;i++)
        {
            int j;
            flag=0;
            for(j=0;j<=n;j++)
            {
                if(x[i]==tree_huffman[j].c)
                {
                    flag=1;
                    tree_huffman[j].w++;
                    break;
                }
            }
            if(!flag)
            {
                n++;
                tree_huffman[n].c=x[i];
                tree_huffman[n].w=1.0;
            }
        }
        return n+1;
    }
    

    建立哈夫曼树

    • 首先给所有节点的权值由小到大排序;
    • 取出最小的两个节点,将它们的权值相加,得到一个新节点
    • 使用这个新节点代替两个原来的节点
    • 继续排序,替换
    • 直到整个队列中只有一个节点
    • 这就构成了一棵哈夫曼树
    int cmp(Tree a, Tree b)
    {
        return a.w<b.w;
    }
    
    int create_huffman(int n)   ///构建哈夫曼树
    {
        int rear = n, font = 0;
        Tree last;
        while(rear > font)
        {
            sort(tree_huffman+font, tree_huffman+rear, cmp);
            last = tree_huffman[font];
            last.l = font;
            font++;
            if (rear <= font)
                break;
            else
            {
                Tree t = tree_huffman[font];
                last.w += t.w;
                last.c = '\0';
                last.r = font;
                last.par = -1;
                font++;
                tree_huffman[rear++] = last;
            }
        }
        for(int i=0;i<rear;++i)
        {
            if(tree_huffman[i].l >= 0)
            {
                int lchild = tree_huffman[i].l;
                tree_huffman[lchild].par = i;
            }
            if(tree_huffman[i].r >= 0)
            {
                int rchild = tree_huffman[i].r;
                tree_huffman[rchild].par = i;
            }
        }
        //for(int i=0;i<rear;++i)
            //printf("%d, %c,%.2lf,%d,%d,%d\n", i, tree_huffman[i].c, tree_huffman[i].w, tree_huffman[i].l, tree_huffman[i].r, tree_huffman[i].par);
        return rear;
    
    }
    

    获取哈夫曼编码

    • 采用递归获取哈夫曼编码
    • 需要注意一个问题:使用char *进行递归时,系统只会给char *开辟一块内存
    • 这样造成哈夫曼编码前缀相同
    • 解决问题方法:换用string,string每次都开辟新内存来递归;或每次递归时给char *开辟新内存
    void output_tree_code(Tree &temp, char *code)
    {
        if(temp.l == -1 && temp.r == -1)
        {
            printf("%s\n", code);
            strcpy(temp.flag, code);
            return;
        }
        char t1[256], t2[256];
        strcpy(t1, code);
        strcpy(t2, code);
        output_tree_code(tree_huffman[temp.l], strcat(t1, "0"));
        output_tree_code(tree_huffman[temp.r], strcat(t2, "1"));
    }
    

    将转换后的编码写入新文件

    • 将哈夫曼编码每八位截取,不足8位的后面补零
    • 再将单个字节写入二进制文件
    void wfile(const char *filename1, const char *filename2, int n)
    {
        FILE *fp = NULL;
        fp = fopen(filename2, "wb");
        char *buf = read_file(filename1);
        char *temp = new char [10000];
        temp[0] = '\0';
        for(int i=0;i<int(strlen(buf));++i)
        {
            for(int j=0;j<n;++j)
            {
                if(buf[i] == tree_huffman[j].c)
                {
                    strcat(temp, tree_huffman[j].flag);
                    break;
                }
            }
        }
        printf("%s\n", temp);
        int len = 0;
        if(strlen(temp) % 8 == 0)
            len = strlen(temp) / 8;
        else
        {
            len = strlen(temp) / 8 + 1;
            while(strlen(temp) % 8 != 0)
            {
                strcat(temp, "0");
            }
        }
    
        for(int i=0;i<len;++i)
        {
            int a = 0;
            for(int j=0;j<8;++j)
            {
                int ca = temp[i*8+j] - '0';
                a += ca * pow(2, 7-j);
                //printf("%d\t", ca * pow(2, 8-j));
            }
            fwrite(&a, 1, 1, fp);
        }
        fclose(fp);
    }
    

    检测压缩率

    • 查看压缩文件2.huffman的大小

    • 查看原文件大小

    • 342/636 = 53%,也就是说压缩率为47%,压缩了将近一半的大小,就压缩率而言,相当可观。

    利用编码文件进行还原文本

    • 读取哈夫曼编码还原文本;
    • 从第一个字符开始读,如果为0,则向根节点的左子树走,如果为1,则向根节点的右子树走;
    • 每读取一个字符,进行一次移动操作;
    • 直到移动至叶子节点,该节点的左右子树均为空,递归结束,输出该节点的字符;
    • 继续读取下一个字符;
    • 直到所有字符读取完毕;
    void unzip_huffman(const char *filename, int root)
    {
        FILE *fp = NULL;
        if((fp = fopen(filename, "rb"))==NULL)
        {
            perror("can't open the file");
            exit(1);
        }
        int cb[10000];
        int num = 0;
        while(!feof(fp))
        {
            int element = getc(fp);
            //printf("%d\t", element);
            if(element != -1)
            {
                for(int i=0;i<8;++i)
                {
                    int t = element % 2;
                    element = element / 2;
                    cb[num++] = t;
                }
            }
        }
        int ccb[10000];
        int xnum = 0;
        for(int i=0;i<num/8;++i)
        {
            for(int j=0;j<8;++j)
            {
                ccb[xnum++] = cb[i*8+7-j];
            }
        }
        fclose(fp);
        char ss[10000] = "\0";
        int sr = 0;
        num = 0;
        int rt = root;
        while(num < xnum)
        {
            while(tree_huffman[rt].l != -1 && tree_huffman[rt].r != -1)
            {
                if(ccb[num] == 0)
                {
                    rt = tree_huffman[rt].l;
                }
                else if(ccb[num] == 1)
                {
                    rt = tree_huffman[rt].r;
                }
                num++;
            }
            ss[sr++] = tree_huffman[rt].c;
            //printf("%c", tree_huffman[rt].c);
            rt = root;
    
        }
        printf("%s\n", ss);
    }
    

    完整code

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<string>
    #include<stdio.h>
    #include<stdlib.h>
    #include<cmath>
    using namespace std;
    
    typedef struct haffman
    {
        char c;///标记字符
        char flag[256]; ///标记哈夫曼编码
        double w;///标记权值
        int l, r;///左孩子有孩子
        int par;///标记是否存在父母节点
    }Tree;
    
    Tree tree_huffman[128]; ///ascii表共128个字符
    
    
    char *read_file(const char *filename)     ///从文件中读取字符串
    {
        FILE *fp = NULL;
        char buf[256];
        int len = 0;
        char *x = new char [10000];
        *x = '\0';
    
        if((fp = fopen(filename, "r"))==NULL)
        {
            perror("can't open the file");
            exit(1);
        }
        while(fgets(buf, 255, fp) != NULL)
        {
            len = strlen(buf);
            //printf("%d", len);
            if(buf[len-1] == '\n')
            {
                buf[len-1] = '\0';
            }
            //printf("%s\n", buf);
            strcat(x, buf);
        }
        //printf("%s\n", x);
        fclose(fp);
        return x;
    }
    
    int samechar(char *x)     ///该函数将不同字符出现的次数记录下来
    {
        int flag;
        int n=0;
        tree_huffman[n].c = x[0];
        tree_huffman[n].w = 1.0;
        int l=strlen(x);
        for(int i=1;i<l;i++)
        {
            int j;
            flag=0;
            for(j=0;j<=n;j++)
            {
                if(x[i]==tree_huffman[j].c)
                {
                    flag=1;
                    tree_huffman[j].w++;
                    break;
                }
            }
            if(!flag)
            {
                n++;
                tree_huffman[n].c=x[i];
                tree_huffman[n].w=1.0;
            }
        }
        return n+1;
    }
    
    int cmp(Tree a, Tree b)
    {
        return a.w<b.w;
    }
    
    int create_huffman(int n)   ///构建哈夫曼树
    {
        int rear = n, font = 0;
        Tree last;
        while(rear > font)
        {
            sort(tree_huffman+font, tree_huffman+rear, cmp);
            last = tree_huffman[font];
            last.l = font;
            font++;
            if (rear <= font)
                break;
            else
            {
                Tree t = tree_huffman[font];
                last.w += t.w;
                last.c = '\0';
                last.r = font;
                last.par = -1;
                font++;
                tree_huffman[rear++] = last;
            }
        }
        for(int i=0;i<rear;++i)
        {
            if(tree_huffman[i].l >= 0)
            {
                int lchild = tree_huffman[i].l;
                tree_huffman[lchild].par = i;
            }
            if(tree_huffman[i].r >= 0)
            {
                int rchild = tree_huffman[i].r;
                tree_huffman[rchild].par = i;
            }
        }
        //for(int i=0;i<rear;++i)
            //printf("%d, %c,%.2lf,%d,%d,%d\n", i, tree_huffman[i].c, tree_huffman[i].w, tree_huffman[i].l, tree_huffman[i].r, tree_huffman[i].par);
        return rear;
    
    }
    
    void output_tree_code(Tree &temp, char *code)
    {
        if(temp.l == -1 && temp.r == -1)
        {
            printf("%s\n", code);
            strcpy(temp.flag, code);
            return;
        }
        char t1[256], t2[256];
        strcpy(t1, code);
        strcpy(t2, code);
        output_tree_code(tree_huffman[temp.l], strcat(t1, "0"));
        output_tree_code(tree_huffman[temp.r], strcat(t2, "1"));
    }
    
    void wfile(const char *filename1, const char *filename2, int n)
    {
        FILE *fp = NULL;
        fp = fopen(filename2, "wb");
        char *buf = read_file(filename1);
        char *temp = new char [10000];
        temp[0] = '\0';
        for(int i=0;i<int(strlen(buf));++i)
        {
            for(int j=0;j<n;++j)
            {
                if(buf[i] == tree_huffman[j].c)
                {
                    //printf("%s\n", tree_huffman[j].flag);
                    strcat(temp, tree_huffman[j].flag);
                    //fwrite(tree_huffman[j].flag, (1.0/8.0)*strlen(tree_huffman[j].flag), 1, fp);
                    break;
                }
            }
        }
        printf("%s\n", temp);
        /*
        for(int i=0;i<8;++i)
        {
            int len = strlen(temp);
            if(len % 8 != 0)
            {
                strcat(temp, "0");
            }
            else
                break;
        }*/
        //printf("%s\n", temp);
        int len = 0;
        if(strlen(temp) % 8 == 0)
            len = strlen(temp) / 8;
        else
        {
            len = strlen(temp) / 8 + 1;
            while(strlen(temp) % 8 != 0)
            {
                strcat(temp, "0");
            }
        }
    
        for(int i=0;i<len;++i)
        {
            int a = 0;
            for(int j=0;j<8;++j)
            {
                int ca = temp[i*8+j] - '0';
                a += ca * pow(2, 7-j);
                //printf("%d\t", ca * pow(2, 8-j));
            }
            //printf("\n");
            //printf("%d\n", a);
            fwrite(&a, 1, 1, fp);
        }
        fclose(fp);
    }
    
    void unzip_huffman(const char *filename, int root)
    {
        FILE *fp = NULL;
        if((fp = fopen(filename, "rb"))==NULL)
        {
            perror("can't open the file");
            exit(1);
        }
        int cb[10000];
        int num = 0;
        while(!feof(fp))
        {
            int element = getc(fp);
            //printf("%d\t", element);
            if(element != -1)
            {
                for(int i=0;i<8;++i)
                {
                    int t = element % 2;
                    element = element / 2;
                    cb[num++] = t;
                }
            }
        }
        //printf("\n");
        //printf("cb:\n");
        //for(int i=0;i<num;++i)
            //printf("%d ", cb[i]);
        //printf("\n");
        int ccb[10000];
        int xnum = 0;
        for(int i=0;i<num/8;++i)
        {
            for(int j=0;j<8;++j)
            {
                ccb[xnum++] = cb[i*8+7-j];
            }
        }
        //for(int i=0;i<xnum;++i)
            //printf("%d ", ccb[i]);
        fclose(fp);
        char ss[10000] = "\0";
        int sr = 0;
        num = 0;
        int rt = root;
        while(num < xnum)
        {
            while(tree_huffman[rt].l != -1 && tree_huffman[rt].r != -1)
            {
                if(ccb[num] == 0)
                {
                    rt = tree_huffman[rt].l;
                }
                else if(ccb[num] == 1)
                {
                    rt = tree_huffman[rt].r;
                }
                num++;
            }
            ss[sr++] = tree_huffman[rt].c;
            //printf("%c", tree_huffman[rt].c);
            rt = root;
    
        }
        printf("%s\n", ss);
    }
    
    int main()
    {
    
        ios::sync_with_stdio(false);
        const char *filename = "doc1.txt";
        char *st = read_file(filename);
        printf("input file's reading:\n");
        printf("%s\n", st);
        int n = samechar(st);
        printf("the char kinds of %d\n", n);
        for(int i=0;i<n;++i)
        {
            //printf("%c", tree_huffman[i].c);
            tree_huffman[i].w /= strlen(st);
            tree_huffman[i].l = -1;
            tree_huffman[i].r = -1;
            tree_huffman[i].par = -1;
            memset(tree_huffman[i].flag, 0, sizeof(tree_huffman[i].flag));
            //printf("%.2lf\n", tree_huffman[i].w);
        }
        n = create_huffman(n);
        char code[256] = "\0";
        //printf("%d", n);
        output_tree_code(tree_huffman[n-1], code);
        for(int i=0;i<n;++i)
        {
            printf("%d, %c,%.2lf,%d,%d,%d, ", i, tree_huffman[i].c, tree_huffman[i].w, tree_huffman[i].l, tree_huffman[i].r, tree_huffman[i].par);
            printf("%s\n", tree_huffman[i].flag);
            //cout<<tree_huffman[i].flag<<endl;
        }
        wfile(filename, "2.huffman", n);
    
        unzip_huffman("2.huffman", n-1);
        return 0;
    }
    
    
    展开全文
  • 对英文文本文件进行哈夫曼编码译码的C++实现 以及压缩率计算哈夫曼编码压缩原理:由于每个字符在内存中都是以ASCII码进行存储,所以每个字符都占用了八个01位,利用哈夫曼树对每个字符进行01编码,根据字符在文章中...

    哈夫曼编码压缩原理:由于每个字符在内存中都是以ASCII码进行存储,所以每个字符都占用了八个01位,利用哈夫曼树对每个字符进行01编码,根据字符在文章中出现的频率调整01串长度,出现频率高的字符在哈夫曼树中的权重大,编码后01串短,从而使得最终计算出的平均编码长度小于8,在本代码中平均编码长度约为4.72,压缩率约为59%,从而达到压缩文本的目的。

    // HuffmanEncode.cpp: 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<string>
    int length;  //文章长度
    //定义结构体统计单个字符出现次数
    struct Char_Frequency
    {
        char c;
        int Frequency;
    };
    Char_Frequency a[10000];   //建立结构体数组 存储每个字符的出现次数
                               /*从文本文件中统计各字符出现次数*/
    void Char_Probability_Fromfile(FILE *fp)
    {
        length = 0;
        for (int i = 0; i < 100; i++)   //对结构体数组初始化
        {
            a[i].c = NULL;
            a[i].Frequency = 0;
        }
        char ch;
        while (fscanf(fp, "%c", &ch) == 1)
        {
            length++;
            int i = 0, flag = 0;
            while (a[i].c != NULL)
            {
                if (a[i].c == ch)
                {
                    a[i].Frequency++;
                    flag = 1;
                }
                i++;
            }
            if (!flag)
            {
                a[i].c = ch;
                a[i].Frequency = 1;
            }
        }
    
    }
    /*哈夫曼树存储结构*/
    typedef struct {
        int weight;
        char c;
        int lchild;
        int rchild;
        int parent;
    }HTNODE;
    typedef HTNODE HuffmanT[10000];
    HuffmanT T;
    /*初始化哈夫曼树*/
    void InitHT()
    {
        for (int i = 0; i < 100; i++)
        {
            T[i].c = NULL;
            T[i].lchild = -1;
            T[i].rchild = -1;
            T[i].parent = -1;
            T[i].weight = NULL;
        }
    }
    /*为哈夫曼树加载权值*/
    void InputW(int n)
    {
        for (int i = 0; i < n; i++)
        {
            T[i].c = a[i].c;
            T[i].weight = a[i].Frequency;
        }
        for (int i = 0; i < n; i++)
        {
            printf("权重初始为:%c %ld\n", T[i].c, T[i].weight);
        }
    }
    /*找到两个最小权值节点*/
    void SelectMin(int n, int *p1, int *p2)
    {
    
        int i, j;
        for (i = 0; i < n; i++)
        {
            if (T[i].parent == -1)
            {
                *p1 = i;
                break;
            }
        }
        for (j = i + 1; j < n; j++)
        {
            if (T[j].parent == -1)
            {
                *p2 = j;
                break;
            }
        }
        for (i = 0; i < n; i++)
        {
            if ((T[*p1].weight > T[i].weight) && (T[i].parent == -1) && (*p2 != i))
                *p1 = i;
        }
        for (j = 0; j < n; j++)
        {
            if ((T[*p2].weight > T[j].weight) && (T[j].parent == -1) && (*p1 != j))
                *p2 = j;
        }
    }
    /*哈夫曼树构造算法,n为有权值的节点个数*/
    void CreateHT(int n)
    {
        int i, p1, p2;
        InitHT();
        InputW(n);
        for (i = n; i < 2 * n; i++)
        {
            SelectMin(i, &p1, &p2);
            T[p1].parent = T[p2].parent = i;
            T[i].lchild = p1;
            T[i].rchild = p2;
            T[i].weight = T[p1].weight + T[p2].weight;
        }
    
    }
    /*哈夫曼编码表的存储结构*/
    typedef struct {
        char ch;
        char bits[1000];
    }CodeNode;
    typedef CodeNode HuffmanCode[100000];
    HuffmanCode H;
    /*哈夫曼编码算法实现*/
    void CharSetHuffmanEncoding(int n)
    {
        int c, p, i;
        char cd[10000];
        int start;
        cd[n] = '\0';
        for (i = 0; i < n; i++)
        {
            H[i].ch = T[i].c;
            start = n;
    
    
            c = i;
            while ((p = T[c].parent) >0)
            {
                cd[--start] = (T[p].lchild == c) ? '0' : '1';
                c = p;
            }
            strcpy(H[i].bits, &cd[start]);
        }
    }
    char copy[100000000];
    /*编码写入文件*/
    void Encode(int n)
    {
        FILE *fp = fopen("D:\\test2.txt", "r");
        FILE *fp2 = fopen("D:\\test2w.txt", "w");
        char ch;
        while (fscanf(fp, "%c", &ch) == 1)
        {
            for (int i = 0; i < n; i++)
            {
                if (H[i].ch == ch)
                {
                    fprintf(fp2, "%s", H[i].bits);
                    strcat(copy, H[i].bits);
                }
            }
        }
    }
    /*解码写入文件*/
    void Decode(int n)
    {
    
        FILE *fp = fopen("D:\\decode.txt", "w");
        int root,p, i, j = 0;
        p = root = 2 * n - 1;
        for (i = 0; i < strlen(copy); i++)
        {
            if (copy[i] == '0')
            {
                p = T[p].lchild;
            }
            else if (copy[i] == '1')
            {
                p = T[p].rchild;
            }
            if (T[p].lchild == -1 && T[p].rchild == -1)
            {
    
                fprintf(fp, "%c", T[p].c);
                p = root;
            }
        }
    
    
    }
    /*求压缩率*/
    void Encode_Rate(int n)
    {
        float WPL=0;
        for (int i = 0; i < n; i++)
        {
            WPL += (float)strlen(H[i].bits)*((float)((float)a[i].Frequency / (float)length));
        }
    
        printf("压缩率为:    %f\n", WPL/8.00);
    
    }
    
    
    
    
    int main()
    {
        FILE *fp = fopen("D:\\test2.txt", "r");
        Char_Probability_Fromfile(fp);
        int i = 0;
        while (a[i].c != NULL)
        {
            printf("%c %d      %d", a[i].c, a[i].c, a[i].Frequency);
            printf("\n");
            i++;
        }
        printf("i为:%d\n", i);
    
        CreateHT(i);
        int n = 0;
        while (T[n].weight != NULL)
        {
            printf("序号:%d  %c 权重:%d  父母:%d 左儿子:%d  右儿子:%d \n", n, T[n].c, T[n].weight, T[n].parent, T[n].lchild, T[n].rchild);
            n++;
        }
        printf("-------\n");
    
        CharSetHuffmanEncoding(i);
        n = 0;
    
        Encode(i);
        Decode(i);
    
        printf("\n");
        Encode_Rate(i);
    
    
    
    
    
        return 0;
    }
    
    

    附上运行结果图片:

    压缩译码前:这里写图片描述

    压缩译码后:这里写图片描述

    译码后,恢复原文:这里写图片描述

    这里写图片描述
    这里写图片描述
    这里写图片描述

    展开全文
  • 利用哈夫曼编码压缩文件

    千次阅读 2017-09-05 17:54:48
    本大作业主要考核如何以C实现集成电路测试向量文件的无损压缩。在通常的文件存储中,无论是二进制格式的文件还是文本文件,几乎都是等宽的编码。比如ASCII码格式的文本文件,每个字符由一个ASCII码表示,宽度为8bit...

                                                利用哈夫曼编码压缩解压文件

    1.     引言

    本文为大一下学期C语言课程的期末大作业,经过修改后发布。文中要用到的测试文件1.lst见链接:  https://pan.baidu.com/s/1hs7XoIK  密码: wpru。              

    编译环境:Ubuntu 16.04

    本文主要考核如何以C实现集成电路测试向量文件的无损压缩。在通常的文件存储中,无论是二进制格式的文件还是文本文件,几乎都是等宽的编码。比如ASCII码格式的文本文件,每个字符由一个ASCII码表示,宽度为8bit。然而,从磁盘空间利用率的角度看,这并不是一种效率最高的存储方案。为了理解定长编码与变长编码的区别,假设某个文件纯粹由abcdef6个字符组成,作为定长编码,至少需要3bit才能表示6个不同的字符,假设每个字符出现的频率以及两种编码方案如下表所示


    下面我们计算一下上述两种编码方案的总编码长度。由于6个字符共出现了 100K次,对于定长编码,每个字符占用3bit,总共将占用300Kb的空间;对于变长编码,总计的编码长度为:45*1+(13+12+16)*3+(9+5)*4=224Kb,节省了76Kb的空间。这也正是本次大作业的基本的实现原理。上表中的变长编码有个特点,就是出现越频繁的字符,用越短的编码去表示;而且,每个字符的编码都不是另一个字符编码的前缀,从而简化了解码时的难度,因此又被称为前缀编码。哈夫曼编码就是这样一种编码。本作业要求以哈夫曼编码的原理,编写一个可以将给定的文件进行文件压缩,同时可以将压缩的文件进行解压的程序。比如假设编写的程序为huffhuff -c test.dat –o test.hufftest.dat文件压缩为test.huff;类似的,huff -d test.huff -o test.dat将压缩文件进行解压为原始的test.dat。现在问题的主要难点在于如何针对给定的文件由程序自己统计不同字符出现的频率并据此构造哈夫曼编码。

    哈夫曼编码原理

    此处以一个实例说明构造哈夫曼编码的过程。构造哈夫曼编码的过程可以等效为一个构造哈夫曼编码树的过程。以上节中的例子为例,首先需要统计各个字符出现的频率,如
    上面表格中所示。 哈夫曼编码树的构造过程如下图所示。



    首先,创建 个叶子节点,如上图(a)所示,冒号后面是该节点字符出现的频率;接下来每次从当前结点中寻找两个出现频度最低的节点,出现频率最低的放在左边,如(b)f,次低的放右边,如上图(b)的 e,然后将这两个出现频率最低的节点合并为一个节点,以两个节点出现的总频率为名字,如上图(b)的 14 节点, 14 节点和 与 分别用标记为 0/1的边连接,这时 和 两个节点已被删除并被合并为一个 14 节点,因此总的节点数少了一个;接下来继续寻找两个频率最低的节点,如上图(c)中的 和 b,二者合并为 25 节点,分别与 和 以边 0/1 连接;接下来 14 和 节点出现频率最低,分别为 14 和 16,合并为 30节点;继续此过程, 25 和 30 节点合并为 55 节点, 55 节点和 合并为最终的 100 节点。至此哈夫曼编码树构造完成,如上图(f)。观察上图(f),所有表示真实字符的节点都放置于矩形框中,且都是叶子节点。从根节点到叶子节点的边的标签相连就是该叶子节点的编码,即 a: 0; b: 101; c: 100; d: 111; e: 1101;f: 1100,恰好是前面表中的变长编码方案。 


    2.       基本原理/实现方法

    以下是几个主要部分的编码解释,大家可以直接跳过,文件源代码贴在最后。 


    由试验简介,根据哈夫曼编码的原理,可以实现文件的压缩与解压。压缩时读取字符转化而相应的哈夫曼二进制编码,解压即为其逆操作。接下来对完成的程序进行分析,具体的代码见huffman.c。

    【程序及算法分析】

    a)        哈夫曼树建立预备步骤

    void initialize(struct node *HuffmanTreeNodeTemp,int count[]) 函数

    /***********压缩文件的准备工作*************/
    void initialize(struct node *HuffmanTreeNodeTemp,int count[])
    {
    	int i,j;
    	struct node temp;
    	for (i=0;i<256;i++)                      //给每一个临时的节点赋值
        {
            HuffmanTreeNodeTemp[i].value=count[i];
            HuffmanTreeNodeTemp[i].ch=(char)i;
        }
        for (i=0;i<256;i++)                      //筛选出现过的字符
        {
            for (j=i+1;j<256;j++)
            {
                if (HuffmanTreeNodeTemp[i].value<HuffmanTreeNodeTemp[j].value)
                {
                    temp=HuffmanTreeNodeTemp[i];
                    HuffmanTreeNodeTemp[i]=HuffmanTreeNodeTemp[j];
                    HuffmanTreeNodeTemp[j]=temp;
                }
            }
        }
    }


    根据main()函数中统计的256个各个不同字符所重复出现的次数,来创建出256个临时结点结构。又由于实际哈夫曼树的建立并不需要考虑未出现过的字符,所以将这256个节点根据出现的次数(value值)进行排序,将有用的部分放在前面,为下一步建立正式哈夫曼结点准备。

     

    b)        哈夫曼树的建立:void CreatHuffmanTree(int nodecount,int max,struct node *HuffmanTreeNodeTemp,structnode *HuffmanTreeNode)函数

    /************构造哈夫曼树************/
    void CreatHuffmanTree(int nodecount,int max,struct node *HuffmanTreeNodeTemp,struct node *HuffmanTreeNode)
    {
        int i,j,k,m,n,value;
        int min;
        for (i=0;i<nodecount;i++)
        {
            HuffmanTreeNode[i]=HuffmanTreeNodeTemp[i];
        }
        for (i=0;i<2*nodecount-1;i++)
        {
            HuffmanTreeNode[i].tag=0;
            HuffmanTreeNode[i].parent=0;
        }
        for (i=nodecount;i<2*nodecount-1;i++)
        {
            min=INT_MAX;
            for (j=0;j<i;j++)       //查找最大值m
            {
                if ((HuffmanTreeNode[j].tag==0) && (HuffmanTreeNode[j].value<=min))
                {
                    min=HuffmanTreeNode[j].value;
                    m=j;              //m,n分别表示其为最大,次大值为第几个
                }
            }
            HuffmanTreeNode[m].tag=1;
            min=INT_MAX;
            for (j=0;j<i;j++)        //查找次大值n
            {
                if ((HuffmanTreeNode[j].tag==0)  &&( HuffmanTreeNode[j].value<=min))
                {
                    min=HuffmanTreeNode[j].value;
                    n=j;
                }
            }
            HuffmanTreeNode[n].tag=1;      			//被找过的值就标记1,下一次就不会再找了
            HuffmanTreeNode[i].lchild=m;
            HuffmanTreeNode[i].rchild=n;
            HuffmanTreeNode[m].parent=i;
            HuffmanTreeNode[n].parent=i;
            HuffmanTreeNode[i].value=HuffmanTreeNode[m].value+HuffmanTreeNode[n].value;
        }
    
        //生成哈夫曼编码
        int index,temp;
    
        for (i=0;i<nodecount;i++)
        {
            index=255;
            for (j=i;HuffmanTreeNode[j].parent!=0;)
            {
                temp=HuffmanTreeNode[j].parent;
                if (HuffmanTreeNode[temp].lchild==j)
                {
                    HuffmanTreeNode[i].hufcodetemp[index]=1;
                    index--;
                }
                else if (HuffmanTreeNode[temp].rchild==j)
                {
                    HuffmanTreeNode[i].hufcodetemp[index]=0;
                    index--;
                }
                j=temp;
            }
    
            int length=255-index;
            HuffmanTreeNode[i].hufcode=malloc(length*sizeof(int));
            HuffmanTreeNode[i].codelen=length;
    
            for (k=0;k<length;k++)
            {
                index++;
                HuffmanTreeNode[i].hufcode[k]=HuffmanTreeNode[i].hufcodetemp[index];
            }
        }
    }


    哈夫曼树的总节点个数为2*叶子个数-1,叶子个数n即为有效的字符个数,因此可以先分配出2n-1个的结点,其中,前n个为叶子结点,后n-1个为非叶子结点。根据哈夫曼树的建立原理,在建立哈夫曼树的过程中,先寻找已存在的结点中value值最大和次大的且tag值为0的结点,将这两个选择的结点tag值设置为1,这样下次搜索就会跳过它。同时,将其父亲结点加入下一次的搜索范围之内。记录相应的lchild、rchild、parent等必要数据值。如此循环,直到哈夫曼树建立完成。

     

    c)        压缩文件核心部分:

    void compressfile(struct node *HuffmanTreeNode,int wordcount,intnodecount,char FILE1[],char FILE2[]) 函数

    /**********对文件进行压缩************/
    void compressfile(struct node *HuffmanTreeNode,int wordcount,int nodecount,char FILE1[],char FILE2[])
    {
    	FILE *ptr=fopen(FILE1,"rb");
        FILE *ptw=fopen(FILE2,"wb");
        char readtemp;
        unsigned char codetemp;
        int wcount=0,i,j;
        int length,num;
        codetemp='\0';
        						//写入哈夫曼编码
        fwrite(&nodecount,sizeof(int),1,ptw);
        fwrite(&wordcount,sizeof(int),1,ptw);
        for (i=0;i<nodecount;i++)
        {
            fwrite(&(HuffmanTreeNode[i].ch),sizeof(char),1,ptw);
        }
        for (i=nodecount;i<nodecount*2-1;i++)
        {
            fwrite(&(HuffmanTreeNode[i].lchild),sizeof(int),1,ptw);
            fwrite(&(HuffmanTreeNode[i].rchild),sizeof(int),1,ptw);
        }
    
        while(!feof(ptr))
        {
            readtemp=getc(ptr);
            for (j=0;j<nodecount;j++)                    //找对应的字符
            {
                if (HuffmanTreeNode[j].ch==readtemp)
                {
                    num=j;
                    break;
                }
            }
    
            for (i=0;i<HuffmanTreeNode[num].codelen;i++)		//位操作来进行
            {
                codetemp<<=1;
                codetemp|=HuffmanTreeNode[num].hufcode[i];
    
                wcount++;
                if (wcount==8)						//满八位以后写入压缩文件
                {
                    fwrite(&codetemp,sizeof(unsigned char),1,ptw);
                    wcount=0;
                    codetemp='\0';
                }
            }
           if (feof(ptr))
                break;
        }
        if (wcount>0)							//处理最后的未满八位的字节
        {
            for (i=0;i<8-wcount;i++)
                codetemp<<=1;
    
            fwrite(&codetemp,sizeof(unsigned char),1,ptw);
        }
        fclose(ptr);
        fclose(ptw);
    }

    根据建立的哈夫曼树,不妨假设父亲节点的左儿子编码为1,右儿子为0,这样就能从根结点开始得到每一个字符的哈夫曼编码。在进行压缩的时候,依次读取测试文件中的字符,根据该字符的哈夫曼编码通过位操作写入压缩文件中,在写入的过程中加入一个计数器wcount,当得到一位值,wcount就加一。当其值满8时及说明可以向压缩文件中写入一个字符,再将计数器归零。以此循环直到最后。最后可能出现为满8位的情况,这时要将其右端加0填满8位再写入文件。

    需要说明的是,为了解压时候处理最后一个字符方便,需要将解压时所需要的相关信息在压缩之前写入文件。需要写入的重要信息有:所含有的有效字符种类,为了读取时分配大小、确定树叶节点个数;所含有的字符个数,输出最后一个字符时使用;叶子结点的字符值,非叶子结点的左儿子、右儿子值,为了从根节点一步一步得到叶子结点是使用。


    d)        解压文件部分:void extract(charFILE2[],char FILE3[])函数

    /************解压文件正式程序************/
    void extract(char FILE2[],char FILE3[])
    {
        int i,j;
        FILE *ptr=fopen(FILE2,"rb");
        int countch;
        int curwordcount=0;
        int wordcount;
    
        fread(&countch,sizeof(int),1,ptr);                          //从文件中获取构建哈夫曼树的相关信息
        fread(&wordcount,sizeof(int),1,ptr);
    	struct node *extractHuffmanTreeNode = malloc((countch*2-1)*sizeof(struct node));
    	for (i=0;i<countch;i++)
        {
            extractHuffmanTreeNode[i].rchild=-1;
            extractHuffmanTreeNode[i].lchild=-1;
        }
        for (i=0;i<countch;i++)
        {
            fread(&(extractHuffmanTreeNode[i].ch),sizeof(char),1,ptr);
        }
    
        for (i=countch;i<2*countch-1;i++)
        {
            fread(&(extractHuffmanTreeNode[i].lchild),sizeof(int),1,ptr);
            fread(&(extractHuffmanTreeNode[i].rchild),sizeof(int),1,ptr);
        }
    
        int nextnode=2*countch-2;
        int pose;
        unsigned char chtemp;
    
        FILE *ptw=fopen(FILE3,"wb");
        while (!feof(ptr))							//读取文件进行解码
        {
            fread(&chtemp,sizeof(unsigned char),1,ptr);
            for (i=0;i<8;i++)
            {
                if (curwordcount>=wordcount)	//让打印的字符数与原文件相同,这个是由于用huffman编码压缩时,最后不满8位的都被进行移位处理了,当解压时无法判断最后的0是不是移位造成的
                    break;
                if (((int)chtemp&128)==128)				//采用掩码来判断该位上为0还是1
                    pose=1;
                else
                    pose=0;
                chtemp<<=1;
                if (nextnode>=countch)     //非叶子节点,继续
                {
                    if (pose==1)
                    {
                        nextnode=extractHuffmanTreeNode[nextnode].lchild;
                    }
                    else
                    {
                        nextnode=extractHuffmanTreeNode[nextnode].rchild;
    
                    }
                    if (nextnode<countch)      //到达叶子节点,将解压的字符输出
                    {
                        fwrite(&(extractHuffmanTreeNode[nextnode].ch),sizeof(char),1,ptw);
                        curwordcount++;
                        nextnode=2*countch-2;
                    }
                }
            }
        }
        free(extractHuffmanTreeNode);
        fclose(ptw);
        fclose(ptr);
    }


    解压文件即为压缩文件的逆过程。首先读取解压缩所需的相关信息,根据其建立哈夫曼树。进行解压文件时,依次读取文件的一个字符,一位字符占八位字节,可以通过掩码(mask)来确定某一位上的值。确定一位值就在哈夫曼树上由跟节点移动一步,得到相应的解码后的字符值。其中和压缩时设置的一样,左儿子为1,右儿子为0。每读到一个字符就向解压文件中写入该字符,再从头开始重新求下一个字符。

    由于压缩时最后一位的处理比较特殊,通过移动往后增加了几个0,而解压时很难判断这几个0是哈夫曼编码还是移动得到的。因此在之前压缩时已经写入了该文件应包含几个字符,解压时即可用计数器统计解压产生的字符个数,当其值到达要求值时就退出循环。

     

    3.       实现过程/实验数据

    a)       函数运行结果分析:


    时间:

    压缩文件(包括写压缩文件&构造哈夫曼树)用时约25.2s,解压缩(包括重构哈夫曼树&写解压缩文件)用时约22.6s。

    1.lst为原文件(即老师提供的文件,改了一下名字,方便输入),生成的2.lst为压缩文件,3.lst为解压后的文件。三个文件见附件。通过ubuntu下的diff命令操作,比较1.lst和3.lst是否相同,当不返回任何内容时,两个文件即为相同的,否则则返回两文件不同的部分。由截图可以看出,该程序解压得到的文件和原文件相同。即说明压缩与解压程序可以正确运行。

     

    b)        压缩率分析:


    查看两个文件大小:原文件1.lst大小为849,646,229字节,压缩后的文件2.lst为123,313,632 字节,压缩率为

     

    c)   内存泄漏分析:

    通过valgrind工具可以分析该程序的内存泄漏情况:


    可以看到,该程序所有需要释放的内存都已经被释放,内存无泄漏。

     


    ****************************下面是源码***************************

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <limits.h>
    
    struct node{
        int value;                  //权重
        int parent,lchild,rchild;
        char ch;
        int tag;
        int hufcodetemp[256];
        int *hufcode;
        int codelen;
        };
    
    void CreatHuffmanTree(int nodecount,int max,struct node *huffmanTreeNodeTemp,struct node *huffmanTreeNode);
    void initialize(struct node *HuffmanTreeNodeTemp,int count[]);
    void compressfile(struct node *HuffmanTreeNode,int wordcount,int nodecount,char FILE1[],char FILE2[]);
    void compress(int count[],int wordcount,char FILE1[],char FILE2[]);
    void extract(char FILE1[],char FILE2[]);
    
    /************解压文件正式程序************/
    void extract(char FILE2[],char FILE3[])
    {
        int i,j;
        FILE *ptr=fopen(FILE2,"rb");
        int countch;
        int curwordcount=0;
        int wordcount;
    
        fread(&countch,sizeof(int),1,ptr);                          //从文件中获取构建哈夫曼树的相关信息
        fread(&wordcount,sizeof(int),1,ptr);
    	struct node *extractHuffmanTreeNode = malloc((countch*2-1)*sizeof(struct node));
    	for (i=0;i<countch;i++)
        {
            extractHuffmanTreeNode[i].rchild=-1;
            extractHuffmanTreeNode[i].lchild=-1;
        }
        for (i=0;i<countch;i++)
        {
            fread(&(extractHuffmanTreeNode[i].ch),sizeof(char),1,ptr);
        }
    
        for (i=countch;i<2*countch-1;i++)
        {
            fread(&(extractHuffmanTreeNode[i].lchild),sizeof(int),1,ptr);
            fread(&(extractHuffmanTreeNode[i].rchild),sizeof(int),1,ptr);
        }
    
        int nextnode=2*countch-2;
        int pose;
        unsigned char chtemp;
    
        FILE *ptw=fopen(FILE3,"wb");
        while (!feof(ptr))							//读取文件进行解码
        {
            fread(&chtemp,sizeof(unsigned char),1,ptr);
            for (i=0;i<8;i++)
            {
                if (curwordcount>=wordcount)	//让打印的字符数与原文件相同,这个是由于用huffman编码压缩时,最后不满8位的都被进行移位处理了,当解压时无法判断最后的0是不是移位造成的
                    break;
                if (((int)chtemp&128)==128)				//采用掩码来判断该位上为0还是1
                    pose=1;
                else
                    pose=0;
                chtemp<<=1;
                if (nextnode>=countch)     //非叶子节点,继续
                {
                    if (pose==1)
                    {
                        nextnode=extractHuffmanTreeNode[nextnode].lchild;
                    }
                    else
                    {
                        nextnode=extractHuffmanTreeNode[nextnode].rchild;
    
                    }
                    if (nextnode<countch)      //到达叶子节点,将解压的字符输出
                    {
                        fwrite(&(extractHuffmanTreeNode[nextnode].ch),sizeof(char),1,ptw);
                        curwordcount++;
                        nextnode=2*countch-2;
                    }
                }
            }
        }
        free(extractHuffmanTreeNode);
        fclose(ptw);
        fclose(ptr);
    }
    
    /************构造哈夫曼树************/
    void CreatHuffmanTree(int nodecount,int max,struct node *HuffmanTreeNodeTemp,struct node *HuffmanTreeNode)
    {
        int i,j,k,m,n,value;
        int min;
        for (i=0;i<nodecount;i++)
        {
            HuffmanTreeNode[i]=HuffmanTreeNodeTemp[i];
        }
        for (i=0;i<2*nodecount-1;i++)
        {
            HuffmanTreeNode[i].tag=0;
            HuffmanTreeNode[i].parent=0;
        }
        for (i=nodecount;i<2*nodecount-1;i++)
        {
            min=INT_MAX;
            for (j=0;j<i;j++)       //查找最大值m
            {
                if ((HuffmanTreeNode[j].tag==0) && (HuffmanTreeNode[j].value<=min))
                {
                    min=HuffmanTreeNode[j].value;
                    m=j;              //m,n分别表示其为最大,次大值为第几个
                }
            }
            HuffmanTreeNode[m].tag=1;
            min=INT_MAX;
            for (j=0;j<i;j++)        //查找次大值n
            {
                if ((HuffmanTreeNode[j].tag==0)  &&( HuffmanTreeNode[j].value<=min))
                {
                    min=HuffmanTreeNode[j].value;
                    n=j;
                }
            }
            HuffmanTreeNode[n].tag=1;      			//被找过的值就标记1,下一次就不会再找了
            HuffmanTreeNode[i].lchild=m;
            HuffmanTreeNode[i].rchild=n;
            HuffmanTreeNode[m].parent=i;
            HuffmanTreeNode[n].parent=i;
            HuffmanTreeNode[i].value=HuffmanTreeNode[m].value+HuffmanTreeNode[n].value;
        }
    
        //生成哈夫曼编码
        int index,temp;
    
        for (i=0;i<nodecount;i++)
        {
            index=255;
            for (j=i;HuffmanTreeNode[j].parent!=0;)
            {
                temp=HuffmanTreeNode[j].parent;
                if (HuffmanTreeNode[temp].lchild==j)
                {
                    HuffmanTreeNode[i].hufcodetemp[index]=1;
                    index--;
                }
                else if (HuffmanTreeNode[temp].rchild==j)
                {
                    HuffmanTreeNode[i].hufcodetemp[index]=0;
                    index--;
                }
                j=temp;
            }
    
            int length=255-index;
            HuffmanTreeNode[i].hufcode=malloc(length*sizeof(int));
            HuffmanTreeNode[i].codelen=length;
    
            for (k=0;k<length;k++)
            {
                index++;
                HuffmanTreeNode[i].hufcode[k]=HuffmanTreeNode[i].hufcodetemp[index];
            }
        }
    }
    
    /***********压缩文件的准备工作*************/
    void initialize(struct node *HuffmanTreeNodeTemp,int count[])
    {
    	int i,j;
    	struct node temp;
    	for (i=0;i<256;i++)                      //给每一个临时的节点赋值
        {
            HuffmanTreeNodeTemp[i].value=count[i];
            HuffmanTreeNodeTemp[i].ch=(char)i;
        }
        for (i=0;i<256;i++)                      //筛选出现过的字符
        {
            for (j=i+1;j<256;j++)
            {
                if (HuffmanTreeNodeTemp[i].value<HuffmanTreeNodeTemp[j].value)
                {
                    temp=HuffmanTreeNodeTemp[i];
                    HuffmanTreeNodeTemp[i]=HuffmanTreeNodeTemp[j];
                    HuffmanTreeNodeTemp[j]=temp;
                }
            }
        }
    }
    
    /**********对文件进行压缩************/
    void compressfile(struct node *HuffmanTreeNode,int wordcount,int nodecount,char FILE1[],char FILE2[])
    {
    	FILE *ptr=fopen(FILE1,"rb");
        FILE *ptw=fopen(FILE2,"wb");
        char readtemp;
        unsigned char codetemp;
        int wcount=0,i,j;
        int length,num;
        codetemp='\0';
        						//写入哈夫曼编码
        fwrite(&nodecount,sizeof(int),1,ptw);
        fwrite(&wordcount,sizeof(int),1,ptw);
        for (i=0;i<nodecount;i++)
        {
            fwrite(&(HuffmanTreeNode[i].ch),sizeof(char),1,ptw);
        }
        for (i=nodecount;i<nodecount*2-1;i++)
        {
            fwrite(&(HuffmanTreeNode[i].lchild),sizeof(int),1,ptw);
            fwrite(&(HuffmanTreeNode[i].rchild),sizeof(int),1,ptw);
        }
    
        while(!feof(ptr))
        {
            readtemp=getc(ptr);
            for (j=0;j<nodecount;j++)                    //找对应的字符
            {
                if (HuffmanTreeNode[j].ch==readtemp)
                {
                    num=j;
                    break;
                }
            }
    
            for (i=0;i<HuffmanTreeNode[num].codelen;i++)		//位操作来进行
            {
                codetemp<<=1;
                codetemp|=HuffmanTreeNode[num].hufcode[i];
    
                wcount++;
                if (wcount==8)						//满八位以后写入压缩文件
                {
                    fwrite(&codetemp,sizeof(unsigned char),1,ptw);
                    wcount=0;
                    codetemp='\0';
                }
            }
           if (feof(ptr))
                break;
        }
        if (wcount>0)							//处理最后的未满八位的字节
        {
            for (i=0;i<8-wcount;i++)
                codetemp<<=1;
    
            fwrite(&codetemp,sizeof(unsigned char),1,ptw);
        }
        fclose(ptr);
        fclose(ptw);
    }
    
    /************压缩文件的正式程序***********/
    void compress(int count[],int wordcount,char FILE1[],char FILE2[])
    {
        int i,j,nodecount=0;
        struct node *HuffmanTreeNodeTemp=malloc(256*sizeof(struct node));      										//先给每一个可能的字符都初始化哈夫曼节点
    
        initialize(HuffmanTreeNodeTemp, count);		//处理这些节点,排序
    
        int max=HuffmanTreeNodeTemp[0].value;		//重新建立一棵包含有效的节点的哈夫曼树
    
        for (i=0;i<256;i++)
        {
            if (HuffmanTreeNodeTemp[i].value!=0)
                    nodecount++;
            if (HuffmanTreeNodeTemp[i].value>max)
                    max=HuffmanTreeNodeTemp[i].value;
        }
        struct node *HuffmanTreeNode=malloc((2*nodecount-1)*sizeof(struct node));
        for (i=0;i<nodecount;i++)
        {
            HuffmanTreeNode[i]=HuffmanTreeNodeTemp[i];
        }
    
        CreatHuffmanTree(nodecount,max,HuffmanTreeNodeTemp,HuffmanTreeNode);
    
        for (i=0;i<nodecount;i++)				//打印哈夫曼编码
        {
            printf("[%d]",i);
            printf(" %c ",HuffmanTreeNode[i].ch);
            for (j=0;j<HuffmanTreeNode[i].codelen;j++)
                {
                    printf("%d",HuffmanTreeNode[i].hufcode[j]);
                }
            printf("\n");
        }
    
        compressfile(HuffmanTreeNode,wordcount,nodecount,FILE1,FILE2);   //压缩文件
        for (i=0;i<nodecount;i++)
        {
        	free(HuffmanTreeNode[i].hufcode);
        }
            free(HuffmanTreeNode);
            free(HuffmanTreeNodeTemp);
    }
    
    /*************主函数**************/
    int main()
    {
        int i;
        char ch;
        char FILE1[100],FILE2[100],FILE3[100];
        int wordcount=0;      //统计文件中的字符个数
        int count[256]={0};
    
        FILE *fp=fopen(FILE1,"rb");
        printf("Please enter the file name.\n");
        scanf("%s",FILE1);
        while ((fp=fopen(FILE1,"r"))==NULL)
        {
            printf("Sorry, can't open it.\nPlease enter the file name again.\n");
            scanf("%s",FILE1);
        }
        printf("Please enter the compressed file name.\n");
        scanf("%s",FILE2);
        printf("Please enter the extracted file name.\n");
        scanf("%s",FILE3);
    
        while((ch=getc(fp))!=EOF){
                    count[(int)ch]+=1;
                    wordcount++;
        }
        fclose(fp);
        int a,b;
        printf("compressing now\n");
        a=clock();
        compress(count,wordcount,FILE1,FILE2);
        b=clock();
        printf("\ncompress use time:   %dus\n",b-a);
        printf("extracting now\n");
        a=clock();
        extract(FILE2,FILE3);
        b=clock();
        printf("\nextract use time:   %dus\n",b-a);
        return 0;
    }
    

     

     

    展开全文
  • 讨论优化哈夫曼编码的数据压缩技术及C语言程序实现,并与静态哈夫曼编码方法进行比较,给出部分压缩率实例.
  • 利用优先级队列+DFS优化的哈夫曼编码译码器,可进行中文压缩,最高压缩率可达到1:3
  • 哈夫曼编码实现文件压缩和结压缩的C语言,程序,江湖救急 读一原来文本文件 能压缩生成一压缩文件 能计算出压缩率 删除原文本文件后,能用压缩文件还原出文本文件</p>
  • 哈夫曼编码—数据压缩与解压(Java) 博客说明 文章所涉及的资料来自互联网整理和个人总结,意在于...其压缩率通常在20%~90%之间 赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,称之为最

    哈夫曼编码—数据压缩与解压(Java)

    博客说明

    文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢!

    介绍

    • 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法
    • 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
    • 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%~90%之间
    • 赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,称之为最佳编码

    通信领域中信息的处理方式

    定长编码

    数据传输太长

    i like like like java do you like a java       // 共40个字符(包括空格)  
    
    105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97  //对应Ascii码
    
    01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001 //对应的二进制
    变长编码

    存在多义性

    i like like like java do you like a java       // 共40个字符(包括空格)
    
    d:1 y:1 u:1 j:2  v:2  o:2  l:4  k:4  e:4 i:5  a:5   :9  // 各个字符对应的个数
    0=  ,  1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d
    说明:按照各个字符出现的次数进行编码,原则是出现次数越多的,则编码越小,比如 空格出现了9 次, 编码为0 ,其它依次类推.
    
    按照上面给各个字符规定的编码,则我们在传输  "i like like like java do you like a java" 数据时,编码就是 10010110100...  
    
    哈夫曼编码(前缀编码)
    i like like like java do you like a java       // 共40个字符(包括空格)
    
    d:1 y:1 u:1 j:2  v:2  o:2  l:4  k:4  e:4 i:5  a:5   :9  // 各个字符对应的个数
    按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值
    
    //根据赫夫曼树,给各个字符
    //规定编码 , 向左的路径为0
    //向右的路径为1 , 编码如下:
    
    o: 1000   u: 10010  d: 100110  y: 100111  i: 101
    a : 110     k: 1110    e: 1111       j: 0000       v: 0001
    l: 001          : 01
    
    
    按照上面的赫夫曼编码,我们的"i like like like java do you like a java"   字符串对应的编码为 (注意这里我们使用的无损压缩)
    
    1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110
    
    
    长度为 : 133 
    说明:
    原来长度是  359 , 压缩了  (359-133) / 359 = 62.9%
    此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性
    

    注意

    这个哈夫曼树根据排序方法不同,也可能不太一样,这样对应的赫夫曼编码也不完全一样,但是wpl 是一样的,都是最小的

    压缩思路

    • 首先将字符串转化为字节数组
    • 创建哈夫曼树,将值和权重写入
    • 根据叶子结点的权重来计算哈夫曼编码表
    • 根据哈夫曼编码表来计算哈夫曼编码
    • 最后再转化为字节数组

    代码

    package cn.guizimo.huffmancode;
    
    import java.util.*;
    
    /**
     * @author guizimo
     * @date 2020/8/8 11:55 上午
     */
    public class HuffmanCode {
        public static void main(String[] args) {
            String content = "i like like like java do you like a java";
            byte[] contentBytes = content.getBytes();
    
            //哈夫曼编码
            byte[] zip = huffmanZip(contentBytes);
            System.out.println("哈夫曼编码:" + Arrays.toString(zip));
        }
    
        private static byte[] huffmanZip(byte[] bytes){
            List<Node> nodes = getNodes(bytes);
            //哈夫曼树
            Node huffmanTree = createHuffmanTree(nodes);
            //哈夫曼编码表
            Map<Byte, String> huffmanCodes = getCodes(huffmanTree);
            //哈夫曼编码
            byte[] zip = zip(bytes, huffmanCodes);
            return zip;
        }
    
        //压缩
        private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
            StringBuilder stringBuilder = new StringBuilder();
            for (byte b : bytes) {
                stringBuilder.append(huffmanCodes.get(b));
            }
            int len;
            if (stringBuilder.length() % 8 == 0) {
                len = stringBuilder.length() / 8;
            } else {
                len = stringBuilder.length() / 8 + 1;
            }
            byte[] by = new byte[len];
            int index = 0;
            for (int i = 0; i < stringBuilder.length(); i += 8) {
                String strByte;
                if (i + 8 > stringBuilder.length()) {
                    strByte = stringBuilder.substring(i);
                    by[index] = (byte) Integer.parseInt(strByte, 2);
                    index++;
                } else {
                    strByte = stringBuilder.substring(i, i + 8);
                    by[index] = (byte) Integer.parseInt(strByte, 2);
                    index++;
                }
            }
            return by;
        }
    
        static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();
        static StringBuilder stringBuilder = new StringBuilder();
    
        //重载
        private static Map<Byte, String> getCodes(Node root) {
            if (root == null) {
                return null;
            }
            getCodes(root.left, "0", stringBuilder);
            getCodes(root.right, "1", stringBuilder);
            return huffmanCodes;
        }
    
        //获取哈夫曼编码
        private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
            StringBuilder builder = new StringBuilder(stringBuilder);
            builder.append(code);
            if (node != null) {
                if (node.data == null) {  //递归
                    getCodes(node.left, "0", builder);
                    getCodes(node.right, "1", builder);
                } else {
                    huffmanCodes.put(node.data, builder.toString());
                }
            }
        }
    
        //前序遍历
        private static void preOrder(Node root) {
            if (root != null) {
                root.preOrder();
            } else {
                System.out.println("哈夫曼树为空");
            }
        }
    
        //生成哈夫曼树
        private static Node createHuffmanTree(List<Node> nodes) {
            while (nodes.size() > 1) {
                Collections.sort(nodes);
    
                Node leftNode = nodes.get(0);
                Node rightNode = nodes.get(1);
    
                Node parent = new Node(null, leftNode.weight + rightNode.weight);
                parent.left = leftNode;
                parent.right = rightNode;
    
                nodes.remove(leftNode);
                nodes.remove(rightNode);
                nodes.add(parent);
            }
            return nodes.get(0);
        }
    
        //接收字节数组
        private static List<Node> getNodes(byte[] bytes) {
            List<Node> nodes = new ArrayList<>();
            Map<Byte, Integer> counts = new HashMap<>();
            for (byte b : bytes) {
                Integer count = counts.get(b);
                if (count == null) {
                    counts.put(b, 1);
                } else {
                    counts.put(b, count + 1);
                }
            }
            //遍历map
            for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
                nodes.add(new Node(entry.getKey(), entry.getValue()));
            }
            return nodes;
        }
    }
    
    class Node implements Comparable<Node> {
        Byte data;
        int weight; //字符出现的次数
        Node left;
        Node right;
    
        //前序遍历
        public void preOrder() {
            System.out.println(this);
            if (this.left != null) {
                this.left.preOrder();
            }
            if (this.right != null) {
                this.right.preOrder();
            }
        }
    
        public Node(Byte data, int weight) {
            this.data = data;
            this.weight = weight;
        }
    
        @Override
        public int compareTo(Node o) {
            //从小到大排序
            return this.weight - o.weight;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", weight=" + weight +
                    '}';
        }
    }
    

    解压思路

    • 将字节数组转化为二进制
    • 根据反转的哈夫曼编码表生成ASCLL集合

    代码

    package cn.guizimo.huffmancode;
    
    import java.util.*;
    
    /**
     * @author guizimo
     * @date 2020/8/8 11:55 上午
     */
    public class HuffmanCode {
        public static void main(String[] args) {
            String content = "i like like like java do you like a java";
            byte[] contentBytes = content.getBytes();
    
            //哈夫曼压缩
            byte[] zip = huffmanZip(contentBytes);
            System.out.println("哈夫曼压缩:" + Arrays.toString(zip));
    
            //哈夫曼解压
            byte[] unzip = huffmanUnzip(huffmanCodes, zip);
            System.out.println("哈夫曼解压:" + new String(unzip));
        }
    
        //哈夫曼解压
        private static byte[] huffmanUnzip(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < huffmanBytes.length; i++) {
                byte b = huffmanBytes[i];
                boolean flag = (i == huffmanBytes.length - 1);
                stringBuilder.append(byteToBitString(!flag, b));
            }
    
            //解码,反向编码表
            HashMap<String, Byte> map = new HashMap<>();
            for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
                map.put(entry.getValue(), entry.getKey());
            }
    
            //根据编码扫描到对应的ASCLL码对应的字符
            List<Byte> list = new ArrayList<>();
            for (int i = 0; i < stringBuilder.length(); ) {
                int count = 1;
                boolean flag = true;
                Byte b = null;
                while (flag) {
                    String key = stringBuilder.substring(i, i + count);
                    b = map.get(key);
                    if (b == null) {
                        count++;
                    } else {
                        flag = false;
                    }
                }
                list.add(b);
                i += count;
            }
    
            byte b[] = new byte[list.size()];
            for (int i = 0; i < b.length; i++) {
                b[i] = list.get(i);
            }
            return b;
    
        }
    
        //转化二进制
        private static String byteToBitString(boolean flag, byte b) {
            int temp = b;
            if (flag) {
                temp |= 256;
            }
            String str = Integer.toBinaryString(temp);
            if (flag) {
                return str.substring(str.length() - 8);
            } else {
                return str;
            }
        }
    
    
        //哈夫曼编码压缩
        private static byte[] huffmanZip(byte[] bytes) {
            List<Node> nodes = getNodes(bytes);
            //哈夫曼树
            Node huffmanTree = createHuffmanTree(nodes);
            //哈夫曼编码表
            Map<Byte, String> huffmanCodes = getCodes(huffmanTree);
            //哈夫曼编码
            byte[] zip = zip(bytes, huffmanCodes);
            return zip;
        }
    
        //压缩
        private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
            StringBuilder stringBuilder = new StringBuilder();
            for (byte b : bytes) {
                stringBuilder.append(huffmanCodes.get(b));
            }
            int len;
            if (stringBuilder.length() % 8 == 0) {
                len = stringBuilder.length() / 8;
            } else {
                len = stringBuilder.length() / 8 + 1;
            }
            byte[] by = new byte[len];
            int index = 0;
            for (int i = 0; i < stringBuilder.length(); i += 8) {
                String strByte;
                if (i + 8 > stringBuilder.length()) {
                    strByte = stringBuilder.substring(i);
                    by[index] = (byte) Integer.parseInt(strByte, 2);
                    index++;
                } else {
                    strByte = stringBuilder.substring(i, i + 8);
                    by[index] = (byte) Integer.parseInt(strByte, 2);
                    index++;
                }
            }
            return by;
        }
    
        static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();
        static StringBuilder stringBuilder = new StringBuilder();
    
        //重载
        private static Map<Byte, String> getCodes(Node root) {
            if (root == null) {
                return null;
            }
            getCodes(root.left, "0", stringBuilder);
            getCodes(root.right, "1", stringBuilder);
            return huffmanCodes;
        }
    
        //获取哈夫曼编码
        private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
            StringBuilder builder = new StringBuilder(stringBuilder);
            builder.append(code);
            if (node != null) {
                if (node.data == null) {  //递归
                    getCodes(node.left, "0", builder);
                    getCodes(node.right, "1", builder);
                } else {
                    huffmanCodes.put(node.data, builder.toString());
                }
            }
        }
    
        //前序遍历
        private static void preOrder(Node root) {
            if (root != null) {
                root.preOrder();
            } else {
                System.out.println("哈夫曼树为空");
            }
        }
    
        //生成哈夫曼树
        private static Node createHuffmanTree(List<Node> nodes) {
            while (nodes.size() > 1) {
                Collections.sort(nodes);
    
                Node leftNode = nodes.get(0);
                Node rightNode = nodes.get(1);
    
                Node parent = new Node(null, leftNode.weight + rightNode.weight);
                parent.left = leftNode;
                parent.right = rightNode;
    
                nodes.remove(leftNode);
                nodes.remove(rightNode);
                nodes.add(parent);
            }
            return nodes.get(0);
        }
    
        //接收字节数组
        private static List<Node> getNodes(byte[] bytes) {
            List<Node> nodes = new ArrayList<>();
            Map<Byte, Integer> counts = new HashMap<>();
            for (byte b : bytes) {
                Integer count = counts.get(b);
                if (count == null) {
                    counts.put(b, 1);
                } else {
                    counts.put(b, count + 1);
                }
            }
            //遍历map
            for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
                nodes.add(new Node(entry.getKey(), entry.getValue()));
            }
            return nodes;
        }
    }
    
    class Node implements Comparable<Node> {
        Byte data;
        int weight; //字符出现的次数
        Node left;
        Node right;
    
        //前序遍历
        public void preOrder() {
            System.out.println(this);
            if (this.left != null) {
                this.left.preOrder();
            }
            if (this.right != null) {
                this.right.preOrder();
            }
        }
    
        public Node(Byte data, int weight) {
            this.data = data;
            this.weight = weight;
        }
    
        @Override
        public int compareTo(Node o) {
            //从小到大排序
            return this.weight - o.weight;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", weight=" + weight +
                    '}';
        }
    }
    

    测试

    image-20200808151105162

    感谢

    尚硅谷

    以及勤劳的自己

    展开全文
  • 哈夫曼编码

    千次阅读 2015-11-05 23:02:15
    数据结构实验之二叉树六:哈夫曼编码 Time Limit: 1000MS Memory limit: 65536K ...字符的编码方式有多种,除了大家熟悉的ASCII编码,哈夫曼编码(Huffman ...哈夫曼编码常被用于数据文件压缩中,其压缩率通常在
  • 文本: a b c a c a d b a c d...传统表示未压缩时: 0001100010001101001011001000001001001000 统计次数:a:9, b:5, c:4, d:2 前缀码表示:a: 0, b: 10, c:110, d:111 压缩后: 0101100110011110011011101000110100100
  • 压缩软件 源码 c++ 源码很简单,基于哈夫曼编码。一种理论上压缩率最高的基于统计的压缩算法
  • 哈夫曼编码与译码

    2020-11-24 11:10:47
    从文件中读入任意一篇...计算哈夫曼编码文件的压缩率; 将哈夫曼编码文件译码为文本文件,并与原文件进行比较。 利用堆结构,优化的哈夫曼编码算法 #include<stdio.h> #include<stdlib.h> #define MAXLE.
  • 哈夫曼编码 POJ 1521

    2020-07-18 11:08:50
    哈夫曼编码习题——POJ 1521哈夫曼编码原理题目理解实现 ...输出: ascii编码所需2进制长度 哈夫曼编码后长度 压缩率(前者除以后者),遇到END终结。 解题思路: 重点在哈夫曼树的实现。 实现 讲真,这
  • 哈夫曼编码C++实现

    2018-03-25 21:23:39
    哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方式,其压缩率通常在20%—90%之间。哈夫曼编码算法是通过使用字符在文件中出现的频率表来构造最优前缀码的贪心算法。所谓前缀码,即是任一字符的编码都不是其他...
  • 利用赫夫曼编码进行通信可以大大提高信道利用,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传输数据预先编码,在接收端将传送来的数据进行译码
  • 实验报告 实验课名称数据结构实验 实验名称文件压缩问题 班级20132012 学号 姓名 时间2015-6-9 一问题描述 哈夫曼编码是一种常用的数据压缩技术对数据文件进行哈夫曼编码可 大大缩短文件的传输长度提高信道利用及...
  • 实验报告 实验课名称数据结构实验 实验名称:文件压缩问题 班级203212 学号: 姓名 时间2015 一问题描述 哈夫曼编码就是一种常用得数据压缩技术,对数据文件进行哈夫曼编码可大大缩短文件得传输长度,提高信道利用及...
  • Huffman Coding:是哈夫曼树在电讯通信领域的经典应用,被用于数据文件压缩,其压缩率在20%-90%之间,是可变字长编码(VLC)的一种,属于无损压缩; 固定长度编码:使用固定长度的符号编码,如使用8位二进制数进行...
  • 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%~90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。资源为哈夫曼编码可执行文件
  • 哈夫曼编码/译码器

    2021-02-16 17:47:35
    (1)读取一个待压缩的文本文件SourceTextFile.txt,统计文本文件中各字符的个数作为权值,生成哈夫曼树,并将对应的哈夫曼编码存入文件HFMCodeFile.txt和打印到屏幕上; (2)编码(Encoding)。利用所得哈夫曼编码...
  • 哈夫曼编码 介绍 哈夫曼树(HuffManTree)是用来压缩数据的一种数据结构,它适合压缩数据重复较高的情况。 文本A:123456789,这串文本重复为0,因为每个字符都是唯一的,没有重复而言; 文本B:111222334,这...
  • 哈夫曼树、哈夫曼编码与译码实现(c语言)

    千次阅读 多人点赞 2019-12-27 17:18:26
    注:因为当时时间有限,故其实该代码还有优化空间,且输出文件是0/1字符串文本(UTF-8)并不是ASCII码编码文件,计算压缩率除以8即可。 实验项目:哈夫曼编码与译码方法 哈夫曼编码是一种以哈夫曼树(最优二叉树,...
  • 哈夫曼编码和算数编码都属于熵编码,仔细分析它们的原理,这两种编码是十分类似的,但也有微妙的不同之处,这也导致算数编码的压缩率通常比哈夫曼编码略高,这些我们都会加以探讨。 不过我们首先要了解什么是熵编码...
  • 哈夫曼树中压缩率到底是什么意思

    千次阅读 2020-12-12 23:09:35
    哈夫曼树中压缩率到底是什么意思 编码的含义 编码就是将一系列个体赋予一个能唯一标识的信息标志,这个标志可以简单的是一个编号,或者更复杂的约定好的其他数据结构。目的就是将电脑不能用0、1表示的物体(声音、...
  • 贪心算法-03哈夫曼编码问题

    千次阅读 2019-04-16 21:35:11
    哈夫曼编码是一种字符编码方式,可以对指定的字符集进行数据压缩,压缩率在20%到90%。 问题描述 现在有一个包含5个字符{A,B,C,D,E},各个字符的出现频率依次为{0.35, 0.1, 0.2, 0.2, 0.15}。需要构造一种有效的...
  • 如果采取标准的语料库进行编码,一般可以得到比较满意的编码结果(对不同文件产生不同压缩率的折中方法)。 本文采取对单独一个文件进行编码的方式来演示此压缩算法的使用。 分为下面几个步骤: 1.统计词频数据 ...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 207
精华内容 82
关键字:

哈夫曼编码压缩率