信息论编码课程设计(用哈夫曼编码实现一个完整的压缩与解压程序)

课程设计任务书 2011—2012学年第二学期 专业： 信息与计算科学 学号： 姓名： 课程设计名称： 信息论与编码课程设计 设计题目： 用哈夫曼编码实现一个完整的压缩与解压程序 完成期限：自 年 月 日至 年 月 日共 天 一．设计目的 1、深刻理解信源编码的基本思想与目的； 2、理解哈夫曼编码方法的基本过程与特点； 3、详细地理解文件的压缩与解压过程； 4、提高综合运用所学理论知识独立分析和解决问题的能力； 5、使用C语言进行编程。 二．设计内容 假设已知一个文件内部所有的字符，编写适当函数，对其进行哈夫曼编码的编译，同时将其运用位操作进行压缩与解压，并且由其文件内字符长度的压缩和气原本长度进行计算，从而得出压缩率的大小。 三．设计要求 1、编写的函数要有通用性； 2、压缩的文件可以为任意文件，自由选择，并且解压其压缩后的文件显示其是否与原文件内容一致。 四．设计条件 计算机、VC6.0编译环境 五．参考资料 李亦农、李梅 《信息论基础教程》

指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日 摘 要 哈夫曼编码(Huffman Coding)是一种编码方式，也是可变字长编码(VLC)的一种。这种方法完全依据字符出现的概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作哈夫曼编码。对于M进制哈弗曼编码，为了提高编码效率，就要使长码的符号数量尽量少、概率尽量小，所以应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。 本文将采用利用二进制哈夫曼编码来进行文件的压缩与解压。 在二进制哈夫曼编码中，得出码字、平均码长和编码效率，构造哈夫曼树，沿着根节点到叶节点从左到右依次为0、1，并且码字的频率由大到小排序。在本文中采用Visual C++6.0进行编程，此程序中具有输入字符集大小和权值大小，构造哈夫曼树，并对原本的文件进行编码等功能。

关键词：哈弗曼编码；信源；哈夫曼树；Visual C++6.0； 目 录 1课题描述..................................................................................................................... 1 2设计原理..................................................................................................................... 1 3 设计过程.................................................................................................................... 2 3.1软件介绍........................................................................................................... 2 3.1.1 Visual C++ 6.0简介 ............................................................................... 2 3.1.2主要部分................................................................................................. 2 3.2设计内容........................................................................................................... 2 4编码程序分析及其结果............................................................................................. 3 总 结.............................................................................................................................. 7 参考文献........................................................................................................................ 7 课程设计说明书（论文）

第 1 页 共10页 1课题描述 在这个信息量爆炸的时代，凡是能载荷一定信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。为此，必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字最短。能获得最佳码的编码方法主要有：香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。 哈夫曼(Huffman)编码是一种常用的压缩编码方法，是Huffman于1952年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。 哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。 哈夫曼编码是哈夫曼树的一个应用，是一种最优的前缀技术，然而其存在的不足却制约了它的直接应用。首先，其解码时间为O(lavg)，其中lavg为码字的平均长度；其次，更为重要的是，解码器需要知道哈夫曼编码树的结构，因而编码器必须为解码器保存或传输哈夫曼编码树。对于小量数据的压缩而言，这是很大的开销。因而，应用哈夫曼编码的关键是如何降低哈夫曼编码树的存储空间。目前流行的很多压缩方法都是用了该技术，如 GZIB、ZLIB、PNC等。

2设计原理 课程设计说明书（论文）

第 2 页 共10页 3 设计过程

3.1软件介绍 3.1.1 Visual C++ 6.0简介 Visual C++ 6.0，简称VC或者VC6.0，是微软推出的一款C++编译器，将“高级语言”翻译为“机器语言（低级语言）”的程序。Visual C++是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出Visual C++1.0后，随着其新版本的不断问世，Visual C++已成为专业程序员进行软件开发的首选工具。Visual C++6.0由Microsoft开发, 它不仅是一个C++ 编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrated development environment，IDE）。Visual C++6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。 这些组件通过一个名为Developer Studio的组件集成为和谐的开发环境。Microsoft的主力软件产品。Visual C++是一个功能强大的可视化软件开发工具。 Visual C++6.0以拥有“语法高亮”，自动编译功能以及高级除错功能而著称。比如，它允许用户进行远程调试，单步执行等。还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。其编译及创建预编译头文件(stdafx.h)、最小重建功能及累加连结(link)著称。这些特征明显缩短程序编辑、编译及连结的时间花费，在大型软件计划上尤其显著。

3.1.2主要部分 运用C语言将实验中一些关于文件读写功能、二进制数移位，指针的移位，字符的拼接、复制等等编写，该环境将数组中字符或者数字的调用与提取变得简单，同时将文件压缩与解压转换成二进制字符的位操作。

3.2设计内容 压缩部分 1. 构造哈夫曼树，对其进行前缀编码 （1）扫描待压缩文件，得出各字符出现频率。 （2）根据给定的n个权值{W1,W2,...Wn}构成n棵二叉树的集合F={T1，T2，„，课程设计说明书（论文） 第 3 页 共10页 Tn}，每棵二叉树Ti中只有一个带权为Wi的根节点，其左右子树均空。 （3）在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且值新的二叉树的根节点的权值为其左右子树上根节点的全值之和。 （4）在F中删除这两棵树。同时将新得到的二叉树加入F中。 重置（2）和（3），直到F只含一棵树为止。这棵树便是哈夫曼树。 2. 由Huffman树得到各字符前缀编码。 3. 根据前缀编码，对文件中各个字符进行编码，并按每八位一次写入压缩文件。 4. 处理剩余不到八位部分，写入压缩文件。 5. 将前缀编码及相关信息写入压缩文件。 6. 关闭指针，完成压缩。根据前者记录下的原文件字符长以及压缩后的文件长度计算压缩率。 解压部分 1. 读入压缩文件长度和源文件长度。读入前缀编码。 2. 对文件中各字符与压缩相反的进行解码，并写入解压文件。 3. 判断解压文件是否完好（对比压缩前文件长度），关闭指针，完成解压。

4编码程序及其分析 1）定义哈夫曼编码所需的数据 struct head { unsigned char b; //记录字符在数组中的位置 long count; //字符出现频率（权值） long parent,lchild,rchild;//定义哈夫曼树指针变量 char bits[256]; //定义存储哈夫曼编码的数组 } header[512],tmp; 2）压缩过程 1、判断需要压缩的文件是否存在以及是否将压缩后的文件名定义； FILE *ifp,*ofp; printf("\t请您输入需要压缩的文件:"); gets(filename); ifp=fopen(filename,"rb"); if(ifp==NULL) { printf("\n\t文件打开失败!\n\n"); return; } printf("\t请您输入压缩后的文件名："); gets(outputfile); ofp=fopen(outputfile,"wb"); if(ofp==NULL) { printf("\n\t压缩文件失败!\n\n"); return; } 2、计算权值，并初始化并构造哈夫曼树； flength=0; while(!feof(ifp)) { fread(&c,1,1,ifp); header[c].count++;//字符重复出现频率+1 flength++; //字符出现原文件长度+1 } flength--; header[c].count--; for(i=0;i<512;i++) { if(header[i].count!=0) header[i].b=(unsigned char)i; else header[i].b=0;