文件的压缩与解压LZW算法解析与实现毕业设计论文.doc

文件的压缩与解压
──LZW算法解析与实现
摘 要: 随着人们对数据的大量需求以及计算机使用时间的增加，计算机磁盘上的文 件越来越大，越来越多。如何让有限的磁盘空间容纳更多的数据成为需要解决的 问题。一方面，高速发展的存储技术以提高磁盘容量来解决这样的需求，但随着网络环境下数据传递的产生以及带宽的限制，大容量数据问题日益突出。在这两种需求的推动下，对数据压缩的需求产生了。人们可以将文件在不改变其本身的 条件下，将其以更小的占用空间存储，并且在需要的时候将文件恢复成原有的样 子，这就是压缩目的。本论文主要研究文件的无损压缩技术，并简要介绍了文件压缩的分类、几种常用的无损压缩格式和常用的压缩算法。运用LZW字典算法，使用Java 语言在Eclipse 环境下设计了使用LZW 算法对文件压缩与解压缩的实现程序。用户可以根据自己的需求，使 用此程序方便地对文件进行压缩或者解压缩操作。这里压缩的实质是数字变换，在多媒体信息中包含大量冗余的信息，把这些余冗的信息去掉，就是实现了压缩；解压是由于计算机处理的信息是以二进制数的形式表示的，因此压缩软件就是把二进制信息中相同的字符串以特殊字符标记来达到压缩的目的。
关键词：压缩；解压缩；LZW
Abstract ：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 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 compression 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 classification, file compression of several commonly used lossless compression formats and commonly used compression algorithms are briefly introduced. The use of LZW dictionary algorithm, using Java language in the Eclipse environment designed for file compression anddecompression algorithm using 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 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 to achieve the purpose of compression.
KeyWords:compression ;decompression; LZW

1 需求分析

文件的压缩与解压缩，要能方便地进行，要完成的功能包括压缩功能，解压 缩功能，选择文件路径，选择操作方案。此程序还要在压缩成功后显示被压缩文件的大小，并对非法操作给出提示。 用户可以选择文件进行压缩或解压缩操作，并选择生成保存路径，默认的保 存路径为原文件目录，压缩的生成文件以原文件加.lzw 后缀命名，在解压缩操 作中，若输入文件不是gzip 格式的压缩文件，则提示gzip 文件格式不对。 程序的基本设计原则有：方便性原则、功能实用性原则和开放性原则等。程 序设计时采用较好的压缩技术，能保证文件压缩的压缩比和可恢复性，确保程序 有较长的生命周期。 本程序的总体目标是实现文件压缩与解压缩的便捷操作，因此需要有便捷的 操作界面。
1.1 LZW算法简介
字符串和编码的对应关系是在压缩过程中动态生成的，并且隐含在压缩数据中，解压的时候根据表来进行恢复，算是一种无损压缩.根据 Lempel-Ziv-Welch Encoding ，简称 LZW 的压缩算法，用任何一种语言来实现它.LZW压缩算法[1] 的基本概念：LZW压缩有三个重要的对象：数据流（CharStream）、编码流（CodeStream）和编译表（String Table）。在编码时，数据流是输入对象（文本文件的据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都须要用借助的对象。字符（Character）：最基础的数据元素，在文本文件中就是一个字节，在光栅数据中就是一个像素的颜色在指定的颜色列表中的索引值；字符串（String）：由几个连续的字符组成； 前缀（Prefix）：也是一个字符串，不过通常用在另一个字符的前面，而且它的长度可以为0；根（Root）：一个长度的字符串；编码（Code）：一个数字，按照固定长度（编码长度）从编码流中取出，编译表的映射值；图案：一个字符串，按不定长度从数据流中读出，映射到编译表条目.LZW压缩算法[2] 的基本原理：提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。看起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始文件数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表.
1.2 项目要达到的目标
本项目设定的目标如下：
（1）系统能够提供友好的用户界面，使操作人员的工作量最大限度的减少
（2）系统具有良好的运行效率，能够得到提高生产率的目的
（3）系统应有良好的可扩充性，可以容易的加入其它系统的应用。
（4）平台的设计具有一定的超前性，灵活性
（5）通过这个项目可以锻炼队伍，提高团队的开发能力和项目管理能力

压 缩 程 序
解 压 程 序
压缩与解压程序
1.3 系统整体结构

