LZW编码分析

大家好，欢迎来到IT知识分享网。

LZW特点：
1）LZW编码有效利用了字符出现频率计算冗余度进行压缩，字典自适应生成。
2）数据流中有多次重复出现的字符时，LZW编码具有很好的压缩效果。
3）LZW码在压缩时不保存字典信息，在解码时自动生成，因此节省了很多空间。

LZW编码原理：

通俗来讲就是在编码时将当前的逻辑符号与上一个已经编码过的逻辑符号组合成一个新的逻辑符号将其编为一个新的码字编入词典中，当下一次这两个逻辑符号的组合再次出现时即可直接用之前词典中已经编码过的码字来表示，而直接从词典中查找到有对应码字的逻辑符号，又会作为一个整体与下一个逻辑符号组成新的组合再生成一个新码字……以此类推。因此在遇到文件中信息关联性较高时，LZW码的编码效果会非常好。

LZW解码原理：

因为在编码后对应逻辑符号与码字的词典并不存储，因此在解码时需要实时生成码表。因为编码时是按照有一定规律编码的，因此在生成时也比较容易，也就是根据压缩后的码字和刚刚生成的逻辑符号来一边生成词典，然后再从词典中找对应逻辑符号解码。而这也会出现一种尴尬的情况：

这个情况就是在解码时突然出现了一个码字，该码字的大小大于我一边解码一边生成的词典中最大的那个码字。这种情况的出现是因为编码的进度总是比解码进度快一步，因此在解码时会滞后一步，一般来说都是没有什么影响的，恰恰是在编码时刚刚生成了一个码字便立刻使用了这个码字的情况下，在解码时的滞后一步会解不出这个码字对应的逻辑符号，不过也好解决，这种情况就只需要将上一个解出的逻辑符号再加上该符号序列的第一个符号输出就可以了。

代码实现（老师给的示例代码，带理解注释）：
LZW.C：

/* * Definition for LZW coding * * vim: ts=4 sw=4 cindent nowrap */
#include <stdlib.h>
#include <stdio.h>
#include "bitio.h"
#define MAX_CODE 65535
struct { 
   
