Skip to content

FLHonker/HuffmanCompress

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

6 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Huffman压缩编码

——使用C++、文件操作和Huffman算法实现“图片压缩程序”。

@Author:Frank Liu

@email:[email protected]

@Blog:https://flhonker.github.io

@time: 2017-05

[TOC]

1. 核心知识

(1) 树的存储结构 (2) 二叉树的三种遍历方法 (3) Huffman树、Huffman编码算法

2. 功能要求

  1. 针对一幅BMP格式的图片文件,统计256种不同字节的重复次数,以每种字节重复次数作为权值,构造一颗有256个叶子节点的哈夫曼二叉树。

  2. 利用上述哈夫曼树产生的哈夫曼编码对图片文件进行压缩。

  3. 压缩后的文件与原图片文件同名,加上后缀.huf(保留原后缀),如pic.bmp 压缩后pic.bmp.huf

3.分析与设计

使用Huffman算法实现图片压缩程序,可分为6个步骤。

(1)创建工程

创建HuffmanCompressCPro工程,定义入口函数int main();

(2)读取原文件

读取文件,统计256种字节重复的次数;

(3)生成Huffman树

根据上一步统计的结果,构建Huffman树;

(4)生成Huffman编码

遍历Huffman树,记录256个叶子节点的路径,生成Huffman编码;

(5)压缩编码

使用Huffman编码,对原文件中的字节重新编码,获得压缩后的文件数据;

(6)保存文件

将编码过的数据,保存到文件“Pic.bmp.huf”中。

4. 数据结构的设计

1.记录统计256种不同字节的重复次数即权值使用整型数组:

unsigned int weight[256];

2.二叉树的存储结构。使用结构体存储节点,使用数组存储树的节点,使用静态二叉链表方式存储二叉树。

struct HTNode{ 
	int weight; 
	int parent; 
	int lchild; 
	int rchild; 
};
typedef HTNode *HuffmanTree;

3.Huffman编码存储结构定义一个二维数组:

char HufCode[256][];

因考虑每个字节的Huffman编码长度不一样,可使用字符串指针数组:

typedef char **HuffmanCode;

4.压缩文件的算法的数据结构:

为正确解压文件,除了要保存原文件长度外,还要保存原文件中256种字节重复的次数,即权值。定义一个文件头,保存相关的信息:

struct HEAD { 
	char type[4];        //文件类型 
	int length;         //原文件的长度 
	char weight[256];    //权值 
}

压缩文件时,定义一个内存缓冲区:

char *pBuffer; //其大小视原文件压缩后的大小

5. 核心算法设计

**(1)构造Huffman树算法 **

void CreateHuffmanTree(HuffmanTree &pHT, int weight[])
{
	/* i、j:循环变量,m1、m2:构造哈夫曼树不同过程中两个最小权值结点的权值,
	x1、x2:构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
	int i, j, m1, m2, x1, x2;
	HuffmanTree p;
	pHT = (HuffmanTree)malloc(2 * nSIZE * sizeof(HTNode));
	for (p = pHT, i = 0; i < nSIZE; ++i, ++p)
		*p = { weight[i], -1, -1, -1 };
	for (; i < 2 * nSIZE - 1; ++i, ++p)
		*p = { 0, -1, -1, -1 };
	/* 循环构造 Huffman 树 */
	for (i = 0; i<nSIZE - 1; i++)
	{
		m1 = m2 = MAXVALUE;     /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
		x1 = x2 = 0;
		/* 找出所有结点中权值最小、无父结点的两个结点,并合并之为一颗二叉树 */
		for (j = 0; j<nSIZE + i; j++)
		{
			if (pHT[j].weight < m1 && pHT[j].parent == -1)
			{
				m2 = m1;
				x2 = x1;
				m1 = pHT[j].weight;
				x1 = j;
			}
			else if (pHT[j].weight < m2 && pHT[j].parent == -1)
			{
				m2 = pHT[j].weight;
				x2 = j;
			}
		}
		/* 设置找到的两个子结点 x1、x2 的父结点信息 */
		pHT[x1].parent = nSIZE + i;
		pHT[x2].parent = nSIZE + i;
		pHT[nSIZE + i].weight = pHT[x1].weight + pHT[x2].weight;
		pHT[nSIZE + i].lchild = x1;
		pHT[nSIZE + i].rchild = x2;
	}
}

**(2)生成Huffman编码算法 **

