lzw压缩算法的c语言实现

《lzw压缩算法的c语言实现》由会员分享，可在线阅读，更多相关《lzw压缩算法的c语言实现（18页珍藏版）》请在装配图网上搜索。

1、标准的LZW压缩原理：先来解释一下几个基本概念：LZW压缩有三个重要的对象：数据流(CharStream)、编码流(CodeStream)和编译 表(String Table)。在编码时，数据流是输入对象(图象的光栅数据序列)，编码流 就是输出对象(经过压缩运算的编码数据)；在解码时，编码流则是输入对象，数据 流是输出对象；而编译表是在编码和解码时都须要用借助的对象。字符(Character):最基础的数据元素，在文本文件中就是一个字节，在光栅数据中就 是一个像素的颜色在指定的颜色列表中的索引值；字符串(Str ing)：由几个连续的字符组成；前缀(Prefix):也是一个字符串，不过通常用在

2、另一个字符的前面，而且它的长度可以为0； 根(Root):单个长度的字符串；编码(Code):个数字，按照固定长度(编码长度)从编码流中取出，编译表的映射值； 图案：一个字符串，按不定长度从数据流中读出,映射到编译表条目.LZW 压缩的原理：提取原始图象数据中的不同图案，基于这些图案创建一个编译表， 然后用编译表中的图案索引来替代原始光栅数据中的相应图案，减少原始数据大小。看 起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事 先创建好的，而是根据原始图象数据动态创建的，解码时还要从已编码的数据中还原出 原来的编译表(GIF文件中是不携带编译表信息的)，为了更好理解编

3、解码原理，我们 来看看具体的处理过程：编码器(Compressor)编码数据，第一步，初始化一个编译表，假设这个编译表的大小是12 位的，也就是最 多有4096个单位，另外假设我们有32个不同的字符(也可以认为图象的每个像素最多有32 种颜色)，表示为a，b，c，d，e.，初始化编译表：第0项为a,第1项为b,第2项为c. 一直到第 31 项，我们把这 32 项就称为根。开始编译，先定义一个前缀对象Current Prefix，记为.c.,现在它是空的，然后 定义一个当前字符串CurrentString,标记为.c.k, .c.就为Current Prefix，k就为当前读取字符。现在来读取数

4、据流的第一个字符，假如为p,那么Current String就等 于.c.p (由于.c.为空，实际上值就等于p),现在在编译表中查找有没有Current String的值，由于p就是一个根字符，我们已经初始了 32个根索引，当然可以找到，把p 设为 Current Prefix 的值，不做任何事继续读取下一个字符，假设为 q， Current String 就等于.c.q (也就是pq),看看在编译表中有没有该值，当然。没有，这时我们要做下 面的事情：将CurrentString的值(也就是pq)添加到编译表的第32项，把Current Prefix的值(也就是p)在编译表中的索引输出到编码

5、流，修改Current Prefix为当前读取的字符(也就是q)。继续往下读，如果在编译表中可以查找到CurrentString的值(.c.k),则把Current String的值(.c.k)赋予Current Prefix；如果查找不到，则添加CurrentString的值(.c.k)到编译表，把Current Prefix的值(.c.)在编译表中所对应的索引 输出到编码流，同时修改Current Prefix为k，这样一直循环下去直到数据流结束。伪代码看起来就像下面这样：编码器伪代码Initialize String Table;.c. = Empty;.c.k = First Char

6、acter in CharStream;while (.c.k != EOF )if ( .c.k is in the StringTable).c. = .c.k;elseadd .c.k to the StringTable;OutputtheIndex of.c. in the StringTableto the CodeStream;.c.= k;.c.k=NextCharacterin CharStream;Output theIndexof .c.in the StringTable to theCodeStream;来看一个具体的例子，我们有一个字母表a, b, c, d.有一个

7、输入的字符流abacaba。现在来初始化编译表：#0=a,#l=b,#2=c,#3=d.现在开始读取第一个字符a，.c.a=a， 可以在在编译表中找到，修改.c.=a;不做任何事继续读取第二个字符b，.c.b=ab, 在编译表中不能找，那么添加.c.b到编译表：#4=ab，同时输出.c.（也就是a）的 索引#0到编码流，修改.c.=b；读下一个字符a，.c.a=ba，在编译表中不能找到： 添加编译表#5=ba，输出.c.的索引#1到编码流，修改.c.=a；读下一个字符c， .c.c=ac，在编译表中不能找到：添加编译表#6=ac，输出.c.的索引#0到编码流， 修改.c.=c；读下一个字符a，

