哈夫曼编码与译码(附源码)

1、建立Huffman树进行编码和译码的设计李香兰2015548947哈尔滨工业大学计算机科学与技术学院1501班摘要：建立一个简易的系统，对于给定的一篇英文文章，统计字符出现的概率，并根据概率建立Huffman树，利用Huffman编码对文章进行编码和译码。掌握Huffman树的建立与应用，并进一步熟练掌握程序的设计流程。关键词：Huffman树Huffman编码文章译码文件压缩解压缩1.引言:给定一篇文章，统计字符出现的概率，根据概率建立哈夫曼树，并进行哈夫曼编码，进而可以利用哈夫曼编码对文章进行编码与译码和文件压缩、解压缩等操作。2.程序设计流程文字表述开始进入功能选择界面，包含五种操作：1

2、.读取文章并对字符编码，2.哈夫曼编码信息，3.文章编码，4.文章译码，5.文件压缩，6.文件解压缩，7.退出程序。操作1：给定一篇文章，统计字符出现的概率，并根据概率建立Huffman树，并利用Huffman树对字符进行Huffman编码。操作2：显示Huffman编码信息，包括字符，字符出现的概率，Huffman编码。操作3：对文章进行译码，显示译码信息,并保存。操作4：对文章进行译码，显示并保存。操作5：对文件进行压缩，每7位二进制序列对应一个ASCII码。操作6：对文件进行解压缩。(2)流程图(3)程序数据要求及功能实现1.读取文件并对字符进行编码IC:msysbirsh.exe夢输入

3、文件名：English,txt操作完毕！请按任意键继续2哈夫曼编码信息IC:msysbinshexe哈夫曼编码：字符权值哈夫曼编码F0.00334728001001100.05857740110r0.061924710000.157322110E0.001673641110010011U0.0217573111011P0.0117155001010e0.0887029000a0.06861921001n0.05690380101s0.055230101003文件编码IC:msysbinshexe=1.显示文章编码二二二二二二二二2.保存文章编码二二二二二二二二3.返回上一界面二二二请选择功能:

4、(1)显示文件编码文章编码如下：W100110011010001101110010011111011100001100010100001001010101001110011110111110L1100011000111011101101110111101101001111110011111110010011010011111101001100101L1010100100010U1100101111111010011100010101000101001111111010111010000011101000L100010011101110111111110100111001000000011011

5、1011111010100110000010011111011111L0111011010010101101001001111110100010100111011011111111110011110111110111000001)1111011101010101110000001101111100111100010100101011101110011111110010011010011L1110100110010101001100111101110111000101001010111011101111101111010010011011111)1010110000001000110001001

6、011101111111101111101110001100011101110110111011110110L0011111101011110010100110010001101101110101010111111111110100001101011000010010L0110100101011101110111101101100011101011000010001010001101001010111000111101101MOI1100000010000100001000110001001000000110100111101101000001100011101011000010M101000

7、110100101010100110011110011001011110010111111101111100111100000011001111L1100100110100111111010011001010100110100101010010111101011001101000000001000110)1111100010111001011110011110011001011110010111111100011101011000010001010001101)0101010100110111110011110000001100111111100100110100111111010011001

8、010100011111Ml11001111101010111000110100111101111111011101101000010011011111011110100101111)000100110111110111100111111100111000000011110001000110100101010111101100111000030011110001000110001100110101100010101001010110100000100110011001110001110000010Ml10111110111000101010001100011110110100011100000

9、010000100110001010100110100111L0110111110101011000011001100111000111000010001100111110111111101110001000110001L0011011101101011111100010100000100110001111011010001110000001000010011011101010toil1000000110001001010001010111110100100101111110011110001001101000000010100110toil11110011110100101010111101

10、10111001000111110011110101010100101010100111001111Ml11010001111110101100110100000011000101010011010011110110101110110111010101001(2)保存文件编码C:rrsysbinsh.exe请输入保存文童编码的文件名:bianma.txt保存完毕！请按任意键继续.4文件译码C:msysbinsh.exe=!.显示文章编码的译码-2.保存文章编码的译码=3.返回上一界面请选择功能:(1)显示文章编码的译码(2)保存文章编码的译码5.文件压缩6文件解压缩EC:msysbinsh.e

11、xe请输入待解压缩的文件名:yasuo.txt请输入解压后的文件名：jieyasuo.txt解压后的文件内容为：ForEuropeans,theAugustvacatiorisntaprivilegebutasecular-humanistright,theyliketakingvacationsduringthistime.ButtheAugusthassolittlemeaningtoAmericanworkers.BecauseAmericansdonfttakevacationsanymore.WhydnTtAmericanstakevacations?Theauthorsthinks

