精华内容
下载资源
问答
  • 使用哈夫曼编码统计字符的频率作为权值来实现压缩技术 ,包括哈夫曼树的创建,构造哈夫曼编码,使用哈夫曼编码压缩文件,和解压文件
  • 哈夫曼编码压缩.rar

    2019-12-13 10:34:30
    哈夫曼编码实训,通过构建哈夫曼树及哈夫曼编码,实现无损压缩压缩,内含完整注释,代码简便容易理解(100%运行成功+代码+简单窗口美化)~~~仅供学习交流,请勿他用!!
  • 专业实践,使用哈夫曼编码进行压缩解压
  • 利用哈夫曼编码压缩文本

    千次阅读 多人点赞 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++和MFC的哈夫曼编码压缩软件的实现
  • 运用哈夫曼编码压缩解压文件源代码,代码有详细的注释,很好的压缩解压的源代码
  • 哈夫曼编码压缩与解压软件介绍及资料简介: 完全免费压缩哈夫曼二叉树堆栈 xp、vc6环境软件 包括:源代码,《哈夫曼编码压缩与解压软件介绍及资料简介.txt》 全部来源于网络,分享于网络,谢谢各个资料的原作者。
  • 数据结构大作业——哈夫曼编码压缩BMP格式文件

    千次阅读 多人点赞 2020-04-17 10:21:06
    数据结构大作业——哈夫曼编码压缩BMP格式文件 首先需要了解BMP图像格式 BMP图像格式详解 其次需要了解哈夫曼编码如何对BMP文件进行压缩 哈夫曼压缩与解压缩 编程部分 从BMP文件中读取需要的内容 首先是自定义图像...

    数据结构大作业——哈夫曼编码压缩BMP格式文件

    首先需要了解BMP图像格式

    BMP图像格式详解

    其次需要了解哈夫曼编码如何对BMP文件进行压缩

    哈夫曼压缩与解压缩

    编程部分

    使用的头文件

    虽然这里用了using namespace std;,实际上C语言更多一点,只是为了使用类似于Python的字符串变量的加和功能(C语言本身的字符串拼接很多功能自己不熟练……

    #include <stdio.h>
    #include <windows.h>
    #include <string> 
    #include <bitset>
    
    using namespace std;
    

    从BMP文件中读取需要的内容

    首先是自定义图像文件头结构:
    需要BMP图像文件的文件头数据、信息头数据、BMP调色板数据(RGB)

    struct BMPHeader {
        BITMAPFILEHEADER BF;   		//文件头
        BITMAPINFOHEADER BI;		//信息头
        int rgb[256];				//BMP调色板
    };
    

    需要知道的数据有:
    图像的大小:
    图像的高度(以像素为单位)——biHeight
    图像的宽度(以像素为单位)——biWidth
    像素点占位数(以比特位/像素位单位)——biBitCount

    读取BMP图片文件

    int ReadBMP(string filename, BMPHeader & ih, unsigned char ** & data) 
    {
        FILE * fp;
        fp = fopen(filename.c_str(), "rb");
        if (fp == NULL) {
            return 0;
        } 
    //为所需信息赋值:
        fread(&ih.BF, sizeof(BITMAPFILEHEADER), 1, fp);			//如果没有读取头文件会导致 biBitCount直接成为40—— 位图信息头大小(40byte) 
        fread(&ih.BI, sizeof(BITMAPINFOHEADER), 1, fp);
        fread(&ih.rgb, sizeof(int), 256, fp);
    //只能打开256色位BMP图像:
        if (ih.BI.biBitCount != 8) {
            printf("文件打开失败,请选择正确文件格式!\n");
            return 0;
        }
    
        data = new unsigned char*[ih.BI.biHeight];
        int row_width = ih.BI.biWidth + (4 - ih.BI.biWidth % 4);
        for (int i = 0; i < ih.BI.biHeight; i++) {
            data[i] = new unsigned char[ih.BI.biWidth];
        }
        for (int i = 0; i < ih.BI.biHeight; i++) {
            for (int j = 0; j < ih.BI.biWidth; j++) {
                fread(&data[i][j], 1, 1, fp);//data赋值——将位图中每一个像素点的信息提取保存起来,作为数据的一部分。
            }
            if (ih.BI.biWidth % 4 > 0) {//偏移量定位
                fseek(fp, 4 - ih.BI.biWidth % 4, SEEK_CUR);
            }
        }
        fclose(fp);
        return 1;
    }
    

    使用BMP中的数据创建哈夫曼树并生成哈夫曼编码

    首先创建树节点:

    typedef struct node {
        int weight;					//权重
        int left;					//左子树
        int right;					//右子树
        int inrange;				//是否在检索范围内(接下来会解释)
    } HFTNode;
    
    

    生成哈夫曼树

    int CreateHFTree(HFTNode* HFTNodes, int* weights) {
        for (int i = 0; i < 256; i++) {
            HFTNodes[i].left =HFTNodes[i].right = -1;
            HFTNodes[i].weight = weights[i];
            HFTNodes[i].inrange = 0;
        }//结点初始化
        int range = 256;//初始化搜索范围:前256个叶子结点
    
        while (1) {		//循环构树
            int lc = SelectMinW(HFTNodes, range);	//寻找构树节点
            if (lc == -1) {		//说明到达了根结点处,哈夫曼树已经构建完毕
                break;
            }
            int rc = SelectMinW(HFTNodes, range);
            if (rc == -1) {
                break;
            }
            HFTNodes[range].left = lc;
            HFTNodes[range].right = rc;
            HFTNodes[range].weight = HFTNodes[lc].weight + HFTNodes[rc].weight;					//将左右子树的权值赋予根节点,该节点代替左右子树加入搜索范围进行下一轮搜索
            HFTNodes[range].inrange = 0;//边缘结点加入搜索
            range++;
            //很容易理解:每一轮循环将一个新的结点加入森林,而这个结点的编号恰好是range,搜索范围需要加1
        }
        return range;	//改点返回根结点的标号,用于确定后续过程的循环用条件
    }
    

    使用的另一个功能是针对该类型的选择函数:

    int SelectMinW(HFTNode* HFTNodes, int range) {
        int node = -1;
        for (int i = 0; i < range; i++) {		//只在范围内寻找
    	if(!HFTNodes[i].inrange&&HFTNodes[i].weight > 0)//判断是否在搜索范围以内(去除了权重为0的结点,因为用不到)
        	if (node == -1 || HFTNodes[i].weight < HFTNodes[node].weight)//判断是否是根节点或者是否满足较小条件
          	 	{node = i;}
            }
        //得到最小值的序号了!
        if (node != -1) {
            HFTNodes[node].inrange = 1;//把这个结点排出搜索范围之中
        }
        return node;//返回该较小值的序号
    }
    

    创建哈夫曼编码结构:

    由哈夫曼树构造哈夫曼编码:(从叶子结点到根节点)

    typedef struct
    {
    	int weight;		//权重
    	int parent;		//双亲结点
    	int lc;		//左孩子结点
    	int rc;		//右孩子结点
    } HFNode;
    
    typedef struct
    {
    	char cd[N];		//存放哈夫曼码
    	int start;
    } HCode;
    
    void CreateHCode(HFNode* HFNodes,HCode* hcode,int range)	//由哈夫曼树HFNodes构造哈夫曼编码hcode
    {
    	int i,f,c;
    	HCode hc;
    	for (i=0;i<range;i++)	//根据哈夫曼树构造所有叶子结点的哈夫曼编码
    	{
    		hc.start=range;c=i;
    		f=HFNodes[i].parent;
    		while (f!=-1)	//循环直到树根结点
    		{
    			if (HFNodes[f].lc==c)	//处理左孩子结点
    				hc.cd[hc.start--]='0';
    			else					//处理右孩子结点
    				hc.cd[hc.start--]='1';
    			c=f;f=HFNodes[f].parent;		//找到双亲结点向上查找
    		}
    		hc.start++;		//start指向哈夫曼编码最开始字符
    		hcode[i]=hc;		//由于并不需要记录中间结点,只对叶子结点进行处理
    	}
    }
    

    递归生成哈夫曼编码:(从根结点到叶子结点)

    void CHFTCode(HFTNode* HFTNodes, int pos, string bits, string * Code) {
    
    /********************函数初始条件********************/
        int l = HFTNodes[pos].left;
        int r = HFTNodes[pos].right;
        
    /********************递归终止条件********************/
        if (HFTNodes[pos].left == -1 && HFTNodes[pos].right == -1) {//左右孩子均为空->已经是叶子结点了,编码已经可以结束了
            Code[pos] = bits;			//赋值哈夫曼编码! 
            return;
        }
    
    /********************递归嵌套语句********************/
        CHFTCode(HFTNodes, r, bits + "1", Code);//将函数推向右孩子
        CHFTCode(HFTNodes, l, bits + "0", Code);//将函数推向左孩子
        //递归过程中哈夫曼编码的“前缀”得以保留。
    }
    

    这里的Code实际上是一个字符串数组,将每一结点的哈夫曼编码转化为一串字符串(仅看叶子结点:Code[i]=HCode[i].cd)。

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

    void HuffmanEncode(unsigned char * data[], int height, int width, const char *filename) 
    {
        int weights[256];						//256种点的权重
        memset(weights, 0, sizeof(int) * 256);	//初始化
        for (int i = 0; i < height; i++) 
    	{
            for (int j = 0; j < width; j++) 
    		{
                weights[data[i][j]]++;			//循环求每一种点的权重
            }
        }
    
        HFTNode HFTNodes[256 * 2-1];			//开辟需要的节点个数(哈夫曼树最多需要如此多个结点)
         string Code[256];						//为每一个叶子结点开辟哈夫曼编码空间
         
        int range = CreateHFTree(HFTNodes, weights);	
    											//返回根点值——确定查找范围
    
        CHFTCode(HFTNodes, range - 1, "", Code);
    
    											//开辟缓冲区
        int BuffLength = 0;
        for (int i = 0; i < 256; i++) {
            BuffLength += weights[i] * Code[i].size();
    											//计算所有哈夫曼编码的总长度以确定缓冲区的大小
        }
        char * Buff = new char[BuffLength];
        
       	//将压缩后的文件读入“缓冲区”——这个意义不严格
        int cur = 0;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                for (int k = 0; k < Code[data[i][j]].size(); k++) {
                    Buff[cur] = Code[data[i][j]][k];		//data的数据是像素点的信息
                    cur++;
                }
            }
        }
        //生成新的压缩文件 
        FILE* fp;
        fp = fopen(filename, "wb");			//新建文件,二进制写入
        int times = BuffLength / 32 + 1;	//int——>32位
        string total = "";
        total = total + Buff;				//一次性写入数据区
        for (int i = 0; i < 32 * times - BuffLength; i++) {
            total = total + "0";			//尾缀“000000000”——>存在不足现象——哈夫曼编码长度不确定
            								//在解压缩的时候每一个像素点对应的哈夫曼编码实际是确定的
            								//尾缀生成的像素可以在解压缩图的像素矩阵中排除
        }
        fwrite(&BuffLength, sizeof(int), 1, fp); //写数据的长度
        for (int i = 0; i < times; i++) 
    	{
            bitset<32> byte(total.substr(32 * i, 32));
    					//每次取total的32位,并以i为计数器向后推移
            unsigned long tmp = byte.to_ulong();
            fwrite(&tmp, sizeof(int), 1, fp);
            			//写入,写入……
        }
        fclose(fp);
    }
    

    生成新的文件

    int main() 
    {
    	//初始化 
        char readpath[50];
        printf("请输入BMP文件名(全英、不带文件类型后缀):");
        scanf("%s", readpath);
        unsigned char ** data;				//老二维数组了
    	//读取文件信息 
    	//char path1[]="";
        //strcat(path1, readpath);
    	//strcat(path1, ".bmp");//文件名的拼接
    	string path1 = "";
        path1 = path1 + readpath + ".bmp";
    	BMPHeader ih;
        if (ReadBMP(path1, ih, data)) {
            printf("图片 %s 读取成功.\n", readpath);
        } else {
            printf("图片 %s 读取失败.\n", readpath);
            return 0;
        }
    	//生成压缩后的哈夫曼文件
        string path2="";
        path2 = path2 + readpath + ".bmp.huf";
        HuffmanEncode(data, ih.BI.biHeight, ih.BI.biWidth, path2.c_str());
        printf("文件压缩成功.\n");
    }
    

    验证部分

    对压缩文件进行解压,并将得到的数据重新生成BMP文件

    展开全文
  • 本文采用哈夫曼编码的方式进行文件(文本文件)压缩和解压缩,首先介绍项目的整体思路:哈夫曼编码压缩文件实际就是统计出文件中各个字符出现的频率,然后为每个字符生成对应的编码,然后将每个字符用哈夫曼编码的...

             本文采用哈夫曼编码的方式进行文件(文本文件)压缩和解压缩,首先介绍项目的整体思路:哈夫曼编码压缩文件实际就是统计出文件中各个字符出现的频率,然后为每个字符生成对应的编码,然后将每个字符用哈夫曼编码的形式按字节保存在压缩文件中。而文件的解压缩实际上就是将压缩文件翻译过来保存到解压缩文件中,需要使用压缩过程中生成的配置文件配合完成。下面将具体介绍文件的压缩和解压缩步骤:

           文件的压缩的核心是产生哈夫曼编码,而哈夫曼编码的过程中需要找到一系列数据中的最小权重和次小权重,我们自然联想到用堆这种结构时间复发度小并且很方便找到最小值和次小值,我将堆的源代码放在Heap.h文件中(见下文)。现在我们进行文件压缩。

           1。统计文件中所有字符的出现次数。由于Ascall码字符一共255个,只有前128个字符可以显示,定义字符变量时一定要定义成无符号型变量unsigned char ch如下,这是ch读不到文件的结束标志,所以我们可以用函数feof来代替文件的结束标志EOF,最重要的是文件的打开方式一定要是二进制的形式打开否则读不到汉字字符,将出现乱码。关于存储方式我们采用哈希表的方式将每个字符映射为哈希表的下标,这样可以很方便的将每个字符和出现的次数对应起来。需要说明的是我们这个哈希表存的绝不是单纯的次数而是结点FileInfo,这个节点称为权重结点中保存出现次数和字符以及将来我们产生的哈夫曼编码,方便我门进行索引。

    bool Compress(const char *filename)//该函数起到统计的作用
    {
    FILE *fout = fopen(filename, "rb");//以二进制形式打开文件
    assert(fout);
    unsigned char ch = fgetc(fout);
    while (!feof(fout))
    {
    _Infos[ch]._count++;//统计各种字符在文件中的个数
    ch = fgetc(fout);
    COUNT++;//统计文件中总的字符个数
    }
    fclose(fout);
    return true;
    }

         2。现在我们创建一个最小堆,将统计到的结点压入堆中

         3。从堆中取数据在HuffMan.h头文件中建立哈夫曼树

         4。通过哈夫曼树产生哈夫曼编码存入节点中

         5。遍历待压缩文件将对应的哈夫曼编码按字节保存到压缩文件中

         6.将每个字符出现的个数保存到配置文件中。由步骤5产生的压缩文件,当我们遍历到文件的最后一个字符时,如果编码凑不成8      一个字节我们给剩下的位置补0,为了解决最后一个字符的解析问题,我们将待压缩文件中的总的字符个数统计出来存到配置文       件的第一行,以后每行一“X,n”的形式存放字符和对应的出现次数。这样我们的文件压缩过程就完成了。


         文件的解压缩思路简单,但是要尤其注意细节读配置文件就要花些心思,体现在换行符的统计上,下面进行文件的解压缩(源文件见Uncompress.h):

          1。读配置文件

          2。通过配置文件重构哈夫曼树

          3。开始文件的解压缩,按字符读入编码通过编码在哈夫曼树种寻找对应的字符,并将字符存入到解压缩文件中去,通过配置文件中读入的COUNT来控制最后一个字符正确编码的起止。这样文件的解压缩完成。

    总结:

    项目的特点和用到的技术有,仿函数,堆,哈夫曼编码技术,string类,哈希表

    项目注意事项,文件名字转换方法艺术,文件的二进制读入写入,读配置文件时换行符的处理,以及统计的字符数如何以10进制字符的形式存到文件中去。其他问题详见源代码重点注释的地方。

    Heap.h

    #include <vector>
    
    
    template<class T>
    struct Less
    {
    	bool operator() (const T& l, const T& r)
    	{
    		return l < r; // operator<
    	}
    };
    
    template<class T>
    struct Greater
    {
    	bool operator() (const T& l, const T& r)
    	{
    		return l > r; // operator>
    	}
    };
    
    
    template<class T, class Compare=Less<T>>//哈夫曼结点的仿函数
    class Heap
    {
    public:
    	Heap()
    	{}
    	Heap(const T* a, size_t size)
    	{
    		for (size_t i = 0; i < size; ++i)
    		{
    			_arrays.push_back(a[i]);//将所有数据插入堆
    		}
    
    		// 建堆
    		for (int i = (_arrays.size() - 2) / 2; i >= 0; --i)
    		{
    			AdjustDown(i);//对这个范围的每个节点都向下调整,建堆的过程实际就是向下调整堆的过程
    		}
    	}
    
    	void Push(const T& x)
    	{
    		_arrays.push_back(x);
    		AdjustUp(_arrays.size() - 1);//插入节点的过程实际就是向上调整堆的过程
    	}
    
    	void Pop()
    	{
    		assert(_arrays.size() > 0);
    		swap(_arrays[0], _arrays[_arrays.size() - 1]);
    		_arrays.pop_back();
    
    		AdjustDown(0);
    	}
    
    	T& Top()
    	{
    		assert(_arrays.size() > 0);
    		return _arrays[0];
    	}
    
    	bool Empty()
    	{
    		return _arrays.empty();
    	}
    
    	size_t Size()
    	{
    		return _arrays.size();
    	}
    
    	void AdjustDown(int root)
    	{
    		int child = root * 2 + 1;
    
    		Compare com;
    		while (child < _arrays.size())
    		{
    			// 比较出左右孩子中小的那个
    			if (child + 1<_arrays.size() &&
    				com(_arrays[child + 1], _arrays[child]))
    			{
    				++child;
    			}
    
    			if (com(_arrays[child], _arrays[root]))
    			{
    				swap(_arrays[child], _arrays[root]);
    				root = child;
    				child = 2 * root + 1;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    
    	void AdjustUp(int child)
    	{
    		int parent = (child - 1) / 2;
    
    		while (child > 0)
    		{
    			if (Compare()(_arrays[child], _arrays[parent]))
    			{
    				swap(_arrays[parent], _arrays[child]);
    				child = parent;
    				parent = (child - 1) / 2;
    			}
    			else
    			{
    				break;
    			}
    		}
    	}
    
    	void Print()
    	{
    		for (size_t i = 0; i < _arrays.size(); ++i)
    		{
    			cout << _arrays[i] << " ";
    		}
    		cout << endl;
    	}
    
    public:
    	vector<T> _arrays;
    };
    
    //测试堆 
    //void Test1()
    //{
    //	int a[10] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 };
    //	Heap<int, Greater<int> > hp1(a, 10);
    //	hp1.Push(1);
    //	hp1.Print();
    //
    //	Heap<int> hp2(a, 10);
    //	hp2.Push(1);
    //	hp2.Print();
    //
    //
    //	Less<int> less;
    //	cout<<less(1, 2)<<endl;
    //
    //	Greater<int> greater;
    //	cout<<greater(1, 2)<<endl;
    //}
    
    HuffMan.h

    #pragma once
    
    #include "Heap.h"
    
    template<class T>
    struct HuffManNode
    {
    	HuffManNode<T> *_left;
    	HuffManNode<T> *_right;
    	HuffManNode<T> *_parent;
    	T _weight;
    	HuffManNode(const T&x)
    		: _left(NULL)
    		, _right(NULL)
    		, _parent(NULL)
    		, _weight(x)
    	{}
    };
    
    template<class T>
    class HuffMan
    {
    	typedef HuffManNode<T> Node;
    
    	template<class T>
    	struct NodeCompare
    	{
    		bool operator() ( const Node*l, const Node*r)//模板不能分离编译
    		//因此用到NodeCompare的地方都要放到一个文件
    		{
    			return l->_weight < r->_weight;
    		}
    	};
    
    protected:
    	Node* _root;
    
    public:
    	HuffMan()
    		:_root(NULL)
    	{}
    
    	~HuffMan()
    	{}
    
    public:
    	Node* GetRootNode()
    	{
    		return _root;
    	}
    
    	Node* CreatTree(T*a, size_t size,const T& invalid)
    	{
    		//取数转换成哈夫曼结点,放到最小堆中
    		assert(a);
    		Heap<Node*, NodeCompare<T>> minHeap;
    		for (size_t i = 0; i < size; ++i)
    		{
    			if (a[i] != invalid)
    			{
    				Node*node = new Node(a[i]);
    			    minHeap.Push(node);
    			}
    			
    		}
    		/*for (int i = 0; i<10; i++)
    		{
    			Node *temp = minHeap._arrays[i];//用于测试的代码
    			cout << temp->_weight << " ";
    		}*/
    		//从最小堆中取最小的和次小的结点,建立哈夫曼树
    		while (minHeap.Size()>1)
    		{
    			Node* left = minHeap.Top();//取最小的
    			minHeap.Pop();
    			Node* right = minHeap.Top();//取次小的
    			minHeap.Pop();
    			Node *parent = new Node(left->_weight + right->_weight);
    			parent->_left = left;
    			parent->_right = right;
    			left->_parent = parent;
    			right->_parent = parent;//链接节点间的关系
    
    			minHeap.Push(parent);//将最小的和次小的之和放到堆中重新调整
    		}
    		_root = minHeap.Top();//堆中最后剩下的结点就是哈夫曼的根结点
    		return _root;
    	}
    	
    	HuffManNode<T>* GetRoot()
    	{
    		return _root;
    	}
    	void PrintHuff()
    	{
    		Node *root = _root;
    		_Print(root);
    	}
    protected:
    	void _Print(Node *root)
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		else
    		{
    			cout << root->_weight;
    		}
    		_Print(root->_left);
    		_Print(root->_right);
    	}
    
    };
    
    //void TestHuff()
    //{
    //	int a[] = { 1, 0, 2, 3, 4, 5, 6, 7, 8, 9 };
    //	HuffMan<int> t;
    //	t.CreatTree(a, sizeof(a) / sizeof(int), -1);
    //
    //}
    filecompress.h

    # include<iostream>
    # include<cassert>
    # include<string>
    # include<algorithm>
    # include"HuffMan.h"
    using namespace std;
    typedef unsigned long long LongType;
    struct FileInfo
    {
      unsigned	char _ch;
      LongType  _count;
      string  _code;
      FileInfo(unsigned char ch=0)
    	  :_ch(ch)
    	  , _count(0)
      {}
     FileInfo operator+(FileInfo filein)
      {
    	 FileInfo temp;
    	 temp._count=_count + filein._count;
    	 return temp;
      }
     bool operator<( const FileInfo filein)const               
     {
    	 return _count < filein._count;
     }
     bool operator!=(const FileInfo  Invalid)const
     {
    	 return _count != Invalid._count;
     }
    };
    class FileCompress
    {
    protected:
    	FileInfo _Infos[256];
    	LongType COUNT = 0;
    public:
    	FileCompress()
    	{
    		for (int i = 0; i < 256;i++)
    		{
    			_Infos[i]._ch = i;
    		}
    	}
    	bool Compress(const char *filename)//该函数起到统计的作用
    	{
    		FILE *fout = fopen(filename, "rb");//以二进制形式打开文件
    		assert(fout);
    		unsigned char ch = fgetc(fout);
    		while (!feof(fout))
    		{
    			_Infos[ch]._count++;//统计各种字符在文件中的个数
    			ch = fgetc(fout);
    			COUNT++;//统计文件中总的字符个数
    		}
    		fclose(fout);
    		return true;
    	}
    	void GenerateHuffManCode()
    	{
    		HuffMan<FileInfo> t;
    		FileInfo invalid;
    		t.CreatTree(_Infos, 256, invalid);
    		HuffManNode<FileInfo>*root = t.GetRoot();
    		_GenrateHuffManCode(root);
    	}
    	void _GenrateHuffManCode(HuffManNode<FileInfo>* root)
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		_GenrateHuffManCode(root->_left);
    		_GenrateHuffManCode(root->_right);
    
    		if ((root->_left == NULL) && (root->_right == NULL))
    		{
    			HuffManNode<FileInfo>*cur = root;
    			HuffManNode<FileInfo>*parent = cur->_parent;
    			string &code = _Infos[cur->_weight._ch]._code;
    			while (parent)//从叶子节点走到根结点
    			{
    				if (parent->_left == cur)
    			
    					code += '0';		
    				else		
    					code += '1';	
    				cur = parent;
    				parent = cur->_parent;
    			}
    			reverse(code.begin(), code.end());
    		}		
    	}
    
    	//下面进行文件压缩
    	void CompressFile(const char *filename)
    	{
    		Compress(filename);
    		string compressFile = filename;
    		compressFile += ".huffman";
    		FILE *FinCompress = fopen(compressFile.c_str(), "wb");
    		assert(FinCompress);//对压缩文件的命名处理
    		
    		GenerateHuffManCode();//产生编码
    		FILE *fout = fopen(filename, "rb");
    		assert(fout);
    
    		//进行文件压缩
    		 unsigned char inch = 0;
    		int index = 0;
    		char ch = fgetc(fout);
    		while (ch!=EOF)
    		{
    			string&code = _Infos[(unsigned char)ch]._code;
    			for (int i = 0; i < code.size(); ++i)
    			{
    				++index;
    				inch <<= 1;
    				if (code[i] == '1')
    				{
    					inch |= 1;
    				}
    				if (index == 8)
    				{
    					fputc(inch, FinCompress);
    					index = 0;
    					inch = 0;
    				}		
    			}
    			ch = fgetc(fout);
    		}
    		if (index != 0)
    		{
    			inch <<= (8 - index);
    			fputc(inch,FinCompress);
    		}
    		fclose(fout);
    		FileInfo invalid;
    		CreateConfig(filename,invalid);
    	}
    	void CreateConfig( const char* filename,FileInfo invalid)
    	{
    		string ConfigFile = filename;
    		ConfigFile += ".config";
    		FILE *FileConfig = fopen(ConfigFile.c_str(), "wb");
    		assert(FileConfig);
    
    		char ch[256];
    		string tempcount;
    		int i = 0;
    		tempcount=	_itoa(COUNT, ch, 10);
    		while (i < tempcount.size())
    		{
    			fputc(tempcount[i],FileConfig);
    			i++;
    		}//将总的字符数写入配置文件
    		fputc('\n', FileConfig);
    		for (size_t i = 0; i < 256; i++)
    		{
    			if (_Infos[i] != invalid)
    			{
    				string chInfo;
    				chInfo.clear();
    
    				if (_Infos[i]._count>0)
    				{
    					chInfo += _Infos[i]._ch;
    					chInfo += ',';
    					char ch[256]; //转换成的字符可能足够长
    					_itoa(_Infos[i]._count,ch, 10);
    					chInfo += ch;
    					for (int j = 0; j < chInfo.size(); j++)
    					{
    						fputc(chInfo[j], FileConfig);
    					}
    								
    						fputc('\n', FileConfig);					
    				}
    			}
    		}
    		fclose(FileConfig);
    	}
    
    };
    void TestFileCompress()
    {
    	FileCompress FC;
    	FC.CompressFile("fin.txt");
    	cout << "压缩成功" << endl;
    }
    
    Uncompress.h



    # include<iostream>
    using namespace std;
    # include"HuffMan.h"
    # include"filecompress.h"
    
    class Uncompress
    {
    private:
    	FileInfo _UNinfos[256];
    	LongType Count;
    public:
    	Uncompress()//哈希表的初始化
    	{
    		for (int i = 0; i < 256; i++)
    		{
    			_UNinfos[i]._ch = i;
    		}
    		Count = 0;
    	}
    	bool _Uncompress(const char *Ufilename)//读配置文件
    	{
    		string Configfile = Ufilename;
    		Configfile += ".config";
    		FILE *fpConfig = fopen(Configfile.c_str(), "rb");
    		assert(fpConfig);
    
    		string line;
    	    unsigned char ch = fgetc(fpConfig);
    		while (ch != '\n')
    		{   
    			line += ch;
    			ch =fgetc(fpConfig);		
    		}//读取第一个字符
    		Count = atoi(line.substr(0).c_str());//(总的字符个数)
    		ch = fgetc(fpConfig);//读入下一行字符
    		line.clear();
    		int j = 0;
    		while (!feof(fpConfig))
    		{
    			
    			j++;
    			while (ch != '\n')
    			{
    				line += ch;
    				ch = fgetc(fpConfig);
    
    			}
    			if (line.empty())
    			{
    				line += '\n';
    				ch = fgetc(fpConfig);
    				while (ch != '\n')
    				{
    					line += ch;
    					ch = fgetc(fpConfig);
    				}
    			}
    			ch = fgetc(fpConfig);
    			unsigned char tempch = line[0];//将第一个字符转换成无符号数和下标对应起来
    			                               //尤其要注意这里稍微不注意就全乱码了  
    			_UNinfos[tempch]._count = atoi(line.substr(2).c_str());//截取字符串并转换成整型数据
    			line.clear();
    		}
    		return true;
    	}
    	void GenrateHuffManCode(HuffManNode<FileInfo>* root)//重构哈夫曼树
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		GenrateHuffManCode(root->_left);
    		GenrateHuffManCode(root->_right);
    
    		if ((root->_left == NULL) && (root->_right == NULL))
    		{
    			HuffManNode<FileInfo>*cur = root;
    			HuffManNode<FileInfo>*parent = cur->_parent;
    			string &code = _UNinfos[cur->_weight._ch]._code;
    			while (parent)//从叶子节点走到根结点
    			{
    				if (parent->_left == cur)
    
    					code += '0';
    				else
    					code += '1';
    				cur = parent;
    				parent = cur->_parent;
    			}
    			reverse(code.begin(), code.end());
    		}
    	}
    
    	bool UncomPress(const char *UNfilename)//文件的解压缩过程
    	{
    		_Uncompress(UNfilename);
    		HuffMan<FileInfo> Re_huffTree;
    		FileInfo invalid;
    		HuffManNode<FileInfo>*root = Re_huffTree.CreatTree(_UNinfos, 256, invalid);//重构哈夫曼树
    		GenrateHuffManCode(root);
    
    		//打开文件
    		string UnComPressFile = UNfilename;
    		UnComPressFile += ".Unhuffman";
    		FILE *UCPfile = fopen(UnComPressFile.c_str(), "wb");
    		string ComPressFile = UNfilename;
    		ComPressFile += ".huffman";
    		FILE *CPfile = fopen(ComPressFile.c_str(), "rb");
    
    		//解压缩字符写入文件
    
    
    		HuffManNode<FileInfo>*tempRoot = root;//获得其根结点
    		while (!feof(CPfile))
    		{
    			unsigned char ch = fgetc(CPfile);
    			int bitCount = 7;
    			for (int i = bitCount; i >= 0; i--)
    			{
    				if (ch&(1 << i))
    				{
    					tempRoot = tempRoot->_right;
    				}
    				else
    				{
    					tempRoot = tempRoot->_left;
    				}
    				if (!tempRoot->_left&&!tempRoot->_right)//做到这里
    				{
    					fputc(tempRoot->_weight._ch, UCPfile);
    					Count--;
    					tempRoot = root;
    				}
    				if (Count <= 0)
    				{
    					break;
    				}
    			}
    			if (Count <= 0)
    			{
    				break;
    			}
    		}
    		return true;
    	}
    
    };
    void TestUNCP()
    {
    	Uncompress Uncp;
    	Uncp.UncomPress("fin.txt");
    }




    展开全文
  • 草稿版代码 内容超详细 可压缩任何文件类型 本人亲测 但代码有些部分时间复杂度待优化
  • 【实习题目】 文本文件的哈夫曼编码压缩实现 【问题描述】哈夫曼编码是一种有效且可逆的编码方式。要求用哈夫曼编码方式实现对一个文本文件的压缩操作。 【基本要求】1) 要求程序同时具有哈夫曼编码压缩和解压的...

     

    【实习题目】
         文本文件的哈夫曼编码压缩实现
     
    【问题描述】
    哈夫曼编码是一种有效且可逆的编码方式。要求用哈夫曼编码方式实现对一个文本文件的压缩操作。
     
    【基本要求】
    1)      要求程序同时具有哈夫曼编码压缩和解压的功能模块。
    2)      压缩模块:统计源文件中各字符出现频率,建立哈夫曼树,通过哈夫曼树求得各字符的哈夫曼编码,最后将哈夫曼树的数据和编码数据写入压缩文件。
    3)      解压模块:从压缩文件中读取哈夫曼数据和编码后的数据,解码得到源文件。
     
    【需求分析】
    1)      考虑制作图形化界面。
    2)      保证有压缩效果。即,生成的压缩文件应该比源文件体积小。
    3)      解压缩后的文件应该与源文件完全一致。
    4)      最好保留程序调试功能以便于检查错误。
     
    【概要设计】
           (本实验程序使用Delphi 2005编写)
    设计程序界面如下:
    “选择文件”按钮:选择磁盘上的文件,用于压缩或解压;
    “压缩”按钮:对选定文件执行压缩操作;
        - 包括统计文件中字符出现频率、建立哈夫曼树、获取字符编码以及写入文件四个执行步骤。
    “解压”按钮:对选定文件执行解压操作;
        - 包括检查压缩文件合法性、从文件读取哈夫曼编码、写入解码文件三个步骤。
    “调试模式”复选框:让程序以调试模式运行;
    - 正常模式下,执行完压缩或解压操作后程序将自动退出;调试模式下不立即退出,可执行检查哈夫曼树、查看编码等操作。
    “退出”按钮:结束程序。
     
    主要数据结构为二叉链表表示的哈夫曼二叉树,辅助数据结构有用于求字符频率的线性表等。
     
    (1) 数据类型定义
     
    type
     HuffmanTree = ^HTNode;
     HTNode = record
        data: Integer;
        dataC: Char;
        lchild, rchild: HuffmanTree;
     end;
    // 二叉树。为了方便,字符型和整数型的数据域各设置了一个。
     
     HuffmanElem = record
        ch: Char;
        freq: Integer;
        code: string;
     end;
     HuffmanTableArr = Array of HuffmanElem;
     HuffmanTable = record
        data: HuffmanTableArr;
        top: SmallInt;
     end;
    // 线性表。top域用于表中元素个数,即叶节点个数。
    // 对每个元素而言,ch存放字符本身,freq存放字符在源文件中出现的频数,code存放其编码。
    // 程序刚开始时此表为空。执行求频数操作后得ch和freq域的值,编码结束后才能得code域的值。
     
     TZipForm = class(TForm)
        ...
    end;
             // TZipForm窗体类。为本程序运行的主窗体。具体定义略。
     
    (2) 压缩模块
     
        procedure enc_GetHuffmanFreq(F: TStrings; var H: HuffmanTable);
    // 求字符串表F中各字符的出现频数,录入线性表H各元素的freq域中。
    // 其中F从读入的文本文件中直接载入。
     
    procedure enc_HuffmanCoding(var H: HuffmanTable; var T: HuffmanTree);
        // 根据线性表H中已经求得的各字符出现频率,自下而上构建哈夫曼树T。
        // 哈夫曼树的具体构造方法参见教材相关章节,这里不再赘述。
        // 构建哈夫曼树T完成后,再利用此树进行深度优先搜索,获得各字符(叶节点)的哈夫曼编码。
     
        procedure enc_WriteToFile(HFMFileName: string);
        // 将哈夫曼树相关信息和编码后的文件数据写入以HFMFileName为文件名的文件中。
        // 输入的信息包含本程序所生成的压缩文件独有标识,以便于解码时检验文件合法性。
     
        procedure TZipForm.Button2Click(Sender: TObject);    // Compress
        // 主窗体上“压缩”按钮的单击事件。
        // 在此处执行输入合法性检验、文件覆盖确认等操作处理,并通过源文件名获取HFMFileName。
        // 若源文件名为abc.txt,则经处理之后得到HFMFileName为abc.hfm。
     
        (3) 解压模块
     
        procedure dec_DecodeHFMFile(HFMFileName: string; ExtractedFileName: string);
        // 将文件HFMFileName解码,将解码后的信息写入文件ExtractedFileName中。
        // 首先检查待解码文件中是否包含本程序所独有的标识。如有才能执行解码操作,否则提示错误。
        // 本过程主要包含读取待解码文件中的哈夫曼树和解开哈夫曼编码两步操作。
     
        (4) 编码文件格式
       
    - 默认文件后缀名为.hfm
        - 文件的前三个字节为’hfm’。用于检验此文件是否为合法生成的哈夫曼编码文件。
        - 接下来两个字节是一个ShortInt整数,记录源文件的字符数量(以下用n表示)。
    - 再以后是n组哈夫曼编码数据。每一组的构成为:原字符 + 编码长度 + 编码。其中编码每8位占据一个字节,多余位数用0填补。
    - 然后是编码内容正文。每8位以一个字节的方式存储。同样的,文件末端多余位数补0。
    - 文件的末尾一个字节为编码内容正文末端的补0数目。
     
    【细节说明】
    由于程序代码过长,这里不直接贴出源代码,仅将程序中一些细节上的实现作简单的解释如下:
     
    (1) 文件合法性校验
     
           点击压缩按钮或解压按钮时,会首先作文件合法性校验。
    根据待压缩/待解压的文件的文件名生成压缩/解压的文件名之后,要首先检查程序执行目录下是否已经存在此文件名的文件。如有,则弹出对话框询问是否覆盖。只有用户选择允许覆盖之后,程序才能继续运行。
     
        if FileExists(FileName) then
    if MessageDlg('文件 "' + FileName + '" 已经存在,覆盖吗?', mtConfirmation, [mbYes, mbNo], 0) = mrNo then
        Exit;
     
    此段代码表示:假使以FileName为名的文件存在,则弹出一个包含Yes/No按钮的对话框。如果用户选择No则取消当前的压缩或解压操作。
     
    对于解压模块而言,还需检验选择的待解压文件是否具有特定标识(即前三个字符为’hfm’),只有检验通过后,才能继续执行解压操作。
     
    FReadStream.ReadBuffer(Buffer, 3);
    if not ((Buffer[0] = 'h') and (Buffer[1] = 'f') and (Buffer[2] = 'm')) then
    begin
    ShowMessage('错误:此文件不是一个合法的hfm文件。');
    Halt;
    end;
     
    Buffer是一个字符数组。此段代码从输入流读入三个字符存入Buffer中。如果检查出这三个字符不是’hfm’,则提示错误并中断程序运行。
     
    (2) 输入输出的方法
     
    为了提高效率,故不能使用文本文件(TextFile)的读写类型,改用文件流类型(TFileStream)。文件流的读写方法分别为:
     
           procedure ReadBuffer(Buffer, Count: Integer);
           function Read(Buffer, Count: Integer): Integer;
           procedure WriteBuffer(Buffer, Count: Integer);
           function Write(Buffer, Count: Integer): Integer;
     
    其中,Buffer是未定义类型变量,通常使用字符数组(Array of Char)。Count则表示预计输入/输出的长度。函数Read和Write有返回值,其返回值为一个整数,表示实际输入/输出的字节数量。如果此返回值小于Count参数,则表示可能已经到达文件末尾。过程ReadBuffer和WriteBuffer则没有返回值。
    然而在压缩模块中读入待压缩的文本文件时,使用字符串列表TStrings仍然比较方便。TStrings类的基础是一个以字符串为元素构成的数组,可用其LoadFromFile方法直接从文本文件中以字符串的形式读入每一行,操作较为简便。
    虽然使用TString无法直接从字符串中读入回车符,但回车符的数量可由行数(TStrings的Count属性) 直接得到。
     
        有全局变量:
           var
    FileSS: TStringList;
    压缩模块刚开始执行时,用以下语句将输入文件(FileName为文件名)中的文本读入到字符串序列FileSS之中。
           FileSS := TStringList.Create;
           if FileExists(FileName) then
             FileSS.LoadFromFile(FileName);
     
    (3) 建立哈夫曼树的算法
     
    procedure enc_HuffmanCoding(var H: HuffmanTable; var T: HuffmanTree);
     
    type
     LeafArr = Array of HuffmanTree;
    // 记录叶节点的线性表类型
     
    var
     leaf: LeafArr;
     i, k, lc, rc: Integer;          
     p: HuffmanTree;
     s: string;
        // 哈夫曼树的建树方法是一种“由下而上归并叶节点”的策略。指针p用于新建节点、整数lc和rc
        // 则用于在叶数组leaf中选取值最小的两个用于归并。
        // 叶数组leaf是动态更新的。每一次lc和rc归并后,lc用归并后的节点p替代,而rc标记为
        // nil(空指针)。后面的搜索将无视所有已经标记为nil的数组元素。
        // 执行归并的次数为(节点数-1),用for循环即可。。
     
     procedure FindTwoMins(arr: LeafArr; var Min1: Integer; var Min2: Integer);
        // 从LeafArr类数组arr中找出两个值最小的,将其下标存入Min1和Min2中。
     
     procedure HuffmanEncode(T: HuffmanTree);
     var
        i: Integer;
     begin
        if (T^.lchild = nil) and (T^.rchild = nil) then
          begin
            for i := 0 to H.top do
              if H.data[i].ch = T^.dataC then
                begin
                  H.data[i].code := s;
                  Exit;
                end;
          end;
        s := s + '0'; HuffmanEncode(T^.lchild); Delete(s, Length(s), 1);
        s := s + '1'; HuffmanEncode(T^.rchild); Delete(s, Length(s), 1);
     end;
        // 深度优先建立哈夫曼树。S用于记录路径。向左子树搜索则添0,向右则添1。
    // 当前节点深搜完成之后回溯,尝试另一条路径。
     
    begin
     SetLength(leaf, H.top+1);
     for i := 0 to H.Top do
        begin
          New(leaf[i]);
          leaf[i]^.lchild := nil; leaf[i]^.rchild := nil;
          leaf[i]^.data := H.data[i].freq; leaf[i]^.dataC := H.data[i].ch;
        end;
        // 建立叶节点
     for k := 0 to H.top-1 do
        begin
          FindTwoMins(leaf, lc, rc);
          New(p);
          p^.data := leaf[lc]^.data + leaf[rc]^.data;
          p^.lchild := leaf[lc]; p^.rchild := leaf[rc];
          leaf[lc] := p; leaf[rc] := nil;
        end;
        // 归并叶节点,并更新叶节点数组
     T := leaf[lc];
     s := '';
     HuffmanEncode(T);
    end;
     
    (4) 使用哈希表
     
        为了提高效率,编码和解码的时候,都需要用到哈希表。
        将编码写入压缩文件时,要挨个扫描源文件中的字符,然后从哈夫曼编码表中找到字符对应的编码。由于字符是混乱无序的(如按照普通数组下标那样存储势必浪费存储空间),故采用哈希表。使用哈希函数,通过字符可以求得下标,通过下标又能很方便的访问编码字符串。这样就建立了字符与编码之间的对应关系。
    解码时,在读取哈夫曼编码的同时,需构建通过编码可以直接得到相应字符的哈希函数,这样便能够比较容易的进行解码操作。
     
    Delphi提供了一个TStringHash类,使用它可以直接建立一种比较简单的哈希表,其关键字是字符串、值为整数。这样一来,上面提到的编码用哈希表只需要建立线性表中字符与下标的对应关系,解码用哈希表只需要建立编码与相应字符的ASCII编码的对应关系即可。
     
    TStringHash类主要有以下方法:
     
    Procedure Add(Str: string, Int: Integer)
    // 此过程可以在哈希表中建立Str与Int的对应关系。
    Function ValueOf(Str: string)
    // 此函数的返回值为哈希表中关键字Str所对应的整数值。若Str不对应任何值,则返回-1。
     
    写入哈夫曼树之前,先通过记录各叶子节点的线性表来建立哈希表。
     
    // 定义:
    var
    HuffmanHash: TStringHash;
    // 建立:
    HuffmanHash := TStringHash.Create;
     for i := 0 to HT.top do
        HuffmanHash.Add(HT.data[i].ch, GetSubscript(HT.data[i].ch));
     
    HT是记录叶的线性表。其中GetSubscript函数用于在HT.data之中搜索获得相应字符的下标。
     
        (5) 哈夫曼树录入压缩文件
       
    只有将哈夫曼树数据成功写入压缩文件,此文件才能正常被解压。在“概要设计”的“编码文件格式”一节中已经描述了存储方式。其具体实现方法如下:
     
    // --- 录入哈夫曼编码于压缩文件之中 ---
    // var
    //   i, j, CodeLen, ByteCount: Integer;
    //   FOutStream: TFileStream;
    //   TempStr: String;
    //   c, CodeLenCh: Char;
    // 以上为变量定义
     
    for i := 0 to HT.top do
     begin
        FOutStream.WriteBuffer(HT.data[i].ch, Sizeof(Char));
     // 先写入当前字符,即线性表中第i个元素的ch域。
        CodeLen := Length(HT.data[i].code);
        ByteCount := (CodeLen - 1) div 8 + 1;
       // 以上两句分别求出该字符编码(0-1串)长度和存储此编码所需字节数。
        CodeLenCh := Chr(CodeLen);
    FOutStream.WriteBuffer(CodeLenCh, Sizeof(Char));
    // 接下来,把该字符编码长度转换为字符型,并写入文件。
        TempStr := HT.data[i].code;
        for j := 0 to ByteCount-1 do
          begin
            c := Chr(Str01ToInt(Copy(TempStr, 1, 8)));
            Delete(TempStr, 1, 8);
            FOutStream.WriteBuffer(c, Sizeof(Char));
          end;
        // 最后,把编码按8位一组转换为字符的方式写入文件,末位用0补齐。
     end;
          
           其中用到的Str01ToInt子函数定义为:
               function Str01ToInt(s: string): Integer;
    使用此函数要求s为8位以内的0-1串。其功能为将0-1串末尾补零(若长度不足8位)后,总体看作二进制数以转换为十进制数,再在程序中转换为字符,以存入压缩文件中。
       
        (6) 写入编码以及末尾补零处理
       
    有了以上的准备,写入编码就相对比较容易了。逐行扫描(源文件生成的)字符串列表,利用哈希表获取当前字符的编码,写入文件就可以了。
    可以用一个字符串变量作为缓冲区,每扫描一个源字符写入编码后,检查缓冲区长度是否大于8.若是,则不断截取其前8位转换为字符类型写入压缩文件,直到其长度小于8。可用while语句实现:
     
    Str01 := Str01 + HT.data[HuffmanHash.ValueOf(FileSS[i][j])].code;
        while Length(Str01) >= 8 do
          begin
            c := Chr(Str01ToInt(Copy(Str01, 1, 8)));
            FOutStream.WriteBuffer(c, Sizeof(Char));
            Delete(Str01, 1, 8);
          end;
     
    其中Str01为字符串缓冲区。i扫描行,j扫描每行的字符串的每个字符。并且注意到缓冲区更新的过程中已经使用到了事先建立的哈希表。
        另外需要注意的问题是回车符的处理。由于采用字符串列表的读入方式,故无法直接读入回车符。解决办法是每读完一行(i值改变的时候),执行一次回车符的写入。当然还必须判断是否已经到达最后一行,如果是,就不需要写入回车符了。即:
     
         for i := 0 to FileSS.Count-1 do
           begin
            // j循环处理当前行
              if i <> FileSS.Count-1 then
                begin
                  // 如果未读到最后一行,即i值不等于(行数-1),则写入一个回车符的编码
                end;
            end;
     
        如果扫描完所有字符之后,字符串缓冲区不为空,则末尾必须补充若干个零才能将所有的编码信息转化为字符序列存储。相应处理方法为:
     
         if Str01 <> '' then
            begin
             ZeroFill := 8 - Length(Str01);
              c := Chr(Str01ToInt(Str01));
              FOutStream.WriteBuffer(c, Sizeof(Char));
            end
          else
            ZeroFill := 0;
         FOutStream.WriteBuffer(ZeroFill, Sizeof(Byte));
     
        整数变量ZeroFill记录下需要补零的个数,最后写入文件末尾。
        上面已经提到Str01ToInt函数能够自行在末尾补零再转换为十进制数。
    例如,如果最后缓冲区Str01 = ‘10011’,则Str01ToInt(Str01)的结果为(10011000)2,即(152)10。又因为对ZeroFill的赋值是在Str01ToInt执行之前,故ZeroFill最后的结果为3,表示成功补了3个零。
       
        (7) 解码
       
    解码的步骤包含:建立相应读写文件流、检验文件合法性、读取编码字符数目、依次读取各字符编码并建立哈希表、读取编码正文并写入目标文件(解压后的文件)。
    程序中,整个解码过程由dec_DecodeHFMFile这个过程来完成。
    解码必须得先读取哈夫曼树。包括读取编码的第4、5个字符(前三个字符为’hfm’),得到总编码数目,然后建立哈希表,用for循环依次读入每一个字符及其对应的编码存入哈希表中。
     
     // 已经读入节点个数存放于整数变量NodeNum中
     HashForDecode := TStringHash.Create;
     for i := 1 to NodeNum do
        begin
          FReadStream.ReadBuffer(Buffer, 2);
          CodeLen := Ord(Buffer[1]);
          ByteCount := (CodeLen - 1) div 8 + 1;
          Str := '';
          for j := 1 to ByteCount do
            begin
              FReadStream.ReadBuffer(c, Sizeof(Char));
              TempInt := Ord(c);
              Str := Str + DecToBin(TempInt);
            end;
          Str := Copy(Str, 1, CodeLen);
          HashForDecode.Add(Str, Ord(Buffer[0]));
        end;
       
           其中用到的的DecToBin函数:
               function DecToBin(DecInt: Byte): string;
    可以看作前面提及的Str01ToInt的反函数,其功能为将十进制数转化为0-1串。不足8位则高位补零。
       
           哈希表建立完成之后,便可以开始解码。
        同样建立一个字符串缓冲区,将压缩文件逐字节转换为0-1串读入。为了提高效率,一次读入三个字节。另外需要注意的是文件末尾判定。因为补零数存放于文件的最后一个字节,所以读入的时候需要随时检查是否已经到了文件尾部。由于要一次读入3个字节,我们定义一个字符数组Buffer。
       
    type
       TBuffer = Array [0..2] of Char;
    var
           Buffer: TBuffer;
       
        现在我们要明确,TFileStream类有两个属性:Position和Size。前者标定当前的流指针指向的位置,后者标定流的大小。容易知道,对于输入流而言,每次执行Read方法读取n个字节,Position将自加n。而Size在把文件载入流的过程中就已经确定了。
        我们用:
    ReadCount := FReadStream.Read(Buffer, Sizeof(TBuffer));
    读入字节。这样一来,读到文件尾部时候,会出现三种情况:
        a. FReadStream.Position = FReadStream.Size - 1
    此时可以确定,这一趟的三个字符读入之后,输入流中仅剩下最后一个字符。它就是ZeroFill。所以我们单独读入最终字符:
    FReadStream.ReadBuffer(c, Sizeof(Char));
    Zerofill := Ord(c);
    成功得到补零数,再把Buffer[0]和Buffer[1]和Buffer[2]读入缓冲区并删除缓冲区的末ZeroFill位。
        b. FReadStream.Position = FReadStream.Size
    此时正好读完整个流。显然Buffer[2]就是ZeroFill。此时先把Buffer[0]和Buffer[1]读入缓冲区,再:
               Zerofill := Ord(Buffer[2]);
           即可,最后删除缓冲区的末ZeroFill位。
        c. ReadCount < Sizeof(TBuffer)
    此时ReadCount应等于2。Buffer[1]是ZeroFill。所以应先把Buffer[0]读入字符串缓冲区,再:
               Zerofill := Ord(Buffer[1]);
           即可,最后删除缓冲区的末ZeroFill位。
       
        程序运行到最后,三种情况必择其一。以上任意一种情况执行后,都要执行Flag := False。
        删除末ZeroFill位的语句:
           Delete(Str, Length(Str) - Zerofill + 1, Zerofill);
       
        while Flag do
        begin
          ReadCount := FReadStream.Read(Buffer, Sizeof(TBuffer));
          if ReadCount < Sizeof(TBuffer) then
            // 情况c
          else if FReadStream.Position = FReadStream.Size then
            // 情况b
          else if FReadStream.Position = FReadStream.Size - 1 then
            // 情况a
          else
            begin
    Str := Str + DecToBin(Ord(Buffer[0])) + DecToBin(Ord(Buffer[1]))
    + DecToBin(Ord(Buffer[2]));
            end;
          i := 0;
          while i < Length(Str) do
            begin
              Inc(i);
              TempInt := HashForDecode.ValueOf(Copy(Str, 1, i));
              // 尝试缓冲区的前i位。如果恰好是有编码的0-1串片段,则TempInt为相应的哈希函数值,
            // 否则TempInt返回-1,继续尝试缓冲区的前i+1位。
    if TempInt > -1 then
                begin
                  c := Chr(TempInt);
                  if c = #13 then
                    FWriteStream.WriteBuffer(#13#10, 2)
                  // Delphi中要写入回车必须写#13#10而不能直接写入#13
                  else
                    FWriteStream.WriteBuffer(c, Sizeof(Char));
                  // 如果待写入的字符不是回车,则直接将c写入即可
                  Delete(Str, 1, i);
                  i := 0;
                  Continue;
                // 删去已经解码完成的0-1串片段,并重新将i置零
                end;
            end;
        end;
     
    (8) 调试模式
     
        为方便调试程序,特设立调试模式。如果在程序运行时选中调试模式复选框,将会激活一个新的程序窗体作为调试窗体,并在建立哈夫曼树和读取哈夫曼编码的同时,将读得的编码和字符写入该窗体的一个列表框组件中,程序运行完成后不会立即退出,只是不能继续进行压缩、解压等操作,但可以呼出调试窗体,检验建树或读取过程是否正确。
     
    【调试分析】
        测试数据为两个文本文件:
    Alice in Wonderland.txt (141kb)
    科大商家联盟第六期商家见面会会议材料.txt (280kb)
       
        选定调试模式,压缩爱丽丝漫游仙境英文版,程序执行时间1秒左右。
        得到Alice in Wonderland.hfm (79.9kb)
        此时可呼出调试窗体查看哈夫曼编码。
       
        退出并重新进入程序,选择Alice in Wonderland.hfm进行解压,同样选中调试模式。
       
        解压耗时稍长。得到Alice in Wonderland_ext.txt (141kb),用记事本打开查看,与原文本文件完全一致。
        呼出调试窗体查看读取编码结果:
     
        科大商家联盟第六期商家见面会会议材料的测试结果也比较成功。压缩过后218kb。解压之后也与源文件完全一致。

     

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

    2012-07-09 02:57:00
    用Java实现,哈夫曼编码实现文件压缩,有详细注释
  • 哈夫曼编码压缩解压缩程序(CPP写的) 多媒体课程设计中也许能用的到 希望能帮到能用的到的人
  • 压缩压缩后 经验证解压缩前与解压缩后文本一致,无出入 文件目录 binaryTreeNode.h linkedBinaryTree.h 源.cpp 代码如下 binaryTreeNode.h #ifndef binaryTreeNode_ #define binaryTreeNode_ #include #...
  • 通过哈夫曼编码压缩文件

    千次阅读 2018-10-11 15:04:06
    原理就是统计带压缩文件字符频率,构建哈夫曼树,然后求哈夫曼编码,将字符频率(解压的时候通过字符频率建树)和哈夫曼编码写入文件,完成压缩压缩代码: //获取一个文件的每个字符的频率 void get_frequency...
  • 哈夫曼编码压缩和解压文件的Java实现 上一次已经介绍了如何用Huffman树实现文件的压缩及其原理,那么今天我们试着真正运用它实现文件的压缩与解压 前戏 我们先来整理一下思路 首先我们拿到一个文件,看起来是一串串...
  • 5.对应哈夫曼编码生成新的bytes,并将bytes和哈夫曼编码一同输出到压缩文件中 解压: 1.先读取数据和哈夫曼编码 2.反转哈夫曼编码(key,value互换) 3.对应反转后的哈夫曼编码恢复原来文件 3.输出恢复好的文件 注意...
  • 哈夫曼编码和解码代码,利用哈夫曼编码压缩和解压文件的小工具。
  • 哈夫曼编码压缩工具

    2012-05-15 20:08:44
    一个MFC开发的哈夫曼压缩工具,有点小问题:编码最长16位,失败情况较多
  • 数据压缩实践-用哈夫曼编码压缩解压文件 引言: 哈夫曼编码的一大用处便是数据压缩,我们在学完之后,当然要学会试着运用其来压缩解压文件。一下便是写着做的文件压缩尝试。 文件准备: 首先在D盘下准备个了个34kB...
  • 5)步骤五:通过哈夫曼编码获得哈夫曼编码字符串(就是将所有的哈夫曼编码字符串拼接) 6)步骤六:我们按照,每八个01串切割一次并转换成十进制数存入byte[ ]数组中,的规则去获得我们的压缩后的byte数组,即压缩...
  • 作者 |小灰来源 |程序员小灰(ID:chengxuyuanxiaohui)在上一期,我们介绍了一种特殊的数据结构“哈夫曼树”,也被称为最优二叉树。没看过的小伙伴可以点击下方链接:漫画:什么是 “哈夫曼树” ?那么,这种数据结构...
  • 对英文文本文件进行哈夫曼编码译码的C++实现 以及压缩率计算哈夫曼编码压缩原理:由于每个字符在内存中都是以ASCII码进行存储,所以每个字符都占用了八个01位,利用哈夫曼树对每个字符进行01编码,根据字符在文章中...
  • 实验目的:理解哈弗曼信源编码算法,并能应用于文件压缩中。 实验内容:写出程序,利用哈弗曼编码实现对文件的压缩,并能解压文件。 实验步骤: 1、压缩 (1) 统计原始文件中各字节出现的概率(次数); (2) 采用...
  • 哈夫曼编码压缩文件

    热门讨论 2012-05-09 15:57:03
    这是我自己学习huffman编码时编写的一个小程序。可以对文件进行压缩和解压缩,支持2种压缩算法,文件名称和压缩模式在命令行参数设置。内有编译好的执行文件,测试结果,数据文件,比较详细的使用说明和注释。程序...
  • 用面向对象的程序设计思想自己动手写压缩软件,采用了优先队列这一很好的数据结构实现的贪心算法构造Huffman树,能打印Huffman树,显示编码表,压缩文件和解压缩文件,采用UTF-8字符集,支持中文文件

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,797
精华内容 718
关键字:

哈夫曼编码压缩