《文件的压缩与解压huffman算法功能实现-大学毕业设计》由会员分享，可在线阅读，更多相关《文件的压缩与解压huffman算法功能实现-大学毕业设计（31页珍藏版）》请在金锄头文库上搜索。
1、文件的压缩与解压huffman算法功能实现 摘 要：压缩的实质是数字变换，在多媒体信息中包含大量冗余的信息，把这些余冗的信息去掉，就是实现了压缩；解压是由于计算机处理的信息是以二进制数的形式表示的，因此压缩软件就是把二进制信息中相同的字符串以特殊字符标记来达到压缩的目的。 关键词：压缩；解压缩；需求分析；概要设计；详细设计；测试Abstract：Compression is the essence of digital transformation, contains a large amount of redundant information in the multimedia infor
2、mation, 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 information in the same string tag as special characters to achieve the purpose of compre
3、ssion.Key words：Compression; The decompression; Demand analysis; The profile design; The detailed design; Test; 1 需求分析解决整个项目系统的“做什么”的问题。在这里，对于开发技术并没有涉及，而主要是通过建立模型的方式来描述用户的需求，为客户、用户、开发方等不同参与方提供一个交流的渠道。随着科学技术的进步 ，信息技术越来越广泛地应用到社会的各个行业和领域，互联网深刻地改变着人们的生活方式，推动着人类文明的进步。伴随着信息技术的 普及和发展，互联网技术覆盖了社会政治、经济、文化、生产的
4、各个领域，这种普及使日常生活和工作更加的方便、文娱乐方式更加的多样化。但是，在信息技术的飞速发展，文件的信息量不断增加的背景下，如何让有限的磁盘空间容纳更多数据，成为需要解决的问题。高速发展的存储技术以提高磁盘容量来解决这样的需要，但随着网络环境下数据传递的产生以及宽带的限制，大容量数据问题日益突出。在需求的推动下，对数据压缩的需求产生了。要求文件的存储和拷贝能够保持数据的意思不变的情况下缩小容量，并在使用者需要的时候将文件恢复成原有的样子，这就是压缩与解压的目的。1.1 项目要达到的目标 本项目设定的目标如下：（1）系统能够提供友好的用户界面，使操作人员的工作量最大限度的减少（2）系统具有良
5、好的运行效率，能够得到提高生产率的目的（3）系统应有良好的可扩充性，可以容易的加入其它系统的应用。（4）平台的设计具有一定的超前性，灵活性（5）通过这个项目可以锻炼队伍，提高团队的开发能力和项目管理能力1.2 系统整体结构压 缩 程 序解 压 程 序 压缩与解压程序 1.3 环境1.3.1 系统开发环境 使用了Eclipse进行程序开发，Eclipse是一个可视化JAVA开发工具。是在JAVA2平台上开发商业引用程序、数据库、发布程序的优秀工具。它支持J2EE，所以程序员可以快速的转换企业版JAVA应用程序。使用此开发工具可以实现程序的可视化。系统平台开发语言：JAVA开发工具：myEclip
6、se开发环境运行平台：Windows XP(SP3) 或者Windows 7硬件配置CPU:core i3内存：2G硬盘：500G分辨率：最佳效果 10247681.3.2 系统运行环境 在安装了JAVA虚拟机的操作平台下即可使用。我用的是在WINDOWS 7上安装的JAVA虚拟机操作系统：Windows 7硬件配置CPU:core i3内存：2G硬盘：500G分辨率：最佳效果 1024768用的是jdk-6u10-rc2-bin-b32-windows-i586-p-12_sep_2008。环境变量为：JAVA_HOME=C:Program FilesJavajdk1.6.0_26。Path
7、=“;%JAVA_HOME%bin;%JAVA_HOME%jrebin”CLASSPATH=“.;%JAVA_HOME%lib;%JAVA_HOME%libtools.jar”1.4 功能 文件的压缩与解压，要能方便的进行，要完成的功能有：(1).压缩功能(2).解压缩功能(3).选择文件路径(4).选择操作方案(5).选择新文件保存路径(6).压缩成功后显示被压缩文件的大小(7).错误操作，给出提示1.5 性能需求根据用户对本系统的要求，确定系统在响应时间、可靠性、安全等方面有较高的性能要求。(1）数据精确度压缩时压缩准确（2）时间特性 一般操作的响应时间应在3秒以内。（3）适用性 适用性强
8、，能满足一般用户的要求。（4）正确性要求发布的软件达到用户的预期目标，运行时基本无错误。（5）可靠性 在一般的情况下，不会出错。（6）运行效率 具有较高的效率，几乎不需要用户的等待。（7）易使用性 要求能尽量为用户的使用提供方便。 （8）可维护性 要求本软件在运行中发现错误时，能快速、准确对其进行定位、诊断和修改。（9）可测试性 设计时尽可能减少测试本软件的各项功能所需的工作量。1.5.1 界面需求系统的界面要求如下：主题突出，站点定义、术语和行文格式统一、规范、明确，栏目、菜单设置和布局合理，传递的信息准确、及时。内容丰富，文字准确，语句通顺；专用术语规范，行文格式统一规范。1.5.2 响应
9、时间需求 用户单击后，软件响应速度低于0.5s。单个文件压缩速度不低于3mb/s1.5.3 开放性需求系统应具有十分的灵活性，以适应将来功能扩展的需求。1.5.4 可扩展性需求系统设计要求能够体现扩展性要求，以适应将来功能扩展的需求。2 压缩与解压程序设计2.1 概要设计 Huffman算法简介David Albert Huffman（哈夫曼/赫夫曼/霍夫曼）在MIT攻读博士学位期间于1952年提出了一种从下到上的编码方法，现在被称为Huffman编码，它是一种统计最优的变码长符号编码，让最频繁出现的符号具有最短的编码。Huffman编码的过程具体编码步骤为：(1)将符号按概率从小到大顺序从左
10、至右排列叶节点；(2)连接两个概率最小的顶层节点来组成一个父节点，并在到左右子节点的两条连线上分别标记0和1；(3)重复步骤2，直到得到根节点，形成一棵二叉树；(4)从根节点开始到相应于每个符号的叶节点的0/1串，就是该符号的二进制编码。由于符号按概率大小的排列既可以从左至右、又可以从右至左，而且左右分枝哪个标记为0哪个标记为1是无关紧要的，所以最后的编码结果可能不唯一，但这仅仅是分配的代码不同，而代码的平均长度是相同的。编码式压缩利用各个单字节使用频率不一样的倾向，使定长编码变为不定长编码，给使用频率高的字节更短的编码，使用频率低的字节更长的编码，起到压缩的效果。由于Huffman编码为根结
11、点到叶子结点路径上的0和1的序列，而一个叶子结点的路径不可能是另一个叶子结点路径的前缀，因此一个Huffman编码不可能为另一个Huffman编码的前缀，这就保证了Huffman编码是可以区分的。由于用Huffman算法建立起来的树总是一棵最优二叉树，因此这又让Huffman编码能够实际应用到压缩中。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的 路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N个权值Wi(i=1,
12、2,.n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,.n)。可以证明哈夫曼树的WPL是最小的。哈夫曼编码步骤：一、 对给定的n个权值W1,W2,W3,.,Wi,.,Wn构成n棵二叉树的初始集合F= T1,T2,T3,.,Ti,.,Tn，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算 法，一般还要求以Ti的权值Wi的升序排列。）二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。四、
13、重复二和三两步，直到集合F中只有一棵二叉树为止。利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。哈夫曼树节点:public class Node implements Comparable Node private T data; /当前节点private double weight; /节点权重 private String coding = ;/此节点的哈夫曼编码 private Node lef
14、t; /节点左子树根节点 private Node right; /节点右子树根节点 public Node(T data, double weight) this.data = data; this.weight = weight; public T getData() return data; public void setData(T data) this.data = data; public double getWeight() return weight; public void setWeight(double weight) this.weight = weight; public Node getLeft() return left; public void setLeft(Node left) this.left = left; public Node getRight() return right;
