哈夫曼编码（贪心算法）报告.doc
需积分: 47 177 浏览量
2019-12-26
16:36:46
上传
评论 3
收藏 123KB DOC 举报
实验十：哈夫曼编码（贪心算法）报告
2017061111 李静娴
1．问题描述
哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在 ～
之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用 ， 串表示各字符
的最优表示方式。一个包含 个字符的文件，各字符出现频率不同，如下表所示。
有多种方式表示文件中的信息，若用 码表示字符的方法，即每个字符用唯一的一个
串表示。若采用定长编码表示，则需要 位表示一个字符，整个文件编码需要
位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到
整 体 编 码 减 少 的 目 的 ， 则 整 个 文 件 编 码 需 要
（） 位，由此可见，变长码比定长码方案好，
总码长减小约 。
前缀码：对每一个字符规定一个 串作为其代码，并要求任一字符的代码都不是其他
字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如
可以唯一的分解为 ，因而其译码为 。
译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，
可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字
符的前缀码；代码中每一位的 或 分别作为指示某节点到左儿子或右儿子的“路标”。
表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有 个儿子。图 表
示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若
是编码字符集，表示其最优前缀码的二叉树中恰有个叶子。每个叶子对应于字符集中的
剩余12页未读，继续阅读
资源评论
