精华内容
下载资源
问答
  • 哈夫曼压缩与解压缩(c语言版)
    千次阅读 多人点赞
    2019-09-29 19:18:13

    目录

    哈夫曼压缩与解压缩(c语言版)

    一:引言

    二:主要原理

    三:主要技术点

    四:实现过程

    1.压缩:

    2.解压缩:

    五:详细分析,及代码实现


    哈夫曼压缩与解压缩(c语言版)

    一:引言

    学过数据结构的同学,应该都听过哈夫曼树,和哈夫曼压缩算法,今天小编向大家讲解哈夫曼压缩与压缩的过程以及代码也算是记录一下自己所学所做的东西。

    哈夫曼压缩,其实效率不是很高,一般情况下压缩率13%左右,特殊情况下效率很高(频率高的字符的情况)。但是尝试自己去完成它,对你的代码能力有很大的提升。下面开始讲解

    二:主要原理

    1.哈夫曼树

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

    以 下数组为例,构建哈夫曼树

    int a[] = {0,1,2,3,4,5,6,7,8}

    我们可以发现以下规律

    1:9个数构成的哈夫曼树一共有17个结点,也就是可以n个数可以生产2*n-1个结点

    2:数字越大的数离根节点越近,越小的数离根节点越近。


    2.如何利用haffman编码实现文件压缩:

    比如abc.txt文件中有以下字符:aaaabbbccde,

    1.进行字符统计

        aaaabbbccde
         
        a : 4次
        b : 3次
        c : 2次
        d : 1次
        e : 1次

    2.用统计结果构建哈夫曼树

    3.用哈夫曼树生成哈夫曼编码(从根结点开始,路径左边记为0,右边记为1):

        a的编码:1
        b的编码:01
        c的编码:000
        d的编码:0011
        e的编码:0010

    4.哈夫曼编码代替字符,进行压缩。

    源文件内容为:aaaabbbccde
    将源文件用对应的哈夫曼编码(haffman code)替换,则有:11110101 01000000 00110010   (总共3个字节)

    由此可见,源文件一共有11个字符,占11字节的内存,但是经过用haffman code替换之后,只占3个字节,这样就能达到压缩的目的

    三:主要技术点

    1.哈夫曼树算法(哈夫曼压缩的基本算法,如何不懂该算法,小编建议先学习下该算法)

    2.哈希算法(字符统计时候会用到)

    3.位运算(涉及到将指定位,置0或置1)

    4.内存对齐模式(小编在这里踩过坑,非常重要)

    5.存储模式(大端存储,小端存储,能看懂文件16进制的形式)

    6.主函数带参(很简单)

    7.设置压缩密码,解压输入密码解压(小编自己加的内容)

    四:实现过程

    1.压缩:

    1.遍历文件每个字节,统计所有的字符和其频率,

    2.构建哈夫曼树

    3.遍历树,给叶子节点生成哈夫曼编码

    4.将字符和其频率,以及密码,写入新文件。

    5.再次遍历文件每个字节,将该字节内容用哈夫曼编码代表,将哈夫曼编码写入文件。

    2.解压缩:

    1.从文件中将将字符和其频率读出来,生成一张表。读之前可以先验证输入密码是否正确

    2.用改表构建哈夫曼树。

    3.遍历哈夫曼树,给叶子节点生成哈夫曼编码

    4遍历文件每个bit位,按照哈夫曼编码,得到数个bit所对应得到字符,将该字符写入文件。

    五:详细分析,及代码实现

    三个必要的位运算,(这三个方法是他人提供)

    //判断指定位是否为0,若index位为0,则GET_BYTE值为假,否则为真
    #define GET_BYTE(value, index) (((value) & (1 << ((index) ^ 7))) != 0)
    //将指定位,置为1
    #define SET_BYTE(value, index) ((value) |= (1 << ((index) ^ 7)))
    //将指定位,置为0
    #define CLR_BYTE(value, index) ((value) &= (~(1 << ((index) ^ 7))))

    1.字符统计

    结构体定义

    typedef struct huffman{
    	int character;
    	int freq;
    }HUFFMAN;

    统计过程及哈希算法

    //count初值为0,传过来用于统计多少种字符,goalfile,为文件名称
    HUFFMAN *freqhuf(int *count, char *goalfile){
    	int freq[256] = {0};
    	int i;
    	int index;
    	HUFFMAN *result;
    	FILE *fpIn;
    	int ch;
    	
    	fpIn = fopen(goalfile, "rb");
    	ch = fgetc(fpIn);
    //统计所有字符,这里巧妙的采用哈希算法,用字符的ASCII码值作为下标,
    //freq[ASCII]的值,作为该字符的频率,很巧妙的形成字符和其频率的映射关系
    	while (!feof(fpIn)) {
    		freq[ch]++;
    		ch = fgetc(fpIn);
    	}
    	fclose(fpIn);
    //统计多少种字符
    	for(i = 0; i < 256; i++){
    		if(freq[i] != 0){
    			(*count)++;
    		}
    	}
    //将统计的结果,字符和其频率生成数组返回出去。
    	result = (HUFFMAN *)calloc((2*(*count) - 1), sizeof(HUFFMAN));
    	for(i = 0,index = 0; i < 256; i++){
    		if(freq[i] != 0){
    			result[index].character = i;
    			result[index++].freq = freq[i];
    		}
    	}
    	return result;
    }

    2.构建哈夫曼树

    //哈夫曼树的节点
    typedef struct huff{
            //字符及其频率
    	HUFFMAN freq;
            //左孩子
    	int left;
            //右孩子
    	int right;
            //是否用过0表示没有用过1表示用过
    	int use;
            //该节点对于的哈夫曼编码字符串
    	char *code;
    }Huff;
    //创建哈夫曼树
    Huff *bulidhuftree(HUFFMAN *information, int *count){
    	int i;
    	int degree = 2*(*count) - 1;
    	Huff *result;
    	int temp;
    
    	//将生成的哈夫曼树放在result里返回
    	result = (Huff *)calloc(sizeof(Huff), degree);
            //填充基本字符及其频度
    	for(i = 0; i < *count; i++){
    		result[i].freq.freq = information[i].freq;
    		result[i].freq.character= information[i].character;
    		result[i].left = -1;
    		result[i].right = -1;
    		result[i].use = 0;
    		result[i].code = (char*)malloc(sizeof(char)*(*count));
    	}
    	//根据基本字符及其频度填充哈夫曼表
    	for(i = *count; i < degree; i++){
    		result[i].use = 1;
    		result[i].freq.character = '#';
    		result[i].right = searchmin(result, *count);
    		result[i].left = searchmin(result, *count);
    		result[i].freq.freq = result[result[i].right].freq.freq + result[result[i].left].freq.freq;
    		temp  = searchmin(result, ++(*count));
    		if(temp == -1){
    			break;
    		}
    		result[temp].use = 0;
    		result[i].use = 0;
    	}
    	return result;
    }
    //查找到频率最小的字符的下标
    int searchmin(Huff *freq, int count){
    	int i;
    	int minindex = -1;
    	
    	for(i = 0; i < count; i++){
    		if(freq[i].use == 0){
    			minindex = i;
    			break;
    		}
    	}
    	if(minindex == -1){
    		return -1;
    	}
    	for(i = 0; i < count; i++){
    		if((freq[i].freq.freq <= freq[minindex].freq.freq) && freq[i].use == 0){
    			minindex = i;
    		}
    	}
    	freq[minindex].use = 1;
    	return minindex;
    }

    3.构建哈夫曼编码

    根节点所在的下标,index为字符串下标,str为字符串,
    
    void bulidhuftreecode(int root, int index, Huff *freq, char *str){
    	//采用递归,此处是哈夫曼压缩最难得地方,建议大家根据代码遍历跟踪一遍
    	if(freq[root].left != -1 && freq[root].right != -1){
    		str[index] = '1';
    		bulidhuftreecode(freq[root].left, index+1, freq, str);
    		str[index] = '0';
    		bulidhuftreecode(freq[root].right, index+1, freq, str);
    	}
    	else{
    		str[index] = 0;
    		strcpy(freq[root].code, str);
    	}	
    }

    4.写入压缩文件头信息(密码,字符数量,压缩文件标志),写入所有字符和其频率。

    typedef unsigned char u8;
    //压缩文件的头信息
    typedef struct message{
            //前三个字节用M,u,f代表哈夫曼文件,不是这三个字符代表该文件不是压缩文件
     	u8 ishuf[3];
            //字符数量
     	u8 count;
            //最后一个字符所对应的下标
     	u8 lastindex;
            //密码(密码可以用自己学过的加密方式加密,这里我没有用加密算法)
     	int password;
    }MESSAGE;
    //创建压缩文件
    void creatcodefile(Huff *freq, int count, char *goalfile, char *resultfile, HUFFMAN *storefreq){
    	FILE *fpOut;
    	FILE *fpIn;
    	unsigned char value;
    	int i;
    	int index = 0;
    	const char *hufCode;
    	int arr[256];
    	int ch;
    	int password;
    	MESSAGE headcode = {'M', 'u', 'f'};
    
    	//将密码存入文件头信息
    	printf("请设置压缩密码,以便解压时候用:\n");
    	scanf("%d", &headcode.password);
    	printf("压缩中!请稍等。\n");
    	
    	fpOut = fopen(resultfile, "wb");
    	fpIn = fopen(goalfile, "rb");
    	headcode.count = (u8)(count + 1)/2;
    	headcode.lastindex = howlongchar(freq, count);
            //将文件头信息写入文件
    	fwrite(&headcode, sizeof(MESSAGE), 1, fpOut);
            //将字符和其频率写入文件
    	fwrite(storefreq, sizeof(HUFFMAN), (count + 1)/2, fpOut);
    	
    	for(i = 0; i < (count + 1)/2; i++){
    		arr[freq[i].freq.character] = i;
    	}
            //遍历源文件,将每个字符按其哈夫曼编码写入新文件
    	ch = fgetc(fpIn);
    	while(!feof(fpIn)){
    		hufCode = freq[arr[ch]].code;
    		for(i = 0; hufCode[i]; i++){
    			if(hufCode[i] == '0'){
    				CLR_BYTE(value, index);
    			}
    			if(hufCode[i] == '1'){
    				SET_BYTE(value, index);
    			}
    			if(++index >= 8){
    				index = 0;
    				fwrite(&value, 1, 1, fpOut);
    			}
    		}
    		ch = fgetc(fpIn);
    	}
    	if(index){
    		fwrite(&value, 1, 1, fpOut);
    	}
    	fclose(fpIn);
    	fclose(fpOut);
    }

    压缩后的文件展示

     

    主函数代码,以及其他辅助方法。

    //得到哈夫曼文件最后一个字节第几个是有效位
    int howlongchar(Huff *freq, int count){
    	int i;
    	int sum = 0;
    	
    	for(i = 0; i < (count + 1)/2; i++){
    		sum = sum + strlen(freq[i].code);
    		sum &= 0xFF;
    	}
    	return sum % 8 == 0 ? 8 : sum % 8;
    }
    int main(int argc, char *argv[]) {
    	int count = 0;
    	HUFFMAN *information;
    	Huff *freq;
    	char *str;
    	char 	resultfile[50];
    	char  goalfile[50];
    	FILE *fp;
    	int i;
    	
    	fp = fopen(argv[1], "r");
    	if(fp == NULL){
    		printf("不存在该文件!");
    		return 0;
    	}
    	fclose(fp);
    	fp = fopen(argv[2], "w");
    	fclose(fp);	
    	strcpy(goalfile, argv[1]);
    	strcpy(resultfile, argv[2]);
    	//统计字符
    	information = freqhuf(&count, goalfile);
            //临时数组存每个字符code
    	str = (char*)malloc(sizeof(char)*(count+1));
            //构建哈夫曼树
    	freq = bulidhuftree(information, &count);
            //构建哈夫曼编码
    	bulidhuftreecode(count - 1, 0, freq, str);
            //创建压缩文件
    	creatcodefile(freq, count, goalfile, resultfile, information);
    	//释放内存
    	free(information);
    	free(str);
    	for(i = 0; i < count; i++){
    		free(freq[i].code);
    	}
    	free(freq);
    	printf("压缩成功!");
    	
    	return 0;  
    }

    解压缩:基本与压缩原理相似

    1.从文件中将将字符和其频率读出来,生成一张表。读之前可以先验证输入密码是否正确

    HUFFMAN *freqhuf(int *count, char *goalfile, int *lastindex){
    	int i;
    	HUFFMAN *result;
    	FILE *fpIn;
    	
    	fpIn = fopen(goalfile, "rb");
    	if(fseek(fpIn, 3L, SEEK_SET) == 0){
    		fread(count, sizeof(char),  1, fpIn);
    		fread(lastindex, sizeof(char),  1, fpIn);
    	}
    	result = (HUFFMAN *)calloc(sizeof(HUFFMAN), *count);
    	if(fseek(fpIn, 12L, SEEK_SET) == 0){
    		fread(result, sizeof(HUFFMAN), *count, fpIn);
    	}
    	fclose(fpIn);
    	return result;
    }

    2、初始化哈夫曼表

    和压缩过程一样。

    3、生成哈夫曼树

    和压缩过程一样。

    4、生成哈夫曼编码

    和压缩过程一样。

    5、从压缩文件中读取二进制信息,还原文件

    void creatsourcefile(Huff *freq, int count, char *goalfile, char *resultfile, int lastindex){
    	FILE *fpOut;
    	FILE *fpIn;
    	long temp;
    	u8 value;
    	int index = 0;
    	int root;
    	long bitecount;
    	int fininsh = 0;
    	
    	fpIn = fopen(goalfile, "rb");
    	fseek(fpIn, 0L, SEEK_END);
    	bitecount = ftell(fpIn);
    	fclose(fpIn);
    	
    	root = count - 1;
    	temp = (long)(count + 1)/2;
    	fpOut = fopen(resultfile, "wb");
    	fpIn = fopen(goalfile, "rb");
    	if(fseek(fpIn, temp * 8 + 12, SEEK_SET) == 0){
    		printf("解码中!");
    		fread(&value, sizeof(char), 1, fpIn);
    		while(!fininsh){
    			if(GET_BYTE(value, index) == 0){
    				root = freq[root].right;
    			}
    			if(GET_BYTE(value, index) == 1){
    				root = freq[root].left;
    			}
    			if(freq[root].right == -1 && freq[root].right == -1){
    				fwrite(&freq[root].freq.character, sizeof(char), 1, fpOut);
    				root = count - 1;
    			}
    			if(++index >= 8){
    				index = 0;
    				fread(&value, sizeof(char), 1, fpIn);
    			}
    			if(ftell(fpIn) == bitecount){
    				if(index >= lastindex){
    					fininsh = 1;
    				}
    			}		
    		}
    		printf("解码成功!\n");	
    	}
    	else{
    		printf("解码失败!\n");
    	}
    }

    主函数

    int main(int argc, char *argv[]) {
    	int count = 0;
    	HUFFMAN *information;
    	Huff *freq;
    	char *str;
    	char 	resultfile[50];
    	char  goalfile[50];
    	FILE *fp;
    	char Huf[3];
    	int lastindex = 0;
    	int i;
    	int password;
    	int unpassword;
    	
    	fp = fopen(argv[1], "rb");
    	if(fp == NULL){
    		printf("不存在该文件!");
    		return 0;
    	}
    	fread(&Huf, sizeof(char), 3, fp);
    	if(Huf[0] != 'M' || Huf[1] != 'u' || Huf[2] != 'f'){
    		printf("该文件不是哈夫曼压缩的文件!");
    		return 0;
    	}
    	if(fseek(fp, 8L, SEEK_SET) == 0){
    		fread(&password, sizeof(int), 1, fp);
    		printf("请输入解压密码:");
    		scanf("%d", &unpassword);
    		if(password != unpassword){
    			printf("密码错误!");
    			return 0;
    		}
    	}
    	fclose(fp);
    	fp = fopen(argv[2], "w");
    	fclose(fp);
    	strcpy(goalfile, argv[1]);
    	strcpy(resultfile, argv[2]);
    	
    	information = freqhuf(&count, goalfile, &lastindex);
    	str = (char*)malloc(sizeof(char)*(count+1));  //临时数组存每个字符code
    	freq = bulidhuftree(information, &count);
    	bulidhuftreecode(count - 1, 0, freq, str);
    	free(str);
    	creatsourcefile(freq, count, goalfile, resultfile, lastindex);
    	
    	free(information);
    	for(i = 0; i < count; i++){
    		free(freq[i].code);
    	}
    	free(freq);
    	free(str);
    	return 0;  
    }

    更多相关内容
  • 哈夫曼压缩与解压缩

    万次阅读 多人点赞 2018-08-13 12:52:01
    哈夫曼压缩与解压缩 目录 哈夫曼压缩与解压缩 一:引言 二:主要技术点 三:过程介绍 1、压缩: 2、解压缩 四:详细分析 一:准备过程 二:压缩 三:解压缩 五:结果演示 六:总结 七:源码地址 一:...

    哈夫曼压缩与解压缩

    目录

    哈夫曼压缩与解压缩

    一:引言

    二:主要技术点

    三:过程介绍

    1、压缩:

    2、解压缩

    四:详细分析

    一:准备过程

    二:压缩

    三:解压缩

    五:结果演示

    六:总结

    七:源码地址


    一:引言

    之前的两个贪吃蛇和巨大数的练习,总体来说难度不大,有好的算法和比较新颖的微译码补码。但是,哈夫曼压缩与解压缩可以说难度比前两个大得多,涉及的知识面更加广。做完这个,是对自己基本功的检测,更能提升自己的编程能力。 

    hffman编码的思想对文件进行压缩,主要原理是通过huffman编码来重新表示字符,使得出现频率高的字符编码短,出现少的字符编码长。整体下来的话,所需的总的bit位是减少的。但是要注意当大部分字符出现的频率都差不多时,huffman压缩的压缩效率会很低。

    编程环境:

    UE(或sublime),TDM-GCC。

    二:主要技术点

    1. 文件的各种操作
    2. 递归思想构造哈夫曼编码。
    3. 位运算思想进行压缩与解压缩。
    4. 自定义目标压缩文件头部元数据。
    5. 主函数带参,命令行参数。

    三:过程介绍

    1、压缩:

    1、统计字符种类及频度:ASCII码值当下标,字符频度当对应下标的值。

    2、构建哈夫曼树:在没有访问过的节点中,找最小字符频度下标来构建哈夫曼树。

    3、构建哈夫曼编码:递归思想构建。

    4、生成压缩文件(.ycyHuf后缀名):把字符的哈夫曼编码以二进制形式写入目标文件中。给压缩文件头部写入元数据,解压缩时需使用这些数据。

    注意事项:给目标文件写二进制数据时,最后一个字节如果不满八位,会产生垃圾数据,如果不进行处理,在解压后,就不能完整的还原。所以,需计算最后一个字节中的有效位数。

    2、解压缩

    1、根据压缩文件的头部元数据,得到字符种类和频度。

    2、构建哈夫曼树:在没有访问过的节点中,找最小字符频度下标来构建哈夫曼树。

    3、构建哈夫曼编码:递归思想构建。

    4、生成解压缩的文件(后缀名和源文件后缀名一样 )即可:一位一位的从压缩文件中读取信息,'1'向左子树走,'0'向右子树走。

    注意事项:压缩文件头部有元数据,所以,解压时需要把文件指针定位到真正的信息处。当碰到最后一字节的垃圾位时,应结束,否则解压出的信息和源文件会不匹配。

    四:详细分析

    一:准备过程

    三个关于位运算的宏

    1、取出index位,若取出的index位为0,则GET_BYTE值为假,否则为真

    #define GET_BYTE(vbyte, index) (((vbyte) & (1 << ((index) ^ 7))) != 0)

    2、把index位设置为‘1’

    #define SET_BYTE(vbyte, index) ((vbyte) |= (1 << ((index) ^ 7)))

    3、把index位设置为‘0’ 

    #define CLR_BYTE(vbyte, index) ((vbyte) &= (~(1 << ((index) ^ 7))))

    二:压缩

    1、统计字符种类和频度

    结构体定义:

    typedef struct ALPHA_FREQ {
    	unsigned char alpha;		//字符,考虑到文件中有汉字,所以定义成unsigned char
    	int freq;					//字符出现的频度
    } ALPHA_FREQ;

    代码分析:

    ALPHA_FREQ *getAlphaFreq(char *sourceFileName, int *alphaVariety) {
    	int freq[256] = {0};
    	int i;
    	int index;
    	ALPHA_FREQ *alphaFreq = NULL;
    	FILE *fpIn;
    	int ch;
    	
    	fpIn = fopen(sourceFileName, "rb");
    	
    	/*统计所有字符的频度*/
    	ch = fgetc(fpIn);
    	while(!feof(fpIn)) {
    		freq[ch]++;
    		ch = fgetc(fpIn);
    	}
    	fclose(fpIn);
    
    	/*统计所有字符的种类*/
    	for(i = 0; i < 256; i++) {
    		if(freq[i]) {
    			(*alphaVariety)++;
    		}
    	}
    
    	alphaFreq = (ALPHA_FREQ *) calloc(sizeof(ALPHA_FREQ), *alphaVariety);
    	for(i = index = 0; i < 256; i++) {
    		if(freq[i]) {
    			alphaFreq[index].alpha = i;
    			alphaFreq[index].freq = freq[i];
    			index++;
    		}
    	}
    
    	return alphaFreq;
    }

    统计字符及其频度,开始想到了一个笨办法。 如下:

    AlPHA_FREQ freq[256]
    count = 0;
    i = 0;
    
    while(str[i]) {
    	index = 0;
    	while(index < count) {
    		if(freq[index].alpha == str[i]) {
    			break;
    		}
    		index++
    	}
    	
    	if(index < count) {
    		freq[count].freq++;
    	} else {
    		freq[count].alpha = str[i];
    		freq[count].freq = 1;
    		count++;
    	}
    }

    但是,这样做有一个很大的缺点:随着字符串的增多,查找次数就会越来越多,极端情况下,没有重复的字符,那么就要执行n-1次,光一个统计字符的函数,其时间复杂度就达到了O(n^2);这显然是不合理的。因此,有一个更好的算法:构建一个大的数组,以字符的ASCII码值当下标,字符频度当对应下标的值,实现用空间,换时间的目的。例如'A'的频度,永远存放在下标为65的元素中。这样做,其时间复杂度达到了O(n)。

    2、初始化哈夫曼表

    结构体定义:

    typedef struct HUFFMAN_TAB {
    	ALPHA_FREQ alphaFreq;
    	int leftChild;
    	int rightChild;
    	boolean visited;
    	char *code;
    } HUFFMAN_TAB;
    HUFFMAN_TAB *initHuffmanTab(ALPHA_FREQ *alphaFreq, int alphaVariety, int *hufIndex) {
    	int i;
    	HUFFMAN_TAB *huffmanTab = NULL;
    
    	huffmanTab = (HUFFMAN_TAB *) calloc(sizeof(HUFFMAN_TAB), 2 * alphaVariety - 1);
    	//huffmanTab申请了 2 * alphaVariety - 1大小的空间,在这只用了 alphaVariety个,还剩alphaVariety - 1个
    	for(i = 0; i < alphaVariety; i++) {
    		hufIndex[alphaFreq[i].alpha] = i;	//把哈夫曼表中的字符和其对应的下标形成键值对,存到hufIndex中
    		huffmanTab[i].alphaFreq = alphaFreq[i];
    		huffmanTab[i].leftChild = huffmanTab[i].rightChild = -1;
    		huffmanTab[i].visited = FALSE;
    		huffmanTab[i].code = (char *) calloc(sizeof(char), alphaVariety);
    	}
    
    	return huffmanTab;
    }

    字符种类个数即为哈夫曼树的叶子结点个数,那么,根据完全二叉树的性质,这个哈夫曼树的总结点数为叶子节点数加度为2的节点数,所以,n总 = 2 * n0 - 1。先构建出哈夫曼表,为后面构建哈夫曼树做准备。注意,需设置一个visited成员来表示结点有没有被访问过。

    例如:字符串为“siytweusitweusitweusitwesitesitesitesieieieeeeee”,那么,统计出的结果为这样:

    根据这个哈夫曼表,可以画出哈夫曼树的结构了,如下:

    3、生成哈夫曼树

    生成哈夫曼树,我们需要把频度大的节点放在离根近的地方,频度小的节点放在离根远的地方。所以,需要进行最小字符频度的查找。

    int getMinFreq(HUFFMAN_TAB *huffmanTab, int count) {
    	int index;
    	int minIndex = NOT_INIT;
    
    	for(index = 0; index < count; index++) {
    		if(FALSE == huffmanTab[index].visited) {
    			if(NOT_INIT == minIndex || huffmanTab[index].alphaFreq.freq < huffmanTab[minIndex].alphaFreq.freq) {
    				minIndex = index;
    			}
    		}
    	}
    	huffmanTab[minIndex].visited = TRUE;
    
    	return minIndex;
    }
    void creatHuffmanTree(HUFFMAN_TAB *huffmanTab, int alphaVariety) {
    	int i;
    	int leftChild;
    	int rightChild;
    
    	//huffmanTab使用剩下的 alphaVariety - 1个空间
    	for(i = 0; i < alphaVariety - 1; i++) {
    		leftChild = getMinFreq(huffmanTab, alphaVariety + i);
    		rightChild = getMinFreq(huffmanTab, alphaVariety + i);
    		huffmanTab[alphaVariety + i].alphaFreq.alpha = '#';
    		huffmanTab[alphaVariety + i].alphaFreq.freq = huffmanTab[leftChild].alphaFreq.freq
    																									 + huffmanTab[rightChild].alphaFreq.freq;
    		huffmanTab[alphaVariety + i].leftChild = leftChild;
    		huffmanTab[alphaVariety + i].rightChild = rightChild;
    		huffmanTab[alphaVariety + i].visited = FALSE;
    	}
    }

    生成的哈夫曼树的表格形式如下

    4、生成哈夫曼编码

    哈夫曼树都已经生成,那么就需要生成哈夫曼编码了。

    思路:需要把哈夫曼树从根节点除法,进行遍历,向左子树为‘1’,右子树为‘0’;若碰到叶子结点,需要把编码存给对应的字符。若没有碰到叶子结点,则需要继续向下遍历。所以,这需要一个递归程序完成。

    void makeHuffmanCode(HUFFMAN_TAB *huffmanTab, int root, int index, char *code) {
    	if(huffmanTab[root].leftChild != -1 && huffmanTab[root].rightChild != -1) {
    		code[index] = '1';
    		makeHuffmanCode(huffmanTab, huffmanTab[root].leftChild, index + 1, code);
    		code[index] = '0';
    		makeHuffmanCode(huffmanTab, huffmanTab[root].rightChild, index + 1, code);
    	} else {
    		code[index] = 0;
    		strcpy(huffmanTab[root].code, code);
    	}
    }

    5、把哈夫曼编码以二进制位形式写入目标文件中

    此时,我们需要考虑一个问题。如果,光把“siytweusitweusitweusitwesitesitesitesieieieeeeee”这个字符串的哈夫曼编码以二进制形式写入目标文件,形成的目标文件中全是0101这种二进制代码,那如何解密呢?没有人能看懂这种二进制代码,所以,我们需要给目标文件的头部写入元数据(解释数据的数据),这些元数据主要包括源文件字符种类,字符频度。有了元数据,那么,就可以在解压缩程序中再构造一个完全相同的哈夫曼树,完成解压缩。

    所以,我们也可以构造我们的文件头部元数据,定义一个结构体如下:

    typedef struct HUF_FILE_HEAD {
    	unsigned char flag[3];				//压缩二进制文件头部标志 ycy
    	unsigned char alphaVariety;		//字符种类
    	unsigned char lastValidBit;		//最后一个字节的有效位数
    	unsigned char unused[11];			//待用空间
    } HUF_FILE_HEAD;								//这个结构体总共占用16个字节的空间

    依次给文件头部写入头部标志“ycy”, 字符种类alphaVariety, 最后一字节的有效位数lastValidBit。

    HUF_FILE_HEAD fileHead = {'y', 'c', 'y'};
    fileHead.alphaVariety = (unsigned char) alphaVariety;
    fileHead.lastValidBit = getlastValidBit(huffmanTab, alphaVariety);
    
    fwrite(&fileHead, sizeof(HUF_FILE_HEAD), 1, fpOut);
    fwrite(alphaFreq, sizeof(ALPHA_FREQ), alphaVariety, fpOut);

    lastValidBit计算过程:

    //取最后一个字节的有效位数
    int getlastValidBit(HUFFMAN_TAB *huffmanTab, int alphaVariety) {
    	int sum = 0;
    	int i;
    	
    	for(i = 0; i < alphaVariety; i++) {
    		sum += strlen(huffmanTab[i].code) * huffmanTab[i].alphaFreq.freq;
    		//如果不执行这一步,当数据长度超过int的表示范围,就会出错
    		sum &= 0xFF; //0xFF化为二进制位1111 1111,这样做sum始终是最后一个字节,8位
    	}
    	//举例:若最后生成7位二进制,划分为一个字节,那么,这一个字节只有7位为有效位,其余都是垃圾位。
    	//我们只需要取出这个字节的那7个有效位,所以sum和8取余即可
    	//sum = sum % 8 <=> sum = sum & 0x7
    	//返回最后一个字节的有效位数
    	sum &= 0x7;
    		
    	return sum == 0 ? 8 : sum;
    }

    完后,我们的.ycyHuf文件头部就写好了:

    头部元数据写好后,就需要写入真正的压缩信息了。但是,如何根据字符,迅速找到其哈夫曼编码呢?有一种笨办法,就是每次都根据当前字符,在哈夫曼表中查找,如果字符匹配,就找到了哈夫曼编码。

    for(i = 0; i < alphaVariety; i++) {
    	if(str[index] == huffmanTab[i]) {
    	hufCode = huffmanTab[i].code;
        }
    }

     但是,这样每次查找进行的比较次数平均为n / 2,若字符串长度为len,则时间复杂度为O(len * n / 2)。所以,这样做不是很好,有一种方法,可以不进行“查找”,就能“查找到”,时间复杂度为O(1); 这样,需要构造出一个“字符”:“下标”的键值对关系,字符可以直接定位,就完成了这个“迅速查找”的任务。所以,我在初始化哈夫曼表initHuffmanTab()函数中,构造了这个键值对关系。

    //构造键值对
    hufIndex[alphaFreq[i].alpha] = i;	//把哈夫曼表中的字符和其对应的下标形成键值对,存到hufIndex中
    //查找
    hufCode = huffmanTab[hufIndex[ch]].code;

    下来,就可以正式的给目标压缩文件中写数据了。

    ch = fgetc(fpIn);
    	while(!feof(fpIn)) {
    		hufCode = huffmanTab[hufIndex[ch]].code;
    		//把每个字符的哈夫曼编码一个一个过。
    		//如果是字符'0',就转换为二进制的0
    		//如果是字符'1',就转换为二进制的1
    		for(i = 0; hufCode[i]; i++) {
    			if('0' == hufCode[i]) {
    				//value为一个字节
    				//从第1位依次赋值,若大于八位(一个字节)了,就写入文件中
    				CLR_BYTE(value, bitIndex);
    			} else {
    				SET_BYTE(value, bitIndex);
    			}
    			bitIndex++;
    			if(bitIndex >= 8) {
    				bitIndex = 0;
    				fwrite(&value, sizeof(unsigned char), 1, fpOut);
    			}
    		}
    		ch = fgetc(fpIn);
    	}
    	//如果最后一次不满一个字节,依然需要写到文件中,注意:写入的最后一个字节可能会存在垃圾位
    	if(bitIndex) {
    		fwrite(&value, sizeof(unsigned char), 1, fpOut);
    	}

     如果遇到了字符‘0’,就利用位运算转换为二进制0,否则,为二进制1。 如果最后一次不满一个字节,依然需要写到文件中,注意:写入的最后一个字节可能会存在垃圾位。

    三:解压缩

    1、统计字符种类和频度

    直接从压缩的文件中的头部读取。先匹配是不是自定义的格式:

    fileHead = readFileHead(sourceFileName);
    if(!(fileHead.flag[0] == 'y' && fileHead.flag[1] == 'c' && fileHead.flag[2] == 'y')) {
    	printf("不可识别的文件格式\n");
    }

     如果是“ycy”,那么再统计字符种类和频度:

    ALPHA_FREQ *getAlphaFreq(char *sourceFileName, int *alphaVariety, HUF_FILE_HEAD fileHead) {
    	int freq[256] = {0};
    	int i;
    	int index;
    	ALPHA_FREQ *alphaFreq = NULL;
    	FILE *fpIn;
    	int ch;
    
    	*alphaVariety = fileHead.alphaVariety;
    	alphaFreq = (ALPHA_FREQ *) calloc(sizeof(ALPHA_FREQ), *alphaVariety);
    	fpIn = fopen(sourceFileName, "rb");
    	//略过前16个字节的元数据
    	fseek(fpIn, 16, SEEK_SET);
    	fread(alphaFreq, sizeof(ALPHA_FREQ), *alphaVariety, fpIn);
    	fclose(fpIn);
    
    	return alphaFreq;
    }

     2、初始化哈夫曼表

    和压缩过程一样。

    3、生成哈夫曼树

    和压缩过程一样。

    4、生成哈夫曼编码

    和压缩过程一样。

    5、从压缩文件中读取二进制信息,还原文件

     应该先利用fseek()函数把文件指针跳过前面的元数据和字符种类及频度,定位到真正需要还原的地方。一位一位的进行判断,'1'向左子树走,'0'向右子树走;若到达叶子结点,向文件中写入叶子结点下标对应的字符。再回到根结点继续;若超过一个字节,8位,则需要读取下一个字节。

    void huffmanDecoding(HUFFMAN_TAB *huffmanTab, char *sourceFileName, char *targetFileName, int alphaVariety, HUF_FILE_HEAD fileHead) {
    	int root = 2 * alphaVariety - 2;
    	FILE *fpIn;
    	FILE *fpOut;
    	boolean finished = FALSE;
    	unsigned char value;
    	unsigned char outValue;
    	int index = 0;
    	long fileSize;
    	long curLocation;
    
    	fpIn = fopen(sourceFileName, "rb");
    	fpOut = fopen(targetFileName, "wb");
    	fseek(fpIn, 0L, SEEK_END);
    	fileSize = ftell(fpIn);	//文件总长度fileSize
    	fseek(fpIn, 16 + 5 * fileHead.alphaVariety, SEEK_SET);	//略过前面16个字节的元数据,5字节的字符种类和频度
    	curLocation = ftell(fpIn);
    	
    	//从根出发,'1'向左子树走,'0'向右子树走,若到达叶子结点,输出叶子结点下标对应的字符。再回到根结点继续。
    	fread(&value, sizeof(unsigned char), 1, fpIn);
    	while(!finished) {
    		if(huffmanTab[root].leftChild == -1 && huffmanTab[root].rightChild == -1) {
    			outValue = huffmanTab[root].alphaFreq.alpha;
    			fwrite(&outValue, sizeof(unsigned char), 1, fpOut);
    			if(curLocation >= fileSize && index >= fileHead.lastValidBit) {
    				break;
    			} 
    			root = 2 * alphaVariety - 2;
    		}
    		
    		//取出的一个字节从第一位开始看,'1'向左子树走,'0'向右子树走
    		//若超过一个字节,8位,则需要读取下一个字节
    		if(GET_BYTE(value, index)) {
    			root = huffmanTab[root].leftChild;
    		} else {
    			root = huffmanTab[root].rightChild;
    		}
    		if(++index >= 8) {
    			index = 0;
    			fread(&value, sizeof(unsigned char), 1, fpIn);
    			curLocation = ftell(fpIn);
    		}
    	}
    
    	fclose(fpIn);
    	fclose(fpOut);
    }

    五:结果演示

    六:总结

    哈夫曼压缩与解压缩的项目完成了(以后还会继续完善,优化)。这个项目涉及了C语言里更加高级的操作(文件,位运算,主函数带参······)。哈夫曼压缩与解压缩涉及的知识是我目前以来接触的项目里最多,最广的,收获很多。经过这个练习,还是觉得写程序前,一定一定要认真,仔细的进行手工过程的分析,一定要分析的很到位,否则,程序的逻辑就会出错,酿成大错。最后,不要忘记free申请的空间,以免造成内存泄漏。

    七:源码地址

    https://github.com/yangchaoy259189888/Huffman-compress/

    纠错:
    感谢下面这位前辈指出的这两个问题,经过测试,确实,当初测试了一个bmp文件,成功压缩和解压缩之后,以为大功告成。其实,还有很多极端情况没有考虑到。比如:一个全是a的txt文件就会失败。

    本人能力有限,毕竟这个代码不是我一个人从头到尾完成的,其中的很多思想都来自教主。

    还请看到的大神和我沟通,争取把这个错误解决······

    展开全文
  • 因而下载完会出现压缩文件解压缩失败解决方法:下载时重命名为带一定顺序的文件名,如文件1,文件2,文件3等如何解决单个文件解压失败?论坛中的许多资料都是使用RAR压缩的,上传到下载,在解压过程中可能会出现错误...

    附件经常会是一系列的压缩文件,下载是默认文件名是一个随机数字。

    因而下载完会出现压缩文件解压缩失败

    解决方法:下载时重命名为带一定顺序的文件名,如文件1,文件2,文件3等

    如何解决单个文件解压失败?

    论坛中的许多资料都是使用RAR压缩的,上传到下载,在解压过程中可能会出现错误。一般出现最多的是“CRC”错误,就是在解压末端出现了错误。主要的原因是:1.源文件就有压缩的错误;2. 下载的时候由于线程太多,在收尾的时候出现了错误;3.下载没有完全。

    解决的办法:一、修复。

    1、首先打开WinRAR主窗口,从地址栏转入受损压缩文件所在的目录,选中受损的压缩文件。

    2、用鼠标点击WinRAR工具栏上的“Repair”,然后在下拉菜单上选中“Repair archiver”,这时WinRAR会弹出一个对话框,让你选择修复文件的存放路径。

    3、设定好后点击“OK”确定,WinRAR就会开始对受损的压缩文件进行修复,并会以对话框的形式显示修复的全过程。

    4、进入你设定的修复文件的存放目录,你会发现该目录下增加了一个名为_reconst.rar或_reconst.zip的压缩文件,它就是WinRAR为你修复好的文件。试着对它进行解压缩,如果一切正常,那么恭喜你,你的受损的压缩文件已经修复了!

    需要说明的是,WinRAR内置的压缩文件修复功能并非对于所有受损的压缩文件都有效,对于那些受损严重的压缩文件,WinRAR也会变得无能为力,或者只能修复压缩包中的某些文件。

    我采用的方法很简单:在没有解压完(提示出错的情况下)拷贝文件到其它目录,等解压完成,OK,文件依然好用,这个方法应该是有针对性地,还是枚举一下网络的做法。

    网络的方法:

    办法一:WinRAR本身就带有压缩包修复功能。点击菜单“工具”下的“修复压缩文件”即可,快捷键是“ALT+R”。此法可修复一部分压缩包的常规错误,但是成功率不高。你可以试着连续修复几次。WinRAR的这个功能对压缩包里有很多文件且文件容量都比较小的情况比较适用。

    办法二: 打开压缩包(不是解压,而是用WinRAR打开),选中你要解压缩的文件,单击鼠标右键,在弹出的菜单里选择“无需确认直接解压缩”,快捷键是“ALT+W”。用此方法,不管是好的压缩包还是坏的压缩包,统统畅行无阻,成功率100%!

    办法三:釜底抽薪法!

    其原理就是让RAR压缩包内损坏的文件解压缩出来,不理会WinRAR的警告,能解压多少就解压多少。解压缩软件还是用WinRAR,不过要做小小的设置。

    017244d539d805f3e1aa55604378d3c6.png

    在右键点击解压缩文件后跳出的窗口里,把“保留被损坏的文件”复选框选中,点击确定开始解压缩。不要理会解压缩出错的信息,解压缩结束之后你会发现损坏的文件被解压出来了。经过这样解压出来的损坏文件能正常使用的几率还是非常高的。

    做好保险工作

    1.做好恢复记录

    原始RAR压缩包在压缩时,如果选择放置恢复记录,这样用户下载后即使CRC出错也有自己修复的机会!

    2.采取分卷压缩

    采取分卷压缩的方法便可较大地减少因为出现不可恢复的错误带来的损失。

    3.老文件也加恢复记录

    有人也许会问,新压缩的RAR压缩包可以加入恢复记录,那么已经压缩过的RAR包有没有办法也加上恢复记录呢?给已经压缩好的RAR压缩包加上恢复纪录是有办法的。

    只需要打开压缩包,在“命令”菜单中选择“保护档案文件”即可。

    a8263c4becf7a57110136ae61a7bd79f.png

    小常识:

    其实RAR压缩包出错的解决方法主要是以预防为主!如果没有预防,等到真正出了问题,技术上也是没办法完美解决的!像循环冗余校验码(CRC)出错这种情况,如果RAR压缩包不包含恢复记录的话,用户自己想要修复CRC是不可能的!本文的主要目的是想告诉大家一些出错的原因以及讨论一些从根本上预防出错和把损失减少到最小的办法而已!

    附:

    1.CRC算法原理

    CRC是Cyclic Redundancy Code的缩写,翻译成中文就是“循环冗余码”,它采用多项式编码方法,是一种高效的差错控制方法。所谓的CRC32也就是32位的CRC算法,这就是前面介绍的SFV采用的算法。由于CRC算法编码和解码方法简单,检错和纠错能力强,因此在通信、卫星、控制等领域都有着广泛的应用,在我们的电脑中,也被广泛应用于压缩,光盘刻录、数据存储等方面。

    其实说到CRC,大家更多想到的就是压缩软件,因为许多朋友都遇到过压缩软件提示“CRC错误”,这实际上就是一种文件校验过程,只不过这个过程被自动化了:压缩软件在压缩文件时自动在压缩包内添加CRC校验信息,在解压缩时会自动对CRC进行校验,检查文件是否完整和正确。

    实战:CRC错误的解决方法

    现象一:最近WinRAR不论解压缩什么文件,都是提示“CRC 校验失败,文件被破坏”。

    解决方案:出现这种情况,可能是WinRAR的临时文件保存出现了问题,一般只需要打开系统临时目录(Windows 2000/XP下为/Documents and Settings/用户名/Local Settings/Temp),删除其中名为“Rar$DI00.*”之类的文件夹即可。

    现象二:刚下载的一个软件压缩包,使用WinRAR解压时提示某个文件“CRC 校验失败,文件被破坏”。

    解决方案:这种情况可以判断是那个压缩包出了问题,但很多情况下出现CRC错误时并不代表整个压缩包都已经坏掉,很可能只是某个文件有部分损坏。你可以尝试使用“命令”菜单中的“修复压缩文件”,一般可以解决部分CRC错误的问题。如果仍然不能解决,你可以尝试一下强制解压技巧:首先打开压缩包,选择除那个CRC错误文件以外的所有文件,先将正常的文件解压出来,然后解压那个出错的文件,当提示CRC错误信息时,不要点击任何确认按钮,打开“资源管理器 ”,找到解压后的文件保存路径,可以看到那个出错的文件实际已经被解压了,把它复制到其他文件保存的文件夹中,然后再试试看程序能否正常运行,很多情况下,如果这个文件不是可执行程序,对运行的影响不是很大。

    简单方便的WinRAR用户身份校验

    WinRAR本身除了具备CRC自动校验功能外,还为用户提供了专门的身份校验功能,可以帮助用户了解自己的压缩包是否被人修改过。

    实战:制作一个“只许用不许改”的压缩包

    在“资源管理器”中选择要压缩的文件,单击鼠标右键,选择“添加到压缩文件”,打开“压缩文件名和参数”窗口,勾选“压缩选项”中的“添加用户身份校验信息”选项,单击“确定”按钮生成压缩包。

    双击打开这个压缩包,可以在地址栏中看到“用户校验信息存在”的提示,单击菜单“命令→显示信息”打开对话框,在“用户身份校验信息”栏中可以看到该压缩包的文件名、创建者以及创建日期信息(见图1),记下这些信息,尤其是“创建者”中的信息。

    ee3d4e8b487dba981a0b7b28ea29ee0c.png

    现在你可以把这个压缩包提供给接收方,并同时提供用户身份校验信息。当对方打开这个压缩包时,可以打开“显示信息”对话框,并与你提供的身份校验信息进行比对,如果完全一样的话,说明压缩包没有被修改过,如果身份校验信息不存在或者有了变化,则说明压缩包已经被修改过了。

    小提示

    该功能需要使用注册版的WinRAR,因为身份校验信息就是根据注册用户名来生成的,一个被添加了身份校验信息的压缩包被重新修改时,将丢失身份校验信息,这就是它的校验原理。

    展开全文
  • 软件压缩/解压缩软件Szip(Huffman算法及应用) 1.需求规格说明 【问题描述】 利用哈夫曼树编码进行对已有文件进行重新编码可以大大提高减小文件大小,减少存储空间,但是,这要求在首先对一个现有文件进行编码形成...

    软件压缩/解压缩软件Szip(Huffman算法及应用)

    完整代码下载地址

    1.需求规格说明

    【问题描述】

    利用哈夫曼树编码进行对已有文件进行重新编码可以大大提高减小文件大小,减少存储空间,但是,这要求在首先对一个现有文件进行编码形成新的文件,也就是压缩。在文件使用时,再对压缩文件进行解压缩,也就是译码,复原原有文件。试为完成此功能,写一个压缩/解压缩软件(控制台程序,不要求界面)

    【基本要求】(60%)

    一个完整得系统应具有以下功能:
    (1)压缩准备。读取指定被压缩文件,对文件进行分析,建立哈夫曼树,并给出分析结果(包括数据集大小,每个数据得权值,压缩前后文件得大小),在屏幕上输出。
    (2)压缩。利用已建好的哈夫曼树,对文件进行编码,并将哈夫曼编码及文件编码后的数 据一起写入文件中,形成压缩文件(**.Haf)。
    (3)解压缩。打开已有压缩文件(*.Haf),读取其中的哈夫曼编码,构建哈夫曼树,读取其 中的数据,进行译码后,写入文件,完成解压缩。
    (4)程序使用命令行方式运行
    压缩命令 :SZip A Test.Haf 1.doc
    解压缩命令:SZip X Test.Haf 2.doc 或 SZip X Test.Haf
    用户输入的命令不正确时,给出提示。
    (5)使用面向对象的思想编程,压缩/解压缩、哈夫曼构建功能分别构建类实现。

    【提高要求】(40%)

    (1)采用不同的数据集,比较其压缩比,采用最有效的压缩方式。
    (2)多个文件的压缩。
    (3)试构建程序框架,使其能添加新的压缩/解压缩算法(例如书上 LZW 压缩算法)。

    2.总体分析与设计

    (1)设计思想:

    【存储结构】

    1、构建一个哈夫曼树结点的结构体,其中包括记录结点权值的数据元素、记录结点双亲位置及左右孩子位置的数据元素、记录结点哈夫曼编码的int型指针、记录结点哈夫曼树编码长度的数据元素。
    2、利用动态数组来保存哈夫曼编码。
    3、本题通过构建哈夫曼树来进行压缩和解压缩,当压缩式即从下至上建树,解压缩时即从上至下读树。

    【主要的算法思想】

    本题需要我们运用哈夫曼树的算法来实现软件的压缩和解压,而压缩即可以理解为从下至上建树,解压缩时即可以理解为从上至下读树。
    在压缩时,我们首先要把需要压缩的文件用二进制的形式打开,然和把其中的字符转换成ascll码,然后进行对比,把具有相同ascll码的字符统计出来进行归类,并计算同类字符的权重,根据权重从下至上建立哈夫曼树,再生成哈夫曼编码(其中,权重大的结点哈夫曼编码短,权重小的结点哈夫曼编长,),然后把哈夫曼编码列出来后,8位进1(1Byte=8 Bit),当后面的哈夫曼编码不足八位时 则要在其后边进行补0后向进1,然后再将所有的字节输出到文件中,形成压缩文件。
    在解压缩时,我们同样是要把需要解压缩的文件用二进制的方式进行打开,然后从上至下的读取哈夫曼树,读取哈夫曼编码,将哈夫曼编码装换成编码前对应的内容,即分别对应哈夫曼树中结点的内容,这里要注意的是我们读取的最后一个字节可能是不足8位的,所以我们要注意记录不足八位时的缺省个数,然后再分别对应哈夫曼树中的数据,从而实现解压操作,最后把解压后的内容输出即可。
    最后编写计算文件内占用字节大小的函数,再根据占用内存大小计算压缩率;然后通过对比压缩前和解压后文件内每个字符是否一致来判断解压前和解压后的文件内容是否完全一致。

    (2)设计表示:

    在这里插入图片描述
    在这里插入图片描述

    (3)详细设计表示:

    1、countFrequency()统计字符出现次数
    首先以二进制方式打开文件,然后读取其中的字符,判断这个字符是否是第一次出现,如果是就把它初始化,然后叶子结点总数加一要是不是第一次出现,就把权值加1。
    2、createHuffmanTree()建哈夫曼树
    先找出两个权值最小的结点然后建树,一直到最后只有一棵树,为了减少压缩文件中需要写入的huffman树的信息,约定小标小的结点做为双亲结点的左孩子。
    3、calculateCode() 计算哈夫曼编码
    从下往上一直找到根节点,然后一层一层加,计算哈夫曼的长度然后再从上往下找,左孩子编码0,右孩子编码1。
    4、addBit(int bit)对一个未满8bit的byte中加入一个bit
    如果新增的为0,直接就左移;如果新增为1,就先左移然后与1按位或。
    5、resetByte()将byte清空
    将byte与byte中bit的个数都赋值0,即清空。
    6、doCompress(…)压缩函数
    调用前面编写的函数,首先计算每个字符的权值,再根据权值大小建立哈夫曼树,再给树上的结点进行哈夫曼编码,然后把哈夫曼树从上之下将结点位置写入输出文件;将字符的哈夫曼编码写入byte中,即八位算一字节,如果满了就输出字节,并将原字节清空,然后把不足8位的后面补0,然后输出,再清空。
    7、doDecompress(…)解压函数
    首先读出根节点的位置,然后确立各个几点之间的双亲关系(先左后右),然后方便读取 将数据放入队列,由于在压缩的时候是从上之下存入到文件当中的 所以这个时候直接依此弹出队顶元素即可实现从上至下读树,然后八位一循环,分别与哈夫曼树的左右孩子进行比较,找出哈夫曼编码最后一个字原本对应的内容,注意最后不足8位的字节要单独处理。

    3.编码

    1、编码过程中遇到一些问题,在建立huffman树时不知如何在压缩过程中同时进行编码和建树,不知如何存放编码,编码必须要存储才能建立有效的huffman树。后来想到可以用动态数组保存huffman编码,由于编码长度不定,用动态数组可以弥补这个空缺。
    2、对于不满足八位的字符,最开始没预想到这种情况,压缩过程中出现错误,后来通过同学的提醒,才意识要进行补位的操作。若新增的bit为0,则直接将byte按位左移;新增的bit为1,先将byte按位左移,再与1按位或运算的规律进行补位操作。补位时,还需要预留一个字符,等压缩完后在该位置写入不足一个byte的bit个数。
    3、在测试过程中,解压缩后的文件总是会比原文件大一点,而文件内容的最后总会出现一些乱码,后来通过调试和查找相关资料,我明白了,在ofstream中自带一种文件流指针,便于我们读取文件中的字符,在我压缩的过程当中,压缩到最后,这个文件流指针就走到了文件的最后,而该指针占用一i定的内存,所以在压缩过程中把该指针也进行了压缩,解压缩时自然也输出了该指针,所以会出现解压缩后的文件要比原文件大,所以我在压缩函数中增加了ofsFile.seekp(0, ios::beg);函数,将写指针移动到文件开头,从而解决了该问题。

    4.程序及算法分析

    【使用说明】

    在这里插入图片描述
    输入文件存储的位置,压缩/解压缩文件
    (写博客的时候才发现,我这里给的执行命令好像和老师要求的执行命令不一样,不过是小问题哈哈,读者私下自己改一下好了😁)

    【测试数据】

    1、压缩文件

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    2、解压缩文件

    在这里插入图片描述
    在这里插入图片描述

    3、对比原文件与解压缩后的文件

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    【讨论与分析】

    Huffman压缩以字节为单位进行压缩,将8个bit作为一个byte,通过对bit进行操作,以达到压缩与解压的目的

    【改进设想】

    1、我现在只实现了基本要求,没能实现多个文件的同时压缩
    2、我的压缩算法不是很好,以至于我的压缩率比较大,日后还需要多多学习才能逐步提高自己的能力

    5.附录

    【压缩函数核心代码】

    //压缩函数 成功执行返回 true 失败 false
    bool HuffmanTree::doCompress(char *pcInput, char *pcOutput)
    {
    	if (!countFrequency(pcInput))              //如果不能计算字符出现的次数就返回false 可以计算就继续执行程序
    		return false;
    
    	createHuffmanTree();
    	calculateCode();
    	ifstream ifsFile;
    	ofstream ofsFile;
    	
    	ifsFile.open(pcInput, ios::binary);
    	ofsFile.open(pcOutput, ios::binary);
    	
    	char c;
    	if (!ifsFile){
    		cout << "Unable to open the file" << pcInput << '!' << endl;
    		return false;
    	}
    	if (!ofsFile){
    		cout << "Unable to open the file" << pcOutput << '!' << endl;
    		return false;
    	}
    
    	//输出huffman编码
    	/*while (ifsFile.get(c))
    	{					                     
    		int _nTem = c + 128;
    		for (int i = 0; i < HT[_nTem].nCodeLenght; i++)
    		{
    			ofsFile << HT[_nTem].pnCode[i] << endl;
    		}
    	}*/
    
    	
    	ofsFile.put(0);	                         //预留一个字符,等压缩完后在该位置写入不足一个byte的bit个数
    	ofsFile.put(mnRoot - 384);	             //将根节点的位置-384写入(为使该值不超过char的最大表示范围)
    	                                         //384=256+128
    	for (int i = 0; i<nLeaf * 2 - 1; i++)    //从上往下
    	{		                                 //写入每个结点的双亲结点位置
    		if (HT[i].nParent == -1)	         //若该节点没有双亲结点,则写入127(一个字节所能表示的最大值2⁷-1=128-1=127)
    			ofsFile.put(127);
    		else	                             //否则将双亲结点的位置-384再写入(为使该值不超过char的最大表示范围)
    			ofsFile.put(HT[i].nParent - 384);
    	}
    
    	while (ifsFile.get(c))
    	{					                     //将字符的huffman编码并加入byte中
    		int _nTem = c + 128;
    		
    		for (int i = 0; i < HT[_nTem].nCodeLenght; i++)
    		{
    			//ofsFile.put(HT[_nTem].pnCode[i]);
    			addBit(HT[_nTem].pnCode[i]);     //将字符的huffman编码并加入byte中
    			if (mnBitsNum == 8)
    			{		                         //若byte已满8位,则输出该byte并将byte清空
    				ofsFile.put(mcByte);
    				resetByte();
    			}
    		}
    	}
    	if (mnBitsNum != 0){
    		//满足8位的前面已经通过resetByte()函数清空了 mbitsNum置为0 而不满足8位的执行下面语句
    		//处理最后未满8个字符的byte,用0填充并记录填充的个数
    		for (int i = mnBitsNum; i<8; i++)
    		{
    			addBit(0);
    			mnLackNum++;
    		}
    
    		ofsFile.put(mcByte);                       //再输出and清空
    		resetByte();
    	}
    	ofsFile.seekp(0, ios::beg);	                  //将写指针移动到文件开头(文件流指针)
    	ofsFile.put(mnLackNum);		                  //写入最后一个字节缺失的bit个数
    	ifsFile.close();
    	ofsFile.close();
    
    	return true;
    }
    

    【解压缩函数核心代码】

    //解压缩函数 成功执行返回 true 失败 false
    bool HuffmanTree::doDecompress(char *pcInput, char *pcOutput)
    {
    	queue<char> q;
    	char c;
    	ifstream ifsFile;
    	ofstream ofsFile;
    	ifsFile.open(pcInput, ios::binary);
    	ofsFile.open(pcOutput, ios::binary);
    	if (!ifsFile)
    	{
    		cout << "Unable to open the file" << pcInput << '!' << endl;
    		return true;
    	}
    	if (!ofsFile)
    	{
    		cout << "Unable to open the file" << pcOutput << '!' << endl;
    		return false;
    	}
    
    	ifsFile.get(c);
    	mnLackNum = c;                 	         //读出最后一个字节缺失的bit个数
    	ifsFile.get(c);
    	mnRoot = c + 384;	                     //读出根结点的位置
    	for (int i = 0; i < nLeaf * 2 - 1; i++)
    	{		                                 //建立各结点之间的双亲孩子关系
    		ifsFile.get(c);
    		if (c == 127)                        //等于127->根节点
    			continue;
    		else
    		{
    			HT[i].nParent = c + 384;
    			if (HT[c + 384].nLeftChild == -1)//双亲孩子关系——先左后右
    				HT[c + 384].nLeftChild = i;
    			else
    				HT[c + 384].nRightChild = i;
    		}
    	}
    
    	int _nPoint = mnRoot;
    
    	//为了方便处理最后一个可能有缺失bit的字节,先将读出的数据放入队列
    	while (ifsFile.get(c))
    		q.push(c);
    
    	//还原文件过程
    	while (q.size()>1)
    	{	                                     //还未到最后一个字节
    		c = q.front();                       //返回队顶元素
    		for (int i = 0; i < 8; i++)
    		{                                    //先左后右
    			if (int(c & 128) == 0){
    				_nPoint = HT[_nPoint].nLeftChild;
    
    				//这个左孩子没有左孩子也没有右孩子就把这个输出
    				if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1)
    				{
    					ofsFile.put(char(_nPoint - 128));
    					_nPoint = mnRoot;          //更新
    				}
    				c = c << 1;
    			}
    			else
    			{
    				_nPoint = HT[_nPoint].nRightChild;
    				if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1)
    				{
    					ofsFile.put(char(_nPoint - 128));
    					_nPoint = mnRoot;
    				}
    				c = c << 1;
    			}
    		}
    		q.pop();                             //弹出队顶元素
    	}
    
    	c = q.front();						     //最后一个字节
    	for (int i = 0; i < 8 - mnLackNum; i++)   //原理同上
    	{
    		if (int(c & 128) == 0)
    		{
    			_nPoint = HT[_nPoint].nLeftChild;
    			if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1)
    			{
    				ofsFile.put(char(_nPoint - 128));
    				_nPoint = mnRoot;
    			}
    			c = c << 1;
    		}
    		else{
    			_nPoint = HT[_nPoint].nRightChild;
    			if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1)
    			{
    				ofsFile.put(char(_nPoint - 128));
    				_nPoint = mnRoot;
    			}
    			c = c << 1;
    		}
    	}
    	q.pop();
    	ifsFile.close();
    	ofsFile.close();
    	return true;
    }
    

    注:点击此处下载源代码程序包,感谢阅读~

    展开全文
  • shell命令之解压缩

    千次阅读 2013-08-08 09:47:56
    范例三:将 /tmp/etc.tar.gz 文件解压缩在 /usr/local/src 底下 [root@linux ~]# cd /usr/local/src [root@linux src]# tar -zxvf /tmp/etc.tar.gz # 在预设的情况下,我们可以将压缩档在任何地方解开的!...
  • 一.图像从文件到屏幕过程 通常计算机在显示是CPU与GPU协同合作完成一次... GPU: 纹理混合,顶点变换与计算,像素点的填充计算,渲染到帧缓冲区。 时钟信号:垂直同步信号V-Sync / 水平同步信号H-Sync。 iOS设备...
  • 一.图像从文件到屏幕过程 图片显示到屏幕上是CPU与GPU的协作完成 ... GPU: 纹理混合,顶点变换与计算,像素点的填充计算,渲染到帧缓冲区。 时钟信号:垂直同步信号V-Sync / 水平同步信号H-Sync。 iOS设...
  • WINRAR压缩软件

    2019-01-21 14:07:03
    这款软件中包含的RAR支持在Windows/DOS系统上的命令行操作,格式为: RAR 命令> -开关> 压缩包> 文件...> 解压缩路径\> a 压缩,e、x 解压等常用参数基本无异于DOS版本,可以在批文件中方便地加以引用。...
  • 综述 许多信息资料都或多或少的包含一些多余的数据。通常会导致在客户端与服务器之间,应用程序与计算机之间极大的数据传输量。...这篇文章简要的介绍了数据的压缩与解压缩,并展示了用java.util.zip包来实
  • 既然图片的解压缩需要消耗大量的 CPU 时间,那么我们为什么还要对图片进行解压缩呢?是否可以不经过解压缩,而直接将图片显示到屏幕上呢?答案是否定的。要想弄明白这个问题,我们首先需要知道什么是位图. A ...
  •   linux下的压缩程式有tar、gzip、gunzip、bzip2、bunzip2、compress 、uncompress、 zip、 unzip、rar、unrar等,下面对如何使用它们对.tar、.gz 、.tar.gz、.tgz、.bz2、.tar.bz2、.Z、. tar.Z、.zip、.rar这10...
  • JPEG 图像压缩原理

    千次阅读 2019-10-26 20:24:17
    JPG格式的图片体积相对较小,是因为它采用了一系列的压缩算法,压缩图片弊端就是和原始的图片相比,它牺牲掉了一些画面细节,这些丢失的细节或许可被人的肉眼看出,或许以人的肉眼难以发现,对于这种通过牺牲画面的...
  • 密码破解与HASH计算

    千次阅读 2021-11-19 19:52:32
    ·人工猜 ​ 垃圾桶工程,被动信息收集 ·基于字典暴力破解(主流) ·键盘空间字符爆破 ·字典 ​ 保存有用户名和密码的文本文件(kali自带的字典) -/usr/share/wordlist -/usr/share/wfuzz/wordlist -/usr/...
  • 压缩文件爆破.zip

    2019-06-13 15:31:01
    同一个压缩包,电脑爆破的速度更快和软件没关系主要是电脑运算能力更强,解压我提供的压缩包,双击Ziperello.exe“运行软件”。 导入要爆破的压缩包,在箭头处勾选,然后点击 “nest",勾选所有软件,点击next。 4...
  • 这篇文章主要介绍了如何使用Python破解ZIP或RAR压缩文件密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下我们经常会从网络上下载一些带密码的压缩包,想要...
  • 为了解决扩底桩深基础与普通桩基及浅基础的区分及设计计算,根据均布荷载下的Boussinesq与Mindlin,结合现有文献对"扩底桩"或"扩底墩"等扩底深基础进行界定,对其承载能力特性进行计算分析.结果表明:扩底深基础与普通...
  • 五种CNN模型的尺寸,计算量和参数数量对比详解一、SqueezeNet1.1 设计思想1.2 网络架构1.3 实验结果1.4 速度考量二、Deep Compression2.1 算法流程2.2 模型存储2.3 实验结果2.4 速度考量三、XNorNet3.1 BWN3.2 XNOR-...
  • 常见压缩算法学习

    千次阅读 2020-09-25 13:54:40
    文章目录无损压缩算法理论基础信息熵熵编码字典编码综合通用无损压缩算法相关常见名词说明java对几种常见算法实现Snappydeflate算法Gzip算法huffman算法Lz4算法Lzo算法使用方式 无损压缩算法理论基础 信息熵 信息熵...
  • 通过引入反馈神经网络(recurrent neural network,RNN)模型求解l1范数最小化优化问题,计算RNN的稳态以恢复稀疏信号。对不同方法的测试结果表明,提出的方法在恢复稀疏信号时所需的观测点数最少,并且可推广到...
  • 基于KaKadu的JPEG2000解压缩算法的改进

    千次阅读 2013-10-27 14:57:20
    网络上可以找到的KaKadu源程序版本都... 解压缩的输入参数主要有3个:解压缩基本参数,这些基本参数包括质量层数量、质量层码率、切片大小等;输入文件格式,KaKadu可识别的压缩图像文件格式为:jp2、jpx;压缩图像数
  • Liunx解压缩命令参数详解

    千次阅读 2012-04-11 15:04:08
    一、Linux常用的压缩及解压缩命令如表2-5所示。 常用命令 简要中文说明 程序所在目录 gzip 压缩成文件名为 .gz 的压缩文件(也可用 –d 选项变成解压) /bin ...
  • 由于国际象棋测试支持CPU多线程,而且它做的是大量科学计算,所以经常被用来测试电脑的科学运算能力,该软件通过模拟AI思考国际象棋的算法来测试被测电脑的国际象棋运算能力。国际象棋测试成绩测试成绩对比wPrime是...
  • 转码解密挖矿 显卡计算能力大对比

    千次阅读 2019-02-01 12:04:00
    GPU通用计算发展势头迅猛 泡泡网显卡频道8月27日现在的显卡市场,同质化已经严重到了什么地步呢?不仅仅是板卡厂商之间的显卡性能基本没区别,而且同价位的N卡和A卡在不同游戏中的表现也是难分胜负,让游戏玩家...
  • 性能提升方法 本文github链接 1. 小模型 mobilenet , 更精细模型的设计,紧致网络设计 mobilenet squeezenet shufflenet MobileNet逐通道卷积 + 普通点...2. 模型压缩:参数稀疏、剪裁、量化、分解 ...
  • Huffman编码之文件的/压缩

    千次阅读 2016-06-16 00:00:25
    史上最具人性化的文件压缩详述,基于Huffman算法的文件压缩项目,还在为找练习项目而苦恼?还在为Huffman算法困惑?还在为文件压缩一头雾水?来吧,,,一起学习,共同进步.....
  • 另一方面,gzip在压缩/解压缩时间方面具有最佳性能,而PPM的压缩/解压缩时间要慢得多。 bzip2位于两个指标的中间。 因此,就这两个指标而言,用户对要使用的压缩机的选择主要取决于用户场景的要求。 不可查询(归档...
  • 解压缩内核

    千次阅读 2010-12-31 22:24:00
    4.2.2解压缩内核解压缩内核使用的是decompress_kernel函数,来自arch/x86/boot/compressed/misc.c:301asmlinkage void decompress_kernel(void *rmode, memptr heap, 302 unsigned char *input_data, 303 ...
  • Android 图片压缩详解

    千次阅读 2020-06-30 19:50:06
    Android中图片是以bitmap形式存在的,那么bitmap所占内存,直接影响到了应用所占内存大小,首先要知道bitmap所占内存大小计算方式:图片宽度 x 图片高度 x 单位像素占用的字节数 以下是图片的压缩格式:其中,A代表...
  • rar压缩软件.rar

    2016-02-13 10:52:44
    RAR 是一个让你在命令行模式中管理压缩文件的控制台应用。RAR 提供压缩、加 密、数据恢复和许多其它此手册中描述的其它功能。 RAR 只支持 RAR 格式压缩文件,它默认有 .rar 扩展名。不支持ZIP 和其他格 式。即使...
  • 首先下载两个库, 一个是 libpng , 另一个则是 zlib 库, zlib 库是一套用于压缩数据的库, libpng 借助了该库作为压缩引擎, 也就是说, libpng 依赖于 zlib 库。 关于这两个库的版本选择, 最新版本的 libpng 和 zlib...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 40,107
精华内容 16,042
关键字:

解压缩 运算能力