基于Huffman赫夫曼编码的本压缩程序.doc

1、数据结构课程设计课程设计报告基于赫夫曼编码的文本压缩程序 班级： 09计单学号： 20090502137姓名： 夏军指导教师： 鞠训光 成绩：2011年 6 月 25 日一、 目的及意义通过课程设计的综合训练，旨在帮助学生进一步系统的掌握数据结构这门课的主要内容，并进一步培养学生分析问题和解决问题的能力，主要体现在能够让学生针对实际问题有效地组织数据，选择合适的数据结构，并进行正确和高效地算法设计，并用程序实现算法。该课的课程设计是一个良好的程序设计技能训练的过程使学生能够：1. 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。2. 初步掌握软件开发过程的问题分析、系统设计、

2、程序编码、测试等基本技能和方法。3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力。4. 训练用系统的观点和软件开发一般规范进行软件开发，培养计算机科学与技术专业学生所具备的科学的工作方法和作风。二、程序功能描述程序实现的功能：对文本文件进行压缩以及对压缩的文本文件进行解压缩。程序的实现的理论依据是赫夫曼编码。赫夫曼编码是一种无损的压缩算法，一般用来压缩文本和程序文件。赫夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。程序由三个文件组成：头文

3、件CourseDesign.h、函数实现文件CourseDesign.cpp、测试文件Test.cpp。在CourseDesign.h中声明数据的存储结构以及程序所需要的处理函数；CourseDesign.cpp文件实现在CourseDesign.h中声明的函数；Test.cpp负责对所实现的函数进行调用测试，确定是否满足程序设计要求。利用赫夫曼编码实现对文本的压缩的过程大致为：打开要压缩的文本文件，读取文件中的字符，统计文件中不同字符出现的频率，建立赫夫曼树，通过赫夫曼树对出现的互不相同的字符进行编码，建立编码表，接着将将赫夫曼树（即解码表）写入压缩文件中。再次重新读取文件中的字符，对每个字

4、符通过查阅编码表确定对应的编码，将该字符的赫夫曼编码写入压缩文件。对压缩文件的解压过程为：打开压缩文件，读取压缩文件解码表部分，读取压缩文件的编码数据，将压缩数据通过解码表进行解码，将解码出的字符写入解码文件中。程序执行后，用户按照程序的提示选择相应的功能选项。当用户选择压缩功能，此时程序要求用户输入要压缩的文本文件的路径，用户输入完成后。程序检查文件是否能够建立。检查完成后，程序将文件从硬盘读入内存。接着程序将统计不同字符出现的频率以及建立编码表的初步结构。例如当文件中存有如下表所示字符。表1 文件字符属性表字符第一字节机内码/ASCII第二字节机内码权重的18119620a9709把176

5、20914表1772375班1762241补1781852百17621417防18319212飞1832019博17816913包1762522才1781976方1831898拜1762213A6503份1832215必1772165英文字符在计算机中是以标准ASCII码进行表示，一个英文字符占一个字节空间，编码范围为0127；汉字在计算机中是以GB2312编码进行表示。每个汉字占两个字节存储空间，汉字的存储使用机内码，各字节的机内码编码范围为160254。现在需要考虑使用怎样的数据结构来存放这些字符，如果采用如下简单的数据结构存放：typedef struct char data3; / 存

6、放字符int internal_code1; / 存放第一字节的机内码/ASCII码int internal_code2; / 存放第二字节的机内码，英文默认为0int weight; / 存放字符的权重char *code; / 字符的赫夫曼编码CodeList, *CodePList;分析所要处理的字符数据会发现：许多的字符的第一字节的机内码相同，如“防”、“飞”、“方”、“份”，第一字节机内码都是183。这是因为汉字是通过划分区号和位号来表示的，所有汉字被划分成了94个区，94个位，所以当汉字属于同一个区，那么它的第一字节机内码就会相同。如果采用如上的数据结构建立的线性表来存放处理字符，

