LZW压缩和解压 优选内容

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 = FALSE ；/#define FALSE 0string_tabi.prev = NO_PREV；/#define NO_PREV 0xFFFF表示没有前缀 string_tabi.c= 0;for(i = 0 ; i 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 , %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 , curstr0 ); -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 , sizeof(char), oupindex,outputfd );total += oupindex;printf(nsucessful size = %dn, total);return 0; 在解码的过程中要注意以下两点：1假设码表的每一行在压缩或解码后都有内容，我们来看看码表，我们发现，码表的每一行都是链表的一个结点，结点的前缀就是指向其他行（结点）的指针，若该指针的值为NO_PREV表明该结点是某链表的最后一个结点，因此从任何一行开始都是一个链表，整个码表有4096个链表。每个链表开始结点的行号，就是要被解压的代码，将这个链表中的后缀字符依次排列，得到一个字符串，这个字符串就是要被解压的代码的解码值。2.在开始解码时，码表从258行开始的以后各行都是空的，那么这些空的部分的值在解码的过程中是怎样被填写的呢？首先读入要解码的第一个代码到前缀变量prevcode中，接着对以后的每一个代码依次做以下工作就可以填写码表：（1）读入代码，并将其解码；（2）把解码所得的字符串的第一个字符和prevcode的值填入码表的第一个空白行；（3）将该代码值赋给prevcode，形成新的prevcode值，好进行下一轮的循环。 四、以上代码中用到的函数，供参考#define BUF_SIZE 0x10000#define EMPTY 0xFFFFFFFF#define UEOF 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.hUINT currentpos = INIT_SIZE ;extern ENTRY string_tabTAB_SIZE;BYTE 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= 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(code = NO_PREV) return c; for(i = code +1 ; i 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 != 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);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 = EMPTY)writec(fp , code & 0x0FF);tempcode = (code 4) & 0x0F0);elseu = tempcode | (code & 0x0F);writec(fp ,u & 0x0FF);u = (code 4) & 0x0FF;writec(fp , u);tempcode = EMPTY;UINT getcode(FILE *fp) register UINT code; if(tempcode = EMPTY) code = readc(fp); tempcode = readc(fp); if(tempcode =UEOF | code = UEOF) return UEOF; code = code | (tempcode 4 ) & 0x0F00); return code; else code = readc(