- 1、本文档共67页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
算法的设计与剖析第4章节
?前缀码:对每一个字符规定一个0,1串作为其代码,并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单;例如001011101可以唯一的分解为0,0,101,1101,因而其译码为aabe。 译码过程可以用二叉树作为前缀码的数据结构:树叶表示给定字符;从树根到树叶的路径当作该字符的前缀码;代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 4.4 哈夫曼编码 编码的前缀性质可以使译码方法非常简单。 表示最优前缀码的二叉树总是一棵正则二叉树,即树中任一结点都有2个儿子结点。 平均码长定义为: 使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 给出现频率高的字符较短的编码,出现频率较低的字符以较长的编码,可以大大缩短总码长。 平均码长达到最小 贪心策略体现:要使平均编码长度最短,那么直观上使频率最大的字符对应的编码方案最短。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 4.4 哈夫曼编码 2、构造哈夫曼编码 哈夫曼提出构造最优前缀码的贪心算法,由此产生的编码方案称为哈夫曼编码。 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。 算法以|C|个叶结点开始,执行|C|-1次的“合并”运算后产生最终所要求的树T。 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * 定长编码树 变长编码树 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 其构造步骤如下: (1)假设编码字符集中每一字符c的频率是f(c)。 (2)以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。 (3)一旦2棵具有最小频率的树合并后,产生一棵新的树,其频率为合并的2棵树的频率之和,并将新树插入优先队列Q。 (4)经过n-1次的合并后,优先队列中只剩下一棵树,即所要求的树T。 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 若C是编码字符集,表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符,该二叉树有|C|-1个内部节点。 正则二叉树:只有度为0或者2的节点; Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 4.4 哈夫曼编码 时间复杂度: 算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间,由于最小堆的removeMin和put运算均需O(logn)时间,n-1次的合并总共需要O(nlogn)计算时间。因此,关于n个字符的哈夫曼算法的计算时间为O(nlogn) 。 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 4.5 单源最短路径 给定带权有向图G =(V,E),其中每条边的权是非负实数。另外,还给定V中的一个顶点,称为源。现在要计算从源到
您可能关注的文档
- 第八课第一框“国家财政”.ppt
- 云南省大理云龙一中11-12届高二上学期期末考试化学试卷.doc
- 云南省大理云龙一中11-12届高二上学期期末考试英语试卷.doc
- 云南省大理云龙一中11-12届高二上学期期末考试语文试卷.doc
- 云南省大理云龙一中11-12届高二上学期期末考试生物试卷.doc
- 第六次人口普查之快速汇总细则[朝阳].ppt
- 第六讲加固wìndows的操作系统安全.ppt
- 云南省大理云龙一中2011-2012届高一上学期期末考试历史试卷.doc
- 云南省大理云龙一中2011-2012届高一上学期期末考试政治试卷.doc
- 云南省大理云龙一中2011-2012届高一上学期期末考试化学试卷.doc
文档评论(0)