精华内容
下载资源
问答
  • 哈夫曼压缩与解压缩

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

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

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

    展开全文
  • 主要介绍了java实现哈夫曼压缩与解压缩的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • java实现哈夫曼压缩与解压缩

    千次阅读 2019-09-30 10:30:03
    哈夫曼压缩与解压缩(java版) 一哈夫曼树以及文件压缩原理: 1.哈夫曼树 : 2.如何利用haffman编码实现文件压缩: 二主要技术点: 三实现过程: 四运行展示: 哈夫曼压缩与解压缩(java版) 一哈夫曼树以及...

    目录

    哈夫曼压缩与解压缩(java版)

    一哈夫曼树以及文件压缩原理:

    1.哈夫曼树 :

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

    二主要技术点:

    三实现过程:

    四运行展示: 


    哈夫曼压缩与解压缩(java版)

    一哈夫曼树以及文件压缩原理:

    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.哈希算法(字符统计时候会用到,也可以直接用HashMap统计)

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

    4.java文件操作,以及缓冲操作。

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

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

    三实现过程:

    以上述aaaabbbccde为例

    1.字符统计:

    public class FreqHuf {
    	public static int BUFFER_SIZE = 1 << 18;
    	int freq[] = new int[256];
    	File file;
    	int count;
    	List<HuffmanFreq> list;
    	
    	FreqHuf(String pathname) throws Exception {
    		list = new ArrayList<>();
    		this.file = new File(pathname);
    		if(!file.exists()){
    			throw new Exception("文件不存在");
    		}
    		System.out.println("进行字符统计中");
    		CensusChar();
    		System.out.println("字符统计完毕");
    	}
    	
    	public void CensusChar() throws IOException{
    		int intchar;
    		FileInputStream fis = new FileInputStream(file);
    		System.out.println("统计中");
    
    //这种统计处理方案,速度极慢,不建议使用,以下采用缓存读数据。
    //		while((intchar = fis.read()) != -1){
    //			freq[intchar]++;
    //		}
    
    		//这里采用缓存机制,一次读1 << 18个字节,大大提高效率。
    		byte[] bytes = new byte[BUFFER_SIZE];
    		while((intchar = fis.read(bytes))!= -1){
    			for(int i = 0; i < intchar;i++){
    				int temp = bytes[i]& 0xff;
    				freq[temp]++;
    			}
    		}
    		
    		
    		
    		fis.close();
    		
    		for(int i = 0; i < 256; i++){
    			if(freq[i] != 0){
    				this.count++;
    			}
    		}
    		
    		int index = 0;
    		for(int i = 0; i < 256; i++){
    			if(freq[i] != 0){
    				HuffmanFreq huffman = new HuffmanFreq();
    				huffman.character = (char)i;
    				huffman.freq = freq[i];
    				list.add(index, huffman);
    			}
    		}
    	}
    }
    //统计每个字符和其频率的类
    public class HuffmanFreq {
    	char character;
    	int freq;
    	
    	HuffmanFreq() {
    	}
    	
    	HuffmanFreq(int character,int freq) {
    		this.character = (char)character;
    		this.freq = freq;
    	}
    
    	char getCharacter() {
    		return character;
    	}
    
    	void setCharacter(int character) {
    		this.character = (char)character;
    	}
    
    	int getFreq() {
    		return freq;
    	}
    
    	void setFreq(int freq) {
    		this.freq = freq;
    	}
    	
    	byte[] infoToByte(){
    		byte[] bt = new byte[6];
    		
    		byte[] b1 = ByteAnd8Types.charToByte(character);
    		for(int i= 0; i < b1.length;i++){
    			bt[i] = b1[i];
    		}
    		
    		byte[] b2 = ByteAnd8Types.intToBytes2(freq);
    		int index = 2;
    		for(int i= 0; i < b2.length;i++){
    			bt[index++] = b2[i];
    		}
    		
    		return bt;
    	}
    
    	@Override
    	public String toString() {
    		return "Huffman [character=" + character + ", freq=" + freq + "]";
    	}
    }

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

    //treeSize为总节点数
    private void creatTree(int treeSize){
    		int temp;
    		treeList = new ArrayList<HuffTreeNode>();
    		for(int i =  0; i < treeSize; i++){
    			HuffTreeNode node = new HuffTreeNode();
    			treeList.add(i, node);
    		}
    		
    		for(int i = 0; i < charCount; i++){
    			HuffTreeNode node = treeList.get(i);
    			node.freq.freq = charList.get(i).getFreq();
    			node.freq.character = charList.get(i).getCharacter();
    			node.left = -1;
    			node.right = -1;
    			node.use = 0;
    		}
    		
    		for(int i = charCount; i < treeSize; i++){
    			int index = i;
    			HuffTreeNode node = treeList.get(i);
    			node.use = 0;
    			node.freq.character = '#';
    			node.right = searchmin(index);
    			node.left = searchmin(index);
    			node.freq.freq = treeList.get(node.right).freq.freq + treeList.get(node.left).freq.freq;
    			temp  = searchmin(++index);
    			if(temp == -1){
    				break;
    			}
    			treeList.get(temp).use = 0;
    		}
    	}
    	
    	private int searchmin(int count){
    		int minindex = -1;
    		
    		for(int i = 0; i < count; i++){
    			if(treeList.get(i).use == 0){
    				minindex = i;
    				break;
    			}
    		}
    		if(minindex == -1){
    			return -1;
    		}
    		for(int i = 0; i < count; i++){
    			if((treeList.get(i).freq.freq <= treeList.get(minindex).freq.freq) && treeList.get(i).use == 0){
    				minindex = i;
    			}
    		}
    		treeList.get(minindex).use = 1;
    		return minindex;
    	}

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

            private void bulidhuftreecode(int root, String str){
    		if(treeList.get(root).getLeft() != -1 && treeList.get(root).getRight() != -1){
    			bulidhuftreecode(treeList.get(root).getLeft(), str+"0");
    			bulidhuftreecode(treeList.get(root).getRight(),  str + "1");
    		}
    		else{
    			treeList.get(root).code = str;
    		}	
    	}

     4.哈夫曼编码代替字符,进行压缩,压缩前首先要将文件头(文件标志,字符数量,最后一个字节有效位,密码)字符和其频率的那张表格写入文件,以便于解压缩

        public void creatCodeFile(String path) throws Exception{
    		byte value = 0;
    		int index = 0;
    		int arr[] = new int[256];
    		int intchar;
    		
    		for(int i = 0; i < charCount; i++){
    			arr[treeList.get(i).freq.character] = i;
    			
    		}
    		File file = new File(path);
            if(!file.exists()){
                 if(!file.createNewFile()){
                	 throw new Exception("创建文件失败");
                 }
            }
    		int count = charList.size();
    		HuffmanHead head = new HuffmanHead(count, howlongchar(count), password);
                    //将文件头信息写入文件
    		this.write = new RandomAccessFile(file, "rw");
    		write.write(head.InfoToByte());
                    //将字符及其频率的表写入文件
    		for(HuffmanFreq freq : charList){
    			byte[] bt = freq.infoToByte();
    			write.write(bt);
    		}
    		//将字符用哈夫曼编码进行压缩,这里读写都是采用缓存机制
    		byte[] readBuffer = new byte[BUFFER_SIZE];
    		while((intchar = read.read(readBuffer))!= -1){
    			ProgressBar.SetCurrent(read.getFilePointer());
    			for(int i = 0; i < intchar;i++){
    				int temp = readBuffer[i]& 0xff; 
    				String code = treeList.get(arr[temp]).code;
    				char[] chars = code.toCharArray();
    				
    				for(int j = 0; j < chars.length; j++){
    					if(chars[j] == '0'){
    						value = CLR_BYTE(value, index);
    					}
    					if(chars[j] == '1'){
    						value = SET_BYTE(value, index);
    					}
    					if(++index >= 8){
    						index = 0;
    						writeInBuffer(value);
    					}
    				}
    			}
    		}
    		//此方法速度较慢
    //		while((intchar = is.read()) != -1){
    //			String code = treeList.get(arr[intchar]).code;
    //			char[] chars = code.toCharArray();
    //			
    //			for(int i = 0; i < chars.length; i++){
    //				if(chars[i] == '0'){
    //					value = CLR_BYTE(value, index);
    //				}
    //				if(chars[i] == '1'){
    //					value = SET_BYTE(value, index);
    //				}
    //				if(++index >= 8){
    //					index = 0;
    //					oos.write(value);
    //				}
    //			}
    //		}
    		if(index != 0){
    			writeInBuffer(value);
    		}
    	    byte[] Data = Arrays.copyOfRange(writeBuffer, 0, writeBufferSize);
    	    write.write(Data);
    	    write.close();
    		read.close();
    	}
            //指定位,置1
            byte SET_BYTE(byte value, int index){
    		return (value) |= (1 << ((index) ^ 7));
    	}	
            //指定位,置0
    	byte CLR_BYTE(byte value, int index){ 
    		return (value) &= (~(1 << ((index) ^ 7)));
    	}
            //判断指定位是否为0,0为false,1为true
    	boolean GET_BYTE(byte value, int index){ 
    		return ((value) & (1 << ((index) ^ 7))) != 0;
    	}

    如果一个字节一个字节往文件里写,速度会极慢,为了提高效率,写也采用缓存,先写到缓存区,缓存区满了后写入文件,

            private void writeInBuffer(byte value) throws Exception {
    		if(writeBufferSize < BUFFER_SIZE){
    			writeBuffer[writeBufferSize] = value;
    			if(++writeBufferSize >= BUFFER_SIZE){
    				write.write(writeBuffer);
    				writeBufferSize = 0;
    			}
    		} else{
    			throw new Exception("写入文件出错");
    		}
    	}

    到这里压缩就完成了,以下为解压缩方法

    1.从写入文件中的字符统计的表读出放入list里

    public void init() throws Exception{
    		char isHUf = read.readChar();
                    //验证文件头信息
    		if(isHUf != '哈'){
    			throw new Exception("该文件不是HUFFMAN压缩文件");
    		}
    		this.charCount = read.readChar();
    		this.treeSize = 2*charCount -1;
    		this.lastIndex = read.readChar();
    		int password = read.readInt();
    		if(password != this.password.hashCode()){
    			System.out.println("密码错误");
    		} else{
    			System.out.println("密码正确,正在解压");
    		}
    		
                    //从文件中将字符统计的表读出
    		byte[] buffer = new byte[charCount * 6];
    		read.seek(10);
    		read.read(buffer, 0, charCount * 6);
    		ProgressBar.SetCurrent(read.getFilePointer());
    		for(int i = 0; i < buffer.length; i+=6){
    			byte[] buff = Arrays.copyOfRange(buffer, i, i+2);
    			ByteBuffer bb = ByteBuffer.allocate (buff.length);
    		    bb.put (buff);
    		    bb.flip ();
    		    CharBuffer cb = cs.decode (bb);
    		    byte[] buff1 = Arrays.copyOfRange(buffer, i+2, i+6);
    		    int size = ByteAnd8Types.bytesToInt2(buff1, 0);
    		    HuffmanFreq freq = new HuffmanFreq(cb.array()[0], size);
    		    charList.add(freq);
    		}
    	}

    2.用统计结果构建哈夫曼树(和以上代码一样)

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

    4.遍历文件每个字节,根据哈夫曼编码找到对应的字符,将字符写入新文件

            public void creatsourcefile(String pathname) throws Exception{
    		int root = treeList.size() - 1;
    		int fininsh = 1;
    		long len;
    		File file = new File(pathname);
    		if(!file.exists()){
    			  if(!file.createNewFile()){
    				  throw new Exception("创建文件失败");
    	          }
    		}
    		write = new RandomAccessFile(file, "rw");
    		
    		int intchar;
    		byte[] bytes = new byte[1<<18];
    		int index = 0;
    		while((intchar = read.read(bytes))!= -1){
    			len = read.getFilePointer();
    			ProgressBar.SetCurrent(len);
    			for(int i = 0; i < intchar;i++){
    				for(;index < 8 && fininsh != 0;){
    					if(GET_BYTE(bytes[i], index)){
    						root = treeList.get(root).right;
    					} else{
    						root = treeList.get(root).left;
    					}
    					if(treeList.get(root).right== -1 && treeList.get(root).left == -1){
    						byte temp = (byte)treeList.get(root).freq.character;
    						writeInBuffer(temp);
    						root = treeList.size() - 1;
    					}
    					index++;
    					if(len == this.goalfilelenth && i == intchar-1){
    						if(index >= this.lastIndex){
    							fininsh = 0;
    						}
    					}
    				}
    				index = 0;
    			}
    		}
    		byte[] Data = Arrays.copyOfRange(writeBuffer, 0, writeBufferSize);
    		write.write(Data);
    		write.close();
    		write.close();
    		read.close();
    	}

    四运行展示: 

    以上为哈夫曼压缩,需要具体代码的,可以私信我,谢谢阅读。下方也可以下载资源

    展开全文
  • 哈夫曼压缩与解压缩程序(JAVA)
  • 哈夫曼压缩与解压算法(可以直接运行),压缩成二进制文件,而且生成了txt文件可以查看哈夫曼编码。C++代码
  • Huffman-compress:哈夫曼压缩与解压缩
  • 哈夫曼压缩与解压缩(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;  
    }

    展开全文
  • 哈夫曼树:

    哈夫曼树与哈夫曼编码

    压缩与解压缩技术
           这里提出一种专门针对ASCII码(英文及英文标点)的压缩技术:对文本文件中的字符,按照出现频度大小,将出现频度最大的字符,用最少的二进制位表达(替换);
           比如:假设某文件中,字母e出现了304325次,每一个e都应该是一个ASCII码,即,占用8bit;若能用2个bit的信息替换,则,可以省304325bit * (8-2) = 228243Byte        304325 * 2 / 8 = 76082         76081 / 304325 = 0.25
           假设,有如下字符及其出现频度:
           a        2
           b        8
           c        1
           d        7
           e        20
           f        3
    那么我们就可以形成一棵哈夫曼树,如下图所示:
    在这里插入图片描述
            其形成的原理是:先找出两个出现频度最小的,作为左右孩子,然后将两者频度之和作为根节点;再找出频度第三小的,作为左孩子,与刚才的根节点形成左右孩子,依此类推,形成一棵哈夫曼树。令:向左为0;向右为1,从根出发,到达某一个叶子节点的0、1集合,就是那个叶子节点所表示的字符对应的哈夫曼编码。
    e:0
    b:10
    d:110
    f:1110
    c:11110
    a:11111
    而哈夫曼压缩与解压缩要解决的第一个问题就是:统计给定字符串(文件)中出现的字符种类及其频度。

    哈夫曼压缩与解压缩
    1.针对文件进行压缩和解压缩;即,输入是文件,输出也是文件;
    2.针对文件进行操作:
           2.1统计该文件中出现的不同字节(应该只能使用:unsigned char 类型!!!)及其频度;
           2.2根据上述统计数据,构造哈夫曼树;
           2.3根据上述哈夫曼树,构造每一个字节的哈夫曼编码;
           2.4将文件中的字节,转换成哈夫曼编码;
    3.将由哈夫曼编码形成的最终压缩文件作为输出。
    综上,结构体应定义为:

    typedef struct TREE{
    	char ch;
    	int freq;
    	struct TREE *leftChild;
    	struct TREE *rightChild;
    }TREE;
    

    其实大致思路就是这样,其中最关键的就是,先形成一个表,再由表形成树,具体怎么实现,还是直接上代码吧!!!
    github:https://github.com/xiami-maker/aboutHuffman/tree/master

    感悟:对于哈夫曼压缩和解压缩,主要是对于哈夫曼树的应用,还有一些思想:把压缩和解压缩过程做成工具以便代码复用,方便阅读,减少编程量,采用文件的形式来存放更具有实际意义等。需要读者浏览代码的过程中,自行体会。

    展开全文
  • C语言实现哈夫曼压缩与解压缩

    万次阅读 2019-06-18 17:52:57
    typedef struct { //哈夫曼树 MyType ch; //存字符 WeightType weight; /* 用来存放各个结点的权值 */ int parent, LChild, RChild; /*指向双亲、孩子结点的指针 */ } HTNode; typedef struct { //队列 int tag...
  • 哈夫曼压缩和解压和解压,数据结构课程设计,c++源码。
  • 哈夫曼压缩/解压缩(控制台,C++)

    千次阅读 2016-11-20 16:53:50
    即是如此,在初步了解哈夫曼的原理之后,我只是隐隐约约的了解它的原理,在完成它的过程之中,依旧遇到了许多的问题,但是一切都已经成功的克服,下面我会简单的介绍哈夫曼编码的压缩和解压缩的原理。Ⅰ.哈夫曼原理 ...
  • 计算机使用数字代码来存储字符,ASC II码是最常用的编码。一个ASC II码值占一个字节(8个二进制位),...在解压缩时,首先从文件头读入保存的编码信息,从而对后续的编码解码,还原成ASCII的形式,生成原文相同的文件。
  • 分析可知哈夫曼树是二叉树,所以逻辑结构应该选择树形结构 存储结构设计 由于要存储二叉树的结点,所以二叉树的链式存储方式。链式存储可以更好的表现出二叉树中各个结点之间的关系,有左孩子,右孩子,和父节点三...
  • 基于哈夫曼编码的文本文件压缩与解压缩,使用c语言,实际只是编码解码,不应该称为解压缩,因为编码后文件会更大
  • 哈夫曼编码实现压缩解压缩java

    热门讨论 2012-06-04 19:26:01
    使用哈夫曼编码实现对文本文件的压缩和解压缩
  • 利用哈夫曼算法实现压缩解压缩,Linux c
  • 比较详细的注释,故在此不多解释,注意.docx文件效率比较差,因为其本身已经压缩,txt则可以见到明显的压缩效果 #!/usr/bin/env python3 # -*- coding: utf-8 -*- import sys sys.setrecursionlimit(1000000) ...
  • 哈夫曼压缩与解压

    2017-12-09 21:24:01
    压缩过程(不对哈夫曼编码原理进行详细解释): 1:读取文件内容到StringBuffer中,并使用hashmap统计每个字符出现的频率,按字符出现的频率升序排序(并保存在文件,备解压使用)。 2:对排序结束的字符频率建立...
  • 最近学习韩顺平老师主讲的“图解java 数据结构算法”的哈夫曼编码这一章节时,在编码实现上遇到了些许问题,本文主要记述一下问题及自己的解决方案,如有更优解还请指点
  • 哈夫曼树实现文件的压缩与解压缩
  • 哈夫曼编码用于解压和压缩的示例代码,非常简单易懂,C风格C++写法。
  • 下方链接为用 java 实现哈夫曼树:https://blog.csdn.net/www_chinese_com/article/details/88070625目录一、压缩二、解压一、压缩利用哈夫曼编码对文件进行压缩和解压的大概步骤如下(1)读取文档中的所有字符,在...
  • 实验目的:理解哈弗曼信源编码算法,并能应用于文件压缩中。 实验内容:写出程序,利用哈弗曼编码实现对文件的压缩,并能解压文件。 实验步骤: 1、压缩 (1) 统计原始文件中各字节出现的概率(次数); (2) 采用...
  • 哈夫曼树实现文件压缩与解压缩

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

    千次阅读 2018-09-08 20:08:26
    本文主要介绍如何实现哈夫曼压缩以及提高哈夫曼压缩过程的读写速率,对于哈夫曼树的概念及其构造则没有介绍,感兴趣的朋友可以先百度一下了解相关知识。 一、哈夫曼压缩原理 哈夫曼压缩是一种无损的压缩算法,在...
  • 根据ASCII码文件中各ASCII字符出现的频率情况创建Haffman树,再将各字符对应的哈夫曼编码写入文件中,实现文件压缩

空空如也

空空如也

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

哈夫曼压缩与解压缩