哈夫曼编码译码器实验报告.docx

《哈夫曼编码译码器实验报告.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码译码器实验报告.docx（18页珍藏版）》请在三一办公上搜索。

1、问题解析与解题方法问题分析：设计一个哈夫曼编码、译码系统。对一个ASCII编码的文本文件中的字符进行哈夫曼 编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件。（1）从文件中读入任意一篇英文短文（文件为ASCII编码，扩展名为txt）;（2）统计并输出不同字符在文章中出现的频率（空格、换行、标点等也按字符处理）；（3）根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；（4）将文本文件利用哈夫曼树进行编码，存储成压缩文件（编码文件后缀名.huf）（5）用哈夫曼编码来存储文件，并和输入文本文件大小进行比较，计算文件压缩率；（6）进行译码，将huf文件译码为ASCII编码的txt文件

2、，与原txt文件进行比较。根据上述过程可以知道该编码译码器的关键在于字符统计和哈夫曼树的创建以及解 码。哈夫曼树的理论创建过程如下：一、构成初始集合对给定的n个权值W1,W2,W3,.,Wi,.,Wn构成n棵二叉树的初始集合F=T1,T2,T3,.,Ti,.,Tn，其中每棵二叉树Ti中只有一个权值为Wi的根结点， 它的左右子树均为空。二、选取左右子树在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树 的根结点的权值为其左右子树的根结点的权值之和。三、删除左右子树从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。四、重复二和三两步，重复二和三两步，直到集合F

3、中只有一棵二叉树为止。因此，有如下分析：1. 我们需要一个功能函数对ASCII码的初始化并需要一个数组来保存它们；2. 定义代表森林的数组，在创建哈夫曼树的过程当中保存被选中的字符，即给定报文中出现的字符，模拟哈夫曼树选取和删除左右子树的过程；3. 自底而上地创建哈夫曼树，保存根的地址和每个叶节点的地址，即字符的地址，然 后自底而上检索，首尾对换调整为哈夫曼树实现哈弗曼编码；4. 从哈弗曼编码文件当中读入字符，根据当前字符为0或者1的状况访问左子树或者右孩子，实现解码；5. 使用文件读写操作哈夫曼编码和解码结果的写入；解题方法：结构体、数组、类的定义：1. 定义结构体类型的signode作为哈

4、夫曼树的节点，定义结构体类型的hufnode作 为哈夫曼编码对照表的节点，定义HFM类实现对哈夫曼树的创建，利用其成员函 数完成哈夫曼编码译码的工作。2. 定义signode类型的全局数组 SN256（为方便调用，之后的forest256，hufNode256均为全局数组)，保存ASCII编码的字符，是否在文章中出现(bool类型)以及出现次数(int类型，权重)，左右孩子节点位置，父节点位置信息；3. 为节省存储空间，定义signode *类型的全局数组forest256，模拟森林，在创建 哈夫曼树的过程中保存出现字符的指针，模拟哈夫曼树选取和删除左右子树的过 程；4. 定义hufnode类

