LZW压缩和解压

1、LZW压缩和解压黄陂一中盘龙校区 张兴才LZW压缩是由Lemple、Zip和Welch共同创造，用他们的名字命名的压缩方法。下面结合C语言的实现方法，介绍LZW压缩和解压的原理。 一、码表 被压缩的字符系列称为数据流，压缩后的代码称为编码流，将数据流压缩成编码流要依据码表。什么是码表？我们先看看码表的结构和初始化吧。typedef structchar used ;UINT prev; /typedef UINT unsigned intBYTE c;ENTRY;void InitTable()int i;for(i = 0 ; i < 4096;i+)string_tabi.used

2、= FALSE ；/#define FALSE 0string_tabi.prev = NO_PREV；/#define NO_PREV 0xFFFF表示没有前缀 string_tabi.c= 0;for(i = 0 ; i< 258; i+)string_tabi.used = TRUE; /#define TRUE !FALSEstring_tabi.c = i;从上面的代码可知，码表共有4096行，每行有3列。used表示该行是否被使用，使用了其值为TRUE，否则为FALSE。prev表示前缀，主要存储的是该码表的索引值（行号），用以指示该表的不同行，取值范围是04095。c表示后

3、缀，存储一个字符。该码表的0257行的prev域被初始化，其中的值表示的意义是：0255用来表示单个字符，256表示开始新的码表，257表示压缩结束。二、压缩过程以下程序段将infp中的字符系列压缩到outfp中。putcode(outfp, CC);/outfp是存储编码流的文件，CC的值为256，表示开始新的码表，outfp是存放编码流的文件，以上函数表示将码表开始代码放在outfp文件的开始位置 InitTable();c = readc(infp);/从输入文件读取一个字符，infp表示输入文件，c是后缀变量prevcode = QueryTable(NO_PREV , c);/在码表

