文件的压缩与解压──huffman算法功能实现【毕业论文设计】.doc

1、第 1 页 （共 32 页）本科毕业论文（20 届）文件的压缩与解压huffman 算法功能实现所在学院专业班级 信息与计算科学学生姓名指导教师完成日期第 2 页 （共 32 页）文件的压缩与解压huffman 算法功能实现摘 要：压缩的实质是数字变换，在多媒体信息中包含大量冗余的信息，把这些余冗的信息去掉，就是实现了压缩；解压是由于计算机处理的信息是以二进制数的形式表示的，因此压缩软件就是把二进制信息中相同的字符串以特殊字符标记来达到压缩的目的。关键词：压缩；解压缩；需求分析；概要设计；详细设计；测试Abstract：Compression is the essence of digital

2、 transformation, contains a large amount of redundant information in the multimedia information, the residual redundancy information, is to implement the compression; Decompression is due to the computer processing of information in the form of a binary number, so the compression software is binary

3、information in the same string tag as special characters to achieve the purpose of compression.Key words：Compression; The decompression; Demand analysis; The profile design; The detailed design; Test;第 3 页 （共 32 页）1 需求分析解决整个项目系统的“做什么”的问题。在这里，对于开发技术并没有涉及，而主要是通过建立模型的方式来描述用户的需求，为客户、用户、开发方等不同参与方提供一个交流的渠

4、道。随着科学技术的进步 ，信息技术越来越广泛地应用到社会的各个行业和领域，互联网深刻地改变着人们的生活方式，推动着人类文明的进步。伴随着信息技术的 普及和发展，互联网技术覆盖了社会政治、经济、文化、生产的各个领域，这种普及使日常生活和工作更加的方便、文娱乐方式更加的多样化。但是，在信息技术的飞速发展，文件的信息量不断增加的背景下，如何让有限的磁盘空间容纳更多数据，成为需要解决的问题。高速发展的存储技术以提高磁盘容量来解决这样的需要，但随着网络环境下数据传递的产生以及宽带的限制，大容量数据问题日益突出。在需求的推动下，对数据压缩的需求产生了。要求文件的存储和拷贝能够保持数据的意思不变的情况下缩小

5、容量，并在使用者需要的时候将文件恢复成原有的样子，这就是压缩与解压的目的。1.1 项目要达到的目标 本项目设定的目标如下：（1）系统能够提供友好的用户界面，使操作人员的工作量最大限度的减少（2）系统具有良好的运行效率，能够得到提高生产率的目的（3）系统应有良好的可扩充性，可以容易的加入其它系统的应用。（4）平台的设计具有一定的超前性，灵活性（5）通过这个项目可以锻炼队伍，提高团队的开发能力和项目管理能力1.2 系统整体结构1.3 环境压 缩 程 序 解 压 程 序压缩与解压程序第 4 页 （共 32 页）1.3.1 系统开发环境 使用了 Eclipse 进行程序开发，Eclipse 是一个可视

6、化 JAVA 开发工具。是在 JAVA2 平台上开发商业引用程序、数据库、发布程序的优秀工具。它支持J2EE，所以程序员可以快速的转换企业版 JAVA 应用程序。使用此开发工具可以实现程序的可视化。系统平台开发语言：JAVA开发工具：myEclipse开发环境运行平台：Windows XP(SP3) 或者 Windows 7硬件配置CPU:core i3内存：2G硬盘：500G分辨率：最佳效果 10247681.3.2 系统运行环境在安装了 JAVA 虚拟机的操作平台下即可使用。我用的是在 WINDOWS 7 上安装的 JAVA 虚拟机操作系统：Windows 7硬件配置CPU:core i3

7、内存：2G硬盘：500G分辨率：最佳效果 1024768用的是 jdk-6u10-rc2-bin-b32-windows-i586-p-12_sep_2008。环境变量为：JAVA_HOME=C:Program FilesJavajdk1.6.0_26。Path=“;%JAVA_HOME%bin;%JAVA_HOME%jrebin”CLASSPATH=“.;%JAVA_HOME%lib;%JAVA_HOME%libtools.jar”1.4 功能文件的压缩与解压，要能方便的进行，要完成的功能有：第 5 页 （共 32 页）(1).压缩功能(2).解压缩功能(3).选择文件路径(4).选择操作方

