精华内容
下载资源
问答
  • 基于哈夫曼编码的文本文件压缩与解压缩,使用c语言,实际只是编码解码,不应该称为解压缩,因为编码后文件会更大
  • 使用matlab 实现的封装好的霍夫曼压缩编码 以及对应的解压缩编码。可以直接对一串数据进行压缩。
  • 哈夫曼压缩与解压缩

    万次阅读 多人点赞 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文件就会失败。

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

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

    展开全文
  • 哈夫曼压缩与解压缩(c语言版)

    千次阅读 多人点赞 2019-09-29 19:18:13
    哈夫曼压缩与解压缩(c语言版) 一:引言 二:主要原理 三:主要技术点 四:实现过程 1.压缩: 2.解压缩: 五:详细分析,及代码实现 哈夫曼压缩与解压缩(c语言版) 一:引言 学过数据结构的同学,应该都...

    目录

    哈夫曼压缩与解压缩(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;  
    }

    展开全文
  • 哈夫曼树实现文件压缩与解压缩

    万次阅读 多人点赞 2016-06-06 21:23:14
    见识了360压缩的神奇后,想要实现自己的文件压缩程序,然后花了近一个星期的时间去完成文件压缩与解压缩,期间有很多坑,花了很长时间去调试它,最后把坑给填了(真心的感受到了程序员写代码时的小小粗心会把自己给...

           见识了360压缩的神奇后,想要实现自己的文件压缩程序,然后花了近一个星期的时间去完成文件压缩与解压缩,期间有很多坑,花了很长时间去调试它,最后把坑给填了(真心的感受到了程序员写代码时的小小粗心会把自己给坑惨)。以下是些程序时的一些坑:

    1. 在windows下回车的字符是‘\r’'\n',编译器在读取字符时读取到'\r'后再读取到'\n'就会转换为回车。。。
    2. 在解压缩小文件时不会出现的问题在解压缩大文件时会出现。最常见的时没有解压缩完文件就退出了,因为会出现一些控制字符导致程序提前退出。
    3. 压缩汉字的时候 要使用unsigned char!!!

        正如标题所说,实现文件压缩我是使用哈夫曼树产生哈夫曼编码,使用哈夫曼编码来压缩文件。

        构造哈夫曼树的key值是文件中每个字符出现的次数。将出现的字符插入一个最小堆中,每次从堆中取出出现次数最少的字符构造哈夫曼树。


    为此,我们先实现一个最小堆:
    #pragma once
    #define _CRT_SECURE_NO_WARNINGS 1
    #include<iostream>
    #include<vector>
    #include<assert.h>
    //#include"HaffmanTree.h"
    using namespace std;
    
    template<class T>
    struct Less
    {
    	bool operator()(const T& l, const T& r)
    	{
    		return l < r;
    	}
    };
    
    
    template<class T>
    struct Greater
    {
    	bool operator()(const T& l, const T& r)
    	{
    		return l > r;
    	}
    };
    
    template<class T>
    struct Less<T*>
    {
    	bool operator()(const T*Nodel, const T*Noder)
    	{
    		return Nodel->_wight < Noder->_wight;
    	}
    };
    
    template<class T,class Continer = Less<T>>//默认为小堆
    class Heap
    {
    public:
    	Heap(){};
    	Heap(const T* a, size_t size,const T& invalid);
    	Heap(vector<T> a);
    	Heap(const vector<T>& v);
    	void Push(const T& x);
    	void Pop();
    	T& GetTop();
    	bool Empty();
    	size_t Size();
    	void HeapSort(T* a, size_t size);
    protected:
    	void _AdjustDown(size_t parent);
    	void _AdjustUp(int child);
    protected:
    	vector<T> _a;
    };
    
    template<class T, class Continer = Less<T>>
    Heap<T, Continer>::Heap(const T* a, size_t size,const T& invalid)
    {
    	_a.reserve(size);
    
    	for (size_t i = 0; i < size; ++i)
    	{
    		if (a[i] != invalid)
    		{
    			_a.push_back(a[i]);
    		}
    	}
    
    	//建堆
    	for (int i = (_a.size() - 2) / 2; i >= 0; i--)
    		//从第一个非叶子结点开始下调,叶子结点可以看作是一个大堆或小堆
    	{
    
    		_AdjustDown(i);
    	}
    }
    template<class T, class Continer = Less<T>>
    Heap<T, Continer>::Heap(vector<T> a)
    {
    	_a.swap(a);
    
    	// 建堆
    	for (int i = (_a.size() - 2) / 2; i >= 0; --i)
    	{
    		_AdjustDown(i);
    	}
    }
    template<class T, class Continer = Less<T>>
    Heap<T, Continer>::Heap(const vector<T>& v)
    	:_a(v)
    {
    	//_a.resize(v.size());
    }
    template<class T, class Continer = Less<T>>
    void Heap<T, Continer>::Push(const T& x)
    {
    	_a.push_back(x);
    	_AdjustUp(_a.size() - 1);
    }
    template<class T, class Continer = Less<T>>
    void Heap<T, Continer>::Pop()
    {
    	assert(!_a.empty());
    	size_t size = _a.size();
    	swap(_a[0], _a[size - 1]);
    	_a.pop_back();
    	_AdjustDown(0);
    }
    template<class T, class Continer = Less<T>>
    T& Heap<T, Continer>::GetTop()
    {
    	return _a[0];
    }
    template<class T, class Continer = Less<T>>
    bool Heap<T, Continer>::Empty()
    {
    	return _a.empty();
    }
    template<class T, class Continer = Less<T>>
    size_t Heap<T, Continer>::Size()
    {
    	return _a.size();
    }
    
    template<class T, class Continer = Less<T>>
    void Heap<T, Continer>::_AdjustDown(size_t parent)
    {
    	Continer _con;
    	size_t child = parent * 2 + 1;
    	size_t size = _a.size();
    	while (child < size)
    	{
    		if (child + 1 < size&&_con(_a[child + 1], _a[child]))
    			//注意这必须是child+1更大或更小,所以把child+1放在前面
    			++child;
    		if (/*_a[parent] < _a[child]*/_con(_a[child], _a[parent]))
    		{
    			swap(_a[parent], _a[child]);
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    			break;
    	}
    }
    template<class T, class Continer = Less<T>>
    void Heap<T, Continer>::_AdjustUp(int child)
    {
    	Continer _con;
    	int parent = (child - 1) / 2;
    	while (child > 0)
    	{
    		if (_con(_a[child], _a[parent]))
    		{
    			swap(_a[child], _a[parent]);
    			child = parent;
    			parent = (child - 1) / 2;
    		}
    		else
    			break;
    	}
    <p>}</p>

        使用类模板实现的小顶堆,方便我们传入哈夫曼结点的结构体,并且实现了比较两个结构体的大小的仿函数。实质是比较_wight值


    实现了堆以后实现哈夫曼树:

    #pragma once
    #include<iostream>
    #include"Heap.h"
    #include"FileComparess.h"
    
    using namespace std;
    
    
    template<class T>
    struct HaffmanNode
    {
    	HaffmanNode<T>* _left;
    	HaffmanNode<T>* _right;
    	T _wight;
    	HaffmanNode(const T& wight)
    		:_left(NULL)
    		, _right(NULL)
    		, _wight(wight)
    	{}
    };
    
    
    template<class T>
    class HaffmanTree
    {
    public:
    	typedef HaffmanNode<T> Node;
    	HaffmanTree(const T* a, size_t size, const T& invalid)
    	{
    		_root = _CreatHaffmanTree(a, size, invalid);
    	}
    	Node* GetRoot()
    	{
    		return _root;
    	}
    protected:
    	Node* _CreatHaffmanTree(const T* a,size_t size, const T& invalid)
    	{
    		Heap<Node*, Less<Node*>> minHeap;
    		for (size_t i = 0; i < size; ++i)
    		{
    			if (a[i] != invalid)
    			{
    				Node* tmp = new Node(a[i]);
    				minHeap.Push(tmp);
    			}
    		}
    		while (!minHeap.Empty())
    		{
    			Node* left = minHeap.GetTop();
    			minHeap.Pop();
    			Node* right = NULL;
    			if (!minHeap.Empty())
    			{
    				right = minHeap.GetTop();
    				minHeap.Pop();
    			}
    			Node* parent = NULL;
    			if (right)
    			{
    				parent = new Node(left->_wight + right->_wight);
    			}
    			else
    			{
    				parent = new Node(left->_wight);
    			}
    			parent->_left = left;
    			parent->_right = right;
    			if (minHeap.Empty())
    			{
    				return parent;
    			}
    			minHeap.Push(parent);
    		}
    		return NULL;
    	}
    protected:
    	Node* _root;
    };
    
         可以看到树节点的_wight成员,建立哈夫曼树时就是依据_wight大小来建立的,也就是文件中各个字符出现的次数。

         构造哈夫曼树时每次从小顶堆中取出堆顶元素插入到哈夫曼树中,当堆中的元素为空时,构造哈夫曼树完成。


    哈夫曼树构造完成开始文件压缩

    #pragma once
    #define _CRT_SECURE_NO_WARNINGS 1
    #include<iostream>
    #include"HaffmanTree.h"
    using namespace std;
    typedef long LongType;
    
    struct CharInfo
    {
    	unsigned char _ch;
    	LongType _count;
    	string _code;
    	CharInfo(const LongType count = 0 )
    		:_count(count)
    	{}
    	CharInfo(const char ch)
    		:_ch(ch)
    	{}
    	bool operator!=(const CharInfo& c)const
    	{
    		return _count != c._count;
    	}
    	CharInfo operator+(const CharInfo& c)const
    	{
    		return CharInfo(_count + c._count);
    	}
    	bool operator<(const CharInfo& c)const
    	{
    		return _count < c._count;
    	}
    };
    
    class FileComparess
    {
    public:
    	//文件压缩
    	void Comparess(const char* filename)
    	{
    		FILE* fread = fopen(filename, "rb");
    		if (fread == NULL)
    		{
    			cout << "打开待压缩文件失败" << endl;
    			return;
    		}
    		for (int i = 0; i < 256; i++)
    		{
    			_info[i]._ch = i;
    		}
    		unsigned char ch = fgetc(fread); //不能使用char,压缩汉字时的字符出现范围是0~255
    		while (!feof(fread)) //统计各字符出现的次数
    		{
    			//在windows下回车是'\r\n'的组合,遇到‘\r\n’时屏幕上打印换行
    			if (ch == '\r')
    			{
    				ch = fgetc(fread); //跳过‘\r’
    				if (ch != '\n')
    				{
    					fseek(fread, -1, SEEK_CUR);
    				}
    			}
    			_info[ch]._count++;
    			ch = fgetc(fread);
    		}
    		HaffmanTree<CharInfo> h(_info, 256, CharInfo());
    		HaffmanNode<CharInfo>* root = h.GetRoot();
    		string str;
    		GenerateHaffmanCode(root, str);
    		//重新打开待压缩文件读
    		fseek(fread, 0, SEEK_SET);
    		ch = fgetc(fread);
    		unsigned char data = 0;   //要写入压缩文件的数据
    		int bitcount = 7;  //标记移位信息
    		//打开文件写压缩后的编码
    		string write(filename);
    		write = write + ".comparess";
    		FILE* fwrite = fopen(write.c_str(), "wb");
    		while (!feof(fread))
    		{
    			if (ch == '\r')
    			{
    				ch = fgetc(fread);
    				if (ch != '\n')
    				{
    					fseek(fread, -1, SEEK_CUR);
    				}
    			}
    			const char* cur = _info[ch]._code.c_str();
    			while (*cur)
    			{
    				if (bitcount >= 0)
    				{
    					data = data | ((*cur - '0') << bitcount);
    					bitcount--;
    				}
    				if (bitcount < 0)
    				{
    					fputc(data, fwrite);
    					bitcount = 7;
    					data = 0;
    				}
    				cur++;
    			}
    			ch = fgetc(fread);
    		}
    		fputc(data, fwrite);//最后一个字节没写满8位也要把data写入文件(困扰好久)
    		//写配置文件
    		WriteConfig(filename);
    		fclose(fread);
    		fclose(fwrite);
    	}
    
    
    	//文件解压缩
    	void UnComparess(const char* filename)
    	{
    		CharInfo HNarry[256];
    		//读配置文件
    		ReadConfig(filename, HNarry);
    		//重建Haffman树
    		HaffmanTree<CharInfo> h(HNarry, 256, CharInfo());
    		//遍历树,找叶子结点,写输出文件
    		HaffmanNode<CharInfo>* root = h.GetRoot();
    		HaffmanNode<CharInfo>* cur = root;
    		//打开压缩文件读
    		string comf(filename);
    		comf = comf + ".comparess";
    		FILE* fread = fopen(comf.c_str(), "rb");
    		unsigned char ch = fgetc(fread);
    		FILE* fwrite = fopen("output", "wb");
    		int readcount = root->_wight._count;//根节点的_count值就是整棵树字符出现的次数
    		while (readcount)
    		{
    			unsigned int tmp = 1;
    			int bit = 7;   //移动的位数
    			while (bit>=0)
    			{
    				if (ch & (tmp << bit))
    				{
    					cur = cur->_right;
    					bit--;
    				}
    				else
    				{
    					cur = cur->_left;
    					bit--;
    				}
    				//找到叶子结点
    				if (cur->_left == NULL&&cur->_right == NULL)
    				{
    					fputc(cur->_wight._ch, fwrite);
    					cur = root;
    					readcount--;
    					//最后一个字符的编码在最后两个字节当中的情况
    					if (!readcount)
    					{
    						break;
    					}
    				}
    				
    			}
    			ch = fgetc(fread);
    		}
    		fclose(fread);
    		fclose(fwrite);
    	}
    protected:
    	//得到Haffman编码(后序遍历HaffmanTree)
    	void GenerateHaffmanCode(HaffmanNode<CharInfo>* root, string& code)
    	{
    		if (root == NULL)
    			return;
    		GenerateHaffmanCode(root->_left, code + '0');
    		GenerateHaffmanCode(root->_right, code + '1');
    		root->_wight._code = code;
    		if (root->_left == NULL&&root->_right == NULL)
    		{
    			_info[root->_wight._ch]._code = code;
    		}
    
    	}
    	void WriteConfig(const char* filename)
    	{
    		string conf(filename);
    		conf = conf + "config";
    		FILE* fcon = fopen(conf.c_str(), "wb");
    		for (int i = 0; i < 256; ++i)
    		{
    
    			if (_info[i]._count)
    			{
    				fputc(_info[i]._ch, fcon);
    				fputc(',', fcon);
    				char count[100];
    				_itoa(_info[i]._count, count, 10);
    				fputs(count, fcon);
    				fputc(',', fcon);
    				fputs(_info[i]._code.c_str(), fcon);
    				fputc('\n', fcon);
    			}
    		}
    		fclose(fcon);
    	}
    	void ReadConfig(const char* filename, CharInfo* HNarry)
    	{
    		string conf(filename);
    		conf = conf + "config";
    		FILE* fread = fopen(conf.c_str(), "rb");
    		if (fread == NULL)
    		{
    			cout << "打开待压缩文件失败" << endl;
    			return;
    		}
    		char str[100];
    		while (fgets(str, 100, fread))
    		{
    			char* ptr = str;
    			unsigned char index = (unsigned char)*ptr;
    			if (index == '\n') //换行符
    			{
    				HNarry[index]._ch = index;
    				fgets(str, 100, fread);
    				char* ptr = str;
    				ptr++;
    				LongType count = 0;//字符的权值,出现的次数
    				while (*ptr != ',' && *ptr)
    				{
    					count *= 10;
    					count += (*ptr - '0');
    					ptr++;
    				}
    				HNarry[index]._count = count;
    				ptr++;
    				string code(ptr);
    				HNarry[index]._code = code;
    			}
    			else
    			{
    				HNarry[index]._ch = index;
    				ptr += 2;
    				LongType count = 0;//字符的权值,出现的次数
    				while (*ptr != ',' && *ptr)
    				{
    					count *= 10;
    					count += (*ptr - '0');
    					ptr++;
    				}
    				HNarry[index]._count = count;
    				ptr++;
    				string code(ptr);
    				HNarry[index]._code = code;
    			}
    		}
    	}
    protected:
    	CharInfo _info[256];
    };
        文件压缩的思路已在代码中表明。

    注意:

    1. 在文件压缩时最好写配置文件,使用配置文件可以简化压缩程序代码。
    2. 在写配置文件和读配置文件的时候要采用一样的规则,不然会出错。在这个程序中,我是以“  字符,出现次数,哈夫曼编码          ”的格式来写和读的。
    3. 压缩文件时要考虑到所有会出现的情况,比如在压缩完最后一个字符时往压缩文件中写的那个字节不满8位,我们也要把这个字节写进压缩文件.compress。
    4. 在读压缩文件时这里有一个小技巧。重建哈夫曼树后哈夫曼树的root所携带的_count值就是所有字符出现次数的总和。利用这个值可以控制读压缩文件.compress时什么时候结束。有时候最后一个字节(8位)的后几位并不是我们需要的,如果读了会出现许错误。


    以下是此程序压缩与解压缩花费的时间截图:

    debug下:


    release下:



    展开全文
  • Huffman的应用之文件压缩与解压缩

    千次阅读 2016-10-30 12:02:28
    文件压缩与解压缩>  最近这段时间一直在学习树的这种数据结构,也接触到了Huffman树以及了解了什仫是Huffman编码,而我们常用的zip压缩也是利用的Huffman编码的特性,那仫是不是可以自己实现一个文件压缩呢?当然可以...

    文件压缩与解压缩>

         最近这段时间一直在学习树的这种数据结构,也接触到了Huffman树以及了解了什仫是Huffman编码,而我们常用的zip压缩也是利用的Huffman编码的特性,那仫是不是可以自己实现一个文件压缩呢?当然可以了.在文件压缩中我实现了Huffman树和建堆Heap的代码,zip压缩的介绍>

        下面开始介绍自己实现的文件压缩的思路和问题...

         1).统计>读取一个文件统计这个文件中字符出现的次数.

         2).建树>以字符出现的次数作为权值使用贪心算法构建Huffman树(根据Huffman树的特性>字符出现次数多的一定靠近根结点,出现次数少的一定远离根结点).

         3).生成Huffman编码>规则左0右1.

         4).压缩>再次读取文件,根据生成的Huffman编码压缩文件.

         5).生成配置文件>将字符以及字符出现的次数写进配置文件中.

         6).解压缩>利用配置文件还原出Huffman树,根据压缩文件还原出原文件.

         7).测试>判断解压是否正确需要判断原文件和解压缩之后的文件是否相同,利用Beyond Compare软件进行对比.

         下面是我举的一个简单的范例,模拟压缩和解压缩的过程,希望有读者有帮助

         

         利用Beyond Compare软件进行对比>

        

        

         在实现中出现了很多的问题,下面我提出几个容易犯的问题,仅供参考

         1).在使用贪心算法构建Huffman树的时候,如果我们以unsigned char一个字节来存储它总共有2^8=256个字符,如果将所有的字符都构建Huffman树,这不仅降低了效率还将分配极大的内存.所以我设立了非法值这个概念,只有当字符出现的次数不为0的时候才将该字符构建到Huffman树中.

         2).在写压缩文件的时候我们是将字符对应的Huffman编码转化为对应的位,每当填满一个字节(8位)后再写入压缩文件中.如果最后一个字节没有填满我们就将已经填的位移位空出后几个位置,将未满的位置补0补满一个字节再写入压缩文件中.

         3).如果我们将源文件压缩之后再去解压,因为你的Huffman树和Huffman编码都是在压缩函数中得到的,此时再去解压那仫你的Huffman编码以及不存在了该如何去还原文件呢?这就是为什仫要生成配置文件的原因了,在配置文件中写入了字符以及字符出现的次数.在解压缩中根据配置文件构建新的Huffman树.

        4).由压缩文件还原文件的时候如何知道压了多少个字符呢?也就是说因为我们在压缩的时候最后一个字节是补了0的在解压缩的时候可能会把这个补的位当成字符的编码来处理.一种想法是在统计字符出现的次数的时候设置一个变量,每读取一个字符该变量就加1,最后将该变量写进配置文件中.另外一种想法就是根据根结点的权值,通过上述简单的实例观察可知根结点权值中的_count就是字符出现的次数.

        解决了以上几个问题,我的程序已经可以压缩那256个字符并正确的还原了,那仫如果是大文件或者是汉字,图片以及音频视频呢?

         1).因为有些特殊的字符编码,所以我们统计字符出现的次数的时候应该用的是unsigned char,刚开始我用的文件结束标志是EOF在ASII中它的编码是-1此时已经不可以用EOF来判断是否文件结束了,所以我用了feof这个函数来判断文件是否结束.

         2).统计字符出现次数应该用的类型是long long,这就解决了大文件的压缩和解压缩的问题了.

         3).因为汉字,图片,视频这些在内存中是以二进制的形式存在的,所以我们将以文本形式打开读或者写的修改为以二进制的形式读或者写.

        为了验证大文件的压缩我找了一个8.09M的文件压缩之后是6.50M,并且可以正确还原.

        1).测试效率>

          

        2).利用Beyond Compare软件进行对比,如果一样说明压缩成功>

          

          

          

        

       

        

    #define _CRT_SECURE_NO_WARNINGS 1
    #pragma once
    
    #include "Heap.h"
    
    template<class T>
    struct HuffmanTreeNode
    {
    	T _weight;
    	HuffmanTreeNode<T> *_left;
    	HuffmanTreeNode<T> *_right;
    	HuffmanTreeNode<T> *_parent;
    	HuffmanTreeNode(const T& w=T())
    		:_weight(w)
    		,_left(NULL)
    		,_right(NULL)
    		,_parent(NULL)
    	{}
    };
    
    template<class T>
    class HuffmanTree
    {
    	typedef HuffmanTreeNode<T> Node;
    public:
    	HuffmanTree()
    		:_root(NULL)
    	{}
    	HuffmanTree(const T* a,size_t size)
    		:_root(NULL)
    	{
    		_root=_CreatHuffmanTree(a,size);
    	}
    	//将未出现的字符过滤出来,不构造堆
    	HuffmanTree(const T* a,size_t size,const T& invalid)
    	{
    		_root=_CreatHuffmanTree(a,size,invalid);
    	}
    	Node* GetRoot()
    	{
    		return _root;
    	}
    	~HuffmanTree()
    	{
    		_Destroy(_root);
    	}
    protected:
    	Node *_CreatHuffmanTree(const T* a,size_t size)
    	{
    		struct NodeLess
    		{
    			bool operator()(Node *l,Node *r)const
    			{
    				return l->_weight < r->_weight;
    			}
    		};
    		Heap<Node *,NodeLess> minHeap;
    		//建立结点并放入vector中
    		for (size_t i=0;i<size;++i)
    		{
    			Node *tmp=new Node(a[i]);
    			minHeap.Push(tmp);
    		}
    		//取出较小的两个结点作为左右孩子并构建父结点
    		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);
    		}
    		return minHeap.Top();
    	}
    	//思路类似不带过滤功能的
    	Node *_CreatHuffmanTree(const T* a,size_t size,const T& invalid)
    	{
    		struct NodeLess
    		{
    			bool operator()(Node *l,Node *r)const
    			{
    				return l->_weight < r->_weight;
    			}
    		};
    		Heap<Node *,NodeLess> minHeap;
    		//建立结点并放入vector中
    		for (size_t i=0;i<size;++i)
    		{
    			if(a[i] != invalid)
    			{
    				Node *tmp=new Node(a[i]);
    				minHeap.Push(tmp);
    			}
    		}
    		//取出较小的两个结点作为左右孩子并构建父结点
    		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);
    		}
    		return minHeap.Top();
    	}
    	void _Destroy(Node *&root)
    	{
    		if(root == NULL)
    			return ;
    		Node *cur=root;
    		if(cur)
    		{
    			_Destroy(cur->_left);
    			_Destroy(cur->_right);
    			delete cur;
    			cur=NULL;
    			return ;
    		}
    	}
    protected:
    	Node *_root;
    };
    
    void testHuffmanTree()
    {
    	int a[]={0,1,2,3,4,5,6,7,8,9};
    	int size=sizeof(a)/sizeof(a[0]);
    	HuffmanTree<int> ht(a,size);
    }


     

    #define _CRT_SECURE_NO_WARNINGS 1
    
    #pragma once
    
    //利用仿函数的特性实现代码的复用性
    template<class T>
    struct Small
    {
    	bool operator()(const T& l,const T& r)
    	{
    		return l < r;
    	}
    };
    
    template<class T>
    struct Large
    {
    	bool operator()(const T& l,const T& r)
    	{
    		return l > r;
    	}
    };
    
    template<class T,class Compare=Large<T>>  //缺省是建小堆
    class Heap
    {
    public:
    	Heap()
    	{}
    	Heap(const T *a,int size)
    	{
    		assert(a);
    		_a.reserve(size);
    		for (int i=0;i<size;++i)
    		{
    			_a.push_back(a[i]);
    		}
    		//建堆的时候从倒数第一个非叶子结点开始.
    		for (int j=(size-2)/2;j>=0;--j)
    		{
    			_AdjustDown(j);
    		}
    	}
    	void Push(const T& x)
    	{
    		_a.push_back(x);
    		_AdjustUp(_a.size()-1);
    	}
    	void Pop()
    	{
    		assert(!_a.empty());
    		swap(_a[0],_a[_a.size()-1]);
    		_a.pop_back();
    		_AdjustDown(0);
    	}
    	size_t Size()
    	{
    		return _a.size();
    	}
    	bool Empty()
    	{
    		return _a.empty();
    	}
    	const T& Top()const
    	{
    		assert(!_a.empty());
    		return _a[0];
    	}
    	void Display()
    	{
    		for (size_t i=0;i<_a.size();++i)
    		{
    			cout<<_a[i]<<" ";
    		}
    		cout<<endl;
    	}
    protected:
    	void _AdjustDown(int root)
    	{
    		int parent=root;
    		size_t child=2*root+1;
    		while (child < _a.size())
    		{
    			Compare com;
    			//child指向左右孩子中较大的那个数
    			//if (child+1 < _a.size() 
    			//	&& _a[child+1] > _a[child])
    			if(child+1 < _a.size()
    				&& com(_a[child+1],_a[child]))
    			{
    				child++;
    			}
    			//if (_a[child] > _a[parent])
    			if(com(_a[child],_a[parent]))
    			{
    				swap(_a[child],_a[parent]);
    				parent=child;
    				//初始的child默认指向左孩子
    				child=2*parent+1;
    			}
    			else 
    				break;
    		}
    	}
    	void _AdjustUp(int child)
    	{
    		while (child > 0)
    		{
    			int parent=(child-1)/2;
    			Compare com;
    			//if (_a[child] > _a[parent])
    			if(com(_a[child],_a[parent]))
    			{
    				swap(_a[child],_a[parent]);
    				child=parent;
    			}
    			else
    				//插入的数据比父节点的数据域小
    				break;
    		}
    	}
    protected:
    	vector<T> _a;
    };
    //利用堆解决优先级队列的问题
    template<class T,class Compare=Large<T>>
    class PriorityQueue
    {
    public:
    	PriorityQueue(int *a,int size)
    		:_pq(a,size)
    	{}
    	void Push(const T& x)
    	{
    		_pq.Push(x);
    	}
    	void Pop()
    	{
    		_pq.Pop();
    	}
    	const T& Top()const
    	{
    		return _pq.Top();
    	}
    	void Display()
    	{
    		_pq.Display();
    	}
    protected:
    	Heap<T,Compare> _pq; 
    };


     

     

    #define _CRT_SECURE_NO_WARNINGS 1
    
    #pragma once
    
    #include "HuffmanTree.h"
    
    typedef long long Type;
    
    struct CharInfo
    {
    	unsigned char _ch;     //出现的字符
    	Type _count;           //统计次数
    	string _code;          //Huffman编码
    	CharInfo(Type count=0)
    		:_ch(0)
    		,_count(count)
    		,_code("")
    	{}
    	//重载对应的操作符
    	CharInfo operator + (const CharInfo& fc)const
    	{
    		return CharInfo(_count + fc._count);
    	}
    	bool operator != (const CharInfo fc)const
    	{
    		return _count != fc._count;
    	}
    	bool operator < (const CharInfo& fc)const
    	{
    		return _count < fc._count;
    	}
    };
    
    class FileCompress
    { 
    public:
    	//默认的构造函数
    	FileCompress()
    	{
    		for(size_t i=0;i<256;++i)
    		{
    			_infos[i]._ch=i;
    		}
    	}
    	string Compress(const char *filename)
    	{
    		assert(filename);
    		FILE *pf=fopen(filename,"rb");
    		assert(pf);
    		unsigned char ch=fgetc(pf);
    		//统计字符出现的次数
    		while (!feof(pf))
    		{
    			_infos[ch]._count++;
    			ch=fgetc(pf);
    		}
    		//以该字符出现的次数构建一颗HuffmanTree.
    		CharInfo invalid;   //非法值
    		HuffmanTree<CharInfo> ht(_infos,256,invalid);
    		//生成Huffman编码
    		string code;
    		_CreatHuffmanCode(ht.GetRoot(),code);
    		//_CreatHuffmanCode(ht.GetRoot());
    		//压缩文件
    		fseek(pf,0,SEEK_SET);          //回到文件头
    		string compressfile=filename;
    		compressfile += ".compress";   //压缩后的文件名
    		FILE *fin=fopen(compressfile.c_str(),"wb");
    		assert(fin);
    		size_t pos=0;                  //记录位数
    		unsigned char value=0;
    		ch=fgetc(pf);
    		while (!feof(pf))
    		{
    			string &code=_infos[ch]._code;
    			for (size_t i=0;i<code.size();++i)
    			{
    				value <<= 1;
    				if(code[i] == '1')
    					value |= 1;
    				else
    					value |= 0;    //do-nothing
    				++pos;
    				if(pos == 8)     //满一个字节
    				{
    					fputc(value,fin);
    					value=0;
    					pos=0;
    				}
    			}
    			ch=fgetc(pf);
    		}
    		if(pos)      //解决不足8位的情况.
    		{
    			value <<= (8-pos);
    			fputc(value,fin);
    		}
    		//配置文件--便于重建Huffman树
    		string configfilename=filename;
    		configfilename += ".config";
    		FILE *finconfig=fopen(configfilename.c_str(),"wb");
    		assert(finconfig);
    		string line;
    		char buff[128];
    		for (size_t i=0;i<256;++i)
    		{
    			//一行一行的读
    			if (_infos[i]._count)
    			{
    				line += _infos[i]._ch;
    				line += ",";
    				line += _itoa(_infos[i]._count,buff,10);
    				line += "\n";
    				//fputs(line.c_str(),finconfig);
    				fwrite(line.c_str(),1,line.size(),finconfig);
    				line.clear();
    			}
    		}
    		fclose(pf);
    		fclose(fin);
    		fclose(finconfig);
    		return compressfile;
    	}
    	string UnCompress(const char *filename)
    	{
    		assert(filename);
    		string configfilename=filename;
    		size_t index=configfilename.rfind(".");
    		configfilename=configfilename.substr(0,index);
    		configfilename += ".config";
    		FILE *foutconfig=fopen(configfilename.c_str(),"rb");
    		assert(foutconfig);
    		string line;
    		//读取配置文件--获取字符出现的次数
    		unsigned char ch=0;
    		while (ReadLine(foutconfig,line))
    		{
    			if(line.empty())
    			{
    				line += '\n';
    				continue;
    			}
    			//读到空行
    			ch=line[0];
    			_infos[ch]._count = atoi(line.substr(2).c_str());
    			line.clear();
    		}
    		//构建Huffman树
    		CharInfo invalid;
    		HuffmanTree<CharInfo> hft(_infos,256,invalid);
    		//根结点的权值也就是字符出现的次数总和
    		HuffmanTreeNode<CharInfo> *root=hft.GetRoot();
    		Type charcount=root->_weight._count;
    		//解压缩
    		string uncompressfilename=filename;
    		index=uncompressfilename.rfind(".");
    		uncompressfilename=uncompressfilename.substr(0,index);
    		uncompressfilename += ".uncompress";
    		FILE *fin=fopen(uncompressfilename.c_str(),"wb");
    		assert(fin);
    		//由压缩文件还原文件
    		string compressfilename=filename;
    		FILE *fout=fopen(compressfilename.c_str(),"rb");
    		assert(fout);
    
    		HuffmanTreeNode<CharInfo> *cur=root;
    		int pos=7;
    		ch=fgetc(fout);
    		while (charcount > 0)
    		{
    			while (cur)
    			{
    				if(cur->_left == NULL && cur->_right == NULL)
    				{
    					//叶子结点
    					fputc(cur->_weight._ch,fin);
    					cur=root;
    					--charcount;
    					if (charcount == 0)   //所有的字符都处理完成
    						break;
    				}
    				if (ch & (1 << pos))    //检查字符的每个位
    					cur=cur->_right;    //1向右走
    				else
    					cur=cur->_left;     //0向左走
    				--pos;
    				if(pos < 0)             //一个字节解压完成
    				{
    					ch=fgetc(fout);
    					pos=7;
    				}
    			}
    		}
    		fclose(foutconfig);
    		fclose(fin);
    		fclose(fout);
    		return uncompressfilename;
    	}
    	//读取一行字符并放在line中
    	bool ReadLine(FILE *fout,string& line)
    	{
    		int ch=fgetc(fout);
    		if(ch == EOF)
    			return false;
    		while (ch != EOF && ch != '\n')
    		{
    			line += ch;
    			ch=fgetc(fout);
    		}
    		return true;
    	}
    protected:
    	//递归的方法求HuffmanTreeCode
    	void _CreatHuffmanCode(HuffmanTreeNode<CharInfo> *root,string &code)
    	{
    		if(root == NULL)
    			return ;
    		_CreatHuffmanCode(root->_left,code+'0');
    		_CreatHuffmanCode(root->_right,code+'1');
    		if(root->_left == NULL && root->_right == NULL)   //叶子结点
    		{
    			_infos[root->_weight._ch]._code=code;
    		}
    	}
    	//非递归求HuffmanTreeCode
    	void _CreatHuffmanCode(HuffmanTreeNode<CharInfo> *root)
    	{
    		if(root == NULL)
    			return ;
    		_CreatHuffmanCode(root->_left);
    		_CreatHuffmanCode(root->_right);
    		if(root->_left == NULL && root->_right == NULL)   //叶子结点
    		{
    			string& code=_infos[root->_weight._ch]._code;
    			HuffmanTreeNode<CharInfo> *cur=root;
    			HuffmanTreeNode<CharInfo> *parent=root->_parent;
    			while (parent)
    			{
    				if(parent->_left == cur)
    					code.push_back('0');    //左0
    				else
    					code.push_back('1');    //右1
    				cur=parent;
    				parent=cur->_parent;
    			}
    			//编码是从根到叶子结点的,需要逆置
    			reverse(code.begin(),code.end());
    		}
    	}
    protected:
    	CharInfo _infos[256];
    };
    
    void testFileCompress()
    {
    	FileCompress fc;
    	cout<<"开始压缩"<<endl;
    	cout<<"压缩用时:";
    	int start=GetTickCount();
    	fc.Compress("2.png");    //input input.BIG 3.mp3
    	int end=GetTickCount();
    	cout<<end-start<<endl;
    	cout<<"开始解压"<<endl;
    	cout<<"解缩用时:";
    	start=GetTickCount();
    	fc.UnCompress("2.png.compress"); //input.compress input.BIG.compress 3.mp3
    	end=GetTickCount();
    	cout<<end-start<<endl;
    }
    
    void testFileUncompress()
    {
    	FileCompress fc; 
    	cout<<"开始解压"<<endl;
    	cout<<"解缩用时:";
    	int start=GetTickCount();
    	fc.UnCompress("2.png");
    	int end=GetTickCount();
    	cout<<end-start<<endl;
    }


     

        

         经过测试这个小项目已经可以压缩并还原一些文件了,目前还没有发现什仫大的Bug,如果有童鞋发现请第一时间告诉我哦...

    展开全文
  • 哈夫曼树实现文件的压缩与解压缩

    万次阅读 2017-03-08 19:16:08
    利用哈夫曼树实现文件的压缩与解压缩 压缩: 1、统计出文件中相同字符出现的次数 2、获取哈夫曼编码 次数作为权值构建哈夫曼树 3、重新编码,写回压缩文件 保存头文件: 源文件后缀 编码信息的行数 ...
  • Python3 压缩与解压缩

    千次阅读 2018-06-29 10:38:31
    Python3 压缩与解压缩(zlib / gzip / bz2 / lzma / zipfile / tarfile) 本文由 Luzhuo 编写,转发请保留该信息. 原文: http://blog.csdn.net/Rozol/article/details/72672703 以下代码以Py...
  • 而文件的解压缩实际上就是将压缩文件翻译过来保存到解压缩文件中,需要使用压缩过程中生成的配置文件配合完成。下面将具体介绍文件的压缩和解压缩步骤: 1。统计文件中所有字符的出现次数。由于Ascall码字符一共255...
  • 数据压缩算法,文本压缩算法 几种压缩算法原理介绍- https://blog.csdn.net/clevercode/article/details/46691645 文本压缩算法的对比和选择- https://blog.csdn.net/horkychen/article/details/75174035 数据压缩...
  • Huffman树实现文件的压缩与解压缩

    千次阅读 2018-07-15 12:04:02
    树根到某一节点的路径长度该节点的权的乘积。 树的带权路径长度 树的带权路径长度为树中从根节点到所有叶子节点的各个带权路径长度之和。 Huffman树的构造步骤: 初始化:将给定的节点都看作根节点,...
  • pb实现压缩与解压缩

    热门讨论 2013-01-30 11:42:27
    用PB实现的压缩与解压缩,在将文件保存进数据库前可以压缩存放,也可以在备份文件时压缩存放
  • ffmpeg视频压缩与解压缩

    热门讨论 2013-10-29 20:05:42
    使用ffmpeg实现摄像头视频读取,压缩 和解压缩 demo
  • 用的最多的Linux中的压缩与解压缩命令,在ubnutu中有详细的执行演示截图。
  • 一、实验题目 用哈夫曼编码实现文件压缩 二、实验目的 了解文件的概念 掌握线性链表的插入、删除等算法 ...三、实验设备环境 微型计算机、Windows 系列操作系统 、Visual C++6.0软件 四、...
  • 文件压缩与解压缩(哈夫曼编码)

    千次阅读 2017-09-07 15:41:51
    本文采用哈夫曼编码的方式进行...而文件的解压缩实际上就是将压缩文件翻译过来保存到解压缩文件中,需要使用压缩过程中生成的配置文件配合完成。下面将具体介绍文件的压缩和解压缩步骤: 文件的压缩的核心是产生哈夫曼
  • linux常用的压缩与解压缩命令

    千次阅读 2015-07-05 19:38:51
    1.gzip 压缩gzip 是压缩文件...用法 gunzip 选项 [压缩文件]3.tar这个命令可以将文件打包压缩一起执行,也可以解压缩压缩用法:tar 选项[zcvf] [目录]-c 产生.tar打包文件 -v 显示详细信息 -f 指定压缩后的文件名 -
  • Java实现zip文件压缩与解压缩--附完整代码

    万次阅读 多人点赞 2019-07-26 14:54:09
    Java实现文件压缩与解压缩-----zip、.7z1. 基本概念1.1 Java中实现zip的压缩与解压缩1.1.1 基本概念1.1.2 zip压缩代码实现1.3 zip压缩代码改进 1. 基本概念 1.1 Java中实现zip的压缩与解压缩 1.1.1 基本概念 ...
  • 7z 常用压缩与解压缩命令

    千次阅读 2020-09-25 17:06:36
    压缩 / 解压缩: 7z, XZ, BZIP2, GZIP, TAR, ZIP 仅解压缩: ARJ, CAB, CHM, CPIO, DEB, DMG, FAT, HFS, ISO, LZH, LZMA, MBR, MSI, NSIS, NTFS, RAR, RPM, UDF, VHD, WIM, XAR, Z 7-Zip 支持和 Windows 相类似的...
  • Linux中压缩与解压缩命令

    千次阅读 2018-10-03 14:00:34
    Linux中压缩与解压缩命令 Linux中压缩与解压缩命令 常用压缩格式: .zip .gz .bz2 .tar.gz .tar.bz2 .zip格式 .zip格式压缩 zip 压缩文件名 源文件 #压缩文件 zip -r 压缩文件名 源文件 #压缩目录 .zip格式...
  • 使用Java 语言实现了Huffman编码的压缩和解压缩,能够实现对Ascii 文档的压缩和解压缩,目前尚不支持对二进制文档进行压缩
  • linux下压缩与解压缩-tar和zip

    万次阅读 2017-04-15 11:16:21
    -p:-c参数类似,会将解压缩的结果显示到屏幕上,但不会执行任何的转换 -t:检查压缩文件是否正确 -u:-f参数类似,但是除了更新现有的文件外,也会将压缩文件中的其它文件解压缩到目录中 -v:执行是时...
  • 利用JAVASCRIPT即你想那个GZIP压缩与解压缩 最近流行的网络游戏(FLASH)数据传输都是用GZIP进行压缩与解压缩的,在客户端FLASH对与服务器交互的数据进行解压缩
  • 使用C语言编写的LZW压缩与解压缩程序的改进版,有以下改进: 1. 避免了LZW算法会增大文件大小这个缺陷 2. 提供存储的压缩方法 3. 提升了压缩比 4. 提升了程序的执行速度 程序使用ANSI C语言编写,可在多平台下编译。...
  • 7zip压缩与解压缩在vc++中调用的例子

    热门讨论 2012-03-02 10:39:46
    主要实现7zip压缩与解压缩功能在vc++中的调用方式,本文件以实际的例子呈现给大家
  • ubuntu环境下文件夹压缩与解压缩

    千次阅读 2021-03-26 17:15:56
    ubuntu环境下文件夹压缩与解压缩 一、准备 一个需要压缩的文件夹,里面准备点文件 打开终端,这个 test 文件夹就是刚刚准备好的,里面有 a.c、b.c、z.c 三个文件,准备工作已经做好,就开始行动呗 二、目标 将 ...
  • C# 压缩与解压缩完整源码,支持ZIP,RAR,7Z,WinZip,BZip2等,可以支持压缩批量文件,大文件,文件夹。支持解压单个文件,批量文件,文件夹等。完整源码,本项目包含三个子项目,分别是压缩与解压缩应用项目,压缩源码...
  • Python压缩与解压缩文件   Python能够直接处理zip文件中的数据,并

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 397,633
精华内容 159,053
关键字:

压缩与解压缩

友情链接: LQG codes.rar