8、.c.c=ca，在编译表中不能找到：添加编译表#7=ca， 输出.c.的索引#2到编码流，修改.c.=a；读下一个字符b，.c.b=ab,编译表的 #4=ab，修改.c.=ab；读取最后一个字符a, .c.a=aba，在编译表中不能找到： 添加编译表#8=aba，输出.c.的索引#4到编码流，修改.c.=a；好了，现在没有数 据了，输出.c.的值a的索引#0到编码流，这样最后的输出结果就是：#0#1#0#2#4#0.解码器（Decompressor）好了，现在来看看解码数据。数据的解码，其实就是数据编码的逆向过程，要从 已经编译的数据（编码流）中找出编译表，然后对照编译表还原图象的光栅数据。首

9、先，还是要初始化编译表。GIF文件的图象数据的第一个字节存储的就是LZW编 码的编码大小（一般等于图象的位数），根据编码大小，初始化编译表的根条目（从 0到2的编码大小次方），然后定义一个当前编码Current Code,记作code，定义一 个Old Code,记作old。读取第一个编码到code，这是一个根编码，在编译表中可 以找到，把该编码所对应的字符输出到数据流，old=code；读取下一个编码到code，这就有两种情况：在编译表中有或没有该编码，我们先来看第一种情况：先 输出当前编码code所对应的字符串到数据流，然后把old所对应的字符（串）当成 前缀prefix .，当前编码co

10、de所对应的字符串的第一个字符当成k,组合起来当前字符串CurrentString就为.k,把.k添加到编译表，修改old=code,读下一个编码；我们来看看在编译表中找不到该编码的情况，回想一下编码情况：如 果数据流中有一个p.p.pq这样的字符串，p.在编译表中而p.p不在， 编译器将输出p.的索引而添加p.p到编译表，下一个字符串p.p就可以在 编译表中找到了，而p.pq不在编译表中，同样将输出p.p的索引值而添加 p.pq 到编译表，这样看来，解码器总比编码器慢一步，当我们遇到 p.p 所 对应的索引时，我们不知到该索引对应的字符串（在解码器的编译表中还没有该索引， 事实上，这个索引将

11、在下一步添加），这时需要用猜测法：现在假设上面的 p.所 对应的索引值是#58，那么上面的字符串经过编译之后是#58#59，我们在解码器中读 到#59 时，编译表的最大索引只有#58， #59 所对应的字符串就等于#58所对应的字符串 （也就是p.）加上这个字符串的第一个字符（也就是p），也就是p.p。事实上， 这种猜测法是很准确（有点不好理解，仔细想一想吧）。上面的解码过程用伪代码表 示就像下面这样：解码器伪代码Initialize String Table;code = First Code in the CodeStream;Output the String for code to t

12、he CharStream;old = code;code = Next Code in the CodeStream;while （code != EOF ）if （ code is in the StringTable）Output theStri ngfor code to the CharStream; /输出code所对应的字符串.=tra nslation for old; /old 所对应的字符串k = first character of tra nslation for code; / code所对应的字符串的 第一个字符add.k to the StringTable;ol

13、d = code;else.= translation for old;k = first character of .;Output.k to CharStream;add.k to the StringTable;old = code;code = Next Code in the CodeStream;词典编码词典编码主要利用数据本身包含许多重复的字符串的特性.例如:吃葡萄不吐葡萄皮, 不吃葡萄倒吐葡萄皮. 我们如果用一些简单的代号代替这些字符串,就可以实现压缩,实际上 就是利用了信源符号之间的相关性.字符串与代号的对应表就是词典 . 实用的词典编码算法 的核心就是如何动态地形成词典,以

14、及如何选择输出格式以减小冗余 . 第一类词典编码第一 类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过 ,然后用已 经出现过的字符串替代重复的部分 ,它的输出仅仅是指向早期出现过的字符串的 指针 . LZ77 算法 LZ77 算法在某种意义上又可以称为滑动窗口压缩 ,该算法将一个虚拟的,可以 跟随压缩进程滑动的窗口作为词典,要压缩的字符串如果在该窗口中出现,则输出其出现位置 和长度.使用固定大小窗口进行词语匹配 ,而不是在所有已经编码的信息中匹配 ,是因为匹配 算法的时间消耗往往很多,必须限制词典的大小才能保证算法的效率;随着压缩的进程滑动词 典窗口,使其中总包含最近编码