 int suffix;
 int parent, firstchild, nextsibling;
} dictionary[MAX_CODE+1];
int next_code;
int d_stack[MAX_CODE]; // stack for decoding a phrase
#define input(f) ((int)BitsInput( f, 16))
#define output(f, x) BitsOutput( f, (unsigned long)(x), 16
int DecodeString( int start, int code);
void InitDictionary( void);
void PrintDictionary( void){ 
   
 int n;
 int count;
 for( n=256; n<next_code; n++){ 
   
  count = DecodeString( 0, n);
  printf( "%4d->", n);
  while( 0<count--) printf("%c", (char)(d_stack[count]));
  printf( "\n");
 }
}
int DecodeString( int start, int code){ 
   
 int count;
 count = start;
 while( 0<=code){ 
   
  d_stack[ count] = dictionary[code].suffix;
  code = dictionary[code].parent;
  count ++;
 }
 return count;
}
void InitDictionary( void){ 
    //初始化词典，将256以内的ASCII码初始化到表中
 int i;
 for( i=0; i<256; i++){ 
   
  dictionary[i].suffix = i;//码字的ASCII码
  dictionary[i].parent = -1;//因为是256以内所以没有parent
  dictionary[i].firstchild = -1;//因为是256以内所以没有firstchild
  dictionary[i].nextsibling = i+1;//nextsibling即是下一个ASCII码
 }
 dictionary[255].nextsibling = -1;
 next_code = 256;
}
/* * Input: string represented by string_code in dictionary, * Output: the index of character+string in the dictionary * index = -1 if not found */
int InDictionary( int character, int string_code){ 
   
 int sibling;
 if( 0>string_code) return character;//第一个逻辑符号的情况，没有P
 sibling = dictionary[string_code].firstchild;
 while( -1<sibling){ 
   
  if( character == dictionary[sibling].suffix) return sibling;//如果找到了表中有PC则返回PC
  sibling = dictionary[sibling].nextsibling;//一个一个找
 }
 return -1;//表中没有PC返回-1
}
void AddToDictionary( int character, int string_code){ 
   
 int firstsibling, nextsibling;
 if( 0>string_code) return;
 dictionary[next_code].suffix = character;//C
 dictionary[next_code].parent = string_code;//P
 dictionary[next_code].nextsibling = -1;//新加入还没nextsibling
 dictionary[next_code].firstchild = -1;//新加入还没有firstchild
 firstsibling = dictionary[string_code].firstchild;//找到P的第一个child
 if( -1<firstsibling){ 
    // the parent has child
  nextsibling = firstsibling;
  while( -1<dictionary[nextsibling].nextsibling )
   nextsibling = dictionary[nextsibling].nextsibling;//顺着从第一个child一个一个找兄弟
  dictionary[nextsibling].nextsibling = next_code;//找到最后一个，将nextcode放到最后一位
 }else{ 
   // no child before, modify it to be the first
  dictionary[string_code].firstchild = next_code;//若没找到firstchild，nextcode就是firstchild
 }
 next_code ++;
}
void LZWEncode( FILE *fp, BITFILE *bf){ 
   
 int character;//C
 int string_code;//P
 int index;//PC
 unsigned long file_length;
 fseek( fp, 0, SEEK_END);
 file_length = ftell( fp);//文件长度
 fseek( fp, 0, SEEK_SET);
 BitsOutput( bf, file_length, 4*8);
 InitDictionary();
 string_code = -1;
 while( EOF!=(character=fgetc( fp))){ 
   //判断PC是否在字典中
  index = InDictionary( character, string_code);
  if( 0<=index){ 
    // string+character in dictionary
   string_code = index;//P = PC
  }else{ 
    // string+character not in dictionary
   output( bf, string_code);
   if( MAX_CODE > next_code){ 
    // free space in dictionary
    // add string+character to dictionary
    AddToDictionary( character, string_code);//将PC添加到字典中
   }
   string_code = character;//设置P = C
  }
 }
 output( bf, string_code);
}
void LZWDecode( BITFILE *bf, FILE *fp){ 
   
 int character;
 int new_code, last_code;
 int phrase_length;
 unsigned long file_length;
 file_length = BitsInput( bf, 4*8);
 if( -1 == file_length) file_length = 0;
 InitDictionary();//初始化词典
 last_code = -1;
 while( 0<file_length){ 
   
  new_code = input( bf);
  if( new_code >= next_code){ 
    // this is the case CSCSC( not in dict)
   d_stack[0] = character;//将前一个逻辑符号赋给d_stack[0]
   phrase_length = DecodeString( 1, last_code);//返回Pw长度+1
  }else{ 
   
   phrase_length = DecodeString( 0, new_code);//返回当前长度
  }
  character = d_stack[phrase_length-1];
  while( 0<phrase_length){ 
   
   phrase_length --;
   fputc( d_stack[ phrase_length], fp);
   file_length--;
  }
  if( MAX_CODE>next_code){ 
    // add the new phrase to dictionary
   AddToDictionary( character, last_code);
  }
  last_code = new_code;
 }
}
int main( int argc, char **argv){ 
   
 FILE *fp;
 BITFILE *bf;
 if( 4>argc){ 
   
  fprintf( stdout, "usage: \n%s <o> <ifile> <ofile>\n", argv[0]);
  fprintf( stdout, "\t<o>: E or D reffers encode or decode\n");
  fprintf( stdout, "\t<ifile>: input file name\n");
  fprintf( stdout, "\t<ofile>: output file name\n");
  return -1;
 }
 if( 'E' == argv[1][0]){ 
    // do encoding
  fp = fopen( argv[2], "rb");
  bf = OpenBitFileOutput( argv[3]);
  if( NULL!=fp && NULL!=bf){ 
   
   LZWEncode( fp, bf);
   fclose( fp);
   CloseBitFileOutput( bf);
   fprintf( stdout, "encoding done\n");
  }
 }else if( 'D' == argv[1][0]){ 
    // do decoding
  bf = OpenBitFileInput( argv[2]);
  fp = fopen( argv[3], "wb");
  if( NULL!=fp && NULL!=bf){ 
   
   LZWDecode( bf, fp);
   fclose( fp);
   CloseBitFileInput( bf);
   fprintf( stdout, "decoding done\n");
  }
 }else{ 
    // otherwise
  fprintf( stderr, "not supported operation\n");
 }
 return 0;
}

