资源描述：
《算法分析与设计2004春.课件.第05讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Lecture5.GreedyAlgorithm•Huffmancode•Matroid（拟阵续）清华大学软件学院宋斌恒1HuffmanCodes•Huffmancodes用于数据压缩一般可以达到压缩20％到90%的效果。•什么是编码：编码实质上是用给定的一组符号集的字符串到另外一组符号集的映射。•例如用{0,1}字符串到所有英文字符{a,b,c,…}的映射的8位码清华大学软件学院宋斌恒21Prefixcodes•我们只考虑任一个编码字不是另一个编码字的前缀的编码。•这样的编码叫PrefixCodes。•下页给
2、出几种编码例子：清华大学软件学院宋斌恒3abcdefFrequency(inthousands)4513121695Fixed-lengthcodeword000001010011100101Variable-lengthcodeword010110011111011100Figure16.3Acharacter-codingproblem.Adatafileof100,000characterscontainsonlythecharactersa-f,withthefrequenciesindicated.I
3、feachcharacterisassigneda3-bitcodeword,thefilecanbeencodedin300,000bits.Usingthevariable-lengthcodeshown,thefilecanbeencodedin224,000bits.2Prefixcodesaredesirablebecausetheysimplifydecoding.•示例：在上图非定长编码下，串0001110101唯一代表字符串aaaeab清华大学软件学院宋斌恒5编码表示方式•利用树来表示，下图表示
4、等长编码：1008614582814a:45b:13c:12d:16e:9f:5清华大学软件学院宋斌恒63Anoptimalcodeforafileisalwaysrepresentedbyafullbinarytree.1008614582814a:45b:13c:12d:16e:9f:5清华大学软件学院宋斌恒7GivenatreeTcorrespondingtoaprefixcode,itisasimplemattertocomputethenumberofbitsrequiredtoencodeafile
5、.LetcdenotethecharacterinalphabetC,f(c)denotethefrequencyofcinthefile,dT(c)thedepthofcinthetree.ThenumberofbitsrequiredtoencodeafileisthusB(T)=f(c)d(c)∑Tc∈CwhichwedefineasthecostofthetreeT.清华大学软件学院宋斌恒841001005514a:45862530582814a:45b:13c:12d:16e:9f:514d:16c:
6、12b:13f:5e:9Figure16.4TreescorrespondingtothecodingschemesinFigure16.3.Eachleafislabeledwithacharacteranditsfrequencyofoccurrence.Eachinternalnodeislabeledwiththesumofthefrequenciesoftheleavesinitssubtree.(a)Thetreecorrespondingtothefixed-lengthcodea=000,⋯,f
7、=101.(b)Thetreecorrespondingtotheoptimalprefixcodea=0,b=101,⋯,f=1100.ConstructingaHuffmancode•HuffmaninventedagreedyalgorithmthatconstructsanoptimalprefixcodecalledaHuffmancode.•下面我们给出Huffmancode算法的伪代码清华大学软件学院宋斌恒1051.Huffman(C)1.nÅ
8、C
9、2.QÅC//Qisapriorityqueue
10、=newQ(C)3.ForiÅ1ton-11.Doallocateanewnodez2.Left[z]ÅxÅQ.Extract-Min()3.Right[z]ÅyÅQ.Extract-Min()4.f[z]Åf[x]+f[y]5.Q.insert(z)4.ReturnQ.Extract-Min()清华大学软件学院宋斌恒11f:5e:9c:12b:13d:16a:45清华大学软件学院宋斌
