Java哈夫曼编码译码器.doc

哈夫曼编码/译码器 课程设计（论文）任务书 学院 专业 班课程名称 面向对象技术课程设计 题 目 哈夫曼编码/译码器 任务起止日期： 2010 年12 月 06日 2010 年12月 24 日 学 生 姓 名 学 号 指 导 教 师 教研室主任 年 月 日审查课程设计（论文）任务一、课题内容1问题描述利用哈夫曼编码进行数据通信可以大大提高信道利用率，缩短数据传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（还原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。2基本要求一个完整的编/译码系统应具有以下功能：(1)建立哈夫曼树（Create）。从键盘输入字符集中的所有字符及其对应的频率值，建立哈夫曼树。(2)输出编码表（Table）。利用已建好的哈夫曼树，列出字符集中的所有字符及其对应的哈夫曼编码。(3)编码（Coding）。利用已建好的哈夫曼树，对从键盘输入的正文串进行编码，并在屏幕上显示结果。(4)译码（Decoding）。利用已建好的哈夫曼树，对从键盘输入的0、1代码串进行译码，并在屏幕上显示结果。3 测试数据(1)利用下表中给出的字母/频率数据调试程序。字母CDEFKLUZ频率324212024742372（2）用下表中给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“I love you Loo”字母频率字母频率A77O67B17P20C32Q5D42R59E120S67F24T85G17U37H50V12I76W22J4X4K7Y22L42Z2M24(空格)186N674通过对本课题的实践以期使学生程序编写能力得到较大提高。二、课题要求1. 使用Java完成本课题的程序设计，至少定义2个类；2. 程序中必须有界面设计和事件处理，必要时要做容错处理（异常处理）；3. 程序必须得到合理结果，并对所得结果做必要的分析；4. 设计论文正文篇幅不少于3000字；5. 提交的所有材料必须符合长沙理工大学课程设计管理规定（长理工大教20058号）的要求。三、课题完成后应提交的材料1. 课程设计（论文）按以下排列顺序装订成册(1) 封面（统一到学校教材中心领取，并详细填写） (2) 任务书(3) 中文摘要(4) 英文摘要 (5) 目录 (6) 正文 (7) 参考文献(8) 附件（源程序打印件）2.装订成册的论文装入资料袋 资料袋统一到学校教材中心领取，并详细填写四、主要参考文献（由指导教师选定）1 印旻Java与面向对象程序设计教程北京：高等教育出版社，1999.112 东方人华Java 2 范例入门与提高北京：清华大学出版社，2003.83 杨庚、王汝传.面向对象程序设计与C+语言.北京：人民邮电出版社，2002.74 希尔德（美）.Java编程起步.北京：人民邮电出版社，2001.55 罗省贤.Java程序设计教程（第五版）.北京：电子工业出版社，2007.16 张琛恩.面向对象的设计与模式.北京：电子工业出版社，2004.1注：1. 此任务书由指导教师填写。如不够填写，可另加页。2. 此任务书最迟必须在课程设计（论文）开始前下达给学生。学生送交全部材料日期 学生（签名） 指导教师验收（签名） 摘要Huffman编码是一种可变长编码方式，是二叉树的一种特殊转化形式。它的原理是：将使用次数多的代码转换成长度较短的编码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。本文根据Huffman编码原理，在详细设计中，根据权值和最小的根本原则，我们输入要编码的字符集及其它的权值，再根据在概要设计中提到的节点Node类，算法SuanFa类以及主类JieMian类，建立哈夫曼树，并进行编码，最后输出哈夫曼编码。在完成Huffman编码后，我们利用其构建的哈夫曼编码树来进行译码。与编码过程不同，译码过程中，我们将用户输入的二进制代码串依次与字符集中的每个字符的编码进行比较，译出一个字符后，循环比较下一个字符的编码，直到所有二进制码全部译出为止。在编码和译码的过程中，我们遇到很多问题，诸如算法、语法问题，但我们都通过不断的分析，和调试将这些问题一一解决，最终建立了一个完整的编/译码系统。关键词：Huffman编码树；最优二叉树；编码；译码AbstractHuffman coding is a encoding of variable length and a special transformation form of the binary tree. Its principle is: the code that be used more often will be changed into the code of shorter lengths, while the codes that be used less often can be transformed into the code of longer lengths and the unique solution of coding will be kept. According to the theory of Huffman coding, firstly we enter the character set which will be used to coding and their weights. Secondly, according to the fundanmental principle that the sum of the weights needs to be the smallest , the program designs Huffman tree in accordance with these class which are initialized in the outline such as class Node,class SuanFa,and class JieMian. At last, the computer will output Huffman coding on user interface.And then, we use the Huffman coding tree to decoding after the completion of Huffman coding tree.Here are difference with encoding process. We will compare the binary string that the user input with the character set one by one during the processs of decoding .And then, the cycle of the next character encoding will continue which is based on the completion of translation of a character. It will be finished until all the binary code is translated.During the process of coding and decoding, we encounter many problems, such as the problem on arithmetic and grammar. However, we try our best to solve these problems through constant analysis and debugging.Eventually, we achieve the goal that establish a complete system on coding and decoding successfully.Key Words：Huffman coding tree；optimal binary tree；coding；decoding12目录一、需求分析1二、概要设计22.1开发环境22.2程序执行的命令操作22.3自定义类说明2三、详细设计63.1哈夫曼编码/译码模拟器程序的Java类说明6四、设计和调试分析15五、用户手册16六、测试结果20七、参考文献八、附录哈夫曼编码/译码器一需求分析1.举例说明，先前快速远距离通信的主要手段是电报，即将需要传送的文字转换成由二进制的字符组成的字符串。在传送电文时，希望总长尽可能的短，如果对每个字符设计长度不等的编码，且让电文中出现此处较多的字符尽可能短的编码，以减少数据传输经费。哈夫曼树就是根据此原理设计出来的一种存储结构。2.本程序要做的哈夫曼编码译码器的主要功能是：运用二叉树来设计二进制的前缀编码。根据用户给出字符集中的所有字符及其出现的频率（即为此字符的权值），建立哈夫曼编码树，然后利用哈夫曼编码树将输入的字符串编码成相应的哈夫曼编码；反之，根据哈夫曼译码原理将用户所输入的0/1代码串编译成相应的字符串。由此，让用户方便地实现电文词句的Huffman编码及译码。3.构成哈夫曼编码树的合法字符：字母（忽略大小写）和空格。4.演示程序以人机对话方式执行。5演示程序中，当用户输入错误时，系统会输出相应的提示。6程序执行的命令包括：（1）建树并输出编码表（2）编码（3） 译码（4） 清空二概要设计2.1开发环境开发平台：Microsoft Windows7旗舰版开发工具：MyEclipse8.5JDK1.6.0_182.2程序执行的命令操作（1）建树并输出编码表：根据用户在“字符”文本域输入的字符集和在“权值”文本域输入的权值建立哈夫曼编码树，并在“结果”文本域中输出哈夫曼编码树中的每个字符及其对应的Huffman编码；（2）编码：利用建立好的哈夫曼编码树对用户在“词句”文本域中输入的电文字符进行编码，在“结果”中显示编码结果；（3）译码：利用建立好的哈夫曼编码树对用户在“编码”文本域中输入的0/1代码串进行译码，在“结果”中显示译码结果；（4）清空：清空已建立的哈夫曼编码树，重新操作。2.3自定义类说明本程序定义了三个类，分别实现树的节点操作，编码译码的算法实现，以及界面和事件处理，主要属性及算法如下：（1）类名：Node功能：作为节点类，实现节点的基本操作主要属性private int weight;/节点权值private char name;/节点字符名称private int left;/左孩子节点位置private int right;/右孩子节点位置private int parent;/父节点位置private String code;/节点对应的编码主要方法public Node() /构造方法初始化public Node(int weight,char name) /带参数的构造方法，可初始化权值和字符名称public int getWeight() /获取节点权值public void setWeight(int weight) /设置节点权值public char getName()/获取节点字符名称public void setName(char name)/设置节点字符名称public int getLeft()/获得节点左孩子的位置值public void setLeft(int left)/设置节点左孩子的位置值public int getRight()/获得节点右孩子的位置值public void setRight(int right)/设置右孩子的位置值public int getParent()/获得父节点的位置值public void setParent(int parent) /设置父节点的位置值public String getCode()/获得节点的编码public void setCode(String code)/设置节点的编码public boolean isLeaf() /判断节点是否为叶子节点（2）类名：SuanFa功能：算法类，实现哈夫曼编码树的构造，编码和译码等操作主要属性private List nodes;/定义Node类型的动态数组nodes存放Huffman编码树主要方法public List getNodes()public void setNodes(List nodes)public SuanFa(List nodes) /构造方法public int getRoot() /获取已经构造好的huffman编码树的根节点public int selectMinNode() /选择权值最小节点，保存其下标，并统计剩余的没有进树的节点数public void JianShu() /建立哈夫曼树public String getCode(int i) /获得节点的单个编码public void bianMa1() /从叶子到根对字符集中各个字符进行编码public String bianMa2(String names) /编码方法, 对输入的词句字符进行编码public String jieMa(String codes) /译码方法(3)类名：JieMian（主类）功能：设置界面及其相关操作和监听者设置主要属性private static final long serialVersionUID = 1L;private TextArea textName;/字符文本域private TextArea textWeight; /权值文本域private TextArea textResult; /结果文本域private SuanFa suanFa;/算法类对象suanFaprivate TextArea textArea;标签及按钮：private Label label;/字符、词句标签private Label label_1;/权值、编码标签private Button button;/建树按钮private Button button_4;/清空按钮private Button button_2;/编码按钮private Button button_3;/译码按钮主要方法public void init()/界面操作及监听者设置三 详细设计3.1哈夫曼编码/译码模拟器程序的Java类说明（1）节点类Node类的设计及功能描述：A属性设计：构造哈夫曼编码树需要考虑节点结构问题，编码和译码过程中，对二叉树的建立以及查找操作要求Node类中的节点结构包含六个属性，分别用于存放节点权值，节点字符，左孩子节点的位置下标，右孩子节点的位置下标，父节点的位置下标以及该节点对应的编码。B方法设计：节点类的方法主要用于对节点属性值的操作。在主类中通过调用节点对象的方法，完成对节点对象属性值的操作。主要操作分别有构造方法对属性值初始化，获取各个属性值操作，改变各属性值操作。由于查找二叉树的过程中需要判断是否到达叶子节点，所以必不可少的还有判断该节点是否为叶子节点的操作。class Node /节点类private int weight;/weight存放节点权值private char name;/name存放节点字符private int left;/存放左孩子节点位置下标private int right;/右孩子节点位置下标private int parent;/父节点位置下标private String code;/节点对应的编码public Node() /无参构造方法初始化初始化左右孩子属性，权值属性及父节点属性public Node(int weight,char name) /带参数的构造方法，可利用参数初始化权值和字符名称this.weight=weight;=name;剩余属性初始化；public int getWeight() 返回节点权值 public void setWeight(int weight) 设置节点权值 public char getName() 返回节点字符 public void setName(char name) 设置节点字符public int getLeft() 返回节点左孩子位置下标public void setLeft(int left) 设置节点左孩子位置下标public int getRight() 返回节点右孩子位置下标public void setRight(int right) 设置节点右孩子位置下标public int getParent() 返回父节点位置下标public void setParent(int parent) 返设置父节点位置下标public String getCode() 返回节点编码public void setCode(String code) 设置节点编码public boolean isLeaf()/判断节点是否为叶子节点if(left!=-1|right!=-1)若节点存在左右孩子，则返回falseelse否则返回true（2）算法类SuanFa类的设计及功能描述：A属性设计：以Node类类型，定义动态数组nodes，数组下标即为节点的位置，整个数组用于建立和存放Huffman编码树。private List nodes;/定义Node类型的动态数组 nodes存放Huffman编码树 B方法设计：程序运行时的要求建立Huffman编码树，建树过程中需反复从剩余节点中选取权值最小的节点加入到编码树中，因此设计public int selectMinNode()方法选择权值最小节点，保存其下标，并统计剩余的没有进树的节点数。通过建树方法public void JianShu()循环调用selectMinNode()方法，完成从叶子节点到根节点的建树过程。建立编码树后，由public void bianMa1()方法从叶子节点到根节点对字符集中各字符的编码，由 public String bianMa2(String names)方法对输入的词句字符查找编码表进行编码，public String jieMa(String codes)方法对输入的0/1码串，利用编码表从根节点到叶子节点进行译码。编码和译码的结果都可在结果文本域中输出显示。SuanFa类中主要方法的算法伪代码：class SuanFa private List nodes;/定义Node类型的动态数组 nodes存放编码树public SuanFa(List nodes) /构造函数 继承父类构造函数，并初始化nodes数组public int getRoot()/获取已经构造好的huffman编码树的根节点for(从nodes数组第一到最后一个元素) 若第i个元素节点的父节点域值为-1；则index用i赋值；return index;/返回根节点public int selectMinNode()/选择权值最小节点，保存其下标，并统计剩余的没有进树的节点数int index=-1;/index存放权值最小节点的下标值if(null!=nodes&nodes.size()!=0)/如果数组非空，则选取权值最小的节点for(int i=0;inodes.get(i).getWeight()用node记录权值最小的节点，index记录其下标return new intindex,count;/返回权值最小节点的下标和未进树的节点数public void JianShu()/建立哈夫曼编码树int min=selectMinNode();/选取权值最小的节点while(min11|sum%2!=0) /每两个节点生成一个新的节点if(sum%2=0)取到第一个节点时，新建一个父节点else 当取到第二个节点时，将其权值加到新建的父节点中newNode.setWeight(newNode.getWeight()+node.getWeight();min=selectMinNode();/继续选取下一个权值最小的节点public String getCode(int i)/获得节点的单个编码Node pNode=nodes.get(nodes.get(i).getParent();判断，若此节点是其父节点的左孩子则返回0否则为1；public void bianMa1()/从叶子到根对字符集中各个字符进行编码for(int i=0;inodes.size();i+)if(nodes.get(i).isLeaf()/若节点i为叶子，则获取其编码while(parent!=-1)/该节点i不是根节点，则循环记录0/1码串，从叶子到根编码nodes.get(i).setCode(code);/存放节点i的编码public String bianMa2(String names)/编码方法对输入的词句字符进行编码for(int i=0;inames.length();i+)/从词句中第一个字符开始编码for(int j=0;jnodes.size();j+)查找编码表中是否存在该字符/若在编码表中找到该字符icodes+=nodes.get(j).getCode();/则在codes中记录其编码break;/跳出内循环，继续查找下一个字符的编码else if(j=nodes.size()-1) /若找不到该字符，则返回操作提示语return names.charAt(i)+没在编码表中！请重新操作！;return codes;/返回词句编码结果public String jieMa(String codes)/译码方法for(int i=0,j=root;icodes.length();i+)/从根节点到叶子节点进行译码if(codes.charAt(i)=0)/若编码为0，二叉树向左查找j=nodes.get(j).getLeft();else if(codes.charAt(i)=1)/编码为1，二叉树向右查找else/编码含有非0，1字符，则输出提示语return 编码有误，请检查后重新输入！;若节点为叶子节点，则译码成功；j=root; /j用根节点位置赋值，继续下一个译码return names;/返回译码结果（3）主类JieMian类的设计及功能描述：属性设计：JieMian类主要作用是对界面的设计，以及设计监听者对各种事件进行响应和处理。主要界面组件有字符标签，权值标签，字符输入文本框，权值输入文本框，结果输出文本框，建树并输出编码表按钮，编码按钮，译码按钮，清空按钮。方法设计：在public void init()方法中，对建树并输出编码表按钮，编码按钮，译码按钮和清空按钮分别设置ActionListener()监听者，监听按钮点击事件，并分别对不同情况作出响应的异常处理。init方法伪码如下：public void init() button = new Button(u5EFAu6811u5E76u8F93u51FAu7F16u7801u8868);button.addActionListener(new ActionListener()/设置建树按钮监听者public void actionPerformed(ActionEvent e) /点击按钮事件响应trytextResult.setText();/清空结果文本框获取节点字符，及其权值；若字符文本域为空，则提示请输入字符，返回空值；若权值文本域为空，则提示请输入对应权值，返回空；for(int i=0;istrNames.length();i+)/检查输入字符集是否有重复for(int j=i+1;jstrNames.length();j+)若有重复字符，则输出提示语textResult.setText(字符不能重复，（忽略大小写）);return;如果字符和权值不完全对应，提示重新输入textResult.setText(字符和权值不能完全对应！请检查后重新输入！);return;int weightsOfNum=new intweights.length;/定义整型数组weightsOfNum，存放权值；for(int i=0;iweights.length;i+)/将权值字符串转化为整型权值存放于weightsOfNum中weightsOfNumi=Integer.parseInt(weightsi);suanFa=new SuanFa(nodes);/新建SuanFa类对象suanFasuanFa.JianShu();/调用suanFa对象的 JianShu方法，建立huffman编码树suanFa.bianMa1();/调用biamMa1方法，对字符集各字符编码for(int i=0;i1001 B-000011 C-01110 D-10101 E-001 F-110101 G-101000 H-11011 I-1000 J-00001001 K-0000101 L-11000 M-00000 N-0100 O-0101 P-101001 Q-11001001 R-0001 S-0110 T-1011 U-01111 V-1100101 W-110011 X-11001000 Y-110100 Z-00001000 -111图6.6输入“I love you Loo”时，编码结果如下：图6.7输入0/1码串“100011111000010111001010011111101000101011111111100001010101”时译码结果如下：图6.8参考文献1 印旻Java与面向对象程序设计教程北京：高等教育出版社，1999.112 东方人华Java 2 范例入门与提高北京：清华大学出版社，2003.83 杨庚、王汝传.面向对象程序设计与C+语言.北京：人民邮电出版社，2002.74 希尔德（美）.Java编程起步.北京：人民邮电出版社，2001.55 罗省贤.Java程序设计教程（第五版）.北京：电子工业出版社，2007.16 张琛恩.面向对象的设计与模式.北京：电子工业出版社，2004.1附录源程序文件清单：/JieMian.java文件代码import java.applet.Applet;import java.awt.Label;import java.awt.TextArea;import java.awt.Button;import java.awt.event.ActionListener;import java.awt.event.ActionEvent;import java.util.ArrayList;import java.util.List;import java.awt.Color;public class JieMian extends Appletpublic JieMian() private static final long serialVersionUID = 1L;private TextArea textName;private TextArea textWeight;private TextArea textResult;private SuanFa suanFa;private Label label;/字符、词句标签private Label label_1;/权值、编码标签private Button button;/建树按钮private Button button_4;/清空按钮private Button button_2;/编码按钮private Button button_3;/译码按钮private Label label_3;/标题标签private TextArea textArea;public void init() setLayout(null);setSize(635,420);label = new Label(u5B57u7B26uFF1A);label.setBounds(27, 31, 55, 23);add(label);/添加标签label_1 = new Label(u6743u503CuFF1A);label_1.setBounds(27, 139, 55, 23);add(label_1);textNa