7、就会存在大量数据冗余。在这种情况下，就有必要为特定的数据设计合适的数据结构。通过分析，采用如下数据结构：typedef structchar internal_code; / 存放第二字节机内码char *code; / 存放字符的赫夫曼编码InternalCode;typedef structint count; / 已编码字符数char internal_code; / 存放第一字节机内码InternalCode *internal_code_address; / 第二字节机内码及字符的 HuffmanCode, *HuffmanPCode; /赫夫曼编码的地址 该结构的优点：当汉字的第一

8、字节机内码相同，则该第一字节机内码只会被存储一次，从而消除汉字第一字节机内码存储的冗余，而且可以方便的使用折半查找快速检索编码表来确定字符的赫夫曼编码。采用该数据结构对表1数据进行表示如图1。图1 编码表HC的存储结构这种数据结构形式上类似于图的邻接表结构，功能上类似于哈希表的链地址法。但邻接表的表结点采用链式存储，而图1的表结点和头结点都采用线性表储存。图1中编码表HC的内码1是纵向非递减排列，内码2是横向非递减排列。HCi.count HCi 1.count等于HCi实际存储的字符数量。例如, HC3中字符数为7，HC2中字符数为2，则HC3存放了5个字符，这5个字符拥有相同的第一字节机内

9、码176。程序执行压缩操作详细过程：当程序从文件中读取一个字符后，通过字符的编码范围分析该字符是属于ASCII还是GB2312,若是ASCII编码，增加编码表HC纵向表长，将该字符的ASCII码按非递减次序插入到内码1处，并将当前位置的字符数加1，并置内码2默认为0；如果是汉字，首先通过折半查找算法纵向查找编码表HC的内码1成员，若当前汉字第一字节机内码已经出现过，则折半查找返回该机内码1在HC表中的位置，增加当前位置的横向表长，将汉字的第二字节机内码按非递减次序插入当前位置的内码2处。否则将汉字的第一字节机内码按非递减次序插入HC表的内码1区域，第二字节机内码直接插入内码2处。在读取文件的同

10、时记录文件中各字符出现的频率，当编码表HC表构建完成，此时w = 3, 9, 14, 3, 1, 2, 17, 5, 5, 13, 2, 6, 20, 9, 8, 5, 12。依次从w中选择权重最小并且双亲为0的两个结点，根据这两个结点生成新的结点，新结点的权重为这两个最小结点的和，新结点的左右子树为这两个结点在w中的位置。根据表1数据构建赫夫曼树如图2所示。赫夫曼树存储结构的初始状态如图3(a)，终结状态如图3(b)。图2 根据表1构造的赫夫曼树图3 (a) HT初始状态 图3 (b) HT终止状态根据生成的赫夫曼树对HC表中的字符进行编码，编码的方法：从该叶子到根逆向求该字符的编码。例如图

11、2中“把”的权值为14，对应的编码为：“000”。将得到的赫夫曼编码写入HCi.internal_code_addressj.code指向的区域。当字符编码完成之后，打开压缩文件，将赫夫曼树HT中除权重以外的数据（解码无需权重信息）写入压缩文件中，作为下一次解压缩的解码表。再次打开要压缩的文本文件，读取文件中的字符，根据编码的范围确定该字符是ASCII还是GB2312，如果ASCII则调用折半查找函数，在编码表HC中进行纵向查找，查找此ASCII出现的位置p1，该字符的编码为HCp1.internal_code_address1.code；如果字符是汉字，则调用折半查找先纵向查找该汉字的第一字