8、案(5).选择新文件保存路径(6).压缩成功后显示被压缩文件的大小(7).错误操作，给出提示1.5 性能需求根据用户对本系统的要求，确定系统在响应时间、可靠性、安全等方面有较高的性能要求。(1）数据精确度压缩时压缩准确（2）时间特性一般操作的响应时间应在 3 秒以内。（3）适用性适用性强，能满足一般用户的要求。（4）正确性要求发布的软件达到用户的预期目标，运行时基本无错误。（5）可靠性在一般的情况下，不会出错。（6）运行效率具有较高的效率，几乎不需要用户的等待。（7）易使用性要求能尽量为用户的使用提供方便。 （8）可维护性要求本软件在运行中发现错误时，能快速、准确对其进行定位、诊断和修改。（9

9、）可测试性设计时尽可能减少测试本软件的各项功能所需的工作量。第 6 页 （共 32 页）1.5.1 界面需求系统的界面要求如下：主题突出，站点定义、术语和行文格式统一、规范、明确，栏目、菜单设置和布局合理，传递的信息准确、及时。内容丰富，文字准确，语句通顺；专用术语规范，行文格式统一规范。1.5.2 响应时间需求 用户单击后，软件响应速度低于 0.5s。单个文件压缩速度不低于 3mb/s1.5.3 开放性需求系统应具有十分的灵活性，以适应将来功能扩展的需求。1.5.4 可扩展性需求系统设计要求能够体现扩展性要求，以适应将来功能扩展的需求。2 压缩与解压程序设计2.1 概要设计Huffman 算

10、法简介David Albert Huffman（哈夫曼/赫夫曼/霍夫曼）在 MIT 攻读博士学位期间于 1952 年提出了一种从下到上的编码方法，现在被称为 Huffman 编码，它是一种统计最优的变码长符号编码，让最频繁出现的符号具有最短的编码。Huffman 编码的过程具体编码步骤为：(1)将符号按概率从小到大顺序从左至右排列叶节点；(2)连接两个概率最小的顶层节点来组成一个父节点，并在到左右子节点的两条连线上分别标记 0 和 1；(3)重复步骤 2，直到得到根节点，形成一棵二叉树；(4)从根节点开始到相应于每个符号的叶节点的 0/1 串，就是该符号的二进制编码。由于符号按概率大小的排列既

11、可以从左至右、又可以从右至左，而且左右第 7 页 （共 32 页）分枝哪个标记为 0 哪个标记为 1 是无关紧要的，所以最后的编码结果可能不唯一，但这仅仅是分配的代码不同，而代码的平均长度是相同的。编码式压缩利用各个单字节使用频率不一样的倾向，使定长编码变为不定长编码，给使用频率高的字节更短的编码，使用频率低的字节更长的编码，起到压缩的效果。由于 Huffman 编码为根结点到叶子结点路径上的 0 和 1 的序列，而一个叶子结点的路径不可能是另一个叶子结点路径的前缀，因此一个Huffman 编码不可能为另一个 Huffman 编码的前缀，这就保证了 Huffman 编码是可以区分的。由于用 H

12、uffman 算法建立起来的树总是一棵最优二叉树，因此这又让 Huffman 编码能够实际应用到压缩中。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的 路径长度（若根结点为 0 层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为 WPL= (W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N 个权值 Wi(i=1,2,.n)构成一棵有 N 个叶结点的二叉树，相应的叶结点的路径长度为 Li(i=1,2,.n)。可以证明哈夫曼树的 WPL 是最小的。哈夫曼编码步骤：1、对给定的 n 个权值W1,W2,W

13、3,.,Wi,.,Wn构成 n 棵二叉树的初始集合 F= T1,T2,T3,.,Ti,.,Tn，其中每棵二叉树 Ti 中只有一个权值为 Wi 的根结点，它的左右子树均为空。（为方便在计算机上实现算 法，一般还要求以 Ti 的权值Wi 的升序排列。）二、在 F 中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从 F 中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合 F第 8 页 （共 32 页）中。四、重复二和三两步，直到集合 F 中只有一棵二叉树为止。利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降

14、低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。哈夫曼树节点:public class Node implements Comparable private T data; /当前节点private double weight; /节点权重private String coding = “;/此节点的哈夫曼编码private Node left; /节点左子树根节点 private Node right; /节点右子树根节点public Node(T data, d

15、ouble weight) this.data = data; this.weight = weight; public T getData() return data; public void setData(T data) this.data = data; public double getWeight() 第 9 页 （共 32 页）return weight; public void setWeight(double weight) this.weight = weight; public Node getLeft() return left; public void setLeft

16、(Node left) this.left = left; public Node getRight() return right; public void setRight(Node right) this.right = right; public String getCoding() return coding;public void setCoding(String coding) this.coding = coding;Override public String toString() return “data:“+this.data+“;weight:“+this.weight+

17、“;Coding:“+this.coding; 第 10 页 （共 32 页）Override public int compareTo(Node other) if(other.getWeight() this.getWeight() return 1; if(other.getWeight() /创建哈夫曼树public static Node createTree(List nodes) while(nodes.size() 1) Collections.sort(nodes); /根据权重从大到小排列节点/取权重最小两个节点作为左右子树根节点Node left = nodes.get(nodes.size()-1); Node right = nodes.get(nodes.size()-2); /构造根节点Node parent = new Node(null, left.getWeight()+right.getWeight();