15、过的信息 ,是因为对大多数信息而言,要编码的字符串往往在 最近的上下文中更容易找到匹配串. LZ77 编码的基本流程 1,从当前压缩位置开始,考察未编 码的数据,并试图在滑动窗口中找出最长的匹配字符串 ,如果找到,则进行步骤 2,否则进行步 骤 3. 2,输出三元符号组 ( off, len, c ). 其中 off 为窗口中匹配字符串相对窗口边界的偏 移,len为可匹配的长度,c为下一个字符，即不匹配的第一个字符.然后将窗口向后滑动len + 1 个字符,继续步骤 1. 3,输出三元符号组 ( 0, 0, c ).其中 c 为下一个字符.然后将窗口向后 滑动1个字符，继续步骤1. LZ77算

16、法LZ77编码举例C AB A B B C B A A 5, 3, A ABC 7 5 2, 1, B B 5 4 0, 0, C - 4 3 1, 1, B A 2 2 0, 0, A - 1 1 输出匹配串位置步骤 LZSS 算法 LZ77 通 过输出真实字符解决了在窗口中出现没有匹配串的问题,但这个解决方案包含有冗余信息.冗 余信息表现在两个方面,一是空指针,二是编码器可能输出额外的字符 ,这种字符是指可能包 含在下一个匹配串中的字符. LZSS 算法的思想是如果匹配串的长度比指针本身的长度长就 输出指针(匹配串长度大于等于MIN_LENGTH),否则就输出真实字符.另外要输出额外的标

17、志位区分是指针还是字符. LZSS 编码的基本流程 1,从当前压缩位置开始,考察未编码的字符, 并试图在滑动窗口中找出最长的匹配字符串,如果匹配串长度 len 大于等于最小匹配串长度 (len = MIN_LENGTH),则进行步骤2,否则进行步骤3. 2,输出指针二元组(off, len).其中 off 为窗口中匹配字符串相对窗口边界的偏移 ,len 为匹配串的长度 ,然后将窗口向后滑动 len个字符,继续步骤1. 3,输出当前字符c,然后将窗口向后滑动1个字符,继续步骤1. LZSS 编码举例 C B A AB B C B B A A 字符 11 10 9 8 7 6 5 4 3 2 1

18、位置 C C 11 8 (7,3) AAB 8 7 (3,2) BB 6 6 C - 5 5 B B 4 4 B - 3 3 A A 2 2 A - 1 1 输出匹配串位置步骤输入数据 流：编码过程MIN_LEN =2 LZSS算法在相同的计算机环境下,LZSS算法比LZ77可获得比 较高的压缩比,而译码同样简单.这也就是为什么这种算法成为开发新算法的基础 ,许多后来 开发的文档压缩程序都使用了 LZSS的思想例如,PKZip, GZip, ARJ, LHArc和ZOO等等，其 差别仅仅是指针的长短和窗口的大小等有所不同 . LZSS 同样可以和熵编码联合使用 ,例如 ARJ就与霍夫曼编码联用

19、，而PKZip则与Shannon-Fano联用,它的后续版本也采用霍夫曼编码. 第二类词典编码第二类算法的想法是企图从输入的数据中创建一个短语词典 (dictionary of the phrases),这种短语可以是任意字符的组合.编码数据过程中当遇到已经在词典中出现的” 短语时，编码器就输出这个词典中的短语的索引号，而不是短语本身 LZ78算法LZ78的编 码思想是不断地从字符流中提取新的字符串(String),通俗地理解为新词条，然后用代号也 就是码字(Code word)表示这个词条这样一来，对字符流的编码就变成了用码字(Code word) 去替换字符流(Char stream)，生

