LZW编解码算法

算法分析

LZW算法是通过建立一个字符串表，用较短的代码来表示较长的字符串来实现压缩。LZW算法的核心就是算法词典的建立，通过词典实现对重复字符串的压缩。

算法实现

编码算法实现步骤

根据课件

步骤1：将词典初始化为包含所有可能的单字符，当前前缀P初始化为空。

步骤2：当前字符C=字符流中的下一个字符。

步骤3：判断P＋C是否在词典中

（1）如果“是”，则用C扩展P，即让P=P＋C，返回到步骤2。

（2）如果“否”，则

输出与当前前缀P相对应的码字W；

将P＋C添加到词典中；

令P=C，并返回到步骤2

简而言之就是，第一次出现的进入词典，第二次出现的就可以用词典里的编码代替字符了。

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);
}

           

解码算法实现步骤

根据课件

步骤1：在开始译码时词典包含所有可能的前缀根。

步骤2：令CW：=码字流中的第一个码字。

步骤3：输出当前缀-符串string.CW到码字流。

步骤4：先前码字PW：=当前码字CW。

步骤5：当前码字CW：=码字流的下一个码字。

步骤6：判断当前缀-符串string.CW 是否在词典中。

（1）如果”是”，则把当前缀-符串string.CW输出到字符流。当前前缀P：=先前缀-符串string.PW。当前字符C：=当前前缀-符串string.CW的第一个字符。把缀-符串P+C添加到词典。

（2）如果”否”，则当前前缀P：=先前缀-符串string.PW。当前字符C：=当前缀-符串string.CW的第一个字符。输出缀-符串P+C到字符流,然后把它添加到词典中。

步骤7：判断码字流中是否还有码字要译。

（1）如果”是”，就返回步骤4。

（2）如果”否”，结束。

简而言之就是边解码，边扩充字典。

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;
	}
}

           

调制

实验结果

分析可知，如果字符串重复的内容少，则会出现越压缩越大，而相同字符组合出现多次的文件，该编码的压缩效果明显。