精华内容
下载资源
问答
  • 文章目录使用哈夫曼编码进行压缩文本文本内容读取文件内容至内存中遍历文本内容,获取每个字符对应出现概率值建立哈夫曼树获取哈夫曼编码将转换后编码写入新文件检测压缩率利用编码文件进行还原文本完整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;
    }
    
    

    附上运行结果图片:

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

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

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

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

    展开全文
  • 哈夫曼树中压缩率到底是什么意思

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

    哈夫曼树中压缩率到底是什么意思

    1. 编码的含义
      编码就是将一系列个体赋予一个能唯一标识的信息标志,这个标志可以简单的是一个编号,或者更复杂的约定好的其他数据结构。目的就是将电脑不能用0、1表示的物体(声音、视频、模式类别等),变成最终能用0/1编码来唯一标识的“码”。正因为有相互对应的特性,因而可以进行译码这样的逆操作。

    2. 哈夫曼树对应着一种编码方式,叫哈夫曼编码。被编码的对象,是一组有出现频率这个属性的对象。这种编码方式能够赋予出现频率值更大的对象更短的编码。同时任何一个编码不会是另一个编码的前缀(编译原理术语)。

    3. 假设有n种对象,且知道各自的出现频率,所谓压缩率是指
      =1n×n× logn. 压缩率 = \frac{\sum_1^n每种对象出现频率×哈夫曼编码码长 }{n×\left \lceil \ logn \right \rceil }.

    展开全文
  • 利用优先级队列+DFS优化的哈夫曼编码译码器,可进行中文压缩,最高压缩率可达到1:3
  • 利用哈夫曼编码压缩文件

    千次阅读 2017-09-05 17:54:48
    大作业报告  1. 简介/介绍/引言 本大作业主要考核如何以C实现集成电路测试向量文件的无损压缩。在通常的文件存储中,无论是二进制格式的文件还是...为了理解定长编码与变长编码的区别,假设某个文件纯粹由abcdef共

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

    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;
    }
    

     

     

    展开全文
  • 哈夫曼编码—数据压缩与解压(Java) 博客说明 文章所涉及资料来自互联网整理和个人总结,意在于...其压缩率通常在20%~90%之间 赫夫曼码是可变字长编码(VLC)一种。Huffman于1952年提出一种编码方法,称之为最
  • 哈夫曼编码

    千次阅读 2015-11-05 23:02:15
    数据结构实验之二叉树六:哈夫曼编码 Time Limit: 1000MS Memory limit: 65536K ...字符编码方式有多种,除了大家熟悉ASCII编码,哈夫曼编码(Huffman ...哈夫曼编码常被用于数据文件压缩中,其压缩率通常在
  • 哈夫曼编码和算数编码都属于熵编码,仔细分析它们的原理,这两种编码是十分类似的,但也有微妙的不同之处,这也导致算数编码的压缩率通常比哈夫曼编码略高,这些我们都会加以探讨。 不过我们首先要了解什么是熵编码...
  • 哈夫曼编码与译码

    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 一问题描述 哈夫曼编码是一种常用数据压缩技术对数据文件进行哈夫曼编码可 大大缩短文件传输长度提高信道利用及...
  • Huffman Coding:是哈夫曼树在电讯通信领域经典应用,被用于数据文件压缩,其压缩率在20%-90%之间,是可变字长编码(VLC)一种,属于无损压缩; 固定长度编码:使用固定长度符号编码,如使用8位二进制数进行...
  • 实现哈夫曼压缩, 计算原图和压缩以后尺寸,计算压缩率并比较分析 结果???? Matlab代码???? clear; clear all; A=imread('01.jpg'); I=rgb2gray(A); [M,N] = size(I); I1 = I(:); P = zeros(1,256); ...
  • 1、哈夫曼编码(Huffman Coding),又称霍夫曼编码,是Huffman于1952年提出一种编码方式,可变字长编码(VLC)一种。霍夫曼编码不仅会考察文本中有多少个不同字符,还会考察每个字符出现频率,根据频率不同,...
  • 哈夫曼编码/译码器

    2021-02-16 17:47:35
    (1)读取一个待压缩的文本文件SourceTextFile.txt,统计文本文件中各字符个数作为权值,生成哈夫曼树,并将对应的哈夫曼编码存入文件HFMCodeFile.txt和打印到屏幕上; (2)编码(Encoding)。利用所得哈夫曼编码...
  • 注:因为当时时间有限,故其实该代码还有优化空间,且输出文件是0/1字符串文本(UTF-8)并不是ASCII码编码文件,计算压缩率除以8即可。 实验项目:哈夫曼编码与译码方法 哈夫曼编码是一种以哈夫曼树(最优二叉树,...
  • 贪心算法-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}。需要构造一种有效...
  • 哈夫曼编码 介绍 哈夫曼树(HuffManTree)是用来压缩数据一种数据结构,它适合压缩数据重复较高情况。 文本A:123456789,这串文本重复为0,因为每个字符都是唯一,没有重复而言; 文本B:111222334,这...
  • 哈夫曼树是可变字长编码(VLC)一种,广泛应用于数据文件压缩,其压缩率通常在20%~90%之间。 1.通信领域信息处理方式1----定长编码 以上一段英文包括空格共有40个字符,它们对应Ascii码如下: 再将这些...
  • 今天和大家一起讨论Haffman编码,哈夫曼编码是基于哈夫曼树,也可以被称为最有二叉树,哈夫曼编码可以有效的压缩数据,通常可以节省20%~90%,具体的压缩率依赖于数据的特性。首先给大家介绍一下什么是最优二叉树;...
  • 0023 算法笔记贪心算法哈夫曼编码问题 1 问题描述 哈夫曼编码是广泛地用于数据文件压缩十分有效编码方法 其 压缩率通常在 20% 90% 之间哈夫曼编码 算法 用字符在文件中出现 频率表来建立一个用 0 1 串表示各...
  • 数据结构实验之二叉树六:哈夫曼编码数据结构实验之二叉树六:哈夫曼编码 数据结构实验之二叉树六:哈夫曼编码 Problem Description ...哈夫曼编码常被用于数据文件压缩中,其压缩率通常在20...
  • 文本: 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

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 173
精华内容 69
关键字:

哈夫曼编码的压缩率