12、thatfewerandfewercompaniesoffertheirworkerspaidtimeoff.OthercountriesworkerslikeFritish，French,andItalians,getmorepaidholidayperyeartharAmericans,thenAmericanworkerswillworkmoretimetogetmoir亡money.Andth巳limitationofsocialsystemisoneofthemostimportamtreasons.ForEuropeans,thexugustvacationisnftaprivil

13、egebutasecular-hunianistright,they1iket日kingvacaticmzduringthistime.ButtheAugusthassolittiemeaningtoAmeaoeicanworkers.BecauseAmericansdonttakevacationsanymore.WhydonTtAmericanstakevacatiooeiwaThe已uthorsthinksthatfewerandfewercompaniesoffertheirworkerspaidtimeoff.OthercountriesworkerslikeBritish,Fren

14、ch,andItalians,getmorepaidholidayperyearthanAmericans,thenAmericanworkerswillworkmoretimetogetmoremoney.Ardthelimitationofsocialsystemisoneofthemostimport日ntreasons,ee解压完毕！请按任意键继续附：程序源代码严File:HUFFMANFUNCTION.hAuthor:Administrator*Createdon2011年12月19日，下午6:19*/#ifndefHUFFMANFUNCTION_H#defineHUFFMANFUN

15、CTION_H#includevcstdlib#includeviostream#includevfstream#includevmath.h#definemaxi150#definemax250#definemax3256usingnamespacestd;classHtnotepublic:charname;/字符名doubleweight;权重intlchild;/左孩子intrchild;/右孩子intparent;父亲Htnote()weight=0;lchild=-1;parent=-1;rchild=-1;classNamepublic:intnum;字符出现的次数charpna

