最近由于课程设计需要做解压缩算法
特此来考察字典编码
1 导论
许多场合，开始时不知道要编码数据的统计特性，也不一定允许你事先知道它们的统计特性。因此，人们提出了许许多多的数据压缩方法，企图用来对这些数据进行压缩编码，在实际编码过程中以尽可能获得最大的压缩比。这些技术统称为通用编码技术。
字典编码(dictionary encoding)技术（以下简称DE）就是属于这一类，这种技术属于无损压缩技术。
- DE根据的是
数据本身包含有重复代码这个特性
例如文本文件和光栅图像就具有这种特性
1.1 分类
种类很多，归纳起来大致有两类
1.1.1 查找正在压缩的字符序列是否在历史输入数据中出现过
用已经出现过的字符串替代重复部分，输出仅仅是指向之前出现过的字符串的“指针”
- 这里的“字典”指 用以前处理过的数据来表示编码过程中遇到的重复部分
这类编码的所有算法都是以abraham lempel和jakob ziv在1977年研究发表的称为lz77算法为基础
1.1.2 从输入的数据中创建一个“短语字典(dictionary of the phrases)”
这种短语不一定是像“好好学习天天向上”和“你个糟老头子坏得很我信你个鬼”这类具有具体含义的短语，它可以是任意字符的组合
编码数据过程中当遇到已经在字典中出现的“短语”时，编码器就输出这个字典中的短语的“索引号”，而不是短语本身。
j.ziv和a.lempel在1978年首次发表了这种编码方法的文章
在他们的研究基础上，terry a.weltch在1984年发表了改进这种编码算法的文章，因此把这种编码方法称为LZW(lempel-ziv walch)压缩编码，首先在高速硬盘控制器上应用了这种算法
2 LZ77算法
2.1 常见术语
- 输入数据流(input stream)
要被压缩的字符序列 - 字符(character)
输入数据流中的基本单元。 - 编码位置(coding position)
输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符 - 前向缓冲存储器(Lookahead buffer)
存放从编码位置到输入数据流结束的字符序列的存储器。 - 窗口(window)
包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数 - 指针(pointer)
指向窗口中的匹配串且含长度的指针
核心是查找从前向缓冲存储器开始的最长的匹配串
2.2 执行步骤
1.把编码位置设置到输入数据流的起始位
2.查找窗口中最长的匹配串
3.以“(Pointer, Length) Characters”的格式输出
其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个字符。
4.如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤2
[例]
- “步骤” 编码步骤
- “位置” 编码位置，输入数据流中的第1个字符为编码位置1
- “匹配串” 窗口中找到的最长的匹配串
- “字符” 匹配后在前向缓冲存储器中的第1个字符
- “输出” 以“(Back_chars, Chars_length) Explicit_character”格式输出
- (Back_chars, Chars_length) 指向匹配串的指针
告诉译码器在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出
Explicit_character 真实字符
例如，表编码过程的输出(5,2) C告诉译码器回退5个字符，然后拷贝2个字符“AB”
但wikipedia认为，粗体字理解成
从编码位置开始往回数Back_chars个字符，从该字符开始数起的字符串与接下来的Chars_length个字符完全相同
3 LZ78算法
3.1 术语和符号
- 字符流(Charstream)
要被编码的数据序列 - 字符(Character)
字符流中的基本数据单元 - 前缀(Prefix)
在一个字符之前的字符序列
-缀-符串(String)
前缀＋字符 - 码字(Code word)
码字流中的基本数据单元，代表字典中的一串字符 - 码字流(Codestream)
码字和字符组成的序列，编码器的输出 - 字典(Dictionary)
缀-符串表。按照字典中的索引号对每条缀-符串(String)指定一个码字(Code word) - 当前前缀(Current prefix)
在编码算法中使用，指当前正在处理的前缀，用符号P表示。 - 当前字符(Current character)
在编码算法中使用，指当前前缀之后的字符，用符号C表示。 - 当前码字(Current code word)
在译码算法中使用，指当前处理的码字，用W表示当前码字，String.W表示当前码字的缀-符串
3.2 编码算法
不断从字符流中提取新的缀-符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”
这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流(Charstream)，生成码字流(Codestream)，从而达到压缩数据的目的
在编码开始时字典是空的，不包含任何缀-符串(string)。在这种情况下编码器就输出一个表示空字符串的特殊码字(例如“0”)和字符流中(Charstream)的第一个字符C，并把这个字符C添加到字典中作为一个由一个字符组成的缀-符串(string)。在编码过程中，如果出现类似的情况，也照此办理。在字典中已经包含某些缀-符串(String)之后，如果“当前前缀P +当前字符C”已经在字典中，就用字符C来扩展这个前缀，这样的扩展操作一直重复到获得一个在字典中没有的缀-符串(String)为止。此时就输出表示当前前缀P的码字(Code word)和字符C，并把P+C添加到字典中作为前缀(Prefix)，然后开始处理字符流(Charstream)中的下一个前缀。
LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的缀-符串(String)用字符C进行扩展生成新的缀-符串(String)，然后添加到字典中
具体算法步骤1
步骤1
在开始时，字典和当前前缀P都是空的.
步骤2
当前字符C:=字符流中的下一个字符
步骤3
P+C 是否在字典中
(1) “是”
用C扩展P，让P := P+C
(2) “否”
① 输出与当前前缀P相对应的码字和当前字符C
② 把字符串P+C 添加到字典中
③ 令P:=空值
(3) 字符流中是否还有字符需要编码
① “是” 返回到步骤2
② “否” 若当前前缀P非空，输出相应于当前前缀P的码字，然后结束编码
3.3 译码算法
在译码开始时译码字典为空，它将在译码过程中从码字流中形成
每当从码字流中读入一对码字-字符(W,C)对时，码字就参考已经在字典中的缀-符串，然后把当前码字的缀-符串string
W 和字符C输出到字符流(Charstream)，而把当前缀-符串(string.W+C)添加到字典中。在译码结束之后，重构的字典与编码时生成的字典完全相同
具体算法
步骤1
开始时字典空
步骤2
当前码字W :=码字流中的下一个码字
步骤3
当前字符C := 紧随码字之后的字符。
步骤4
把当前码字的缀-符串(string.W)输出到字符流(Charstream)，然后输出字符C
步骤5
把string.W+C添加到字典中
步骤6
判断码字流中是否还有码字要译
(1) “是” 返回到步骤2
(2) “否” 结束
例
●“步骤” 编码步骤
●“位置” 在输入数据中的当前位置
●“字典” 添加到字典中的缀-符串，缀-符串的索引等于“步骤”序号
●“输出” 以(当前码字W, 当前字符C)简化为(W, C)的形式输出
与LZ77相比，LZ78的最大优点是在每个编码步骤中减少了缀-符串(String)比较的数目，而压缩率与LZ77类似
