Java哈夫曼编码译码器.docx
- 文档编号:1995702
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:47
- 大小:835.24KB
Java哈夫曼编码译码器.docx
《Java哈夫曼编码译码器.docx》由会员分享,可在线阅读,更多相关《Java哈夫曼编码译码器.docx(47页珍藏版)》请在冰点文库上搜索。
哈夫曼编码/译码器
课程设计(论文)任务书
学院 专业 班
课程名称 面向对象技术课程设计
题 目 哈夫曼编码/译码器
任务起止日期:
2010年12月06日~2010年12月24日
学生姓名 学号
指导教师
教研室主任 年 月 日审查
字母
C
D
E
F
K
L
U
Z
频率
32
42
120
24
7
42
37
2
课程设计(论文)任务
一、课题内容
1.[问题描述]
利用哈夫曼编码进行数据通信可以大大提高信道利用率,缩短数据传输时间,降低传输
成本。
但是,这要求在发送端通过一个编码系统对待传数据预先编码;在接收端将传来的数据进行译码(还原)。
对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。
2.[基本要求]
一个完整的编/译码系统应具有以下功能:
(1)建立哈夫曼树(Create)。
从键盘输入字符集中的所有字符及其对应的频率值,建立哈夫曼树。
(2)输出编码表(Table)。
利用已建好的哈夫曼树,列出字符集中的所有字符及其对应的哈夫曼编码。
(3)编码(Coding)。
利用已建好的哈夫曼树,对从键盘输入的正文串进行编码,并在屏幕上显示结果。
(4)译码(Decoding)。
利用已建好的哈夫曼树,对从键盘输入的0、1代码串进行译码,并在屏幕上显示结果。
3.[测试数据]
(1)利用下表中给出的字母/频率数据调试程序。
(2)用下表中给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:
“IloveyouLoo”
字母
频率
字母
频率
A
77
O
67
B
17
P
20
C
32
Q
5
D
42
R
59
E
120
S
67
F
24
T
85
G
17
U
37
H
50
V
12
I
76
W
22
J
4
X
4
7
K
7
Y
22
L
42
Z
2
M
24
(空格)
186
N
67
4.通过对本课题的实践以期使学生程序编写能力得到较大提高。
二、课题要求
1.使用Java完成本课题的程序设计,至少定义2个类;
2.程序中必须有界面设计和事件处理,必要时要做容错处理(异常处理);
3.程序必须得到合理结果,并对所得结果做必要的分析;
4.设计论文正文篇幅不少于3000字;
5.提交的所有材料必须符合《长沙理工大学课程设计管理规定》(长理工大教[2005]8号的要求。
)
三、课题完成后应提交的材料
1.课程设计(论文)按以下排列顺序装订成册
(1)封面(统一到学校教材中心领取,并详细填写)
(2)任务书
(3)中文摘要
(4)英文摘要
(5)目录
(6)正文
(7)参考文献
(8)附件(源程序打印件)
2.装订成册的论文装入资料袋
资料袋统一到学校教材中心领取,并详细填写
四、主要参考文献(由指导教师选定)
[1]印旻.Java与面向对象程序设计教程.北京:
高等教育出版社,1999.11
[2]东方人华.Java2范例入门与提高.北京:
清华大学出版社,2003.8
[3]杨庚、王汝传.面向对象程序设计与C++语言.北京:
人民邮电出版社,2002.7
[4]希尔德(美).Java编程起步.北京:
人民邮电出版社,2001.5
[5]罗省贤.Java程序设计教程(第五版).北京:
电子工业出版社,2007.1
[6]张琛恩.面向对象的设计与模式.北京:
电子工业出版社,2004.1
注:
1.此任务书由指导教师填写。
如不够填写,可另加页。
2.此任务书最迟必须在课程设计(论文)开始前下达给学生。
哈夫曼编码/译码器
学生送交全部材料日期
学生(签名)
指导教师验收(签名)
摘要
Huffman编码是一种可变长编码方式,是二叉树的一种特殊转化形式。
它的原理是:
将使用次数多的代码转换成长度较短的编码,而使用次数少的可以使用较长的编码,并且保持编码的唯一可解性。
本文根据Huffman编码原理,在详细设计中,根据权值和最小的根本原则,我们输入要编码的字符集及其它的权值,再根据在概要设计中提到的节点Node类,算法SuanFa类以及主类JieMian类,建立哈夫曼树,并进行编码,最后输出哈夫曼编码。
在完成Huffman编码后,我们利用其构建的哈夫曼编码树来进行译码。
与编码过程不同,译码过程中,我们将用户输入的二进制代码串依次与字符集中的每个字符的编码进行比较,译出一个字符后,循环比较下一个字符的编码,直到所有二进制码全部译出为止。
在编码和译码的过程中,我们遇到很多问题,诸如算法、语法问题,但我们都通过不断的分析,和调试将这些问题一一解决,最终建立了一个完整的编/译码系统。
关键词:
Huffman编码树;最优二叉树;编码;译码
Abstract
Huffmancodingisaencodingofvariablelengthandaspecialtransformationformofthebinarytree.Itsprincipleis:
thecodethatbeusedmoreoftenwillbechangedintothecodeofshorterlengths,whilethecodesthatbeusedlessoftencanbetransformedintothecodeoflongerlengthsandtheuniquesolutionofcodingwillbekept.AccordingtothetheoryofHuffmancoding,firstlyweenterthecharactersetwhichwillbeusedtocodingandtheirweights.Secondly,accordingtothefundanmentalprinciplethatthesumoftheweightsneedstobethesmallest,theprogramdesignsHuffmantreeinaccordancewiththeseclasswhichareinitializedintheoutlinesuchasclassNode,classSuanFa,andclassJieMian.Atlast,thecomputerwilloutputHuffmancodingonuserinterface.
Andthen,weusetheHuffmancodingtreetodecodingafterthecompletionofHuffmancodingtree.Herearedifferencewithencodingprocess.Wewillcomparethebinarystringthattheuserinputwiththecharactersetonebyoneduringtheprocesssofdecoding.Andthen,thecycleofthenextcharacterencodingwillcontinuewhichisbasedonthecompletionoftranslationofacharacter.Itwillbefinisheduntilallthebinarycodeistranslated.
Duringtheprocessofcodinganddecoding,weencountermanyproblems,suchastheproblemonarithmeticandgrammar.However,wetryourbesttosolvetheseproblemsthroughconstantanalysisanddebugging.Eventually,weachievethegoalthatestablishacompletesystemoncodinganddecodingsuccessfully.
KeyWords:
Huffmancodingtree;optimalbinarytree;coding;decoding
哈夫曼编码/译码器
目录
一、需求分析 1
二、概要设计 2
2.1开发环境 2
2.2程序执行的命令操作 2
2.3自定义类说明 2
三、详细设计 6
3.1哈夫曼编码/译码模拟器程序的Java类说明 6
四、设计和调试分析 15
五、用户手册 16
六、测试结果 20
七、参考文献八、附录
0
哈夫曼编码/译码器一.需求分析
1.举例说明,先前快速远距离通信的主要手段是电报,即将需要传送的文字转换成由二进制的字符组成的字符串。
在传送电文时,希望总长尽可能的短,如果对每个字符设计长度不等的编码,且让电文中出现此处较多的字符尽可能短的编码,以减少数据传输经费。
哈夫曼树就是根据此原理设计出来的一种存储结构。
2.本程序要做的哈夫曼编码译码器的主要功能是:
运用二叉树来设计二进制的前缀编码。
根据用户给出字符集中的所有字符及其出现的频率(即为此字符的权值),建立哈夫曼编码树,然后利用哈夫曼编码树将输入的字符串编码成相应的哈夫曼编码;反之,根据哈夫曼译码原理将用户所输入的0/1代码串编译成相应的字符串。
由此,让用户方便地实现电文词句的Huffman编码及译码。
3.构成哈夫曼编码树的合法字符:
字母(忽略大小写)和空格。
4.演示程序以人机对话方式执行。
5.演示程序中,当用户输入错误时,系统会输出相应的提示。
6.程序执行的命令包括:
(1)建树并输出编码表
(2)编码
(3)译码
(4)清空
26
二.概要设计
2.1开发环境
开发平台:
MicrosoftWindows7旗舰版开发工具:
MyEclipse8.5
JDK1.6.0_18
2.2程序执行的命令操作
(1)建树并输出编码表:
根据用户在“字符”文本域输入的字符集和在“权值”文本域输入的权值建立哈夫曼编码树,并在“结果”文本域中输出哈夫曼编码树中的每个字符及其对应的Huffman编码;
(2)编码:
利用建立好的哈夫曼编码树对用户在“词句”文本域中输入的电文字符进行编码,在“结果”中显示编码结果;
(3)译码:
利用建立好的哈夫曼编码树对用户在“编码”文本域中输入的0/1代码串进行译码,在“结果”中显示译码结果;
(4)清空:
清空已建立的哈夫曼编码树,重新操作。
2.3自定义类说明
本程序定义了三个类,分别实现树的节点操作,编码译码的算法实现,以及界面和事件处理,主要属性及算法如下:
(1)类名:
Node
功能:
作为节点类,实现节点的基本操作
主要属性
privateintweight;//节点权值privatecharname;//节点字符名称privateintleft;//左孩子节点位置privateintright; //右孩子节点位置privateintparent;//父节点位置privateStringcode;//节点对应的编码
主要方法
publicNode() //构造方法初始化publicNode(intweight,charname)
//带参数的构造方法,可初始化权值和字符名称publicintgetWeight()//获取节点权值
publicvoidsetWeight(intweight)//设置节点权值publicchargetName()//获取节点字符名称
publicvoidsetName(charname)//设置节点字符名称publicintgetLeft()//获得节点左孩子的位置值
publicvoidsetLeft(intleft)//设置节点左孩子的位置值publicintgetRight()//获得节点右孩子的位置值publicvoidsetRight(intright)//设置右孩子的位置值publicintgetParent()//获得父节点的位置值
publicvoidsetParent(intparent)//设置父节点的位置值publicStringgetCode()//获得节点的编码
publicvoidsetCode(Stringcode)//设置节点的编码
publicbooleanisLeaf()//判断节点是否为叶子节点
(2)类名:
SuanFa
功能:
算法类,实现哈夫曼编码树的构造,编码和译码等操作
主要属性
privateList
//定义Node类型的动态数组nodes存放Huffman编码树
主要方法
publicList
publicvoidsetNodes(List
publicintgetRoot() //获取已经构造好的huffman编码树
的根节点
publicint[]selectMinNode() //选择权值最小节点,保存其下标,并统计剩余的没有进树的节点数
publicvoidJianShu() //建立哈夫曼树publicStringgetCode(inti)//获得节点的单个编码
publicvoidbianMa1() //从叶子到根对字符集中各个字符进行编码
publicStringbianMa2(Stringnames) //编码方法,对输入的词句字符进行编码
publicStringjieMa(Stringcodes) //译码方法
(3)类名:
JieMian(主类)
功能:
设置界面及其相关操作和监听者设置
主要属性
privatestaticfinallongserialVersionUID=1L;privateTextAreatextName;//字符文本域privateTextAreatextWeight;//权值文本域privateTextAreatextResult;//结果文本域privateSuanFasuanFa;//算法类对象suanFaprivateTextAreatextArea;
标签及按钮:
privateLabellabel;//字符、词句标签privateLabellabel_1;//权值、编码标签privateButtonbutton;//‘建树’按钮privateButtonbutton_4;//‘清空’按钮privateButtonbutton_2;//‘编码’按钮privateButtonbutton_3;//‘译码’按钮
主要方法
publicvoidinit()//界面操作及监听者设置
三.详细设计
3.1哈夫曼编码/译码模拟器程序的Java类说明
(1)节点类Node
类的设计及功能描述:
A.属性设计:
构造哈夫曼编码树需要考虑节点结构问题,编码和译码过程中,对二叉树的建立以及查找操作要求Node类中的节点结构包含六个属性,分别用于存放节点权值,节点字符,左孩子节点的位置下标,右孩子节点的位置下标,父节点的位置下标以及该节点对应的编码。
B.方法设计:
节点类的方法主要用于对节点属性值的操作。
在主类中通过调用节点对象的方法,完成对节点对象属性值的操作。
主要操作分别有构造方法对属性值初始化,获取各个属性值操作,改变各属性值操作。
由于查找二叉树的过程中需要判断是否到达叶子节点,所以必不可少的还有判断该节点是否为叶子节点的操作。
classNode{ //节点类
privateintweight;//weight存放节点权值privatecharname; //name存放节点字符privateintleft; //存放左孩子节点位置下标privateintright; //右孩子节点位置下标privateintparent;//父节点位置下标
privateStringcode;//节点对应的编码publicNode()//无参构造方法初始化
{初始化左右孩子属性,权值属性及父节点属性}publicNode(intweight,charname)
{ //带参数的构造方法,可利用参数初始化权值和字符名称
this.weight=weight;this.name=name;
剩余属性初始化;
}
publicintgetWeight(){返回节点权值}
publicvoidsetWeight(intweight){设置节点权值}publicchargetName(){返回节点字符}
publicvoidsetName(charname){设置节点字符 }publicintgetLeft(){返回节点左孩子位置下标 }
publicvoidsetLeft(intleft){设置节点左孩子位置下标 }publicintgetRight(){返回节点右孩子位置下标 }
publicvoidsetRight(intright){设置节点右孩子位置下标 }publicintgetParent(){返回父节点位置下标}
publicvoidsetParent(intparent){返设置父节点位置下标 }publicStringgetCode(){返回节点编码 }
publicvoidsetCode(Stringcode){设置节点编码}publicbooleanisLeaf()
{ //判断节点是否为叶子节点
if(left!
=-1||right!
=-1){若节点存在左右孩子,则返回false
}else{否则返回true
}}}
(2)算法类SuanFa
类的设计及功能描述:
A.属性设计:
以Node类类型,定义动态数组nodes,数组下标即为节点的位置,整个数组用于建立和存放Huffman编码树。
privateList
//定义Node类型的动态数组nodes存放Huffman编码树B.方法设计:
程序运行时的要求建立Huffman编码树,建树过程中需反复从剩余节点中选取权值最小的节点加入到编码树中,因此设计publicint[]selectMinNode()方法选择权值最小节点,保存其下标,并统计剩余的没有进树的节点数。
通过建树方法public void
JianShu()循环调用selectMinNode()方法,完成从叶子节点到根节点的建树过程。
建立编码树后,由publicvoidbianMa1()方法从叶子节点到根节点对字符集中各字符的编码,由publicStringbianMa2(Stringnames)方法对输入的词句字符查找编码表进行编码,publicStringjieMa(Stringcodes)方法对输入的0/1码串,利用编码表从根节点到叶子节点进行译码。
编码和译码的结果都可在结果文本域中输出显示。
SuanFa类中主要方法的算法伪代码:
classSuanFa
{ privateList
//定义Node类型的动态数组nodes存放编码树
publicSuanFa(List
{继承父类构造函数,并初始化nodes数组
}
publicintgetRoot()//获取已经构造好的huffman编码树的根节点
{
for(从nodes数组第一到最后一个元素)
{ 若第i个元素节点的父节点域值为-1;则{index用i赋值; }
} returnindex;//返回根节点
}
publicint[]selectMinNode()
{//选择权值最小节点,保存其下标,并统计剩余的没有进树的节点数intindex=-1; //index存放权值最小节点的下标值
if(null!
=nodes&&nodes.size()!
=0)//如果数组非空,则选取权值最小的节点
{ for(inti=0;i {//从nodes数组1到最后一个节点循环查找权值最小的节点if(nodes.get(i).getParent()==-1) { count++;//节点的父节点域为-1,说明该节点未被选取if(node==null) { node=nodes.get(i);index=i; }elseif(node.getWeight()>nodes.get(i).getWeight()) { 用node记录权值最小的节点,index记录其下标 } }}} returnnewint[]{in
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Java 哈夫曼 编码 译码器