LZW编解码算法实现

本文主要是介绍LZW编解码算法实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、LZW编码

1.编码原理

2.算法实现

3.结果分析

二、LZW解码

1.解码原理

2.算法实现

3.结果分析

三、不同文件格式的编码比较 

---

一、LZW编码

1.编码原理

LZW的编码思想是不断地从字符流中提取新的字符串，通俗地理解为新“词条”，然后用“代号”也就是码字表示这个“词条”。这样一来，对字符流的编码就变成了用码字去替换字符流，生成码字流，从而达到压缩数据的目的。 LZW 编码是围绕称为词典的转换表来完成的。 LZW 编码器通过管理这个词典完成输入与输出之间的转换。 LZW 编码器的输入是字符流，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位（例如12位）表示的码字流。

LZW编码算法的步骤如下：

步骤1：将词典初始化为包含所有可能的单字符，当前前缀P初始化为空。
步骤2：当前字符C=字符流中的下一个字符。
步骤3：判断P+C是否在词典中：
如果是，则用C扩展P，即让P=P+C，返回到步骤2。
如果否，则输出与当前前缀P相对应的码字W；将P+C添加到词典中；令P=C，并返回到步骤2

2.算法实现

（1）初始化词典

// 初始化字典 
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;
}

（2）查找词典

 // 查找词典 
int InDictionary( int character, int string_code){int sibling;// 单个字符返回C if( 0>string_code) return character;// sinling是前缀的第一个子节点sibling = dictionary[string_code].firstchild;while( -1<sibling){  //没有找到 // 如果输入字符C是P的子节点的前缀，返回子节点的值if( character == dictionary[sibling].suffix) return sibling;// 否则指向子节点的兄弟节点，继续判断C是否是P的子节点sibling = dictionary[sibling].nextsibling;}return -1;
}

（3）更新词典

// 更新词典 
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){	//存在子结点 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 ++;
}

（4）LZW编码算法

// LZW编码 
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);  // 输出文件长度32位 InitDictionary();  // 初始化词典 string_code = -1;while( EOF!=(character=fgetc( fp))){  // 指针移动，获取下一个字符，直至文件结束 index = InDictionary( character, string_code);  // 查找词典，判断P+C是否在字典中 if( 0<=index){ // 如果P+C在词典中，返回P+C string_code = index;  }else{	// 如果P+C不在词典中，输出P对应码字 output( bf, string_code);if( MAX_CODE > next_code){// 更新词典 AddToDictionary( character, string_code);}// 另P=C，继续移动指针 string_code = character;}}output( bf, string_code);
}

3.结果分析

使用txt文本文件进行编码调试，在Dev C++运行选项的参数中输入：

 txt文本文件如下：

编码后呈现的二进制文件如下，可以在右侧看到原文本内容：

 

---

二、LZW解码

1.解码原理

LZW解码算法开始时，译码词典和编码词典相同，包含所有可能的前缀根。具体解码算法如下：
步骤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）如果”否”，结束。

2.算法实现

（1）解码字符流

//  解码字符流，不断向上查找父母结点判断该码字对应字符串有几个字符 
int DecodeString( int start, int code){int count;count = start;while (0 <= code) {  // 上一个字符串不为空 d_stack[count] = dictionary[code].suffix;  // code后缀 code = dictionary[code].parent;  // 首字母给code count++;}return count;
}

（2）LZW解码

利用词典编码结构，不断向上查找母节点，判断该码字对应字符串有几个字符。同时将解码后的字符存入缓冲区，缓冲区内存放后面要用的前缀。

如果在解码中，码字>词典中的最后一个码字，就以为着该码字在词典中不存在。此时P=PW，把上一个字符串首位保存在character中（即将C存入缓冲区，C=CW），输出P+C并添加到词典。

// LZW解码 
void LZWDecode( BITFILE *bf, FILE *fp){int character=0;  // 字符C 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);   //读入16位即第一个字符串if (new_code >= next_code) {//判断C是否在词典中，初始化后next_code=256d_stack[0] = character;  //不在词典中则把C存入d_stack[0]phrase_length = DecodeString(1, last_code);  //decodestring计算字符串长度，通过往上寻找母节点，同时解码}else {//如果字符串在词典中则直接用new_code计算phrase_length = DecodeString(0, new_code);}character = d_stack[phrase_length - 1];  //把第一个字符给Cwhile (0 < phrase_length) {phrase_length--;fputc(d_stack[phrase_length], fp);file_length--;  //倒序输出，同时控制整个循环要读的编码数减少}if (MAX_CODE > next_code) {//把新词条写进词典AddToDictionary(character, last_code);}last_code = new_code;  //P=C}
}

3.结果分析

将在LZW编码输出的二进制文件进行解码，输出文件text_out_decode.txt：

---

 三、不同文件格式的编码比较 

文件格式	输入文件大小	输出二进制文件大小	压缩比
txt	5KB	4KB	80%
png	16KB	25KB	156.25%
bmp	193KB	217KB	112.435%
pptx	1870KB	1417KB	75.77%
xlsx	19KB	28KB	147.37%
pdf	42KB	64KB	152.38%
mp3	2050KB	2544KB	124.10%
wav	6963KB	8095KB	116.26%
mp4	34986KB	42538KB	121.58%
avi	1026KB	1242KB	121.05%

通过表格发现，LZW编码可以对文本文件txt、Powerpoint文件pptx起到压缩作用。LZW词典编码对重复度高的文件压缩率较高，txt和ppt由大量中文字符组成，重复度没那么高压缩率就低。而其他更多复杂的格式，本身压缩程度很高的文件如视音频文件格式，LZW压缩效果并不好。

遇到的一些问题：

• 该实验需将文件放入工程中实现
• 在Dev C++运行选项的参数中输入参数：E/D、输入文件名、输出文件名

参考博客：

​​​​​​LZW编码—图像压缩_糖糖糖-豆的博客-CSDN博客_lzw编码

LZW词典编码与解码_pzp49666的博客-CSDN博客_lzw编码与解码

这篇关于LZW编解码算法实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---