【数据压缩实验】LZW编解码算法实现与分析

目录

一.实验概述

1.算法描述

二.实验目的

三.实验原理

四.实验步骤

LZW压缩算法是一种无损数据压缩算法。在众多的压缩技术中，LZW算法是一种通用的、性能优良并得到广泛应用的压缩算法，它是一种完全可靠的算法，与其他算法相比，往往具有更高的压缩效率。LZW算法保留了LZ码的自适应功能，压缩比也大致相同，其显著特点是逻辑简单（典型的LZW算法处理1个字符不超过三个时钟周期）、硬件实现廉价、运算速度快，在消息长度为一万字符数量级时可以得到令人满意的压缩效果。
 

掌握词典编码的基本原理，用C/C++/Python等语言编程实现LZW解码器并分析编解码算法

核心思想：

词典初始化为包含所有的单字符，当前前缀串P为空。

输入数据流中的下一个字符C，

判断P+C是否在词典中

（1）存在

         将P+C作为新的前缀串赋给P

（2）不存在

         输出P对应的码字CW，将P+C录入词典，再将C作为新的前缀串赋给P

（1）读入码字流中的的第一个码字，赋给CW

（2）并将Dictionary[CW]赋给将要输出的字符流（解码）

（3）将CW赋给PW作为前缀串，同时CW接受码字流中的下一个新码字

（4）将Dictionary[PW]赋给P，将Dictionary[CW]赋给C

（5）判断P+C是否存在于词典中，如果不存在（且词典有足够的空间），就将P+C作为新词条写入

（6）将CW赋给PW作为新的前缀串，重复以上步骤
 

1.bitio.h

#ifndef __BITIO__
#define __BITIO__

#include 

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__

2.bitio.c

#include 
#include 
#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 reachedn");
			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

3.lzw.c

#include 
#include 
#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", n);
		while( 0string_code) return character;
	sibling = dictionary[string_code].firstchild;
	while( -1string_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 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;//pw=-1,作为字符串中的旧字符
	while (0 < file_length)
	{
		new_code = input(bf);//读入一个新的字符，即cw
		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   n", argv[0]);
		fprintf( stdout, "t: E or D reffers encode or decoden");
		fprintf( stdout, "t: input file namen");
		fprintf( stdout, "t: output file namen");
		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 donen");
		}
	}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 donen");
		}
	}else{	// otherwise
		fprintf( stderr, "not supported operationn");
	}
	return 0;
}

1.首先调试LZW的编码程序，以一个文本文件作为输入，得到输出的LZW编码文件。

编写一个文本文件：

2.以实验步骤一得到的编码文件作为输入，编写LZW的解码程序。在写解码程序时需要对关键语句加上注释，并说明进行何操作。在实验报告中重点说明当前码字在词典中不存在时应如何处理并解释原因

发现与原始文本文件一致，成功解码。当前码字在字典中不存在问题
原因：编码时，上一个新的词条刚被创建，下一个词组就需要使用它。即解码端的解码会比编码端晚一步。我们还没有得到最新的词条就需要使用它。
解决方法：下一个词条的尾缀是当前词条的第一个字符，所以就先输出这个字符，然后用前一词条的代号进行解码

3.选择多种不同格式类型的文件，使用LZW编码器进行压缩得到输出的压缩比特流文件。对各种不同格式的文件进行压缩效率的分析