哈夫曼压缩与解压缩

目录

哈夫曼压缩与解压缩

一：引言

二：主要技术点

三：过程介绍

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文件就会失败。

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

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

软件压缩/解压缩软件Szip（Huffman算法及应用）

完整代码下载地址

1．需求规格说明

【问题描述】

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

【基本要求】（60%）

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

【提高要求】（40%）

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

2．总体分析与设计

（1）设计思想：

【存储结构】

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

【主要的算法思想】

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

（2）设计表示：

（3）详细设计表示：

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

3．编码

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

4．程序及算法分析

【使用说明】

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

【测试数据】

1、压缩文件

2、解压缩文件

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

【讨论与分析】

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

【改进设想】

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

5．附录

【压缩函数核心代码】

//压缩函数 成功执行返回 true 失败 false
bool HuffmanTree::doCompress(char *pcInput, char *pcOutput)
{
	if (!countFrequency(pcInput))              //如果不能计算字符出现的次数就返回false 可以计算就继续执行程序
		return false;

	createHuffmanTree();
	calculateCode();
	ifstream ifsFile;
	ofstream ofsFile;
	
	ifsFile.open(pcInput, ios::binary);
	ofsFile.open(pcOutput, ios::binary);
	
	char c;
	if (!ifsFile){
		cout << "Unable to open the file" << pcInput << '!' << endl;
		return false;
	}
	if (!ofsFile){
		cout << "Unable to open the file" << pcOutput << '!' << endl;
		return false;
	}

	//输出huffman编码
	/*while (ifsFile.get(c))
	{					                     
		int _nTem = c + 128;
		for (int i = 0; i < HT[_nTem].nCodeLenght; i++)
		{
			ofsFile << HT[_nTem].pnCode[i] << endl;
		}
	}*/

	
	ofsFile.put(0);	                         //预留一个字符，等压缩完后在该位置写入不足一个byte的bit个数
	ofsFile.put(mnRoot - 384);	             //将根节点的位置-384写入（为使该值不超过char的最大表示范围）
	                                         //384=256+128
	for (int i = 0; i<nLeaf * 2 - 1; i++)    //从上往下
	{		                                 //写入每个结点的双亲结点位置
		if (HT[i].nParent == -1)	         //若该节点没有双亲结点，则写入127(一个字节所能表示的最大值2⁷-1=128-1=127)
			ofsFile.put(127);
		else	                             //否则将双亲结点的位置-384再写入（为使该值不超过char的最大表示范围）
			ofsFile.put(HT[i].nParent - 384);
	}

	while (ifsFile.get(c))
	{					                     //将字符的huffman编码并加入byte中
		int _nTem = c + 128;
		
		for (int i = 0; i < HT[_nTem].nCodeLenght; i++)
		{
			//ofsFile.put(HT[_nTem].pnCode[i]);
			addBit(HT[_nTem].pnCode[i]);     //将字符的huffman编码并加入byte中
			if (mnBitsNum == 8)
			{		                         //若byte已满8位，则输出该byte并将byte清空
				ofsFile.put(mcByte);
				resetByte();
			}
		}
	}
	if (mnBitsNum != 0){
		//满足8位的前面已经通过resetByte()函数清空了 mbitsNum置为0 而不满足8位的执行下面语句
		//处理最后未满8个字符的byte，用0填充并记录填充的个数
		for (int i = mnBitsNum; i<8; i++)
		{
			addBit(0);
			mnLackNum++;
		}

		ofsFile.put(mcByte);                       //再输出and清空
		resetByte();
	}
	ofsFile.seekp(0, ios::beg);	                  //将写指针移动到文件开头（文件流指针）
	ofsFile.put(mnLackNum);		                  //写入最后一个字节缺失的bit个数
	ifsFile.close();
	ofsFile.close();

	return true;
}

【解压缩函数核心代码】

//解压缩函数 成功执行返回 true 失败 false
bool HuffmanTree::doDecompress(char *pcInput, char *pcOutput)
{
	queue<char> q;
	char c;
	ifstream ifsFile;
	ofstream ofsFile;
	ifsFile.open(pcInput, ios::binary);
	ofsFile.open(pcOutput, ios::binary);
	if (!ifsFile)
	{
		cout << "Unable to open the file" << pcInput << '!' << endl;
		return true;
	}
	if (!ofsFile)
	{
		cout << "Unable to open the file" << pcOutput << '!' << endl;
		return false;
	}

	ifsFile.get(c);
	mnLackNum = c;                 	         //读出最后一个字节缺失的bit个数
	ifsFile.get(c);
	mnRoot = c + 384;	                     //读出根结点的位置
	for (int i = 0; i < nLeaf * 2 - 1; i++)
	{		                                 //建立各结点之间的双亲孩子关系
		ifsFile.get(c);
		if (c == 127)                        //等于127->根节点
			continue;
		else
		{
			HT[i].nParent = c + 384;
			if (HT[c + 384].nLeftChild == -1)//双亲孩子关系——先左后右
				HT[c + 384].nLeftChild = i;
			else
				HT[c + 384].nRightChild = i;
		}
	}

	int _nPoint = mnRoot;

	//为了方便处理最后一个可能有缺失bit的字节，先将读出的数据放入队列
	while (ifsFile.get(c))
		q.push(c);

	//还原文件过程
	while (q.size()>1)
	{	                                     //还未到最后一个字节
		c = q.front();                       //返回队顶元素
		for (int i = 0; i < 8; i++)
		{                                    //先左后右
			if (int(c & 128) == 0){
				_nPoint = HT[_nPoint].nLeftChild;

				//这个左孩子没有左孩子也没有右孩子就把这个输出
				if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1)
				{
					ofsFile.put(char(_nPoint - 128));
					_nPoint = mnRoot;          //更新
				}
				c = c << 1;
			}
			else
			{
				_nPoint = HT[_nPoint].nRightChild;
				if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1)
				{
					ofsFile.put(char(_nPoint - 128));
					_nPoint = mnRoot;
				}
				c = c << 1;
			}
		}
		q.pop();                             //弹出队顶元素
	}

	c = q.front();						     //最后一个字节
	for (int i = 0; i < 8 - mnLackNum; i++)   //原理同上
	{
		if (int(c & 128) == 0)
		{
			_nPoint = HT[_nPoint].nLeftChild;
			if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1)
			{
				ofsFile.put(char(_nPoint - 128));
				_nPoint = mnRoot;
			}
			c = c << 1;
		}
		else{
			_nPoint = HT[_nPoint].nRightChild;
			if (HT[_nPoint].nLeftChild == -1 && HT[_nPoint].nRightChild == -1)
			{
				ofsFile.put(char(_nPoint - 128));
				_nPoint = mnRoot;
			}
			c = c << 1;
		}
	}
	q.pop();
	ifsFile.close();
	ofsFile.close();
	return true;
}

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