lzw压缩算法的c语言实现

1、标准的LZW压缩原理： 先来解释一下几个基本概念： LZW压缩有三个重要的对象：数据流(CharStream)、编码流(CodeStream)和编译 表(String Table)。在编码时，数据流是输入对象（图象的光栅数据序列），编码流 就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据 流是输出对象；而编译表是在编码和解码时都须要用借助的对象。 字符(Character)：最基础的数据元素，在文本文件中就是一个字节，在光栅数据中就 是一个像素的颜色在指定的颜色列表中的索引值； 字符串(String)：由几个连续的字符组成； 前缀(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.，现在它是空的，然后 定义一个当前字符串Current String，标记为.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），看看在编译表中有没有该值，当然。没有，这时我们要做下 面的事情：将Current String的值（也就是pq）添加到编译表的第32项，把Current Prefix 的值（也就是p）在编译表中的索引输出到编码

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

6、First Character in CharStream; while (.c.k != EOF ) if ( .c.k is in the StringTable) .c. = .c.k; else add .c.k to the StringTable; Output the Index of .c. in the StringTable to the CodeStream; .c. = k; .c.k = Next Character in CharStream; Output the Index of .c. in the StringTable to the CodeStream;

7、 来看一个具体的例子,我们有一个字母表a，b，c，d.有一个输入的字符流abacaba。 现在来初始化编译表：#0=a,#1=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，输

8、出.c.的索引#0到编码流， 修改.c.=c；读下一个字符a，.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所对应的字符串到数据流，然

10、后把old所对应的字符（串）当成 前缀prefix .，当前编码code所对应的字符串的第一个字符当成k，组合起来当 前字符串Current String就为.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 CodeStrea

12、m; Output the String for code to the CharStream; old = code; code = Next Code in the CodeStream; while (code != EOF ) if ( code is in the StringTable) Output the String for code to the CharStream; / 输出code所对应的字符串 . = translation for old; / old所对应的字符串 k = first character of translation for code; / co

13、de所对应的字符串的第一个字符 add .k to the StringTable; old = 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 为下

16、一个字符.然后将窗口向后滑动 1 个字符,继续步骤 1. LZ77算法 LZ77编码举例 C A B 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

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

18、 A 字符 11 10 9 8 7 6 5 4 3 2 1 位置 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同样可以

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

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

21、到步骤2 LZ78编码举例 A B A C B C B B A 字符 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相比有如下差别: LZ

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

23、将词典初始化为包含所有可能的单字符,当前前缀P初始化为空. 步骤2:当前字符C:=字符流中的下一个字符. 步骤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 BA 6 3 3 4 ABA 7 4 4 7 ABAC 8 6 5 4 3 2 1 码字 1 AB 1 1 C B A 输出词典位置步骤输入数据流: 编码过程: LZW算法

24、 LZW算法得到普遍采用,它的速度比使用LZ77算法的速度快,因为它不需要执行那么多的缀-符串比较操作.对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_BASE0x102/The code base#define CODE_LEN12/Max code length#define TABL

26、E_LEN4099 / It must be prime number and bigger than 2CODE_LEN=4096. / Such as 5051 is also ok.#define BUFFERSIZE1024/-typedef structHANDLEh_sour;/ Source file handle.HANDLEh_dest;/ Destination file handle.HANDLEh_suffix; / Suffix table handle.HANDLEh_prefix; / Prefix table handle.HANDLEh_code;/ Code

27、 table handle.LPWORDlp_prefix; / Prefix table head pointer.LPBYTElp_suffix; / Suffix table head pointer.LPWORDlp_code; / Code table head pointer.WORDcode;WORDprefix;BYTEsuffix;BYTEcur_code_len; / Current code length. used in Dynamic-Code-Length mode LZW_DATA,*PLZW_DATA;typedef structWORDtop;WORDinde

28、x;LPBYTElp_buffer;HANDLEh_buffer;BYTEby_left;DWORDdw_buffer;BOOLend_flag;BUFFER_DATA,*PBUFFER_DATA;typedef struct/Stack used in decodeWORDindex;HANDLEh_stack;LPBYTElp_stack;STACK_DATA,*PSTACK_DATA;/-VOID stack_create( PSTACK_DATA stack )stack-h_stack= GlobalAlloc( GHND , TABLE_LEN*sizeof(BYTE) );sta

29、ck-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_DATAbuffer )buffer-h_buffer= GlobalAlloc(GHND,BUFFERSIZE*sizeof(BYTE);buffer-lp_buffer= GlobalLock( buffer-h_buff

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

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

32、, TABLE_LEN*sizeof(BYTE) );lzw-lp_code= GlobalLock( lzw-h_code);lzw-lp_prefix= GlobalLock( lzw-h_prefix );lzw-lp_suffix= 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(WORD) );/-VOID lzw_destory(PL

33、ZW_DATAlzw)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 /-HANDLEfile_handle(CHAR* file_na

34、me)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 bufferDWORD ret;ReadFile(h_sour,buffer-lp_buffer,BUFFERSIZE,&ret,NULL);buffer-index =

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

36、(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 /-#defineDIVTABLE_LEN#defineHASHSTEP13/ It should bigger than 0./-WORD

37、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;elseresult = FALSE;while( lzw-lp_code hash

38、!= 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-prefix &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_h