LZW压缩算法

LZW编码

LZW算法和LZ78算法在编码方式上的不同：

输出只包含码字，其目的是克服发送每段最后一个未压缩字符造成的低效率。
LZW只输出代表词典中的缀-符串的码字。这就意味着开始时词典不能为空。开始状态，词典中必须包含可能在字符流中出现的所有的单个字符，把这些单个字符称为前缀根。

LZW编码算法的步骤：

步骤1：开始时的词典包含所有可能的根(Root)，当前前缀P为空；

步骤2：当前字符(Char) ：=字符流中的下一个字符；

步骤3：判断缀-符串P+ Char是否在词典中

(1) 如果"是"：P ：= P+ Char // (用Char扩展P) ；

(2) 如果"否"：① 把代表当前前缀P的码字输出到码字流;

② 把缀-符串P+ Char添加到词典;

③ 令P ：= Char //(现在P仅包含一个字符Char);

步骤4：判断字符流中是否还有字符需要编码

(1) 如果"是"，就返回到步骤2；

(2) 如果"否"

① 把代表当前前缀P的码字输出到码字流;

② 结束。

LZW译码过程：

开始时的词典包含所有可能的根(Root)；

步骤1：当前码字(cW) ：=码字流中的待解码的下一个码字；

查词典，输出Dictionary [cW]；

步骤2：先前码字（pW）：=当前码字（cW）;

步骤3：判断码字流中是否还有需要解码的码字，

(1) 如果"是"：当前码字(cW) ：=码字流中的待解码的下一个码字；

判断Dictionary [cW]是否为空（即词典中是否已经有序号为cW的项）

（a）如果"是"：

①查词典，输出Dictionary [cW]；

②prefix:=Dictionary [pW] ；

③Char：=first Character of

Dictionary[cW] ；

④添加词典项Prefix+char；

⑤pW:=cW;

（b）如果"否":

①prefix:=Dictionary [pW] ；

②Char：=first Character of prefix;

③添加词典项Prefix+char；

④查词典，输出Dictionary [cW]；

⑤pW:=cW;

重复步骤3；

算法实现（C#）

/// <summary>
/// 编码器类
/// </summary>
public static class Encoder
{
/// <summary>
/// 词典
/// </summary>
static List<Dictionary> D = new List<Dictionary>();
/// <summary>
/// 在词典中查找相应串
/// </summary>
/// <param name="item"></param>
/// <param name="D"></param>
/// <returns></returns>
static bool Find(string item, List<Dictionary> D)
{
foreach (Dictionary d in D)
if (d.content == item)
return true;
return false;
}
/// <summary>
/// 将一个条目加入词典
/// </summary>
/// <param name="item"></param>
/// <param name="D"></param>
static void AddToDic(string item, List<Dictionary> D)
{
int maxID;
if (D.Count == 0)
maxID = 0;
else
maxID = D.Last().id;
D.Add(new Dictionary(maxID + 1, item));
}
/// <summary>
/// 初始化词典
/// </summary>
/// <param name="str"></param>
public static void InitializeDictionary(string str) /*由于LZW算法必须有一个初始词典，因此在这里将词典初始化*/
{
foreach (char c in str)
{
if (!Find(c.ToString(), D))
{
AddToDic(c.ToString(), D);
}
}
}
/// <summary>
/// 根据词典条目内容查找相应编号
/// </summary>
/// <param name="item"></param>
/// <param name="D"></param>
/// <returns></returns>
static int GetDicID(string item, List<Dictionary> D)
{
foreach (Dictionary d in D)
if (d.content == item)
return d.id;
return 0;
}
/// <summary>
/// 执行LZW编码算法
/// </summary>
/// <param name="str"></param>
public static void Execute(string str)
{
char CHAR = (char)0;
string P = string.Empty;
InitializeDictionary(str);
foreach (char c in str)
{
CHAR = c;
if (Find((P+CHAR.ToString()), D))
{
P += CHAR;
}
else
{
Console.Write("{0},", GetDicID(P,D));
AddToDic(P + CHAR, D);
P = CHAR.ToString();
}
}
Console.Write("{0}", GetDicID(P, D));
Console.WriteLine();
}
}

/// <summary>
/// 解码器类
/// </summary>
public static class Decoder
{
/// <summary>
/// 词典
/// </summary>
static List<Dictionary> D = new List<Dictionary>();
/// <summary>
/// 初始化词典，解码算法中需手工输入
/// </summary>
public static void GetDictionary() //解码算法需手工输入初始词典
{
ShowInputHelp();
while (true)
{
string content = Console.ReadLine();
string[] items = content.Split(' ');
if (Convert.ToInt32(items[0]) != 0)
{
int id = Convert.ToInt32(items[0]);
string ch = items[1];
D.Add(new Dictionary(id, ch));
}
else break;
}
}
/// <summary>
/// 输入方法说明
/// </summary>
static void ShowInputHelp()
{
Console.WriteLine("请输入初始词典:");
Console.WriteLine("格式：");
Console.WriteLine("每行输入一个条目，编号与字符串之间以逗号分隔，以0结束");
}
/// <summary>
/// 根据词典序号找出词典内容
/// </summary>
/// <param name="id"></param>
/// <param name="D"></param>
/// <returns></returns>
static string GetContext(int id, List<Dictionary> D)
{
foreach (Dictionary d in D)
{
if (d.id == id)
return d.content;
}
return string.Empty;
}
/// <summary>
/// 将一个条目加入词典
/// </summary>
/// <param name="item"></param>
/// <param name="D"></param>
static void AddToDic(string item, List<Dictionary> D)
{
int maxID;
if (D.Count == 0)
maxID = 0;
else
maxID = D.Last().id;
D.Add(new Dictionary(maxID + 1, item));
}
/// <summary>
/// 执行LZW解码算法
/// </summary>
/// <param name="str"></param>
public static void Execute(string str)
{
string[] codeStream = str.Split(',');
int cW = 0, pW = 0;
char CHAR = (char)0;
string prefix = string.Empty;
int count = 1;
foreach (string code in codeStream)
{
if (count == 1)
{
cW = Convert.ToInt32(code);
Console.Write(GetContext(cW, D));
pW = cW;
count++;
continue;
}
if (count > 1)
{
cW = Convert.ToInt32(code);
if (GetContext(cW, D) != string.Empty)
{
Console.Write(GetContext(cW, D));
prefix = GetContext(pW, D);
CHAR = GetContext(cW, D).First();
AddToDic(prefix + CHAR, D);
pW = cW;
}
else
{
prefix = GetContext(pW, D);
CHAR = prefix.First();
AddToDic(prefix + CHAR, D);
Console.Write(GetContext(cW, D));
pW = cW;
}
}
}
Console.WriteLine();
}
}

主函数代码省略，执行效果如下：

本例中要编码的字符串有14个字符，压缩后的编码有10个数字，按实际字节算，压缩率为65%。

源代码下载：http://files.cnblogs.com/ryuasuka/LZW.rar