20、成码字流(Code stream),从而达到压缩数据的目的.LZ78编码 器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的字符串(String) 用字符C进行扩展生成新的字符串(String)，然后添加到词典中 LZ78编码算法步骤1:将词典 和当前前缀P都初始化为空.步骤2:当前字符。:=字符流中的下一个字符.步骤3:判断P+C 是否在词典中如果是，则用C扩展P,即让P:=P+C,返回到步骤2.如果否，则输出与当 前前缀P相对应的码字W和当前字符C,即(WQ;将P+C添加到词典中；令P:=空值，并返 回到步骤2 LZ78编码举例 A B A C B C B B A

21、字符9 8 7 6 5 4 3 2 1位置(2, A) BA 8 5 (3, A) BCA 5 4 (2, C) BC 3 3 (0, B) B 2 2 (0, A) A 1 1 输出词典位置步骤输入数据流: 编码过程: LZW算法J.Ziv和A.Lempel在1978年首次发表了介绍第二类词典编码算法的文章.在他们 的研究基础上,Terry A.Welch在1984年发表了改进这种编码算法的文章，因此把这种编码方 法称为LZW(Lempel-Ziv Walch)压缩编码.在编码原理上,LZW与LZ78相比有如下差别： LZW只输出代表词典中的字符串(String)的码字(code word)

22、.这就意味在开始时词典不能是空 的,它必须包含可能在字符流出现中的所有单个字符 .即在编码匹配时,至少可以在词典中找 到长度为1的匹配串 LZW编码是围绕称为词典的转换表来完成的 LZW算法的词典LZW 编码器(软件编码器或硬件编码器)就是通过管理这个词典完成输入与输出之间的转换.LZW 编码器的输入是字符流(Char stream),字符流可以是用8位ASCII字符组成的字符串,而输出 是用n位(例如12位)表示的码字流(Code stream),码字代表单个字符或多个字符组成的字符 串(String). LZW编码算法步骤1:将词典初始化为包含所有可能的单字符，当前前缀P初始化 为空.步骤

23、2:当前字符。:=字符流中的下一个字符.步骤3:判断P+C是否在词典中(1)如果 是，则用C扩展P,即让P:=P+C，返回到步骤2. (2)如果否，则输出与当前前缀P相对应的码字 W;将P+C添加到词典中；令P:=C，并返回到步骤2 LZW编码举例C A B A B A B B A字符 9 8 7 6 5 4 3 2 1 位置 2 BB 5 2 2 2 BA6 3 3 4 ABA 7 4 4 7 ABAC 8 6 5 4 3 2 1 码字 1 AB 1 1 C B A输出词典位置步骤输入数据流：编码过程：LZW算法LZW算法得到普遍采用，它的 速度比使用LZ77算法的速度快，因为它不需要执行那

24、么多的缀-符串比较操作对LZW算法 进一步的改进是增加可变的码字长度 ,以及在词典中删除老的缀-符串.在 GIF 图像格式和 UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法.LZW算法取得了专利，专利 权的所有者是美国的一个大型计算机公司一Unisys(优利系统公司)，除了商业软件生产公司 之外,可以免费使用LZW算法.预测编码预测编码是数据压缩理论的一个重要分支它根据 离散信号之间存在一定相关性的特点，利用前面的一个或多个信号对下一个信号进行预测，然 后对实际值和预测值的差(预测误差)进行编码.如果预测比较准确，那么误差信号就会很小，就 可以用较少的码位进行编码，以达到数据压缩的

25、目的.第n个符号Xn的熵满足：所以参与预 测的符号越多，预测就越准确，该信源的不确定性就越小，数码率就可以降低.lzw压缩算法的c语言实现1 程序由五个模块组成。(1) lzw.h 定义了一些基本的数据结构，常量，还有变量的初始化等。#ifndef _LZW_H_#define _LZW_H_/ #include #include #include #include /#define LZW_BASE 0x102/ The code base#define CODE_LEN 12 / Max code length#define TABLE_LEN4099 / It must be prime

26、 number and bigger than 2ACODE_LEN=4096./ Such as 5051 is also ok.#define BUFFERSIZE 1024/typedef structHANDLE h_sour; / Source file handle.HANDLE h_dest; / Destination file handle.HANDLE h_suffix; / Suffix table handle.HANDLE h_prefix; / Prefix table handle.HANDLE h_code; / Code table handle.LPWORD

27、 lp_prefix; / Prefix table head pointer.LPBYTE lp_suffix; / Suffix table head pointer.LPWORD lp_code; / Code table head pointer.WORDcode;WORD prefix;BYTEsuffix;BYTE cur_code_len; / Current code length. used in Dynamic-Code-Length mode LZW_DATA,*PLZW_DATA;typedef structWORD top;WORD index;LPBYTE lp_b

28、uffer; HANDLE h_buffer;BYTE by_left;DWORD dw_buffer;BOOL end_flag;BUFFER_DATA,*PBUFFER_DATA;typedef struct/Stack used in decodeWORD index;HANDLE h_stack;LPBYTE lp_stack;STACK_DATA,*PSTACK_DATA;/VOID stack_create( PSTACK_DATA stack ) stack-h_stack = GlobalAlloc( GHND , TABLE_LEN*sizeof(BYTE) ); stack

29、-lp_stack = GlobalLock( stack-h_stack );stack-index = 0; /VOID stack_destory( PSTACK_DATA stack )GlobalUnlock( stack-h_stack );GlobalFree ( stack-h_stack );/VOID buffer_create( PBUFFER_DATA buffer ) buffer-h_buffer = GlobalAlloc( GHND, BUFFERSIZE*sizeof(BYTE) ); buffer-lp_buffer = GlobalLock( buffer

30、-h_buffer );buffer-top = 0;buffer-index = 0;buffer-by_left = 0;buffer-dw_buffer = 0; buffer-end_flag = FALSE;/VOID buffer_destory( PBUFFER_DATA buffer )GlobalUnlock( buffer-h_buffer );GlobalFree ( buffer-h_buffer );/VOID re_init_lzw( PLZW_DATA lzw ) /When code table reached its top it should /be rei

31、nitialized.memset( lzw-lp_code, 0xFFFF, TABLE_LEN*sizeof(WORD) ); lzw-code = LZW_BASE;lzw-cur_code_len = 9;/VOID lzw_create(PLZW_DATA lzw, HANDLE h_sour, HANDLE h_dest)WORD i;lzw-h_code= GlobalAlloc( GHND, TABLE_LEN*sizeof(WORD) );lzw-h_prefix lzw-h_suffix= GlobalAlloc( GHND, TABLE_LEN*sizeof(WORD)

32、); = GlobalAlloc( GHND, TABLE_LEN*sizeof(BYTE) );lzw-lp_code lzw-lp_prefix lzw-lp_suffix= GlobalLock( lzw-h_code );= GlobalLock( lzw-h_prefix );= GlobalLock( lzw-h_suffix );lzw-code = LZW_BASE; lzw-cur_code_len = 9;lzw-h_sour= h_sour;lzw-h_dest= h_dest;memset( lzw-lp_code, 0xFFFF, TABLE_LEN*sizeof(W

33、ORD) );/VOID lzw_destory(PLZW_DATA lzw)GlobalUnlock( lzw-h_code );GlobalUnlock( lzw-h_prefix );GlobalUnlock( lzw-h_suffix );GlobalFree( lzw-h_code );GlobalFree( lzw-h_prefix );GlobalFree( lzw-h_suffix ); /#endif (2) fileio.h 定义了一些文件操作#ifndef _FILEIO_H_#define _FILEIO_H_/#include #include #include /H

34、ANDLE file_handle(CHAR* file_name) HANDLE h_file;h_file = CreateFile(file_name,GENERIC_READ|GENERIC_WRITE, FILE_SHARE_READ|FILE_SHARE_WRITE,NULL,OPEN_ALWAYS,0,NULL);return h_file;/WORD load_buffer(HANDLE h_sour, PBUFFER_DATA buffer) / Load file to buffer DWORD ret;ReadFile(h_sour,buffer-lp_buffer,BU

35、FFERSIZE,&ret,NULL);buffer-index = 0;buffer-top = (WORD)ret;return (WORD)ret;/WORD empty_buffer( PLZW_DATA lzw, PBUFFER_DATA buffer)/ Output buffer to file DWORD ret;if(buffer-end_flag) / The flag mark the end of decode if( buffer-by_left )buffer-lp_buffer buffer-index+ = (BYTE)( buffer-dw_buffer 32

36、-buffer-by_left )by_left);WriteFile(lzw-h_dest, buffer-lp_buffer,buffer-index,&ret,NULL);buffer-index = 0;buffer-top = ret;return (WORD)ret;/#endif (3) hash.h 定义了压缩时所用的码表操作函数，为了快速查找使用了 hash 算法，还有处理 hash 冲突的函数 #ifndef _HASH_H_#define _HASH_H_/#include #include #include /#define DIV TABLE_LEN#define H