int HuffmanCoding(HuffmanCode &pHC, HuffmanTree &pHT)
{
	// 无栈非递归遍历Huffman树,求Huffman编码
	char cd[nSIZE] = { '\0' };// 记录访问路径
	int cdlen = 0;// 记录当前路径长度
	int i, c, p;
	for (i = 0; i < nSIZE; i++)
	{
		int start = 255;
		c = i;
		p = pHT[c].parent;
		while (p != -1)         /* 双亲结点存在 */
		{
			if (pHT[p].lchild == c)
				cd[--start] = '0';
			else
				cd[--start] = '1';
			c = p;
			p = pHT[c].parent;    /* 设置下一循环条件 */
		}
		//cd[cdlen] = '\0';

		/* 保存求出的每个叶结点的哈夫曼编码 */
		strcpy(pHC[i], &cd[start]);
		//pHC[i] = (char*)malloc((cdlen + 1) * sizeof(char));
		//pHC[i] = cd;
	}
	return OK;
}

(3)压缩编码算法

int Encode(const char *pFilename, const HuffmanCode pHC, char *pBuffer, const int nSize)
{
	// 开辟缓冲区
	pBuffer = (char *)malloc(nSize * sizeof(char));
	if (!pBuffer)
	{
		cerr << "开辟缓冲区失败!" << endl;
		return ERROR;
	}

	char cd[SIZE] = { ‘\0’ };  // 工作区
	int pos = 0;		// 缓冲区指针
	int ch;
	FILE *in = fopen(pFilename, "rb");
	// 扫描文件,根据Huffman编码表对其进行压缩,压缩结果暂存到缓冲区中。
	while ((ch = fgetc(in)) != EOF)
	{
		strcat(cd, pHC[ch]);	// 从pHC复制编码串到cd
								// 压缩编码
		while (strlen(cd) >= 8)
		{
			// 截取字符串左边的8个字符,编码成字节
			pBuffer[pos++] = Str2byte(cd);
			// 字符串整体左移8字节
			for (int i = 0; i < SIZE - 8; i++)
			{
				cd[i] = cd[i + 8];
			}
		}
	}
	if (strlen(cd) > 0)
	{
		pBuffer[pos++] = Str2byte(cd);
	}

}

int Compress(const char *pFilename, HuffmanCode &pHC, const HEAD sHead)
{
	//计算缓冲区的大小  
	int nbuf = 0;
	for (int i = 0; i<nSIZE; i++)
	{
		nbuf += sHead.weight[i] * sizeof(pHC[i]);
	}
	nbuf = (nbuf % 8) ? nbuf / 8 + 1 : nbuf / 8;
	//cout<<"nbuf = "<<nbuf<<endl; 
	char *pBuffer = NULL;
	Encode(pFilename, pHC, pBuffer, nbuf);
	if (!pBuffer)
		return ERROR;
	int result = WriteFile(pFilename, sHead, pBuffer, nbuf);
	return result;
}

(4)生成压缩文件算法:

int WriteFile(const char *pFilename, const HEAD sHead, char *pBuffer, const int nbuf)
{
	// 生成文件名
	char filename[nSIZE + 5] = { '\0' };
	strcpy(filename, pFilename);
	strcat(filename, ".huf");

	// 以二进制流形式打开文件
	FILE *fout = fopen(filename, "wb");
	// 写文件头
	fwrite(&sHead, sizeof(HEAD), 1, fout);
	// 写压缩后的编码
	fwrite(pBuffer, sizeof(char), nbuf, fout);
	//	cout<<"fwrite2 OK!"<<endl;
	// 关闭文件,释放文件指针
	fclose(fout);
	fout = NULL;

	cout << "生成压缩文件:" << filename << endl;
	int len = sizeof(HEAD) + strlen(pFilename) + 1 + nbuf;
	cout << "压缩文件大小为:" << len << "B" << endl;

	FILE *finhuf = fopen(filename, "rb");
	int ch, huflength = 0;
	// 扫描文件,获得权重
	while ((ch = fgetc(finhuf)) != EOF)
		huflength++;
	// 关闭文件
	fclose(finhuf);
	finhuf = NULL;
	float rate = huflength * 1.0 / sHead.length * 100;
	cout.setf(ios::fixed);
	cout << "压缩率为:" << setprecision(4) << rate << "%" << endl;

	return len;
}

