哈夫曼编码的JAVA实现课程设计

哈夫曼编码的JAVA实现课程设计

目 录

摘 要 ............................................................................................................................. 2

一、问题综述 ............................................................................................................... 2

二、求解方法介绍 ....................................................................................................... 3

三、实验步骤及结果分析 ........................................................................................... 4

四、程序设计源代码 ................................................................................................... 5

参考文献 ....................................................................................................................... 8

摘要

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，试用java语言设计一个哈夫曼编码系统。通过本课程设计，应使学生掌握哈夫曼编码的特点、储存方法和基本原理，培养学生利用java语言正确编写程序及调试程序的能力，运用数据结构知识解决实际问题的能力。

关键字：哈夫曼编码 JAVA语言 类 方法

一、问题综述

1 哈夫曼编码的算法思想

哈夫曼编码也称前缀编码，它是根据每个字符出现的频率而进行编码的，要求任一字符的编码都不是其它任意字符编码的前缀且字符编码的总长度为最短。它主要应用于通信及数据的传送以及对信息的压缩处理等方面。哈夫曼编码的基础是依据字符出现的频率值而构造一棵哈夫曼树，从而实现最短的编码表示最常用的数据块或出现频率最高的数据，具体的方法是：

1.1 建立哈夫曼树

把N 个字符出现的频率值作为字符的权值,然后依据下列步骤建立哈夫曼树。

1.1.1 由N 个权值分别作N 棵树的根结点而形成一个森林。

1.1.2 从中选择两棵根值最小的树T1 和T2 组成一棵以结点T 为根结点的增长树，根结点T = T1 + T2 ,即新树的根值为原来两棵树的根值之和，而T1 和T2 分别为增长树的左右子树。

1.1.3 把这棵新树T 加入到森林中，把原来的两棵树T1 和T2 从森林中删除。

1.1.4 重复1.1.2～1.1.3 步，直到合并成一棵树为止。

1.2 生成各字符的哈夫曼编码

在上面形成的哈夫曼树中，各个字符的权值结点都是叶子结点，从叶子结点开始向根搜索，如果是双亲的左分支，则用“0”标记，右分支用“1”标记，从叶子结点到根结点所经过的分支编码“0”、“1”的组合序列就是各字符的哈夫曼编码。

2 构造哈夫曼树的算法

1）对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。

2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。

3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。

4）重复2）和3），直到集合F中只有一棵二叉树为止。

例如，对于4个权值为1、3、5、7的节点构造一棵哈夫曼树，其构造过程如下图所示：

图1 构造哈夫曼树的过程示例

二、求解方法介绍

以往的哈夫曼编码程序实现都是利用PASCAL 或C 语言描述的，而这两门语言都有相应的指针类型来解决，实现起来较为容易，但是，JAVA语言是面向对象的编程语言，没有提供指针类型，所以在实现上应该结合JAVA 的应用环境，采用静态的方法解决。同时，JAVA 语言是具有平台无关性的网络编程语言，用JAVA 语言实现哈夫曼编码不论在教学中或是在实际应用中都有一定的意义。

本程序是用哈夫曼树来实现哈夫曼编码的功能，根据输入的报文进行分析，建立哈夫曼树。统计输入字符串的长度，并对每个字符的频度进行计算。对每个字符及相应的频度作为叶结点建立哈夫曼树。哈夫曼树的建立过程采用把结点看作树每次选最小的两个建立树，并把他们的频度相加，再继续选取最小的两个数建立，直到所有的结点建立完，才形成完整的哈夫曼树。接下来是对没个结点进行编码，从第一个结点开始看它的双亲，若它双亲做左孩子则记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 核心方法及流程

3.1 main 方法：用于程序的执行入口。其中定义了一个Huff 类实体，调用方法start() 完成数组初始排序，实现哈夫曼编码等一系列的操作。

3.2 addNum 方法：用于方法初始化给定的要进行编码的数组，数组通过控制台键盘录入。