16、me;/字符名doublelweight;权值Name()num=0;lweight=0;classGetNamepublic:charnamefmax2;intn;字符的种类intsum;字符的总数Namelettermax1;存储字符信息的类的数组GetName()sum=0;n=0;voidGetWeight()得到字符的权值for(inti=0;in;i+)letteri.lweight=(double)letteri.num/sum;/出现的次数除总数得到权值intReadLetter()ifstreaminput;cout请输入文件名：”namef;input.open(namef

17、);打开文件if(input.fail()cout该文件不存在！vvendl;return0;charch;ch=input.get();letter0.pname=ch;letter0.num+;sum+;while(!input.eof()/读取文件中的所有字符inttag=0;ch=input.get();for(inti=0;ivn+1;i+)if(letteri.pname=ch)letteri.num+;sum+;tag=1;if(tag=0)n+;lettern.pname=ch;lettern.num+;sum+;sum-;input.close();GetWeight();/

18、得到字符权值；classCodeNode/编码类public:charch;存储字符charbitsmaxl;存储编码;classFunctionpublic:GetNameL;intfn;定义哈夫曼数组大小HtnoteHuffmanTmax3;/哈夫曼数组CodeNodeCodemax1;/字符编码数组Function。fn=0;voidCharHuffmanTCoding()/编码功能实现inti,f,c;charcdL.n+1;暂时存储编码的数组intstart;编码读取起始位置cdL.n=0;for(i=0;i=0)if(HuffmanTf.lchild=c)/如果为左孩子，为Ocd-

19、start=O;else/如果为右孩子，为1cd-start=T;c=f;strcpy(Codei.bits,&cdstart);/将结果存入对应的编码数组中voidOutputHuffmanTCode()cout哈夫曼编码：vvendl;coutvvvvendl;coutvv字符t权值tt哈夫曼编码vvendl;for(inti=0;ivL.n;i+)输出字符，权值，哈夫曼编码coutvvvvendl;coutvvHuffmanTvvtvvHuffmanTi.weightvvt;coutvvCodei.bits;coutvvendl;coutvvvvendl;voidInitHT

20、()哈夫曼初始化L.ReadLetter();fn=(L.n)*2-1;for(inti=0;ivfn;i+)if(ivL.n)HuffmanT=L.letteri.pname;HuffmanTi.weight=L.letteri.lweight;voidSelectMin(intm,int&p1,int&p2)选择最小的两个节点inti,j;doubleml,m2;ml=m2=1;pl=p2=-1;for(i=0;ivm;i+)if(HuffmanTi.parent=-1&HuffmanTi.weightvml)/找出为访问过的最小权值节点m2=ml;p2=pl;ml=Huffm

21、anTi.weight;pl=i;elseif(HuffmanTi.parent=-l&HuffmanTi.weightvm2)/找出为访问的权值第二小结点m2=HuffmanTi.weight;p2=i；voidCreatHT()建立哈夫曼树inti,pl,p2;InitHT();for(i=L.n;ifn;i+)SelectMin(i,p1,p2);HuffmanTp1.parent=HuffmanTp2.parent=i;HuffmanTi.lchild=p1;HuffmanTi.rchild=p2;HuffmanTi.weight=HuffmanTp1.weight+HuffmanTp

22、2.weight;intOutArticleCode()显示文章编码/文章编码操作ifstreaminput;input.open(L.namef);if(input.fail()cout文件不存在！”endl;return0;charch;cout文章编码如下：endl;while(!input.eof()ch=input.get();for(inti=0;iL.n;i+)if(Codei.ch=ch)coutCodei.bits;coutendl;input.close();intSaveArticleCode()保存文章编码ofstreamoutput;ifstreaminput;cha

23、rnameflmax2;input.open(L.namef);if(input.fail()coutnamefl;output.open(namefl);charch;while(!input.eof()ch=input.get();for(inti=0;ivL.n;i+)if(Codei.ch=ch)for(intj=0;jvstrlen(Codei.bits);j+)output.put(Codei.bitsj);input.close();output.close();coutvv保存完毕！vvendl;intOutTransCode()文章译码操作ifstreaminput;char

24、namefmax2;coutvv请输入保存文章编码的文件名：”vvendl;cinnamef;input.open(namef);if(input.fail()coutvv该文件不存在！vvendl;return0;charch;ch=input.get();intc=2*L.n-2;while(!input.eof()if(ch=0)/遇0搜索左子树if(HuffmanTc.lchild=0)c=HuffmanTc.lchild;if(HuffmanTc.lchild=-1)/判断是否到叶子cout=0)c=HuffmanTc.rchild;if(HuffmanTc.rchild=-1)/判

25、断是否到叶子coutHuffmanT;/输出字符c=2*L.n-2;返回根节点ch=input.get();coutendl;input.close();intSaveTransCode()/保存文章译码ofstreamoutput;ifstreaminput;charnamefmax2;charnamef1max2;cout请输入文章编码所在的文件名：namef;input.open(namef);if(input.fail()coutnamef1;output.open(namef1);charch;ch=input.get();intc=2*L.n-2;while(!inpu

26、t.eof()if(ch=0)if(HuffmanTc.lchild=0)c=HuffmanTc.lchild;if(HuffmanTc.lchild=-1)output.put(HuffmanT);c=2*L.n-2;if(ch=T)if(HuffmanTc.rchild=0)c=HuffmanTc.rchild;if(HuffmanTc.rchild=-1)output.put(HuffmanT);c=2*L.n-2;ch=input.get();input.close();output.close();cout保存完毕！endl;intFileCompressio

27、n()/文件压缩功能CreatHT();CharHuffmanTCoding();保存编码ofstreamoutput;ifstreaminput;charnamefl=temp.txt;input.open(L.namef);if(input.fail()cout该文件不存在！vvendl;return0;output.open(namefl);charch;while(!input.eof()ch=input.get();for(inti=0;ivL.n;i+)if(Codei.ch=ch)for(intj=0;jstrlen(Codei.bits);j+)output.put(Codei

28、.bitsj);input.close();output.close();压缩文件ofstreamFilel;ifstreamFile2;charnamef2max2;cout请输入压缩后的文件名：”namef2;File1.open(namef2);File2.open(namef1);if(File2.fail()cout该文件不存在！vvendl;return0;charsh;charth;inti=0;charj=O;intcount=0;while(!File2.eof()sh=File2.get();if(iv7&sh!=EOF)count=count+(sh-0)*pow(2,i

29、);if(sh=0)j+;elsej=0;i+;if(i=7)th=count;Filel.put(th);i=0;count=0;if(sh=EOF)th=count;Filel.put(th);Filel.put(j);i=0;count=0;File1.close();File2.close();remove(namefl);coutnamef2;input.open(namef2,ios:inIios:binary);output.open(namef1,ios:outIios:binary);if(input.fail()coutvv该文件不存在！vvendl;return0;cha

30、rch;input.read(reinterpret_castvchar*(&ch),sizeof(ch);charsh;charth=ch;input.read(reinterpret_castvchar*(&ch),sizeof(ch);intcount;charnum;chart=O;charp=T;while(!input.eof()sh=th;th=ch;input.read(reinterpret_castvchar*(&ch),sizeof(ch);count=sh;if(ch!=EOF)for(inti=0;iv7;i+)num=count%2+0;output.write(reinterpret_castvchar*(&num),sizeof(num);count=count/2;if(ch=EOF)for(inti=0;i(&num),sizeof(num);count=count/2;if(count=0)break;for(inti=0;i(&t),sizeof(t);output.close();input.close();解压文件fstreamFile1;fstreamFile2;char