37、ASHSTEP 13/ It should bigger than 0./WORD get_hash_index( PLZW_DATA lzw )DWORD tmp;WORD result;DWORD prefix;DWORD suffix;prefix = lzw-prefix;suffix = lzw-suffix;tmp = prefixlp_code hash = 0xFFFF )result = FALSE;elseif( lzw-lp_prefix hash = lzw-prefix & lzw-lp_suffix hash = lzw-suffix )result = TRUE;

38、elseresult = FALSE;while( lzw-lp_code hash != 0xFFFF )if( lzw-lp_prefix hash = lzw-prefix & lzw-lp_suffix hash = lzw-suffix )result = TRUE; break;hash = re_hash_index( hash );return result;/WORD get_code( PLZW_DATA lzw )WORD hash;WORD code;hash = get_hash_index( lzw );if( lzw-lp_prefix hash = lzw-pr

39、efix & lzw-lp_suffix hash = lzw-suffix )code = lzw-lp_code hash ;elsewhile( lzw-lp_prefix hash != lzw-prefix | lzw-lp_suffix hash != lzw-suffix )hash = re_hash_index( hash );code = lzw-lp_code hash ;return code;/VOID insert_table( PLZW_DATA lzw )WORD hash;hash = get_hash_index( lzw );if( lzw-lp_code

40、 hash = 0xFFFF )lzw-lp_prefix hash = lzw-prefix;lzw-lp_suffix hash = lzw-suffix; lzw-lp_code hash = lzw-code;elsewhile( lzw-lp_code hash != 0xFFFF )hash = re_hash_index( hash );lzw-lp_prefix hash = lzw-prefix;lzw-lp_suffix hash = lzw-suffix; lzw-lp_code hash = lzw-code;/#endif(4) encode.h 压缩程序主函数#if

