目录
一、LZW原理1.LZW简介2.LZW编码算法步骤3.LZW解码算法步骤
二、代码注释三、实例应用
一、LZW原理
1.LZW简介
LZW的编码思想是不断地从字符流中提取新的字符串,通俗地理解为新“词条”,然后用“代号”也就是码字表示这个“词条”。这样一来,对字符流的编码就变成了用码字去替换字符流,生成码字流,从而达到压缩数据的目的。LZW编码是围绕称为词典的转换表来完成的。LZW编码器通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流,字符流可以是用8位ASCII字符组成的字符串,而输出是用n位(例如12位)表示的码字流。
2.LZW编码算法步骤
步骤1:将词典初始化为包含所有可能的单字符,当前前缀P初始化为空。 步骤2:当前字符C=字符流中的下一个字符。 步骤3:判断P+C是否在词典中 (1)如果“是”,则用C扩展P,即让P=P+C,返回到步骤2。 (2)如果“否”,则 输出与当前前缀P相对应的码字W; 将P+C添加到词典中; 令P=C,并返回到步骤2
流程图 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210418163839131.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NwcEtpbGxNZQ==,size_16,color_FFFFFF,t_70)
3.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)如果”否”,结束。
流程图
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210418164301275.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NwcEtpbGxNZQ==,size_16,color_FFFFFF,t_70)
二、代码注释
void PrintDictionary( void){
int n;
int count;
for( n=256; n
int count;
count = start;
while( 0
int i;
for( i=0; i
int sibling;
if( 0>string_code) return character; //编码为-1
sibling = dictionary[string_code].firstchild;
while( -1
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// 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 // 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 // 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 // add the new phrase to dictionary
AddToDictionary(character, last_code);
}
last_code = new_code;
}
}
三、实例应用
文件预览文件格式压缩前大小压缩后大小 txt1KB1KB txt110KB41KB jpg10,984KB15,378KB cr226,553KB36,276KB mov5,169KB6,351KB pdf242KB312KB png9KB16KB bmp3KB2KB yuv4,320KB785KB m4a50KB66KB
分析: 在以上十个文件中,只有长txt,bmp和yuv文件压缩后变小了。经分析,**当原文件有大量重复信息时,LZW编码方式才会显著的压缩文件。**否则反而会适得其反。
|