1、第 1 页（ 共 43 页）本科毕业论文（20 届）文件的压缩与解压LZW 算法解析与实现 所在学院专业班级 信息与计算科学学生姓名指导教师完成日期第 2 页（ 共 43 页）文件的压缩与解压LZW算法解析与实现 摘 要: 随着人们对数据的大量需求以及计算机使用时间的增加，计算机磁盘上的文 件越来越大，越来越多。如何让有限的磁盘空间容纳更多的数据成为需要解决的 问题。一方面，高速发展的存储技术以提高磁盘容量来解决这样的需求，但随着网络环境下数据传递的产生以及带宽的限制，大容量数据问题日益突出。在这两种需求的推动下，对数据压缩的需求产生了。人们可以将文件在不改变其本身的 条件下，将其以更小的占用
2、空间存储，并且在需要的时候将文件恢复成原有的样 子，这就是压缩目的。本论文主要研究文件的无损压缩技术，并简要介绍了文件压缩的分类、几种常用的无损压缩格式和常用的压缩算法。运用 LZW 字典算法，使用 Java 语言在 Eclipse 环境下设计了使用 LZW 算法对文件压缩与解压缩的实现程序。用户可以根据自己的需求，使 用此程序方便地对文件进行压缩或者解压缩操作。这里压缩的实质是数字变换，在多媒体信息中包含大量冗余的信息，把这些余冗的信息去掉，就是实现了压缩；解压是由于计算机处理的信息是以二进制数的形式表示的，因此压缩软件就是把二进制信息中相同的字符串以特殊字符标记来达到压缩的目的。关键词：压
3、缩；解压缩；LZWAbstract ：with the increasing demand of the large amount of data and the using time of computer, computer disk file is more and more big, more and more. How to make the limited disk space to accommodate more data becomes a problem need to be solved. On the one hand, the rapid development of
4、 storage technology to improve disk capacity to address such needs, but with the networkenvironment of data transfer generation and bandwidth constraints, the problem of large capacity data have become increasingly prominent. In the promotion ofthese two kinds of demand, the need for data compressio
5、n and decompressionproduced. People can file without changing their own condition, be in a smaller storage space, and the file to its original appearance in time of need, this is the final compression. Lossless compression techniques the thesis focuses on the research of documents, and the classific
6、ation, file compression of several commonly used lossless compression formats and commonly used compression algorithms are briefly introduced. The use of LZW dictionary 第 3 页（ 共 43 页）algorithm, using Java language in the Eclipse environment designed for file compression anddecompression algorithm us
7、ing LZW implementation procedures. The user can according to their own needs, so that the compression or decompressionoperation on the file conveniently by using the program. This compression is the essence of digital transformation, contains a large number of redundant information in the multimedia
8、 information, put these on redundancy informationremoved, it is the realization of compression; decompression is because the computer information processing is based on binary form representation, so the compression software is the same two hexadecimal string information in a specialcharacter mark t
9、o achieve the purpose of compression.KeyWords:compression ;decompression; LZW第 4 页（ 共 43 页）1 需求分析文件的压缩与解压缩，要能方便地进行，要完成的功能包括压缩功能，解压 缩功能，选择文件路径，选择操作方案。此程序还要在压缩成功后显示被压缩文件的大小，并对非法操作给出提示。 用户可以选择文件进行压缩或解压缩操作，并选择生成保存路径，默认的保 存路径为原文件目录，压缩的生成文件以原文件加.lzw 后缀命名，在解压缩操 作中，若输入文件不是 gzip 格式的压缩文件，则提示 gzip 文件格式不对。 程序的基
10、本设计原则有：方便性原则、功能实用性原则和开放性原则等。程 序设计时采用较好的压缩技术，能保证文件压缩的压缩比和可恢复性，确保程序 有较长的生命周期。 本程序的总体目标是实现文件压缩与解压缩的便捷操作，因此需要有便捷的 操作界面。1.1 LZW 算法简介字符串和编码的对应关系是在压缩过程中动态生成的，并且隐含在压缩数据中，解压的时候根据表来进行恢复，算是一种无损压缩.根据 Lempel-Ziv-Welch Encoding ，简称 LZW 的压缩算法，用任何一种语言来实现它.LZW 压缩算法1 的基本概念： LZW 压缩有三个重要的对象：数据流（CharStream）、编码流（CodeStre
11、am）和编译表（String Table）。在编码时，数据流是输入对象（文本文件的据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都须要用借助的对象。字符（Character）：最基础的数据元素，在文本文件中就是一个字节，在光栅数据中就是一个像素的颜色在指定的颜色列表中的索引值；字符串（String）：由几个连续的字符组成； 前缀（Prefix）：也是一个字符串，不过通常用在另一个字符的前面，而且它的长度可以为 0；根（Root ）：一个长度的字符串；编码（Code）：一个数字，按照固定长度（编码长度）从编码流中取
12、出，编译表的映射值；图案：一个字符串，按不定长度从数据流中读出，映射到编译表条目.LZW 压缩算法2 的基本原理：提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。看第 5 页（ 共 43 页）起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始文件数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表.1.2 项目要达到的目标本项目设定的目标如下：（1）系统能够提供友好的用户界面，使操作人员的工作量最大限度的减少（2）系统具有良好的运行效率，能够得
13、到提高生产率的目的（3）系统应有良好的可扩充性，可以容易的加入其它系统的应用。（4）平台的设计具有一定的超前性，灵活性（5）通过这个项目可以锻炼队伍，提高团队的开发能力和项目管理能力1.3 系统整体结构1.4 环境1.4.1 系统开发环境 使用了 Eclipse 进行程序开发，Eclipse 是一个可视化 JAVA 开发工具。是在 JAVA2 平台上开发商业引用程序、数据库、发布程序的优秀工具。它支持J2EE，所以程序员可以快速的转换企业版 JAVA 应用程序。使用此开发工具可以实现程序的可视化。1.4.2 系统运行环境操作系统：Windows 7JAVA 虚拟机版本：1.6.0_20硬件配置
14、CPU:core i3内存：2G硬盘：500G压 缩 程 序 解 压 程 序压缩与解压程序第 6 页（ 共 43 页）分辨率：最佳效果 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.5 功能文件的压缩与解压，要能方便的进行，要完成的功能有：(1)
15、.压缩功能(2).解压缩功能(3).选择文件路径(4).选择操作方案(5).压缩成功后显示被压缩文件的大小(6).错误操作，给出提示1.6 性能需求根据用户对本软件的要求，确定软件在响应时间、可靠性、安全等方面有较高的性能要求。1.6.1 界面需求软件的界面要求如下：主题突出，站点定义、术语和行文格式统一、规范、明确，栏目、菜单设置和布局合理，传递的信息准确、及时。内容丰富，文字准确，语句通顺；专用术语规范，行文格式统一规范。1.6.2 响应时间需求 用户单击后，软件响应速度低于 0.5s。单个文件压缩解压速度不低于 3mb/s1.6.3 开放性需求系统应具有十分的灵活性，以适应将来功能扩展的
16、需求。1.6.4 可扩展性需求第 7 页（ 共 43 页）系统设计要求能够体现扩展性要求，以适应将来功能扩展的需求。2 压缩与解压程序设计2.1 概要设计2.1.1 压缩模块2.1.2 解压模块2.1.3 总体流程图入口出口入口读取原文件的相关信息读取文件中编码转换为字符写入解压缩文件出口输出标号结束组成 entery(p,s)认识？开始读取下一个字符Y将前缀变成 entery标号输出前缀，后缀变前缀记录新 entery 到标号集最后一字符？N读取原文件的相关信息读取文件中编码转换为字符写入压缩文件入口出口第 8 页（ 共 43 页）2.1.4 Lzw 算法实现压缩与解压提取原始文本文件数据中
17、的不同 字符基于这些字符创建一个编译表用编译表的字符索引来替代原始文本文件数据中的相应字符,建立文件将文件相关信息写入压缩文件读取文件中字符转换为编码写入压缩文件读取原文件相关信息已编码的数据还原出原来的编译 表.将文件中的相关信息写入解压文件用编译表的字符索引来替代原文本数据的相应字符，建立文件 读取文件中的编码转换为字符写入解压文件第 9 页（ 共 43 页）2.1.5 程序中各个类的初步定义程序中各个类的初步定义 ：为了完成此程序，主要设计和运用以下接口和类。其中有接口：Compressor类：Main； LzwCompressor； ByteCombination；NBitInputS
18、tream；NBitOutputStream； BitInputStream；BitOutputStream；Dict ；LimitedDict；Tools 。异常处理：IOException。各个类的简单介绍如表 1：表 1：程序各个主要类的作用条目 类型 描述Main 类 主类，程序实例化的所在类Compressor 接口 被类 LzwCompressor 等实现的接口lzwCompressor 类 使用 lzw 算法来压缩解压文件类ByteCombination 类 字节数组，代表 lzw 算法的前缀+后缀BitInputStream 类 一个输入流，保存读取数据（要压缩文件数据）Bit
19、OutputStream 类 一个输出流，保存成普通文件数据IOException 异常类 抛出一个输入输出流异常NBitInputStream 类 一个输入流，保存读取数据（压缩文件数据）NBitOutputStream 类 一个输出流，保存压缩文件数据Dict 类 从原码到 code 的双向映射字典第 10 页（ 共 43 页）LimitedDict 类 带限制的字典Tools 类 工具类2.2 详细设计和实现2.2.1 压缩的程序流程压缩程序的实现过程中，涉及到很多类的调用，除了压缩有关的类，还有IO 类的调用。忽略 IO 类，压缩类的调用过程如下：（1）判断文件路径是否正确，正确后，选择压缩方法进行压缩。（2）选择 Lzw 方法进行压缩。（3）LzwCompress 实现接口 compress（4）调用输入流读入文件字符。（5）对读入的文件字符，调用 Dict 存入字典。（6）向 encodeOneChar 方法输入该字节，并返回组合的 code。（7）使用 ByteCombination 把一个 code 变为原码组合。（8）新建一个输入流，为了重新开始读取（9）遇到文件结束符，写入压缩缓存（10）用 Lzw 算法压缩的文件，加个 .lzw 的后缀名（11）压缩完成compressBitInputStreamungziplzwBuildNBitOutputStream