41、ndef _ENCODE_H_#define _ENCODE_H_/#include #include #include /VOID output_code( DWORD code ,PBUFFER_DATA out, PLZW_DATA lzw) out-dw_buffer |= code by_left - lzw-cur_code_len ); out-by_left += lzw-cur_code_len;while( out-by_left = 8 ) if( out-index = BUFFERSIZE ) empty_buffer( lzw,out);out-lp_buffer

42、out-index+ = (BYTE)( out-dw_buffer 24 ); out-dw_buffer by_left -= 8;/VOID do_encode( PBUFFER_DATA in, PBUFFER_DATA out, PLZW_DATA lzw) WORD prefix;while( in-index != in-top )if( !in_table(lzw) )/ current code not in code table/ then add it to table and output prefixinsert_table(lzw);prefix = lzw-suf

43、fix;output_code( lzw-prefix ,out ,lzw );lzw-code+;if( lzw-code = (WORD)1cur_code_len )/ code reached current code top(1cur_code_len+;if( lzw-cur_code_len = CODE_LEN + 1 )re_init_lzw( lzw );else/ current code already in code table/ then output nothing prefix = get_code(lzw);lzw-prefix = prefix;lzw-su

44、ffix = in-lp_buffer in-index+ ;/VOID encode(HANDLE h_sour,HANDLE h_dest)LZW_DATA lzw;BUFFER_DATA in ;BUFFER_DATA out;BOOL first_run = TRUE;lzw_create( &lzw ,h_sour,h_dest );buffer_create( &in );buffer_create( &out );while( load_buffer( h_sour, &in ) )if( first_run )/ File length should be considered

45、 but here we simply/ believe file length bigger than 2 bytes.lzw.prefix = in.lp_buffer in.index+ ;lzw.suffix = in.lp_buffer in.index+ ; first_run = FALSE;do_encode(&in , &out, &lzw);output_code(lzw.prefix, &out , &lzw);output_code(lzw.suffix, &out , &lzw);out.end_flag = TRUE;empty_buffer( &lzw,&out)

46、;lzw_destory( &lzw );buffer_destory( &in );buffer_destory( &out );/ #endif(5) decode.h 解压函数主函数#ifndef _DECODE_H_#define _DECODE_H_/#include #include #include /VOID out_code( WORD code ,PBUFFER_DATA buffer,PLZW_DATA lzw,PSTACK_DATA stack) WORD tmp;if( code lp_stack stack-index+ = code;elsestack-lp_st

47、ack stack-index+ = lzw-lp_suffix code ;tmp = lzw-lp_prefix code ;while( tmp 0x100 )stack-lp_stack stack-index+ = lzw-lp_suffix tmp ;tmp = lzw-lp_prefix tmp ;stack-lp_stack stack-index+ = (BYTE)tmp;while( stack-index )if( buffer-index = BUFFERSIZE )empty_buffer(lzw,buffer);buffer-lp_buffer buffer-ind

48、ex+ = stack-lp_stack -stack-index ;/VOID insert_2_table(PLZW_DATA lzw )lzw-lp_code lzw-code = lzw-code; lzw-lp_prefix lzw-code = lzw-prefix; lzw-lp_suffix lzw-code = lzw-suffix; lzw-code+;if( lzw-code = (WORD)1cur_code_len)-1 )lzw-cur_code_len+;if( lzw-cur_code_len = CODE_LEN+1 ) lzw-cur_code_len =

