数据压缩实验报告3 LZW编解码

写在前面：本次实验由老师写好了LZW编码的代码，先理解了已有代码之后，自己再写解码代码时比较容易。下面给出完整的代码以及实验结果

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;//每写完8位，将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__

bitio.cpp（全部由老师给出）

/*
 * Definitions for bitwise IO
 *
 * vim: ts=4 sw=4 cindent
 */
#define _CRT_SECURE_NO_WARNINGS
#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

lzw_E.cpp（解码部分由自己编写，其他部分由老师给出，自己写了一部分注释）

/*
 * Definition for LZW coding 
 *
 * vim: ts=4 sw=4 cindent nowrap
 */
#define _CRT_SECURE_NO_WARNINGS
#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;//根的后缀字符为对应ASCII码
		dictionary[i].parent = -1;//前缀字符长度为0（没有前缀）
		dictionary[i].firstchild = -1;//没有第一个孩子
		dictionary[i].nextsibling = i+1;//下一个兄弟根节点下标为下一个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;
	sibling = dictionary[string_code].firstchild;//以string_code的第一个孩子为兄弟
	while( -1<sibling){
		if( character == dictionary[sibling].suffix) return sibling; //如果找到一个兄弟的后缀是character，则返回(string_code，character)的编码
		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{
		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);//将输入文件的大小写入输出文件中，file_lengt为32位数字
	InitDictionary();//初始化字典，设置根节点
	string_code = -1;//初始化前缀
	while( EOF!=(character=fgetc( fp))){//扫描输入文件
		index = InDictionary( character, string_code);
		//判断(string_code，character)是否在字典中，如果在则返回对应编码，否则返回-1
		if( 0<=index){	// (string_code，character)在字典中
			string_code = index; //将(string_code，character)对应的编码作为前缀
		}else{	//(string_code，character)不在字典中
			output( bf, string_code);//输出前缀
			if( MAX_CODE > next_code){	//字典空间充足时将(string_code，character)添加到字典中
				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 (file_length > 0)
	{
		new_code = input(bf);
		if (new_code >= next_code)
		{
			d_stack[0] = character;
			phrase_length = DecodeString(1, last_code);
		}
		else
			phrase_length = DecodeString(0, new_code);
		character = d_stack[phrase_length - 1];
		while (phrase_length > 0)
		{
			phrase_length--;
			fputc(d_stack[phrase_length], fp);
			file_length--;
		}
		if (MAX_CODE > next_code)
			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;
}

测试代码：先写一个a.dat，将abbababac写入其中。经过LZW编码后生成b.dat，解码后生成c.dat，可见编码再解码后的文件与原文件一致。

选择10种不同格式的文件进行LZW编码并比较压缩效率：

除了bdf（Quartus II原理图文件）和vwf（Quartus II仿真波形文件）之外，其他文件在进行LZW编码后大小反而增加了。