基于Huffman哈夫曼算法实现的图片压缩程序

Ridiculous

发布日期: 2020-10-06 10:41:23 浏览量: 100
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

1. 核心知识

  • 树的存储结构

  • 二叉树的三种遍历方法

  • Huffman树、Huffman编码算法

2. 功能要求

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

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

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

3.分析与设计

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

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

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

  • 生成Huffman树:根据上一步统计的结果,构建Huffman树

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

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

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

4. 数据结构的设计

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

    1. unsigned int weight[256];
  • 二叉树的存储结构:使用结构体存储节点,使用数组存储树的节点,使用静态二叉链表方式存储二叉树

    1. struct HTNode{
    2. int weight;
    3. int parent;
    4. int lchild;
    5. int rchild;
    6. };
    7. typedef HTNode *HuffmanTree;
  • 二维数组:Huffman编码存储结构定义一个二维数组

    1. char HufCode[256][];
  • 字符串指针数组:因考虑每个字节的Huffman编码长度不一样,可使用字符串指针数组

    1. typedef char **HuffmanCode;
  • 压缩文件的算法的数据结构:为正确解压文件,除了要保存原文件长度外,还要保存原文件中256种字节重复的次数,即权值。定义一个文件头,保存相关的信息:

    1. struct HEAD {
    2. char type[4]; //文件类型
    3. int length; //原文件的长度
    4. char weight[256]; //权值
    5. }
  • 内存缓冲区:压缩文件时,定义一个内存缓冲区

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

5. 核心算法设计

5.1 构造Huffman树算法

  1. void CreateHuffmanTree(HuffmanTree &pHT, int weight[])
  2. {
  3. /* i、j:循环变量,m1、m2:构造哈夫曼树不同过程中两个最小权值结点的权值,
  4. x1、x2:构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
  5. int i, j, m1, m2, x1, x2;
  6. HuffmanTree p;
  7. pHT = (HuffmanTree)malloc(2 * nSIZE * sizeof(HTNode));
  8. for (p = pHT, i = 0; i < nSIZE; ++i, ++p)
  9. *p = { weight[i], -1, -1, -1 };
  10. for (; i < 2 * nSIZE - 1; ++i, ++p)
  11. *p = { 0, -1, -1, -1 };
  12. /* 循环构造 Huffman 树 */
  13. for (i = 0; i<nSIZE - 1; i++)
  14. {
  15. m1 = m2 = MAXVALUE; /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
  16. x1 = x2 = 0;
  17. /* 找出所有结点中权值最小、无父结点的两个结点,并合并之为一颗二叉树 */
  18. for (j = 0; j<nSIZE + i; j++)
  19. {
  20. if (pHT[j].weight < m1 && pHT[j].parent == -1)
  21. {
  22. m2 = m1;
  23. x2 = x1;
  24. m1 = pHT[j].weight;
  25. x1 = j;
  26. }
  27. else if (pHT[j].weight < m2 && pHT[j].parent == -1)
  28. {
  29. m2 = pHT[j].weight;
  30. x2 = j;
  31. }
  32. }
  33. /* 设置找到的两个子结点 x1、x2 的父结点信息 */
  34. pHT[x1].parent = nSIZE + i;
  35. pHT[x2].parent = nSIZE + i;
  36. pHT[nSIZE + i].weight = pHT[x1].weight + pHT[x2].weight;
  37. pHT[nSIZE + i].lchild = x1;
  38. pHT[nSIZE + i].rchild = x2;
  39. }
  40. }

5.2 生成Huffman编码算法

  1. int HuffmanCoding(HuffmanCode &pHC, HuffmanTree &pHT)
  2. {
  3. // 无栈非递归遍历Huffman树,求Huffman编码
  4. char cd[nSIZE] = { '\0' };// 记录访问路径
  5. int cdlen = 0;// 记录当前路径长度
  6. int i, c, p;
  7. for (i = 0; i < nSIZE; i++)
  8. {
  9. int start = 255;
  10. c = i;
  11. p = pHT[c].parent;
  12. while (p != -1) /* 双亲结点存在 */
  13. {
  14. if (pHT[p].lchild == c)
  15. cd[--start] = '0';
  16. else
  17. cd[--start] = '1';
  18. c = p;
  19. p = pHT[c].parent; /* 设置下一循环条件 */
  20. }
  21. //cd[cdlen] = '\0';
  22. /* 保存求出的每个叶结点的哈夫曼编码 */
  23. strcpy(pHC[i], &cd[start]);
  24. //pHC[i] = (char*)malloc((cdlen + 1) * sizeof(char));
  25. //pHC[i] = cd;
  26. }
  27. return OK;
  28. }

