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%。
支付宝扫一扫
微信扫一扫
.png)
.png)
最新评论