LZW编码简介
? ? ? ?LZW压缩算法的基本概念: LZW压缩有三个重要的对象:数据流(CharStream)、编码流(CodeStream) 和编译表(String Table)。 在编码时，数据流是输入对象(例如，一个字符串)，编码流就是输出对象(经过压缩运算的编码数据);在解码时，编码流则是输入对象，数据流是输出对象;而编译表是在编码和解码时都须要用借助的对象。
LZW编码过程
? ? ? ?LZW编码的过程就是构造一一个词 典的过程，首先将基本的根字符(Root) 存入字典，并为根字符分别按顺序赋予相应的编码值(一个编码为一个8位无符号整数)。在编码的过程中，将码流中常出现的字符串存入词典中，并为其赋予编码值。当码流中出现了词典中记录的字符串时，直接用词典中该字符串的编码来表示该字符串以实现信息压缩的功能。
参数介绍
①字符(Character): 最基础的数据元素，本赛题中只有A,B,C三种字符。
②字符串(String): 由几个连续的字符组成，本赛题中由前缀+当前字符构成。
③前缀(Prefix): 是一一个字符或字符串，不过通常用在另-一个字符的前面，而且它的长度可以为0;
④根(Root):长度为- -的字符串(单字符)，本赛题中指的是存在词典中‘A’，‘B’，‘C'三个基本字符，并为其分别赋予相应的编码值( 0x01, 0x02, 0x03);
⑤编码(Code): 一个8位无符号整数，本赛题中为词典中存放的每个字符串所对应的序号。
编码算法
步骤1:开始时，词典中包含所有可能的根(Root)，而当前前缀P是空的;
步骤2:当前字符(C) : =字符流中的下一个字符;
步骤3:判断缀符串P+C是否在词典中
(1)如果“是”: P : =P+C//(用C扩展P)，跳至步骤4 ;
(2)如果“否”
①把代表当前前缀P的编码输出到编码流;
②把缀-符串P+C添加到词典，并为新添加的字符串分配编码值;
③令P: =C //(现在的P仅包含-一个字符C);
步骤4:判断码字 流中是否还有码字要译
(1) 如果“是”，就返回到步骤2;
(2)如果“否”
①把代表当前前缀P的码字输出到编码流;
②结束。
void lzwFun(char *input) // 算法实现
{
int len = strlen(input); // 求出字符串长度
int i=0,j=0,k=0; // 循环变量
char ch = 0; // 当前字符
char preCharFlag = 0;
for(i=0;i<len;i++)
{
Currentchar[0] = input[i];
strcat(preChar,pre); // pre --- preChar
strcat(preChar,Currentchar); // Currentchar --- preChar
for(j=1;j<lenFlag;j++)
{
if(strcmp(root[j],preChar) == 0)
{
puts("字典中有");
preCharFlag = 1; // 表示字典中已经存在，不需要增加
break;
}
}
if(0 == preCharFlag) // 字典中没有的情况
{
strcpy(root[lenFlag],preChar);
for(k=1;k<lenFlag;k++)
{
if(strcmp(root[k],pre) == 0)
{
preCode = k;
break;
}
}
OutputBitStream[lenFlag] = preCode;
strcpy(pre,Currentchar); // 当前字符作为前缀
lenFlag++;
strcpy(preChar,""); // 清除pre+char
}
else // 字典中有的情况
{
preCharFlag = 0; // 置为初始值
strcpy(pre,preChar);
strcpy(preChar,""); // 清除pre+char
}
}
puts(pre);
//当没有字符读入的处理
for(k=1;k<lenFlag;k++)
{
if(strcmp(root[k],pre) == 0)
{
preCode = k;
break;
}
}
OutputBitStream[lenFlag] = preCode;
printf("码字:\t\t");
for(i=0;i<10;i++)
{
printf("%-5d ",i);
}
puts(""); // 换行
printf("字典:\t\t");
for(i=0;i<10;i++)
{
printf("%-5s ",root[i]);
}
puts(""); // 换行
printf("输出码流:\t");
for(i=0;i<10;i++)
{
printf("%-5d ",OutputBitStream[i]);
}
puts(""); // 换行
} 实现效果：
