哈夫曼编码（贪心算法）报告.doc - CSDN文库

算法设计与分析实验报告

需积分: 47 187 浏览量更新于2023-05-14 3 收藏 123KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

实验十：哈夫曼编码（贪心算法）报告

2017061111 李静娴

1．问题描述

哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在 ～

之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用 ， 串表示各字符

的最优表示方式。一个包含  个字符的文件，各字符出现频率不同，如下表所示。

有多种方式表示文件中的信息，若用  码表示字符的方法，即每个字符用唯一的一个

 串表示。若采用定长编码表示，则需要  位表示一个字符，整个文件编码需要 

位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到

整体编码减少的目的，则整个文件编码需要

（） 位，由此可见，变长码比定长码方案好，

总码长减小约 。

前缀码：对每一个字符规定一个  串作为其代码，并要求任一字符的代码都不是其他

字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如

 可以唯一的分解为 ，因而其译码为 。

译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，

可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字

符的前缀码；代码中每一位的  或  分别作为指示某节点到左儿子或右儿子的“路标”。

表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有  个儿子。图  表

示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若 

是编码字符集，表示其最优前缀码的二叉树中恰有个叶子。每个叶子对应于字符集中的

一个字符，该二叉树有 个内部节点。

给定编码字符集  及频率分布 即  中任一字符  以频率 在数据文件中出现。 的一

个前缀码编码方案对应于一棵二叉树 。字符  在树  中的深度记为 。也是字符 

的前缀码长。则平均码长定义为：。使平均码长达到最小的前缀码编

码方案称为  的最优前缀码。

哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。

2．实验目的

（1）熟悉贪心算法，并学以致用

（2）熟练掌握哈夫曼编码算法

3．实验原理

其构造步骤如下：

哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树 。

算法以个叶结点开始，执行－ 次的“合并”运算后产生最终所要求的树 。

假设编码字符集中每一字符  的频率是 。以  为键值的优先队列  用在贪心选择时

有效地确定算法当前要合并的  棵具有最小频率的树。一旦  棵具有最小频率的树合并后，

产生一棵新的树，其频率为合并的  棵树的频率之和，并将新树插入优先队列 。经过 －

 次的合并后，优先队列中只剩下一棵树，即所要求的树 。

算法的时间复杂度：

O(n*lgn



4．实验设计

（）

输入数据格式：程序里设定好字符以及字符的频率。

生成方式：字符数组  存字符， 存字符频率

数据规模：设定好数据规模，为 。

（）

该程序先是设定好字符以及字符的频率。然后调用 HumanTree(f, N)函数构造哈夫曼

树，Pre_Order()用于输出前序遍历结果，In_Order()用于输出中序遍历结果。

（）

程序运行的结果有  个，先是打印各字符出现的对应频率，输出前序遍历结然后果，

再输出中序遍历结果。

剩余12页未读，继续阅读

qq_42236488

粉丝: 4
资源: 17

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