bitio.c:

/* * Definitions for bitwise IO * * vim: ts=4 sw=4 cindent */
#include <stdlib.h>
#include <stdio.h>
#include "bitio.h"
BITFILE *OpenBitFileInput( char *filename){ 
   
 BITFILE *bf;
 bf = (BITFILE *)malloc( sizeof(BITFILE));
 if( NULL == bf) return NULL;
 if( NULL == filename) bf->fp = stdin;
 else bf->fp = fopen( filename, "rb");
 if( NULL == bf->fp) return NULL;
 bf->mask = 0x80;
 bf->rack = 0;
 return bf;
}
BITFILE *OpenBitFileOutput( char *filename){ 
   
 BITFILE *bf;
 bf = (BITFILE *)malloc( sizeof(BITFILE));
 if( NULL == bf) return NULL;
 if( NULL == filename) bf->fp = stdout;
 else bf->fp = fopen( filename, "wb");
 if( NULL == bf->fp) return NULL;
 bf->mask = 0x80;
 bf->rack = 0;
 return bf;
}
void CloseBitFileInput( BITFILE *bf){ 
   
 fclose( bf->fp);
 free( bf);
}
void CloseBitFileOutput( BITFILE *bf){ 
   
 // Output the remaining bits
 if( 0x80 != bf->mask) fputc( bf->rack, bf->fp);
 fclose( bf->fp);
 free( bf);
}
int BitInput( BITFILE *bf){ 
   
 int value;
 if( 0x80 == bf->mask){ 
   
  bf->rack = fgetc( bf->fp);
  if( EOF == bf->rack){ 
   
   fprintf(stderr, "Read after the end of file reached\n");
   exit( -1);
  }
 }
 value = bf->mask & bf->rack;
 bf->mask >>= 1;
 if( 0==bf->mask) bf->mask = 0x80;
 return( (0==value)?0:1);
}
unsigned long BitsInput( BITFILE *bf, int count){ 
   
 unsigned long mask;
 unsigned long value;
 mask = 1L << (count-1);
 value = 0L;
 while( 0!=mask){ 
   
  if( 1 == BitInput( bf))
   value |= mask;
  mask >>= 1;
 }
 return value;
}
void BitOutput( BITFILE *bf, int bit){ 
   
 if( 0 != bit) bf->rack |= bf->mask;
 bf->mask >>= 1;
 if( 0 == bf->mask){ 
    // eight bits in rack
  fputc( bf->rack, bf->fp);
  bf->rack = 0;
  bf->mask = 0x80;
 }
}
void BitsOutput( BITFILE *bf, unsigned long code, int count){ 
   
 unsigned long mask;
 mask = 1L << (count-1);
 while( 0 != mask){ 
   
  BitOutput( bf, (int)(0==(code&mask)?0:1));
  mask >>= 1;
 }
}

bitio.h:

/* * Declaration for bitwise IO * * vim: ts=4 sw=4 cindent */
#ifndef __BITIO__
#define __BITIO__
#include <stdio.h>
typedef struct{ 
   
 FILE *fp;
 unsigned char mask;
 int rack;
}BITFILE;
BITFILE *OpenBitFileInput( char *filename);
BITFILE *OpenBitFileOutput( char *filename);
void CloseBitFileInput( BITFILE *bf);
void CloseBitFileOutput( BITFILE *bf);
int BitInput( BITFILE *bf);
unsigned long BitsInput( BITFILE *bf, int count);
void BitOutput( BITFILE *bf, int bit);
void BitsOutput( BITFILE *bf, unsigned long code, int count);
#endif // __BITIO__

测试：
我采用了十种不同格式的文件压缩，很遗憾的是大多数的文件压缩后反而大小变大了，我认为原因可能是因为这些格式文件中相关性较低，因此在生成码字后会不断的生成新的码字组合却用不到这些新的码字，而对于bmp等图片文件，压缩效果还是不错的：

解码后也都可以恢复成原文件。