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

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

一、需求分析：
在日常的工作生活中，出于文件存储、传输的要求，需要对数据进行压缩。LZW 压缩算法是一种新颖的压缩方法，由Lemple、Ziv及Welch三人共同创造，并用他们的名字命名。
它采用了一种先进的串表压缩，将每个第一次出现的串放在一个串表中，用一个数字来表示串，压缩文件只存贮 数字，则不存贮串，从而使图象文件的压缩效率得到较大的提高的一种无损压缩算法。
由于LZW压缩算法是一种可以即时传输压缩数据并即时解码数据的算法，因此它可以广泛使用在日常的文件压缩及文件传输数据压缩中。

免费下载地址在 http://linux.bkjia.com/

用户名与密码都是www.bkjia.com

具体下载目录在 /2012年资料/1月/27日/C++ 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步。