LZ78编码

LZ78算法，建立词典的算法。

LZ78的编码思想：

不断地从字符流中提取新的缀-符串(String)，通俗地理解为新"词条"，然后用"代号"也就是码字(Code word)表示这个"词条"。

对字符流的编码就变成了用码字(Code word)去替换字符流(Charstream)，生成码字流(Codestream)，从而达到压缩数据的目的。

几个约定：

字符流(Charstream)：要被编码的数据序列。
字符(Character)：字符流中的基本数据单元。
前缀(Prefix)：在一个字符之前的字符序列。
缀-符串(String)：前缀＋字符。
码字(Code word)：编码以后在码字流中的基本数据单元，代表词典中的一串字符
码字流(Codestream)：码字和字符组成的序列，是编码器的输出
词典(Dictionary)：缀-符串表。按照词典中的索引号对每条缀-符串(String)指定一个码字(Code word)
当前前缀(Current prefix)：在编码算法中使用，指当前正在处理的前缀，用符号P表示
当前字符(Current character)：在编码算法中使用，指当前前缀之后的字符，用符号Char表示。
当前码字(Current code word)：在译码算法中使用，指当前处理的码字，用W表示当前码字，String.W表示当前码字的缀-符串。

编码算法步骤：

步骤1：在开始时，词典和当前前缀P 都是空的。

步骤2：当前字符Char :=字符流中的下一个字符。

步骤3：判断P+Char是否在词典中：

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

(2) 如果"否"：① 输出与当前前缀P相对应的码字和当前字符Char；

② 把字符串P+Char 添加到词典中。③ 令P :=空值。

(3) 判断字符流中是否还有字符需要编码

① 如果"是"：返回到步骤2。

② 如果"否"：若当前前缀P不空，输出相应于当前前缀P的码字，结束编码。

解码算法步骤：

步骤1：在开始时词典为空；

步骤2：当前码字W:= 码字流中的下一个码字

步骤3：当前字符Char:=紧随码字之后的字符

步骤4：把当前码字的缀-符串（string.W）输出到字符流，然后输出字符Char

步骤5：把string.W + Char添加到词典中

步骤6：判断码字流中是否还有码字要译码，

（1）如果有，返回步骤2 （2）如果没有，则结束

代码实现（C#）：

/// <summary>
/// LZ78编码所需词典
/// </summary>
public struct Dictionary
{
public int id;
public string context;
public Dictionary(int id, string str)
{
this.id = id;
this.context = str;
}
}

/// <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.context == item)
return true;
return false;
}
/// <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.context == item)
return d.id;
return 0;
}
/// <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>
public static void ShowDictionary()
{
Console.WriteLine("Dictionary:");
foreach (Dictionary d in D)
{
Console.WriteLine("<{0},{1}>", d.id, d.context);
}
}
/// <summary>
/// 执行LZ78编码算法
/// </summary>
/// <param name="str"></param>
public static void Execute(string str)
{
StringBuilder P = new StringBuilder();
char CHAR;
P.Clear();
foreach (char c in str)
{
CHAR = c;
if (Find((P.ToString() + CHAR.ToString()), D))
P.Append(CHAR);
else
{
Console.Write("({0},{1})", GetDicID(P.ToString(), D), c);
AddToDic(P.ToString() + c.ToString(), D);
P.Clear();
}
}
if (P.ToString() != "")
Console.Write("({0},{1})", GetDicID(P.ToString(), D), "/");
Console.WriteLine();
}
}

/// <summary>
/// 解码器类
/// </summary>
public static class Decoder
{
/// <summary>
/// 内部类：将码字字符串转换为编码数组
/// </summary>
struct Codes
{
public int id;
public char code;
public Codes(int id, char code)
{
this.id = id;
this.code = code;
}
}
/// <summary>
/// 词典
/// </summary>
static List<Dictionary> D = new List<Dictionary>();
/// <summary>
/// 码字流，从字符串中获取
/// </summary>
static List<Codes> CodeStream = new List<Codes>();
/// <summary>
/// 将码字串变为码字流
/// </summary>
/// <param name="str"></param>
static void BuildCodes(string str)
{
/******************
* stauts 定义:
* 0: 开始/结束状态
* 1: 逗号之前
* 2: 逗号之后
******************/
int status = 0;
int id = 0;
char code = (char)0;
string number = "";
foreach (char c in str)
{
if (c == '(')
status = 1;
else if (status == 1 && c != ',')
number += c;
else if (c == ',')
{
status = 2;
id = Convert.ToInt32(number);
number = "";
}
else if (status == 2)
{
code = c;
status = 0;
}
else if (c == ')')
CodeStream.Add(new Codes(id, code));
}
}
/// <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="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.context;
}
return string.Empty;
}
/// <summary>
/// 执行LZ78译码算法
/// </summary>
/// <param name="str"></param>
public static void Execute(string str)
{
int W;
char CHAR;
string original;
BuildCodes(str);
foreach (Codes c in CodeStream)
{
W = c.id;
if (c.code != '/')
CHAR = c.code;
else CHAR = (char)0;
if (W == 0)
{
Console.Write(CHAR);
AddToDic(CHAR.ToString(), D);
}
else
{
original = GetContext(W, D);
Console.Write(original + CHAR.ToString());
AddToDic(original + CHAR.ToString(), D);
}
}
Console.WriteLine();
}
}

执行效果（主界面程序代码省略）：

压缩算法实现之LZ78

可见算法执行的结果是完全正确的。

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

秒客网