49、9;if(lzw-code = 1by_left cur_code_len )if( buffer-index = BUFFERSIZE )load_buffer( lzw-h_sour, buffer );next = buffer-lp_buffer buffer-index+ ;buffer-dw_buffer |= (DWORD)next by_left); buffer-by_left += 8;code = buffer-dw_buffer ( 32 - lzw-cur_code_len ); buffer-dw_buffer cur_code_len; buffer-by_lef

50、t -= lzw-cur_code_len;return code; /VOID do_decode( PBUFFER_DATA in, PBUFFER_DATA out, PLZW_DATA lzw, PSTACK_DATA stack) WORD code;WORD tmp;while( in-index != in-top ) code = get_next_code( in ,lzw );if( code suffix = (BYTE)code;elseif( code code )/ code also in table/ then output code chaintmp = lz

51、w-lp_prefix code ;while( tmp 0x100 )tmp = lzw-lp_prefix tmp ;lzw-suffix = (BYTE)tmp;else/ code = lzw-code/ code not in table/ add code into table/ and out put codetmp = lzw-prefix;while( tmp 0x100 )tmp = lzw-lp_prefix tmp ;lzw-suffix = (BYTE)tmp;insert_2_table( lzw ); out_code(code,out,lzw,stack);lz

52、w-prefix = code;/VOID decode( HANDLE h_sour, HANDLE h_dest )LZW_DATA lzw;BUFFER_DATA in ;BUFFER_DATA out;STACK_DATA stack;BOOL first_run;first_run = TRUE;lzw_create( &lzw ,h_sour,h_dest ); buffer_create( &in );buffer_create( &out ); stack_create(&stack );while( load_buffer( h_sour, &in ) )if( first_

53、run )lzw.prefix = get_next_code( &in, &lzw ); lzw.suffix = lzw.prefix;out_code(lzw.prefix, &out, &lzw , &stack); first_run = FALSE; do_decode(&in , &out, &lzw, &stack);empty_buffer( &lzw,&out);lzw_destory( &lzw );buffer_destory( &in );buffer_destory( &out ); stack_destory( &stack);#endif2 下面给出一个应用上面

54、模块的简单例子#include #include /#include lzw.h#include hash.h#include fileio.h#include encode.h#include decode.h/HANDLE h_file_sour;HANDLE h_file_dest;HANDLE h_file;CHAR* file_name_in = d:code.c;CHAR* file_name_out= d:encode.e;CHAR* file_name = d:decode.d;/int main(int argc, char *argv)h_file_sour = file_

55、handle(file_name_in);h_file_dest = file_handle(file_name_out);h_file = file_handle(file_name);encode(h_file_sour, h_file_dest);/ decode(h_file_dest,h_file);CloseHandle(h_file_sour);CloseHandle(h_file_dest);CloseHandle(h_file);return 0;3 后语之前研究gif文件格式时偶然接触了 lzw压缩算法，于是就想自己动手实现。从一开始看人家的原码，然 后跟着模仿，到现在用自己的语言表达出来，从理解原理到代码的实现花费了不少时间与精力，但是真正 的快乐也就在这里，现在把她拿出来跟大家分享也就是分享快乐。