资源描述：
《哈夫曼编码算法课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、算法设计与分析课程设计实验报告算法设计与分析课程设计报告设计题目：HuffmanCodes专业信息与计算科学班级2009级1班学生孙某某郑某学号0918010709180109指导教师莫某某某某起止时间2011/12/19~2011/12/30算法设计分析平时表现程序演示综合成绩2011年12月12算法设计与分析课程设计实验报告实验题目哈夫曼编码一、问题描述：ProblemEDanMcAmbiisamemberofacrackcounter-espionageteamandhasrecentlyobtainedthepartialcontentsofafilec
2、ontaininginformationvitaltohisnation!ˉsinterests.ThefilehadbeencompressedusingHuffmanencoding.Unfortunately,thepartofthefilethatDanhasshowsonlytheHuffmancodesthemselves,notthecompressedinformation.SinceHuffmancodesarebasedonthefrequenciesofthecharactersintheoriginalmessage,Dan!ˉsboss
3、thinksthatsomeinformationmightbeobtainedifDancanreversetheHuffmanencodingprocessandobtainthecharacterfrequenciesfromtheHuffmancodes.Dan!ˉsgutreactiontothisisthatanygivensetofcodescouldbeobtainedfromawidevarietyoffrequencydistributions,buthisbossisnotimpressedwiththisreasonedanalysis.
4、SoDanhascometoyoutogetmoredefinitiveprooftotakebacktohisboss.Huffmanencodingisanoptimaldatacompressionmethodifyouknowinadvancetherelativefrequenciesoflettersinthetexttobecompressed.ThemethodworksbyfirstconstructingaHuffmantreeasfollows.Startwithaforestoftrees,eachtreeasinglenodeconta
5、iningacharacterfromthetextanditsfrequency(thecharactervalueisusedonlyintheleavesoftheresultingtree).Eachstepoftheconstructionalgorithmtakesthetwotreeswiththelowestfrequencyvalues(choosingarbitrarilyifthereareties),andreplacesthemwithanewtreeformedbyjoiningthetwotreesastheleftandright
6、subtreesofanewrootnode.Thefrequencyvalueofthenewrootisthesumofthefrequenciesofthetwosubtrees.Thisprocedurerepeatsuntilonlyonetreeisleft.Anexampleofthisisshownbelow,assumingwehaveafilewithonly5characters¨CA,B,C,DandE¨Cwithfrequencies10%,14%,31%,25%and20%,respectively.Afteryouhaveconst
7、ructedaHuffmantree,assigntheHuffmancodestothecharactersasfollows.Labeleachleftbranchofthetreewitha0andeachrightbranchwitha1.ReadingdownfromtheroottoeachcharactergivestheHuffmancodeforthatcharacter.ThetreeaboveresultsinthefollowingHuffmancodes:A-010,B-011,C-11,D-10andE-00.Forthepurpos
8、eofthisprobl
