【实验三】LZW编码

一、实验原理

关于LZW编码可参考：链接: https://www.cnblogs.com/mcomco/p/10475329.html
.

二、实验过程

lzw_E.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){
 int i;
 
 for( i=0; i<256; i++){
  dictionary[i].suffix = i;
  dictionary[i].parent = -1;
  dictionary[i].firstchild = -1;
  dictionary[i].nextsibling = i+1;
 }
  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;
 sibling = dictionary[string_code].firstchild;
 while( -1<sibling){
  if( character == dictionary[sibling].suffix) return sibling;
  sibling = dictionary[sibling].nextsibling;
 }
 return -1;
}

void AddToDictionary( int character, int string_code){
 int firstsibling, nextsibling;
 if( 0>string_code) return;
 dictionary[next_code].suffix = character;
 dictionary[next_code].parent = string_code;
 dictionary[next_code].nextsibling = -1;
 dictionary[next_code].firstchild = -1;
 firstsibling = dictionary[string_code].firstchild;
 if( -1<firstsibling){ // the parent has child
  nextsibling = firstsibling;
  while( -1<dictionary[nextsibling].nextsibling ) 
   nextsibling = dictionary[nextsibling].nextsibling;
  dictionary[nextsibling].nextsibling = next_code;
 }else{// no child before, modify it to be the first
  dictionary[string_code].firstchild = next_code;
 }
 next_code ++;
}

void LZWEncode( FILE *fp, BITFILE *bf){
 int character;
 int string_code;
 int index;
 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))){
  index = InDictionary( character, string_code);
  if( 0<=index){ // string+character in dictionary
   string_code = index;
  }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);
   }
   string_code = character;
  }
 }
 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;
phrase_length = DecodeString( 1, last_code);
}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{ // 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;
 }
}
#if 0
int main( int argc, char **argv){
 BITFILE *bfi, *bfo;
 int bit;
 int count = 0;

 if( 1<argc){
  if( NULL==OpenBitFileInput( bfi, argv[1])){
   fprintf( stderr, "fail open the file\n");
   return -1;
  }
   }else{
  if( NULL==OpenBitFileInput( bfi, NULL)){
   fprintf( stderr, "fail open stdin\n");
   return -2;
  }
 }
  if( 2<argc){
  if( NULL==OpenBitFileOutput( bfo, argv[2])){
   fprintf( stderr, "fail open file for output\n");
   return -3;
  }
 }else{
  if( NULL==OpenBitFileOutput( bfo, NULL)){
   fprintf( stderr, "fail open stdout\n");
   return -4;
  }
 }  
  while( 1){
  bit = BitInput( bfi);
  fprintf( stderr, "%d", bit);
  count ++;
  if( 0==(count&7))fprintf( stderr, " ");
  BitOutput( bfo, bit);
 }
 return 0;
}
#endif

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__

三、实验结果

文件类型	原始大小	压缩后大小	压缩比
.txt	4866KB	3686KB	75.8%
.jpg	82522KB	116248KB	140.9%
.docx	92353KB	132836KB	143.8%
.pdf	285384KB	278528KB	97.6%
.mobi	10013775KB	16339578KB	163.2%
.mp3	6599716KB	7996690KB	121.2%
.mp4	6091785KB	7462482KB	120.0%
.wav	30044KB	40814KB	135.8%
.bmp	6220854KB	7294792KB	117.3%
.yuv	39321600KB	38272610KB	97.3%