C++ Lzw压缩算法分析与实现[源码][附图]

smallsmile

浏览: 133797 次
性别:
来自: 北京

最近访客更多访客>>

lso

lx784848972

月微凉101

lianer_

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

算法 C C++C#数据结构

一、需求分析：
在日常的工作生活中，出于文件存储、传输的要求，需要对数据进行压缩。LZW 压缩算法是一种新颖的压缩方法，由Lemple、Ziv及Welch三人共同创造，并用他们的名字命名。
它采用了一种先进的串表压缩，将每个第一次出现的串放在一个串表中，用一个数字来表示串，压缩文件只存贮数字，则不存贮串，从而使图象文件的压缩效率得到较大的提高的一种无损压缩算法。
由于LZW压缩算法是一种可以即时传输压缩数据并即时解码数据的算法，因此它可以广泛使用在日常的文件压缩及文件传输数据压缩中。
二、概要设计：
要设计一套压缩软件，最核心的部分即是算法，即字典的建立与添加字典数据，检索数据等功能。
同时，还需要制定一套合理，完善的存储规则。
自然，软件必须分为两部分：压缩部分与解压缩部分。
于是软件整体框架即设计为：

三、详细设计：
1、LZW字典的方法
   根据字典压缩算法，可以设计出针对LZW字典需要的基本方法，有：完成字典的初始化（即将0-255这256个数据加入字典中）、完成字典添加数据功能、完成检加对应串的位置功能等。
2、文件存储的规则
（1）五个字节：
文件的验证属性码：l z w r q 。
（2）一个字节
    原文件名的长度n
（3）n个字节
    文件名
（4）n个字节
文件数据对应的压缩后编码
   3、压缩算法
（1）从输入流中读入一个字符，作为当前串的后缀。
（2）如果当前串在字典中，就用当前串的编码作前缀，转到第1步。
（3）如果当前串不在字典中，就把当前串放到字典中，并把前缀放到输出流，后缀变前缀，转到第1步。
（4）当输入流读完后，串中应还剩一个前缀，前其放到输出流，结束。
4、解压缩算法
（1）在输入流中读入一个字符。
（2）如果当前编码在字典中，则把当前编码的第一个字符作为当前串的后缀，如果当前串不在字典中，就把它加入到字典中，然后把当然编码作为串的后缀，转到第4步。
（3）如果当前编码不在字典中，就把前缀的第一个字符作为后缀，把串加入到字典中，用当前串的编码作前缀，转到第4步。
（4）把前缀放到输入流，转到第1步。

四、程序结构
1、程序结构说明：
本程序采用模块化设计方法，各个功能的实现都有具体的方法，在主函数调用相应的方法即可实现程序的要求。程序的整体性很强。
2、重要数据说明：
字节数据定义:
typedef   unsigned   char   byte;
字典结点：
class LzwNode{
    public:
       int data1;//数据1，存前面存放过的数据
       byte data2;//存放新入的数据
};
    class Lzw{
    public:
       int len;//字典的长度
       LzwNode lzw[4096]; //定义一个长为4096的数组，来存放数据
}
3、函数清单：
字典部分：
//初始化方法
       void unitLzw()
     //添加数据方法
void add(int ad,byte x)
   //判断匹配与否
   int matchdatas(byte ss[],int sscount,int i)
// 判断是否在其中的方法
int check(int data1,byte data2)
//找到i对应的数据
byte gethead(int i)
主体部分：
//压缩方法
   void lzwCompression()
//解压缩方法
void unlzwCompression()
五、调试分析：
1、程序截图：

2、程序调试
发现在解压中出现大量异常，调试后发现输出字节中出现大量负数，分析知是读取文件字节类型时转换到整数时出错，将读到的char型强制转化为int时出错，故将其先转化为无符号char后再转为int后问题得到解决。
遇到很多解压缩串码的问题，调试发现在压缩/解压缩多处有误，改正后程序运行正确。
遇到程序解码时程序卡死情况，分析出出错位置后得到解决。
遇到解压文件提前结束情况，分析得遇到1A结束，查询知：1A就是EOF。打开文件的时候指定为二进制方式后问题得到解决。
六、总结：
1、程序设计难点：
本程序的难点在于字典算法的实现及生成文件规则的制定。
2、程序设计中的不足：
本程序功能上实现了使用LZW字典压缩对于文件的压缩，但是在物理、及时间复杂性上还有待优化。同时，还需将其进一步使用在网络通信上。
3、训练体会：
这次训练我最大的收获有两个：
其一、设计软件前一定要将核心的算法用伪代码写出来，这样会极大的避免一些在程序调试过程中的麻烦，可以省不少时间。
其二、调试软件时，遇到程序跑死情况，可以使用对程序分段标记来查找问题出处。此外，多写信息记录点也是一个良好的习惯。