6. 开发环境

  • Windows10_x64
  • Microsoft Visual Studio 2013以上开发环境

7. 调试说明

调试主要内容为编写程序的语法正确性与否,程序逻辑的正确性与否。调试手段主要采用了Microsoft Visual Studio 2015集成开发环境中“调试(D)”菜单中的调试方法或手段。即:F5:启动调试;F11:逐语句调试;F12:逐过程调试;F9:切换断点;ctrl+B:新建断点等。并且根据VS2015的文本编辑器智能语法提示修改已知错误,然后启用调试,待调试通过检查运行结果,最后用边界值等进行多方面测试,保证程序的健壮性。

  1. 在读取图片文件统计0-255个字符的权值的过程中,一开始采用了C++的ifstream fin(“Pic.bmp”)文件流,然后通过while(fin>>ch){ cout<<ch;}测试输出文件字符码,就出现了无限循环,一直连续不断地输出6位十六进制的数。当时认为是文件流读取方式的原因,加了iOS::binary来控制采用二进制形式,还是没有解决。改用C语言的FILE *fp = fope( )终于可以正常读取输出文件字符码,但是还是没有找出C++读取失败的原因。

  2. 文件编码压缩Encode()函数会产生编码后的一个缓冲区char *pBuffer;写文件函数会使用它直接写磁盘文件。调试过程中并没发现任何问题,就是不能成功地写后缀为.huf的文件。在相关函数中设置断点,观察缓冲区的情况,且编写屏幕输出缓冲区数据的程序段,发现缓冲区是空的。通过在Encode函数中以及 WriteFile函数中做同样的跟踪调试,发现在Encode函数中建立的缓冲区数据并没有带出来,通过分析发现是缓冲区空间构建位置的问题,即不能直接用这个变量做Encode()函数形参,而应该采用指针或者引用类型做函数形参,这样可以通过直接访问pBuffer的内存地址改变缓冲区内容。

  3. 编译时没有错误,通过 pHC[i] = (char*)malloc((cdlen + 1) * sizeof(char)); 获取内存空间,然后pHC[i] = cd; 将字符串数组cd的内容复制到pHC[i]中时出现了内存错误。编译后无错误,运行时出现错误一般是指针使用是内存分配出现错误。打开调试界面查看CPU状态,看到汇编代码,但是汇编功底不是很深,还是没有找到底层原因。只好换了一种实现方式:strcpy(pHC[i], &cd[start]); 问题得以解决。

  4. 编译时总是提示fopen,strcpy,strcat等函数存在不安全问题,采用了3中方法中一种屏蔽了该报错。即在文件开头添加:

#pragma warning(disable:4996)

  1. 在Dev-cpp里面调试时完全没有问题,移植到VC2015里,编译通过,就是执行时fwrite()函数处发生中断。数据格式没有问题,指针也没有错误使用,提示信息显示访问冲突,可是所有的文件流用完都关闭了。最终通过异常处理得到了解决。

8. 测试效果

使用屏幕截图编辑成bmp图片文件pic.bmp测试哈夫曼压缩程序效果截图如下 各图。图1为输入文件名压缩成功界面;图2为读取Pic.bmp产生的部分不同权值字节信息;图3、4为Pic.bmp生成的HuffmanTree结点信息;图5为生成的Huffman编码信息;图6为Pic.bmp压缩大小及压缩率。

图1:输入文件名压缩成功界面

图2:读取Pic.bmp产生的部分不同权值字节信息

图3、4:Pic.bmp生成的HuffmanTree结点信息

图5:生成的Huffman编码信息

图6:Pic.bmp压缩大小及压缩率

9. 综合分析和结论

(1)在Huffman编码的过程中,对字符按概率有大到小的顺序重新排列,应使合并后的新符号尽可能排在靠前的位置,这样可使合并后的新符号重复编码次数减少,使短码得到充分利用。

(2)Huffman编码效率相当高,对编码器的要求也简单得多。

(3)Huffman它保证了出现概率大的符号对应于短码,概率小的符号对应于长码,每次字符的最后两个码字总是最后一位码元不同,前面的各位码元都相同,每次字符的最长两个码字有相同的码长。

(4)Huffman的编法并不一定是唯一的。

(5)通过上述测试用例的效果截图,可以看出:使用Huffman编码对格式为bmp的图片文件的压缩比在50%左右,但对WinRAR软件已经压缩的图片文件或文本文件的压缩情况不佳。