12、节机内码在HC中的位置p1，然后从HCp1.internal_code_address开始横向查找该汉字的第二字节机内码的位置p2，这样就得到了该汉字的赫夫曼编码为HCp1.internal_code_addressp2.code因为赫夫曼编码在HC表中是以字符串形式存放（因为计算机的基本储单位是字节，如果以位存放，需要另设一个空间来表示未编码的位空间大小）。所以需要将字符串“0101“转换为二进制0101写入文件。因为每个赫夫曼编码的长度是不一样的，假设某字符的赫夫曼长度为4，则将该编码写入一个字节后，还剩余4个位，则下一次可以继续从第5个位开始写入，当所有字符的编码都写入完毕后，最后一个字

13、节并不一定会用完，所以需要附设一个字节来记录最后一个字符编码实际写入的编码位数。编码文件的结构如下图所示：图4 压缩文件存储结构程序解压文件：打开压缩文件，取出压缩文件的解码表长度N，根据N读取N条解码表记录，重建解码表HT，然后读取压缩数据DATA，解码的过程是从根出发，按DATA数据的0或1确定找左子树还是右子树，直至叶子结点，便求得了DATA相应的字符。将字符写入文件，直至所有DATA数据处理完毕，整个解压过程结束。三、程序源代码1. 头文件CourseDesign.h#ifndef _COURSEDESIGN_H_#define _COURSEDESIGN_H_/-Huffman树存储

14、结构typedef struct char ch3;unsigned int weight;unsigned int parent, lchild, rchild;HTNode, *HuffmanTree;/-Huffman编码表存储结构typedef structchar internal_code;char *code;InternalCode;typedef structint count;char internal_code;InternalCode *internal_code_address;HuffmanCode, *HuffmanPCode;/-解码表存储结构typedef s

15、tructchar ch3;unsigned int lchild, rchild;DecodeList, *DecodePList;/-辅助数组，置/取一个字节的指定位const static unsigned char mask8 = 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01;template static int Search_Bin(int key, T L, int low, int high);template static void InsertSort(T L , int start, int end);void Select

16、(const HuffmanTree HT, int n, int &s1, int &s2);void Statistics(HuffmanPCode &HC, int internal_code1, int internal_code2, int (*FrequencyMeter)255, int &n);bool Init(char *filename, HuffmanPCode &HC, int *&w, int &n);void CreateHuffmanTree(HuffmanTree &HT, const HuffmanPCode HC, const int *w, int n)

17、;void HuffmanCoding(const HuffmanTree HT, HuffmanPCode HC, int n);bool Compress(char *ifilename, char *ofilename, const HuffmanPCode HC, const HuffmanTree HT, int n);bool DeCompress(char *ifilename, char *ofilename);void Interface();#endif2. 函数实现文件CourseDesign.cpp#includeCourseDesign.h#include#inclu

18、de#include#include#includeusing namespace std;/-折半查找-templateint Search_Bin(int key, T L, int low, int high)int mid = 0;int internal_code;while (low key)high = mid - 1;elselow = mid + 1;return 0;/-对HC表的字符域做插入非递减排序-templatevoid InsertSort(T L , int start, int end)int i;L0 = Lend;i = end - 1;while (i

