|
目录
一、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
流程图 
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）如果”否”，结束。
流程图
二、代码注释
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编码方式才会显著的压缩文件。**否则反而会适得其反。
|