5.3 压缩编码算法

  1. int Encode(const char *pFilename, const HuffmanCode pHC, char *pBuffer, const int nSize)
  2. {
  3. // 开辟缓冲区
  4. pBuffer = (char *)malloc(nSize * sizeof(char));
  5. if (!pBuffer)
  6. {
  7. cerr << "开辟缓冲区失败!" << endl;
  8. return ERROR;
  9. }
  10. char cd[SIZE] = { \0 }; // 工作区
  11. int pos = 0; // 缓冲区指针
  12. int ch;
  13. FILE *in = fopen(pFilename, "rb");
  14. // 扫描文件,根据Huffman编码表对其进行压缩,压缩结果暂存到缓冲区中。
  15. while ((ch = fgetc(in)) != EOF)
  16. {
  17. strcat(cd, pHC[ch]); // 从pHC复制编码串到cd
  18. // 压缩编码
  19. while (strlen(cd) >= 8)
  20. {
  21. // 截取字符串左边的8个字符,编码成字节
  22. pBuffer[pos++] = Str2byte(cd);
  23. // 字符串整体左移8字节
  24. for (int i = 0; i < SIZE - 8; i++)
  25. {
  26. cd[i] = cd[i + 8];
  27. }
  28. }
  29. }
  30. if (strlen(cd) > 0)
  31. {
  32. pBuffer[pos++] = Str2byte(cd);
  33. }
  34. }
  35. int Compress(const char *pFilename, HuffmanCode &pHC, const HEAD sHead)
  36. {
  37. //计算缓冲区的大小
  38. int nbuf = 0;
  39. for (int i = 0; i<nSIZE; i++)
  40. {
  41. nbuf += sHead.weight[i] * sizeof(pHC[i]);
  42. }
  43. nbuf = (nbuf % 8) ? nbuf / 8 + 1 : nbuf / 8;
  44. //cout<<"nbuf = "<<nbuf<<endl;
  45. char *pBuffer = NULL;
  46. Encode(pFilename, pHC, pBuffer, nbuf);
  47. if (!pBuffer)
  48. return ERROR;
  49. int result = WriteFile(pFilename, sHead, pBuffer, nbuf);
  50. return result;
  51. }

5.4 生成压缩文件算法

  1. int WriteFile(const char *pFilename, const HEAD sHead, char *pBuffer, const int nbuf)
  2. {
  3. // 生成文件名
  4. char filename[nSIZE + 5] = { '\0' };
  5. strcpy(filename, pFilename);
  6. strcat(filename, ".huf");
  7. // 以二进制流形式打开文件
  8. FILE *fout = fopen(filename, "wb");
  9. // 写文件头
  10. fwrite(&sHead, sizeof(HEAD), 1, fout);
  11. // 写压缩后的编码
  12. fwrite(pBuffer, sizeof(char), nbuf, fout);
  13. // cout<<"fwrite2 OK!"<<endl;
  14. // 关闭文件,释放文件指针
  15. fclose(fout);
  16. fout = NULL;
  17. cout << "生成压缩文件:" << filename << endl;
  18. int len = sizeof(HEAD) + strlen(pFilename) + 1 + nbuf;
  19. cout << "压缩文件大小为:" << len << "B" << endl;
  20. FILE *finhuf = fopen(filename, "rb");
  21. int ch, huflength = 0;
  22. // 扫描文件,获得权重
  23. while ((ch = fgetc(finhuf)) != EOF)
  24. huflength++;
  25. // 关闭文件
  26. fclose(finhuf);
  27. finhuf = NULL;
  28. float rate = huflength * 1.0 / sHead.length * 100;
  29. cout.setf(ios::fixed);
  30. cout << "压缩率为:" << setprecision(4) << rate << "%" << endl;
  31. return len;
  32. }

6. 开发环境

  • Windows10_x64

  • Microsoft Visual Studio 2015

7. 调试说明

调试主要内容为编写程序的语法正确性与否,程序逻辑的正确性与否。调试手段主要采用了Microsoft Visual Studio 2015集成开发环境中“调试(D)”菜单中的调试方法或手段。即:

  • F5:启动调试

  • F11:逐语句调试

  • F12:逐过程调试

  • F9:切换断点

  • ctrl+B:新建断点

并且根据VS2015的文本编辑器智能语法提示修改已知错误,然后启用调试,待调试通过检查运行结果,最后用边界值等进行多方面测试,保证程序的健壮性。

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

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

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

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

  1. #pragma warning(disable:4996)
  • 在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. 综合分析和结论

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

  • 哈弗曼编码效率相当高,对编码器的要求也简单得多

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

  • 哈弗曼的编法并不一定是唯一的

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

上传的附件 cloud_download 基于Huffman哈夫曼算法实现的图片压缩程序.7z ( 1.12mb, 2次下载 )
error_outline 下载需要9点积分

发送私信

难过时,吃一粒糖,告诉自己生活是甜的

12
文章数
15
评论数
最近文章
eject