3.3 minTo 方法：在一组数中选择最小的两个，按递增顺序返回。

3.4 compareNum 方法：是公共类Huffman的核心算法之一，该方法是将一组树形成哈夫曼树，左孩子为较小值。

3.5 print 方法：是公共类Huffman的核心算法之一，该方法利用递归打印出编码。其流程图如下：

三、实验步骤及结果分析

测试数据：

0.01 0.03 0.07 0.13 0.19 0.26 0.31

程序运行：

请输入一组数，中间用空格分隔：

0.01 0.03 0.07 0.13 0.19 0.26 0.31

输出结果为：

0.01 : 01000 码长：5

0.03 : 01001 码长：5

0.07 : 0101 码长：4

0.13 : 011 码长：3

0.19 : 00 码长：2

0.26 : 10 码长：2

0.31 : 11 码长：2

心得体会：

在本次的课程设计中，就在编写好源代码后的调试中出现了不少的错误，遇到了很多麻烦及困难。我的调试及其中的错误和我最终找出错误，修改为正确的能够执行的程序中，通过分析，我学到了：在递归调用方法时最好不要有返回值，否则会使程序变得逻辑混乱，复杂难懂；当从叶结点向上编码时，根据本程序的特点会有可能重复的tree，所以要分成同tree和不同tree进行不同的逻辑编程。 通过本次的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会了一种算法。当求解一个算法时，不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一不怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。

四、程序设计源代码

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;

public class Huffman {

private List nums;

private List numsMo;

private List trees;

private String temp;

public Huffman() {

nums = new ArrayList();

numsMo = new ArrayList();

trees = new ArrayList(); temp=""; } public void addNums() {// 给定一组数 System.out.println("请输入一组数，中间用空格分隔："); Scanner sca = new Scanner(System.in);

String str = sca.nextLine();

String[] strs = str.split(" ");

for (int i = 0; i

nums.add(Double.parseDouble(strs[i]));

numsMo.add(Double.parseDouble(strs[i]));

}

}

public void compareNum(List nums,List trees) {// 递归算法

} double[] min = new double[2]; if(nums.size()>1){ min = minTwo(nums); Tree t = new Tree(min[0],min[1],min[0]+min[1]); nums.remove(Double.valueOf(min[0])); nums.remove(Double.valueOf(min[1])); nums.add(min[0]+min[1]); trees.add(t); compareNum(nums,trees); } public void print(double num) {// 递归打印编码 for(Tree t : trees){ if(num == t.getRchild()){ temp = 1+temp; print(t.getParents()); break; }else if(num == t.getLchild()){ temp = 0+temp; print(t.getParents()); break; }

} } public void write(double d){ temp = ""; System.out.print(d+" : "); print(d); System.out.print(temp); } public double[] minTwo(List nums) {// 在一组数中System.out.println(" 码长："+temp.length()); 选则最小的两个，按递增排序返回

Double temp = 0.0;

for (int j = 0; j

for (int i = 1; i

if (nums.get(i - 1)

temp = nums.get(i);

nums.set(i, nums.get(i - 1));

nums.set(i - 1, temp);

}

}

}

double[] n =

{nums.get(nums.size()-1),nums.get(nums.size()-2)}; return n;

}

public void start(){

addNums();

compareNum(nums,trees);

while(numsMo.size()>1){

double[] mins = minTwo(numsMo);

if(mins[0]!=mins[1]){

numsMo.remove(Double.valueOf(mins[0])); write(mins[0]);

}

}

if(!numsMo.isEmpty()){

write(numsMo.get(0));

}

}

public static void main(String[] args){

new Huffman().start();

}

}

参考文献

1(美)Stuart Reges，(美)Marty Stepp著 陈志等译，java程序设计教程，机械工业出版社,2008

2（英）David J.C.Mackay著 肖明波，席斌，许芳，王建新译，信息论、推理与学习算法，高等教育出版社，2006