5、型的全局数组hufNode256，在编码时最为哈夫曼编码对照表的 节点，char型c保存字符,int code100保存其哈夫曼编码；5. 定义HFM类，主要保存哈夫曼树的根节点指针，但其丰富的功能函数将实现哈夫 曼编码译码的工作及其他功能；函数介绍：1. void init(signode * sig)(初始化数组 SN；2. void compress()(输出压缩对比情况的信息；3. void exchange()(用两层for循环实现hufNodei节点的成员哈夫曼编码数组code前后元素的对换，因为在之前的编码过程中由于是从叶节点追溯至根节点， 存入code数组的哈夫曼编码与哈夫曼编

6、码的概念反向，故而要调整；4. signode * getroot()(返回哈夫曼树的根节点指针；5. signode * HFM:creat()(创建哈夫曼树，首先用三个for循环查看forest数组，找到权值最小的两个字符，以int型的min1,min2记录其下标，定义signode *类 型指针pp指向新生成signode节点，用指针操作使pp指向的节点的权值为 min1,min2权值之和，pp做孩子指向forestmin1,右孩子指向forestmin2， min1,min2的父指针指向pp，然后将pp存入min1的位置，min2之后的每一个 节点依次往前移一个位置实现从forest数

7、组中清除min1,min2并加入pp的操作；6. void HFM:hufcode()(哈夫曼编码，用for循环控制查看hufNode数组，其初始化已在creat()的开始完成，对每一个字符实现编码，用while循环从叶节点 开始，如果该节点是其父节点的左孩子就将codehufNodei.size+赋值0，否则 赋为1，直至当前节点的父节点为空，while循环结束；7. void HFM:savewithhufcode(FILE * inf,FILE * outf)将读入的文章以哈夫曼编码的形式存储，其中inf为读入文件的指针，outf为写入文件的指针，首先调用 rewind(inf)函数将光

8、标放置在文章开头，防止文件未关闭导致的错误，每读一个字 符就用for循环在hufNode数组中查找，因为hufNode数组就是保存出现的字符 的，故一定可以找到，然后再用fputc函数将code数组的内容写入文件，直至读 入文件结束；8. void HFM:inorder(signode * sig)迭代法遍历树，遍历到叶节点时执行hufNodecount+.sig=sig语句实现hufNode数组指向文章中出现的字符；9. int HFM:maxc().计数变量，记录哈夫曼编码最大位数；10. void HFM:hufdecode(FILE* ipf,FILE* opf)解码，从哈夫曼编码到

9、字符，输出到屏幕和指定的文件中；11. void input(FILE * f).初始读入文章，保存出现的字符记录修改其权重；数据结构选择与算法设计数据结构选择:signode :struct signode(/signode节点，哈夫曼树节点/char c;int weight;bool b;signode * parent;signode * left;signode * right;signode()(字符/权重/文章中是否出现初始化c=NULL;b=false;weight=0;parent=left=right=NULL;C weightb | parentleftrighthufn

10、ode:struct hufnode(哈夫曼编码对照表节点/signode * sig;int code100;保存哈夫曼编码int size;bool b;hufnode()(sig=NULL;size=0;b=true;；Sigcode100sizeHFM:class HFM(private:signode * root;signode * pt;/int alleaf;public:HFM(int all)(root=pt=NULL;alleaf=all;HFM()signode * getroot()return root;signode * creat();void hufcode(

11、);哈夫曼类/哈夫曼树根/编码时做哨兵指针/all是森林中树的个数/创建哈夫曼树/编码/void savewithhufcode(FILE * inf,FILE * outf);用哈弗曼编码存储文件/void hufdecode(FILE* ipf,FILE* opf);解码/void inorder(signode * sig);int maxc();求取哈弗曼编码最大长度/Rootpt | alleafcreat() hufcode() savewithhufcode(inf,outf)inorder(sig)getroot()hufdecode(ipf,opf)maxc()算法设计:测试

12、结果Doc 窗口：out of the orphanage and into the city. 1 14 25 51 12 18 1931423331parents and f Lili of hope. He did not believe that he was abandoned, has been th inking parents would come to him. Finally one day, following his music, he walke| d T h1917211010 F:C + +what i have doneHMFhuffumanDebughuffu

13、man.exe”| U回 I S2j码：011111壁厂一解码遂着压缩率顼L F:C+what i have doneHMFhuffumanDebughuffuman.exe呈符s的哈夫曼编码：11010 字符u的哈夫曼编码:11m。 字符u的哈夫曼编码Himio 字符.的哈夫曼编码 字符e的哈夫曼编码：1110 生技1的哈夫曼褊码=mi0 宅符g的哈夫曼编码=1111100 倪机的哈夫曼编码= 1111101 岸特f的哈夫曼编码:莅擞迎心查看哈关晏编码2 墅丢曼解码 3.查看压缩率+ +v/hat i have doneHMFhuffumanDebughuffuman.exeT id 1 2

14、 3o 1 na a 1 o h 1 w p. a r i ftsQ. ndentlie身码率 nirt 牛.盲 a4-4.用纤 tspof哈曼压 enngt 看着 arkiOu查笛一 p n -1=1 回|2 一哈夫曼解码压缩率3压缩前：2248hit 压缩后：1201bit.010 = 0-534253查看哈夫曼编码2噬丢曼解码3-fit压缩率years, has been front of theii lie was abandoned, has been th following his music, he walke11that1 oidn.td-:h t e n Hoit- d e

15、 e n p n a o o编ndenlhe景码率 Hart夫解缩 tspof哈曼压 ennsrt 看言 ar!iOu查譬： pind LI2.I3.3 压压文件读写（部分）:9| pral -记事本-I 口：回思r文件旧漏辑EJ格式。查卷叫帮助HJThe little boy Evan lived in institutions for 11 ycarss has been front of their p；arents and ful 1 of hope. He did not beli已第己 that he was ab；3ndon已田 has been t上linlfins p；3re

16、nts woi-ild conie to him. Finally one day, following his iriLimic： he walked out of the orph；anage and into the city.4窗pra2 -记事本口|回1思J交住旧蝙激EJ格式。亘尊帮助010111000100111000111101000100110011111011100001111110101011 000001011101110111001101100101101001111010001101110111010111 001000110000100011001101010011

17、000100111011010011000101 011001 101000111111101001010000101111010111100101100111001100101011 010101101000100011011OlOOOOlllll1110111011000011111101010101 011001001001010111111001001010011101000010100001110001100101 011101100100111010000110110010111001111111101101111011110001 010111111000100101001110

18、011101101111000111010011100010111100 010111001100101010010001111111101111010001110110111011100010 01010001101001000100111000011110011011010000110011111011on0 01011110101100111010111101101000100011011 0100001111111101110 110000100101001000110001110111000110011111000001110001100101 0111011001001110100

19、00111101010110110111101011100111110110100 101101110001001101000010010000101101101111000111010110001100 011011110111101011000010101100111000101110110101100101101001 mill 01011110111101010011110100011 OOlllll 00000100100011 OlOO 001011011011011010100011111011011010001001110000111100110111 100111011111

20、010111001010110110100100101011111100100101001110 0010100101001110001000110110001101 nil 001110000110110010111 o 010001100100110100010010100111000111110110001001101100110111管I pra4 -记事本| 口 |回|塞文件旧诡辑（EJ格式。帮助（HJThe little boy Evan lived in institutions for 11 ycarss has been front of their p；arents and

21、 ful 1 of hope. He did not believe that he was abjandonedj has been thinking p；arents woi-ild come to him. Finally one day5 following his iriusi：:：,. he walked out of the orph；anage and into the city.总结程序分析：本次哈夫曼编码译码器的课程实验做得还算成功，不仅仅在于程序能够正常运行，实 现应有的功能，关键在于过程，在于小组成员的分工合作和一起纠错排错的过程，在完成程 序的过程中才能真正理解面向对

22、象和模块化设计的思想，我们不仅仅是说要每人分几个函 数，关键在于这些函数代表的是一个个功能模块，任何一个模块出现问题或者模块之间的街 接出现问题都将导致程序运行的失败。哈夫曼编码译码器课程实验我主要负责完成编码译码器数据结构和功能模块框架的 设计，结构体和类的定义，以及creat函数，hufcode函数，savewithhufcode函数的实现。 在初始设计的时候，我体会到书写流程图的重要性，只有又一个清晰的设计思路才能事半功 倍，分工明确，避免无效劳动或者在错误的编程方向上走弯路，也让大家明白自己在程序设 计中的位置和职责。初始的创建是哈夫曼编码译码系统成功的关键，我在创建的过程当中多次使用

23、树的 先根，配合中根遍历操作，输出接点字符或者权重信息，作为检验，对验证和纠错起到了非 常大的作用。在适当的地方调用它们，运行时可以看到验证编写程序的正确性；通过本次实验，提高了自已调试程序的能力。充分体会到了在程序执行时的提示性输 出的重要性。编写大一点的程序，应先写出算法，再写程序，一段一段调试；对于没有实现 的操作用空操作代替，这样容易找出错误所在。最忌讳将所有代码写完后再调试，这样若程 序有错误，太难找。需要特别强调的是：1. 感觉文件操作自己并不是很熟练，尽管在向显示器输出的时候并没有什么错误但 是读写文件的时候就没那么顺利了，比如说当编写savewithhufcode函数时读文 件

24、，却总不执行，后来通过断点测试发现每次fgetc()返回值总为-1，于是我考虑是 否是文件没有打开或者文件结束的缘故，后来想通了是之前打开的文件光标读操 作结束后仍在结尾故每次总返回-1，故调用rewind函数将光标位置移动到文章开 始。2, 用哈夫曼编码存储文件的时候还应注意数字0,1与字符0,1的不同，不应直接在 fputc()函数中直接写入0,1那么将会是写入的文章中什么都没有，因为0在ASCII码 中代表NULL。3, 该程序函数清晰功能明确，程序具有通用性，对于不同的输入文章都可进行处理， 由于采用哈夫曼编码对照表使得查看哈夫曼编码是效率较高无需每次遍历哈夫曼 树。cpp程序清单#i

25、nclude#include#include#include#includeHh1.husing namespace std;FILE * f1=fopen(d:pra1.txt,r);FILE * f2=fopen(d:pra2.txt,w);FILE * f3=fopen(d:pra4.huf,w);int main()(init(SN);input(f1);for(int i=0;foresti!=NULL;i+)coutc:weightendl;countendl;符种类/HFM huffman(count);创建哈夫曼树/ count=0;huffman.hufcode();exch

26、ange();huffman.savewithhufcode(f1,f2);coutendl;cout1.查看哈夫曼编码endl;cout2.哈夫曼解码endl;cout3.查看压缩率choice;while(choice=1&choice=3)switch(choice)(case 1:/初始化字符数据库/读入初始文件的字符/输出字符及出现次数/ cout出现字符种类/输出字/创建哈夫曼树实例/ huffman.creat();/哈夫曼编码，此时为逆向/调整首尾对调哈夫曼编码/用哈夫曼编码存储原文件for(i=0;hufNodei.sig!=NULL;i+)cout字符c的 哈夫曼编码:;/

27、输出哈夫曼编码/for(int j=0;jhufNodei.size;j+)couthufNodei.codej; coutendl;)cout最大列数:huffman.maxc()endl;break;)case 2:(fclose(f2);f2=fopen(d:pra2.txt,r);huffman.hufdecode(f2,f3);coutendl;break;)case 3:(compress();coutendl;)cout1.查看哈夫曼编码endl;cout2.哈夫曼解码endl;cout3.查看压缩率choice;)cout* 谢谢使用 *endl;return 0;)/哈夫曼解

28、码查看压缩情况退出操作/signode节点，哈夫曼树节点/字符/权重/文章中是否出现/初始化/.h#includeusing namespace std;struct signode(char c;int weight;bool b;signode * parent;signode * left;signode * right;signode()(c=NULL;b=false;weight=0;parent=left=right=NULL;)signode SN256;signode * forest256;/森林数组保存出现的字符/int count=0;/出现字符计数/float memo

29、1=0,memo2=0;/全局变量记录读入字符数和编码的0 1数/void init(signode * sig)/SN数组初始化，输入常见字符/sig0.c=a;sig1.c=b;sig2.c=c;sig3.c=d;sig4.c=e;sig5.c=f;sig6.c=g;sig7.c=h;sig8.c=i;sig9.c=j;sig10.c=k;sig11.c=l;sig12.c=m;sig13.c=n;sig14.c=o;sig15.c=p;sig16.c=q;sig17.c=r;sig18.c=s;sig19.c=t;sig20.c=u;sig21.c=v;sig22.c=w;sig23.c

30、=x;sig24.c=y;sig25.c=z;sig26.c=A;sig27.c=B;sig28.c=C;sig29.c=D;sig30.c=E;sig31.c=F;sig32.c=G;sig33.c=H;sig34.c=I;sig35.c=J;sig36.c=K;sig37.c=L;sig38.c=M;sig39.c=N;sig40.c=O;sig41.c=P;sig42.c=Q;sig43.c=R;sig44.c=S;sig45.c=T;sig46.c=U;sig47.c=V;sig48.c=W;sig49.c=X;sig50.c=Y;sig51.c=Z;sig52.c=0;sig53.c

31、=1;sig54.c=2;sig55.c=3;sig56.c=4;sig57.c=5;sig58.c=6;sig59.c=7;sig60.c=8;sig61.c=9;sig62.c=+;sig63.c=-;sig64.c=*;sig65.c=/;sig66.c=,;sig67.c=.;sig68.c=; sig69.c=;sig70.c=:;sig71.c=;sig72.c=;sig74.c=;sig75.c=?;sig76.c=;sig77.c=(;sig78.c=);sig79.c=;sig80.c=;sig81.c=;sig82.c=;sig83.c=!;sig84.c=;sig85.c

32、=#;sig86.c=$;sig87.c=%;sig88.c=A;sig89.c=&;sig90.c=;sig91.c=10;void compress()压缩情况对上匕cout压缩前:memo1*8bit压缩后:memo2bitendl;cout压缩率:memo2/(memo1*8)endl;struct hufnode/哈夫曼编码对照表节点/signode * sig;int code100;保存哈夫曼编码/int size;bool b;hufnode()sig=NULL;size=0;b=true;hufnode hufNode256;void exchange()(int temp;

33、/调换首尾交换哈夫曼编码/for(int i=0;hufNodei.sig!=NULL;i+)for(int s=0,b=hufNodei.size-1;s=b;s+,b-)temp=hufNodei.codes;hufNodei.codes=hufNodei.codeb;hufNodei.codeb=temp)class HFMprivate:signode * root;signode * pt;int alleaf;public:哈夫曼类/哈夫曼树根/编码时做哨兵指针HFM(int all)root=pt=NULL;alleaf=all;)/all 是森林中树的个数/HFM()signo

34、de * getroot()return root;signode * creat();void hufcode();void savewithhufcode(FILE * inf,FILE * outf);void hufdecode(FILE* ipf,FILE* opf);void inorder(signode * sig);int maxc();创建哈夫曼树/编码/用哈弗曼编码存储文件/解码/求取哈夫码曼最大长度/signode * HFM:creat()signode * pp=NULL;for(int i=0;ib=false;为 hufcode 函数作准备，与此函数无关/ wh

35、ile(count1)int min=10000;int min1,min2;for(int i=0;foresti!=NULL;i+) /以 下三个for循 环选出 当前森 林中的 最小两 个节点/if(foresti-weightweight;min1=i;/min=10000;/for(i=0;foresti!=NULL&i!=min1;i+)/if(foresti-weightweight;min2=i;/for(i=min1 + 1;foresti!=NULL;i+)if(foresti-weightweight;min2=i;)/) 至此找到min1 min2 pp=new sig

36、node();/新生成节点，权值为两最小节点权值之和/pp-left=forestmin1; pp-right=forestmin2; forestmin2-b=true;为hufcode函数作准备，与此函数无关/pp-weight=forestmin1-weight+forestmin2-weight; forestmin1-parent=pp; forestmin2-parent=pp; forestmin1=pp;/新生成节点加 入森林for(i=min2;foresti!=NULL;i+)foresti=foresti+1;/min2 后的节点依次前移/count-; ) root=p

37、p; return pp; ) void HFM:hufcode()/哈夫曼编码，保存在hufNode节点的数组当中/inorder(root); for(int i=0;hufNodei.sig!=NULL;i+) signode * gud=hufNodei.sig; while(gud-parent!=NULL) if(gud-parent-left=gud)hufNodei.codehufNodei.size+=0; else if(gud-parent-right=gud)hufNodei.codehufNodei.size+=1; gud=gud-parent; ) ) ) voi

38、d HFM:savewithhufcode(FILE * inf,FILE * outf)/用哈弗曼编码存储文件/rewind(inf);/回到文件起始防止文件未关闭导致的错误/char ch=fgetc(inf); while(!feof(inf) for(int i=0;hufNodei.sig-c!=ch;i+); if(hufNodei.sig-c=ch) for(int k=0;khufNodei.size;k+) coutleft=NULL&sig-right=NULL)hufNodecount+.sig=sig;return ;)else inorder(sig-left);in

39、order(sig-right);)int HFM:maxc()int ma=0;/计数变量/for(int i=0;ima)ma=hufNodei.size;)return ma;)void HFM:hufdecode(FILE* ipf,FILE* opf)/解码，由哈夫曼码到字符/signode* pt=root;char ch=fgetc(ipf);while(!feof(ipf)/判断有无到文件尾/if(ch=0)if(pt-left=NULL)coutc;fputc(pt-c,opf);pt=root;)pt=pt-left;)else if(ch=1)注意字符0,1与数字0,1是不同的/if(pt-right=NULL)coutc;fputc(pt-c,opf);pt=root;)pt=pt-right;)ch=fgetc(ipf);) coutc;fputc(pt-c,opf);fclose(ipf);f