1.4 环境
1.4.1 系统开发环境
使用了Eclipse进行程序开发，Eclipse是一个可视化JAVA开发工具。是在JAVA2平台上开发商业引用程序、数据库、发布程序的优秀工具。它支持J2EE，所以程序员可以快速的转换企业版JAVA应用程序。使用此开发工具可以实现程序的可视化。
1.4.2 系统运行环境
操作系统：Windows 7
JAVA虚拟机版本：1.6.0_20
硬件配置
CPU:core i3
内存：2G
硬盘：500G
分辨率：最佳效果 1024×768
用的是jdk-6u10-rc2-bin-b32-windows-i586-p-12_sep_2008。
环境变量为：JAVA_HOME=C:\Program Files\Java\jdk1.6.0_26。
Path=“;%JAVA_HOME%\bin;%JAVA_HOME%\jre\bin”
CLASSPATH=“.;%JAVA_HOME%\lib;%JAVA_HOME%\lib\tools.jar”

1.5 功能
文件的压缩与解压，要能方便的进行，要完成的功能有：
(1).压缩功能
(2).解压缩功能
(3).选择文件路径
(4).选择操作方案
(5).压缩成功后显示被压缩文件的大小
(6).错误操作，给出提示

1.6 性能需求
根据用户对本软件的要求，确定软件在响应时间、可靠性、安全等方面有较高的性能要求。
1.6.1 界面需求
软件的界面要求如下：
主题突出，站点定义、术语和行文格式统一、规范、明确，栏目、菜单设置和布局合理，传递的信息准确、及时。内容丰富，文字准确，语句通顺；专用术语规范，行文格式统一规范。
1.6.2 响应时间需求
用户单击后，软件响应速度低于0.5s。
单个文件压缩解压速度不低于3mb/s
1.6.3 开放性需求
系统应具有十分的灵活性，以适应将来功能扩展的需求。
1.6.4 可扩展性需求
系统设计要求能够体现扩展性要求，以适应将来功能扩展的需求。

2 压缩与解压程序设计

入口
入口
2.1 概要设计
读取原文件的相关信息
2.1.1 压缩模块

读取文件中编码转换
为字符写入压缩文件

出口
出口

入口
2.读取原文件的相关信息
读取文件中编码转换
为字符写入解压缩文件
出口
1.2 解压模块

2.1.3 总体流程图

输出标号
结束
组成entery(p,s)
认识？
开始
读取下一个字符
Y
将前缀变成entery标号
输出前缀，后缀变前缀
记录新entery到标号集
最后一字符？
N

2.1.4 Lzw算法实现压缩与解压

读取原文件相关信息
已编码的数据还原出原来的编译
表.
将文件中的相关信息写入解压文
件
用编译表的字符索引来替代原文本数据的相应字符，建立文件
读取文件中的编码转换为字符写
入解压文件
提取原始文本文件数据中的不同
字符
基于这些字符创建一个编译表
用编译表的字符索引来替代原始文本文件数据中的相应字符,建立文件

将文件相关信息写入压缩文件
读取文件中字符转换为编码写入压缩文件

2.1.5 程序中各个类的初步定义
程序中各个类的初步定义 ：
为了完成此程序，主要设计和运用以下接口和类。其中有
接口：Compressor
类：Main；LzwCompressor；ByteCombination；NBitInputStream；NBitOutputStream； BitInputStream；BitOutputStream；Dict；LimitedDict；Tools。
异常处理：IOException。
各个类的简单介绍如表1：
表1：程序各个主要类的作用
条目
类型
描述
Main
类
主类，程序实例化的所在类
Compressor
接口
被类LzwCompressor等实现的接口
lzwCompressor
类
使用lzw算法来压缩解压文件类
ByteCombination
类
字节数组，代表lzw算法的前缀+后缀
BitInputStream
类
一个输入流，保存读取数据（要压缩文件数据）
BitOutputStream
类
一个输出流，保存成普通文件数据
IOException
异常类
抛出一个输入输出流异常
NBitInputStream
类
一个输入流，保存读取数据（压缩文件数据）
NBitOutputStream
类
一个输出流，保存压缩文件数据
Dict
类
从原码到code的双向映射字典
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） 压缩完成
compress
BitInputStream
ungzip
lzwBuild
NBitOutputStream