19、= start & int(Li.internal_code & 0xFF) int(L0.internal_code & 0xFF)Li + 1 = Li;i-;Li + 1 = L0;/- 寻找权重最小的两个结点-void Select(const HuffmanTree HT, int n, int &s1, int &s2)int i = 0;s1 = s2 = 0;for (i = 1; i = n; +i)if (HTi.parent = 0)if (s1 = 0)s1 = i;else if (s2 = 0)s2 = i;else if (HTi.weight HTs1.weig

20、ht | HTi.weight HTs2.weight)s1 = HTs1.weight HTs2.weight ? s1 : s2;s2 = i;/-构建HC.internal_code以及HC.internal_code_address结构-void Statistics(HuffmanPCode &HC, int internal_code1, int internal_code2, int (*FrequencyMeter)255, int &n)int position;if (internal_code1 128)if (FrequencyMeterinternal_code10

21、= 0)+n;HC = (HuffmanPCode)realloc(HC, (n + 1) * sizeof(HuffmanCode);HCn.internal_code = internal_code1;HCn.count = 1;HCn.internal_code_address = (InternalCode *)malloc(2 * sizeof(InternalCode);HCn.internal_code_address1.internal_code = 0; /0号单元未用InsertSort(HC, 1, n);+FrequencyMeterinternal_code10;el

22、seif (FrequencyMeterinternal_code1internal_code2 = 0)position = Search_Bin(internal_code1, HC, 1, n);if (position != 0)+HCposition.count;HCposition.internal_code_address = (InternalCode *)realloc(HCposition.internal_code_address, (HCposition.count + 1) * sizeof(InternalCode);HCposition.internal_code

23、_addressHCposition.count.internal_code = internal_code2;InsertSort(HCposition.internal_code_address, 1, HCposition.count);else+n;HC = (HuffmanPCode)realloc(HC, (n + 1) * sizeof(HuffmanCode);HCn.internal_code = internal_code1;HCn.count = 1;HCn.internal_code_address = (InternalCode *)malloc(2 * sizeof

24、(InternalCode);HCn.internal_code_address1.internal_code = internal_code2;InsertSort(HC, 1, n);+FrequencyMeterinternal_code1internal_code2;/-统计不同字符出现的频率以及构建HC的机内码成员结构-bool Init(char *filename, HuffmanPCode &HC, int *&w, int &n)ifstream ifs(filename);int i = 0, j = 0;int FrequencyMeter255255 = 0;char

25、ch1, ch2;n = 0;HC = NULL;w = NULL;if (ifs.fail()coutcant open file! 128)ch2 = ifs.get();elsech2 = 0;Statistics(HC, int(ch1 & 0xFF), int(ch2 & 0xFF), FrequencyMeter, n);HC0.count = 0;for (i = 2; i = n; +i) HCi.count += HCi - 1.count;w = (int *)malloc(HCn.count * sizeof(int);for (i = 1; i = n; +i)for

26、(j = HCi - 1.count; j HCi.count; +j)wj = FrequencyMeterint(HCi.internal_code & 0xFF)int(HCi.internal_code_addressj - HCi - 1.count + 1.internal_code & 0xFF);ifs.close();return true;/-构造赫夫曼树HT-void CreateHuffmanTree(HuffmanTree &HT, const HuffmanPCode HC, const int *w, int n)int i = 0, j = 0;int m =

27、0, s1 = 0, s2 = 0;if (HCn.count = 1) return;m = 2 * HCn.count - 1;HT = (HuffmanTree)malloc(m + 1) * sizeof(HTNode);for (i = 1; i = n; +i)for (j = HCi - 1.count + 1; j = HCi.count; +j, +w)HTj.ch0 = HCi.internal_code;HTj.ch1 = HCi.internal_code_addressj - HCi - 1.count.internal_code;HTj.ch2 = 0;HTj.we

28、ight = *w;HTj.lchild = HTj.rchild = HTj.parent = 0;for (i = HCn.count + 1; i = m; +i)*HTi.ch = 0;HTi.weight = HTi.lchild = HTi.rchild = HTi.parent = 0;for (i = HCn.count + 1; i = m; +i)Select(HT, i - 1, s1, s2);HTs1.parent = i; HTs2.parent = i;HTi.lchild = s1; HTi.rchild = s2;HTi.weight = HTs1.weigh

29、t + HTs2.weight;/-建立编码表HC-void HuffmanCoding(const HuffmanTree HT, HuffmanPCode HC, int n)int start = 0, c = 0, f = 0;int i = 0, k = 1, r = 1; ;char *cd = NULL;cd = (char *)malloc(HCn.count * sizeof(char);cdHCn.count - 1 = 0;for (i = 1; i HCr.count - HCr - 1.count)k = 1;+r;HCr.internal_code_addressk

30、.code = (char *)malloc(HCn.count - start) * sizeof(char);strcpy(HCr.internal_code_addressk.code, &cdstart);+k;free(cd);/-压缩文件-bool Compress(char *ifilename, char *ofilename, const HuffmanPCode HC, const HuffmanTree HT, int n)ifstream ifs(ifilename);ofstream ofs(ofilename, ios:binary);int bit_size =

31、0;int position1, position2;int internal_code1, internal_code2;char ch;char code = 0;char *code_address;DecodePList decode_list = (DecodePList)malloc(HCn.count * 2) * sizeof(DecodeList);if (ifs.fail() | ofs.fail()coutCant open the file!endl;return false;ofs.write(char *)&HCn.count, sizeof(int); /写入解码

32、表for (int i = 1; i = 2 * HCn.count - 1; +i)strcpy(decode_listi.ch, HTi.ch);decode_listi.lchild = HTi.lchild;decode_listi.rchild = HTi.rchild;ofs.write(char *)&decode_listi, sizeof(DecodeList);while (ch = ifs.get() != EOF)internal_code1 = int(ch & 0xFF);position1 = Search_Bin(internal_code1, HC, 1, n

33、);if (internal_code1 128)internal_code2 = 0;position2 = 1;elseinternal_code2 = int(ifs.get() & 0xFF);position2 = Search_Bin(internal_code2, HCposition1.internal_code_address, 1, HCposition1.count - HCposition1 - 1.count);code_address = HCposition1.internal_code_addressposition2.code;while (*code_add

34、ress)code |= (*code_address+ - 48) * maskbit_size % 8;+bit_size;if (bit_size % 8 = 0)ofscode;code = 0;if (bit_size % 8 != 0)ofscode;ofschar(bit_size % 8);elseofschar(8);ifs.clear();ifs.seekg(0, ios:end);cout压缩完成！endl;cout原始文件大小： ifs.tellg() Bendl;cout压缩文件大小: ofs.tellp() Bendl;cout压缩率:float(ofs.tellp

35、()/float(ifs.tellg()*100 %nn;free(decode_list);free(HT);free(HC);ifs.close();ofs.close();return true;/-解压缩文件-bool DeCompress(char *ifilename, char *ofilename)ifstream ifs(ifilename,ios:binary);ofstream ofs(ofilename);int bit_size;int i;int m, n;char buf;int value;DecodePList decode_list;if (ifs.fail

36、() | ofs.fail()coutCant open the file!endl;return false;ifs.read(char *)&n, sizeof(int); / 读取解码表m = 2 * n - 1;decode_list = (DecodePList)malloc(m + 1) * sizeof(DecodeList);for (i = 1; i = m; +i)ifs.read(char *)&decode_listi, sizeof(DecodeList);streampos pos1 = ifs.tellg();ifs.seekg(-1, ios:end);stre

37、ampos pos2 = ifs.tellg();bit_size = (int(pos2 - pos1) - 1) * 8 + ifs.get();ifs.seekg(pos1, ios:beg);for (i = 0; i bit_size; +i)if (i % 8 = 0)ifs.read(&buf, 1);value = int(buf & 0xFF);if (int(value & maski % 8) != maski % 8) /value编码的i % 8 + 1位是0m = decode_listm.lchild;elsem = decode_listm.rchild;if

38、(decode_listm.lchild = 0 )ofsdecode_listm.ch;m = 2 *n - 1;ifs.close();ofs.close();free(decode_list);cout解压完成！endl;return true;void Interface()cout-nn;cout 基于赫夫曼树的文本压缩程序nn;cout 学号：20090502137 姓名： 夏军 班级： 09计单nn;cout 请选择功能选项:nn;cout 1. 压缩文件n;cout 2. 解压缩文件n;cout 3. 退出nn;cout-n;3. 测试文件Test.cpp#includeCourseDesign.h#include#includeusing namespace std;int main()int n, *w;char ifile50;char compress_file50 = d:压缩文件.huf;char d