4、中查询前缀为“NO_PREV”，后缀为“c”（即刚刚读入的字符）的行，并将行号赋给前缀变量prevcode，其实相当于prevcode=c；+total;while(UEOF != (c = readc(infp)/UEOF为文件结束标志+total;if(NOT_FIND!=(localcode = QueryTable(prevcode , c)/ NOT_FIND表示在码表中查询指定的前缀和后缀对，没有找到prevcode = localcode;/找到指定的前缀后缀对后，将找到行的行号赋给前缀变量，接着从输入文件读入下一个字符作为后缀，进行下一轮的查询continue;putcode(

5、outfp , prevcode);/ 指定的前缀和后缀对没有找到,则将前缀变量prevcode的值输出到存储编码流的输出文件outfp中if(count)/count为码表中空白行的行数 UpdateTable(prevcode, c);/将指定的前缀和后缀分别填入码表的第一个空白行的相应位置 -count;/码表的空白行减1if(count = 0)/如果码表没有空白行了，则重新建一个码表，并在编码流中放入代码CC（256），表示开始新的码表。count = 4096 - 258;currentpos = 258;InitTable();putcode(outfp, CC);/CC表示开始

6、新的码表prevcode = QueryTable(NO_PREV , c);/其实是将c的值赋给prevcodeputcode(outfp , prevcode);putcode(outfp , CEND);/CEND是编码压缩结束标志if(tempcode!=EMPTY)outputbufoupindex+ = (tempcode &0x0F0); /关键！flushout(outfp);/将输出缓存区剩余的编码写入文件中return 0;LZW压缩算法流程是是是否初始化码表读入数据流中第一个字符到前缀变量prevcode中读入一个字符到后缀变量c中文件结束吗？在码表中查找指定的前

7、缀后缀对找到吗？将前缀变量的值写入编码流中码表空否？将前缀变量和后缀变量的值写入码表的第一个空白行重新初始化码表，并将CC的值放入编码流中将后缀变量的值赋给前缀变量把最后一个字符即prevcode变量中的字符写入编码流中结束开始否否将找到行的行号赋给前缀变量 三、.解压过程 这是LZW解码的主要代码：prevcode = 0; while(prevcode = getcode(inputfd)!=CC)if(prevcode = UEOF)return 0; InitTable();prevcode = getcode(inputfd);count = GetChars(prevcode ,

8、curstr , TAB_SIZE);/#define TAB_SIZE 4096memcpy(outbuf , curstr , count);oupindex += count;total = 0;while(UEOF != (local = getcode(inputfd)if(local = CC)space = TAB_SIZE - INIT_SIZE;/#define INIT_SIZE 258currentpos = INIT_SIZE;InitTable();prevcode = getcode(inputfd);count = GetChars(prevcode , curs

9、tr , TAB_SIZE);if(oupindex + count > TAB_SIZE)printf(".");fwrite(outbuf , sizeof(char), oupindex, outputfd);total += oupindex;oupindex = 0;memcpy(&outbufoupindex , curstr , count );oupindex += count;continue;if(local > currentpos)printf("nerror, local > currentpos: %d , %

10、d" ,local, currentpos);fwrite(outbuf , sizeof(char), oupindex, outputfd);return -1; if(string_tablocal.used) count = GetChars(local , curstr , TAB_SIZE); elsecount = GetChars(prevcode , curstr , TAB_SIZE);curstrcount = curstr0;curstr+count = '0'if(space) temp = UpdateTable(prevcode , cu

11、rstr0 ); -space;else if(space = 0)printf("space=0");prevcode = local;if(oupindex + count > TAB_SIZE)printf(".");fwrite(outbuf , sizeof(char), oupindex, outputfd); total += oupindex;oupindex = 0;memcpy(&outbufoupindex , curstr , count );oupindex += count;fwrite(outbuf , siz

12、eof(char), oupindex,outputfd );total += oupindex;printf("nsucessful size = %dn", total);return 0; 在解码的过程中要注意以下两点：1假设码表的每一行在压缩或解码后都有内容，我们来看看码表，我们发现，码表的每一行都是链表的一个结点，结点的前缀就是指向其他行（结点）的指针，若该指针的值为NO_PREV表明该结点是某链表的最后一个结点，因此从任何一行开始都是一个链表，整个码表有4096个链表。每个链表开始结点的行号，就是要被解压的代码，将这个链表中的后缀字符依次排列，得到一个字符串，这

13、个字符串就是要被解压的代码的解码值。2.在开始解码时，码表从258行开始的以后各行都是空的，那么这些空的部分的值在解码的过程中是怎样被填写的呢？首先读入要解码的第一个代码到前缀变量prevcode中，接着对以后的每一个代码依次做以下工作就可以填写码表：（1）读入代码，并将其解码；（2）把解码所得的字符串的第一个字符和prevcode的值填入码表的第一个空白行；（3）将该代码值赋给prevcode，形成新的prevcode值，好进行下一轮的循环。 四、以上代码中用到的函数，供参考#define BUF_SIZE 0x10000#define EMPTY 0xFFFFFFFF#define UEO

14、F 0xFFFF#define NOT_FIND 0xFFFFvoid InitTable();UINT UpdateTable(UINT prevcode , BYTE c);UINT QueryTable(UINT code , BYTE c);UINT readc(FILE *fp);void putcode(FILE *fp, UINT code);void flushout(FILE *fp);#include "commfunc.h"UINT currentpos = INIT_SIZE ;extern ENTRY string_tabTAB_SIZE;BYTE

15、 inputbufBUF_SIZE;int inpindex = EMPTY, limit;BYTE outputbufBUF_SIZE;int oupindex = 0 ,tempcode = EMPTY;void InitTable()int i;for(i = 0 ; i < TAB_SIZE ;i+)string_tabi.used = FALSE ,string_tabi.prev = NO_PREV, string_tabi.c= 0;for(i = 0 ; i< INIT_SIZE ; i+)string_tabi.used = TRUE;string_tabi.c

16、= i;UINT UpdateTable(UINT prevcode , BYTE c) if(currentpos >= TAB_SIZE | prevcode >= TAB_SIZE -1)return NOT_FIND;string_tabcurrentpos.used = TRUE;string_tabcurrentpos.prev = prevcode;string_tabcurrentpos.c = c;return currentpos+;UINT QueryTable(UINT code , BYTE c)register ENTRY *u;UINT i;if(co

17、de = NO_PREV) return c; for(i = code +1 ; i < currentpos ; i+) u = &string_tabi; if(u->used && u->prev=code &&u->c = c)return i;return NOT_FIND;UINT GetChars(UINT code , char *buffer , UINT size)UINT i =0;if(!string_tabcode.used)return 0; while(string_tabcode.prev !=

18、NO_PREV)buffersize-1-i+ = string_tabcode.c;code =string_tabcode.prev;buffersize-1-i+ = string_tabcode.c;memmove(buffer , &buffersize - i , i);bufferi = '0'return i;UINT readc(FILE *fp)static int count= 0;if(inpindex = EMPTY)putchar('.'); count+;if(count%80=0)printf("n")

19、;if(limit =fread(inputbuf , sizeof(char) ,BUF_SIZE , fp)=0)return UEOF;inpindex = 0;return inputbufinpindex+;elseif(inpindex = limit) inpindex = EMPTY;return readc(fp);return inputbufinpindex+;void writec(FILE *fp , BYTE c)if(oupindex >= BUF_SIZE)fwrite(outputbuf ,sizeof(char), BUF_SIZE , fp);oupindex = 0;outputbufoupindex+ = c;void putcode(FILE *fp, UINT code)UINT u;/if(oupindex = 255)/printf("error1");if(tempcode = EMP