2.2.2 解压的程序流程
解压程序的实现过程中，涉及到很多类的调用，除了压缩有关的类，还有IO类的调用。忽略IO类，解压类的调用过程如下：
(1) 获取路径中文件的后缀名，是Lzw，是用Lzw算法压缩的压缩文件
(2) 用Lzw算法解压，创建一个Lzw原码组合
(3) 用压缩器的decompress方法解压
(4) 在字典中寻找字符，在编码数据 流中还有Codeword吗？
(5) 没有则结束译码，去掉后缀lzw
(6) 对应字节不为空就输出

(7) 解压完成

compress
NBitInputStream
gzip
LzwBuild
BitOutputStream
decompress

2.2.3 程序界面设计
为了让用户更加方便的操作软件，还要对程序加入一个可视化界面，其外观设计如下：

用户可根据路径选择文件，然后选择相应压缩解压方法进行压缩解压。
界面核心代码如下：
class zipview {
public zipview() {
}

protected Shell shell;
private Text fileDirText;
private Text fileNameText;
private final FormToolkit formToolkit = new FormToolkit(Display.getDefault());

public void open() {
Display display = Display.getDefault();
createContents();
shell.open();
shell.layout();
while (!shell.isDisposed()) {
if (!display.readAndDispatch()) {
display.sleep();
}
}
}
protected void createContents() {
shell = new Shell();
shell.setSize(450, 300);
shell.setText("压缩解压软件 ");
shell.setLayout(new FormLayout());

Button button = new Button(shell, SWT.NONE);
FormData fd_button = new FormData();
fd_button.right = new FormAttachment(0, 141);
fd_button.top = new FormAttachment(0, 212);
fd_button.left = new FormAttachment(0, 61);
button.addSelectionListener(new ButtonClickListener3());;
button.setLayoutData(fd_button);
button.setText("\u538B\u7F29");

Button button_1 = new Button(shell, SWT.NONE);
FormData fd_button_1 = new FormData();
fd_button_1.right = new FormAttachment(0, 391);
fd_button_1.top = new FormAttachment(0, 212);
fd_button_1.left = new FormAttachment(0, 311);
button_1.addSelectionListener(new ButtonClickListener4());;
button_1.setLayoutData(fd_button_1);
button_1.setText("\u89E3\u538B");

Label label = new Label(shell, SWT.NONE);
FormData fd_label = new FormData();
fd_label.left = new FormAttachment(0, 61);
label.setLayoutData(fd_label);
label.setText("\u538B\u7F29\u7B97\u6CD5\uFF1A");

Button btnLzw = new Button(shell, SWT.RADIO);
fd_label.right = new FormAttachment(btnLzw, -5);
FormData fd_btnLzw = new FormData();
fd_btnLzw.right = new FormAttachment(0, 225);
fd_btnLzw.top = new FormAttachment(0, 61);
fd_btnLzw.left = new FormAttachment(0, 127);
btnLzw.addSelectionListener(new ButtonClickListener());;
btnLzw.setLayoutData(fd_btnLzw);
btnLzw.setText("lzw");

Button btnHaffman = new Button(shell, SWT.RADIO);
FormData fd_btnHaffman = new FormData();
fd_btnHaffman.right = new FormAttachment(0, 225);
fd_btnHaffman.top = new FormAttachment(0, 105);
fd_btnHaffman.left = new FormAttachment(0, 127);
btnHaffman.addSelectionListener(new ButtonClickListener1());;
btnHaffman.setLayoutData(fd_btnHaffman);
btnHaffman.setText("haffman");
Button btnLzwhaffman = new Button(shell, SWT.RADIO);
FormData fd_btnLzwhaffman = new FormData();
fd_btnLzwhaffman.right = new FormAttachment(0, 225);
fd_btnLzwhaffman.top = new FormAttachment(0, 150);
fd_btnLzwhaffman.left = new FormAttachment(0, 127);
btnLzwhaffman.addSelectionListener(new
ButtonClickListener2());;
btnLzwhaffman.setLayoutData(fd_btnLzwhaffman);
btnLzwhaffman.setText("lzw+haffman");

Button button1 = new Button(shell, SWT.NONE);
fd_label.top = new FormAttachment(0, 62);
FormData fd_button1 = new FormData();
fd_button1.bottom = new FormAttachment(label, -17);

button1.setLayoutData(fd_button1);
button1.addSelectionListener(new SelectionAdapter() {
public void widgetSelected(SelectionEvent e) {
FileDialog fileDialog=new FileDialog(shell);
fileDialog.setText("chooser");
fileDialog.open();
fileDirText.setText(fileDialog.getFilterPath()+"\\"+fileDialog.getFileName());
}
});

button1.addSelectionListener(new ButtonClickListener5());
button1.setBounds(213, 77, 72, 22);
button1.setText("浏览");

Label lblNewLabel = new Label(shell, SWT.NONE);
FormData fd_lblNewLabel = new FormData();
fd_lblNewLabel.top = new FormAttachment(0);
lblNewLabel.setLayoutData(fd_lblNewLabel);
lblNewLabel.setBounds(139, 127, 54, 12);
lblNewLabel.setText("文件路径");

fileDirText = new Text(shell, SWT.BORDER);
FormData fd_fileDirText = new FormData();
fd_fileDirText.top = new FormAttachment(lblNewLabel, 7);
fd_fileDirText.left = new FormAttachment(button1, 20);
fileDirText.setLayoutData(fd_fileDirText);
fileDirText.setBounds(213, 127, 70, 18);

Label lblNewLabel_1 = new Label(shell, SWT.NONE);
fd_lblNewLabel.right = new FormAttachment(lblNewLabel_1, -93);
FormData fd_lblNewLabel_1 = new FormData();
fd_lblNewLabel_1.left = new FormAttachment(0, 277);
fd_lblNewLabel_1.top = new FormAttachment(0, 2);
lblNewLabel_1.setLayoutData(fd_lblNewLabel_1);
lblNewLabel_1.setBounds(139, 173, 54, 12);
lblNewLabel_1.setText("文件名");

Hyperlink hprlnkNewHyperlink = formToolkit.createHyperlink(shell, "更多详情", SWT.NONE);
fd_button1.left = new FormAttachment(hprlnkNewHyperlink, 7);
FormData fd_hprlnkNewHyperlink = new FormData();
fd_hprlnkNewHyperlink.right = new FormAttachment(100, -360);
fd_hprlnkNewHyperlink.bottom = new FormAttachment(label, -20);
hprlnkNewHyperlink.setLayoutData(fd_hprlnkNewHyperlink);
hprlnkNewHyperlink.setBounds(139, 81, 63, 14);
formToolkit.paintBordersFor(hprlnkNewHyperlink);
hprlnkNewHyperlink.addHyperlinkListener(new HyperlinkAdapter(){

@Override
public void linkActivated(HyperlinkEvent e) {
try {
Runtime.getRuntime().exec("rundll32 url.dll,FileProtocolHandler ");
} catch (IOException e1) {
e1.printStackTrace();
}

}

});

}
public final class ButtonClickListener extends SelectionAdapter {
public void widgetSelected(SelectionEvent e) {
Compressor compressor;
String path=fileDirText.getText();

if(path.equals(fileDirText.getText()))
{
System.out.println("开始压缩");
compressor=new LzwCompressor();
try {
press(path,
path+".lzw");

} catch (IOException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
System.out.println("压缩完毕");
}else{
System.out.println(path);

}
}
}
public final class ButtonClickListener1 extends SelectionAdapter {

public void widgetSelected(SelectionEvent e) {

Compressor compressor;
//Button btnlzw=new Button(shell,SWT.NONE);
String path=fileDirText.getText();
//btnlzw.addSelectionListener(new ButtonClickListener());
if(path.equals(fileDirText.getText()))
{
System.out.println("开始压缩");

System.out.println("路径为"+fileDirText.getText());
compressor=new HuffmanCompressor();
try {
press(path,
path+".huf");

} catch (IOException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
System.out.println("压缩完毕");

}else{
System.out.println(path);

}

System.out.println("监听成功haffman");

}
}
public final class ButtonClickListener2 extends SelectionAdapter {

public void widgetSelected(SelectionEvent e) {
Compressor compressor;
//Button btnlzw=new Button(shell,SWT.NONE);
String path=fileDirText.getText();
//btnlzw.addSelectionListener(new ButtonClickListener());
if(path.equals(fileDirText.getText()))
{
System.out.println("开始压缩");
compressor=new LzwCompressor();
try {
press(path,
path+".tmp");
} catch (IOException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
compressor=new HuffmanCompressor();
try {
press(path+".tmp",
path+".lhf");
} catch (IOException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
System.out.println("压缩完毕");

}
else{
System.out.println("输入错误，请重新输入");
}

System.out.println("监听成功haffman+lzw");

}
}
public final class ButtonClickListener3 extends SelectionAdapter {
public void widgetSelected(SelectionEvent e) {