1、 1 哈夫曼编码的哈夫曼编码的 JAVAJAVA 实现课程设计实现课程设计 目目 录录 摘 要 2 一、问题综述 2 二、求解方法介绍 3 三、实验步骤及结果分析 4 四、程序设计源代码 5 参考文献 8 2 摘要摘要 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降 低传输成本，试用 java 语言设计一个哈夫曼编码系统。通过本课程设计，应使 学生掌握哈夫曼编码的特点、储存方法和基本原理，培养学生利用 java 语言正 确编写程序及调试程序的能力，运用数据结构知识解决实际问题的能力。 关键字：哈夫曼编码 JAVA 语言 类 方法 一、问题综述 1 哈夫曼编码的算法思想 哈夫
2、曼编码也称前缀编码，它是根据每个字符出现的频率而进行编码的，要 求任一字符的编码都不是其它任意字符编码的前缀且字符编码的总长度为最短。 它主要应用于通信及数据的传送以及对信息的压缩处理等方面。 哈夫曼编码的基 础是依据字符出现的频率值而构造一棵哈夫曼树， 从而实现最短的编码表示最常 用的数据块或出现频率最高的数据，具体的方法是： 1.1 建立哈夫曼树 把N 个字符出现的频率值作为字符的权值,然后依据下列步骤建立哈夫曼 树。 1.1.1 由N 个权值分别作N 棵树的根结点而形成一个森林。 1.1.2 从中选择两棵根值最小的树T1 和T2 组成一棵以结点T 为根结点的 增长树，根结点T = T1
3、+ T2 ,即新树的根值为原来两棵树的根值之和，而T1 和 T2 分别为增长树的左右子树。 1.1.3 把这棵新树T 加入到森林中，把原来的两棵树T1 和T2 从森林中删 除。 1.1.4 重复1.1.21.1.3 步，直到合并成一棵树为止。 1.2 生成各字符的哈夫曼编码 在上面形成的哈夫曼树中，各个字符的权值结点都是叶子结点，从叶子结点 开始向根搜索，如果是双亲的左分支，则用“0”标记，右分支用“1”标记，从 叶子结点到根结点所经过的分支编码“0”、“1”的组合序列就是各字符的哈夫 曼编码。 2 构造哈夫曼树的算法 1）对给定的n个权值W1,W2,W3,.,Wi,.,Wn构成n棵二叉树的初
4、始集合 F=T1,T2,T3,.,Ti,., Tn，其中每棵二叉树Ti中只有一个权值为Wi的根结 点，它的左右子树均为空。 2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新 二叉树的根结点的权值为其左右子树的根结点的权值之和。 3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F 中。 3 4）重复2）和3） ，直到集合F中只有一棵二叉树为止。 例如，对于4个权值为1、3、5、7的节点构造一棵哈夫曼树，其构造过程如下图 所示： 图1 构造哈夫曼树的过程示例 二、求解方法介绍 以往的哈夫曼编码程序实现都是利用PASCAL 或C 语言描述的，而这两门语 言都有相
5、应的指针类型来解决，实现起来较为容易，但是，JAVA语言是面向对象 的编程语言，没有提供指针类型，所以在实现上应该结合JAVA 的应用环境，采 用静态的方法解决。 同时， JAVA 语言是具有平台无关性的网络编程语言， 用JAVA 语言实现哈夫曼编码不论在教学中或是在实际应用中都有一定的意义。 本程序是用哈夫曼树来实现哈夫曼编码的功能，根据输入的报文进行分析， 建立哈夫曼树。统计输入字符串的长度，并对每个字符的频度进行计算。对每个 字符及相应的频度作为叶结点建立哈夫曼树。 哈夫曼树的建立过程采用把结点看 作树每次选最小的两个建立树，并把他们的频度相加，再继续选取最小的两个数 建立，直到所有的结
6、点建立完，才形成完整的哈夫曼树。接下来是对没个结点进 行编码，从第一个结点开始看它的双亲，若它双亲做左孩子则记0，若是右孩子 则记1，依次往上推，直到哈夫曼的根结点为止。记录编码打印出来。 为了体现程序中各个功能的独立性，结合JAVA 语言的编程要求，对程序中 所用到的类和方法进行说明： 1 公共类Tree：组成哈夫曼树的最小单元。其成员变量有： 1.1 lchild：最小单元的左孩子。 1.2 rchild：最小单元的右孩子。 1.3 parents：最小单元的双亲。 2 公共类Huffman：描述哈夫曼编码的整个过程,其成员变量有： 2.1 numsMo：储存要进行编码的一组数。 2.2 nums：临时储存要进行编码的这组数，会随着后面的调用而变化。 2.3 trees：储存哈夫曼树，由若干最小单元构成。 2.4 temp：中间变量，是字符串类型。 3 核心方法及流程 4 3.1 main 方法：用于程序的执行入口。其中定义了一个Huff 类实体，调 用方法start() 完成数组初始排序，实现哈夫曼编码等一系列的操作。 3.2 addNum 方法：用于方法初始化给
