LZW压缩和解压.docVIP

LZW压缩和解压 黄陂一中盘龙校区 张兴才 LZW压缩是由Lemple、Zip和Welch共同创造，用他们的名字命名的压缩方法。下面结合C语言的实现方法，介绍LZW压缩和解压的原理。 一、码表 被压缩的字符系列称为数据流，压缩后的代码称为编码流，将数据流压缩成编码流要依据码表。什么是码表？我们先看看码表的结构和初始化吧。 typedef struct { char used ; UINT prev; //typedef UINT unsigned int BYTE c; }ENTRY; void InitTable() { int i; for(i = 0 ; i 4096;i++) ｛ string_tab[i].used = FALSE ；//#define FALSE 0 string_tab[i].prev = NO_PREV；//#define NO_PREV 0xFFFF表示没有前缀 string_tab[i].c= 0; for(i = 0 ; i 258; i++) { string_tab[i].used = TRUE; //#define TRUE !FALSE string_tab[i].c = i; } } 从上面的代码可知，码表共有4096行，每行有3列。used表示该行是否被使用，使用了其值为TRUE，否则为FALSE。prev表示前缀，主要存储的是该码表的索引值（行号），用以指示该表的不同行，取值范围是0——4095。c表示后缀，存储一个字符。该码表的0——257行的prev域被初始化，其中的值表示的意义是：0—255用来表示单个字符，256表示开始新的码表，257表示压缩结束。 二、压缩过程 以下程序段将infp中的字符系列压缩到outfp中。 putcode(outfp, CC); //outfp是存储编码流的文件，CC的值为256，表示开始新的码表，outfp是存放编码流的文件，以上函数表示将码表开始代码放在outfp文件的开始位置 InitTable(); c = readc(infp); //从输入文件读取一个字符，infp表示输入文件，c是后缀变量 prevcode = QueryTable(NO_PREV , c); //在码表中查询前缀为“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(outfp , prevcode); // 指定的前缀和后缀对没有找到,则将前缀变量prevcode的值输出到存储编码流的输出文件outfp中 if(count)//count为码表中空白行的行数 { UpdateTable(prevcode, c); //将指定的前缀和后缀分别填入码表的第一个空白行的相应位置 --count;//码表的空白行减1 } if(count == 0)//如果码表没有空白行了，则重新建一个码表，并在编码流中放入代码CC（256），表示开始新的码表。 { count = 4096 - 258; currentpos = 258; InitTable(); putcode(outfp, CC);//CC表示开始新的码表 } prevcode = QueryTable(NO_PREV , c);//其实是将c的值赋给prevcode } putcode(outfp , prevcode); putcode(outfp , CEND);//CEND是编码压缩结束标志 if(tempcode!=EMPTY) outputbuf[oupindex++] = (tempcode 0x0F0); //关键！！！！ flushout(outfp);//将输出缓存区剩余的编码写入文件中 return 0; } LZ