LZ 编码和解码

LZ编码是字典编码的一种方法，包括LZ77编码、LZ78编码和LZW编码。它将常用的符号模式存储在字典中，用其在字典中的码字作为标识符传递，对未命中内容使用缺省的编码方式（较为低效）。

LZ77编码

基本方法： 字典为先前已遍历序列的末尾定长的一段序列（搜索缓冲区），机制类似于滑动窗口。

算法：

滑动窗口从左到右依次是搜索缓冲区、搜索指针和前向缓冲区。在移动搜索指针到一个新位置以后，尝试从搜索缓冲区中找出与当前所指向的字符串匹配的最长字符串。

编码输出格式：

对每一个字符串，使用一个三元组<o,l,c>表示，例如下图的就是<7, 4, C(‘r’)>。其中：

o表示offset=Search pointer - Match pointer，记录了匹配字符串的相对起始位置，如果没有匹配字符串就填0

l表示length，记录了匹配字符串部分的长度，如果没有匹配字符串就填0

c表示codeword，记录了前向缓冲区中紧跟在匹配字符串后面的第一个不匹配字符

需要注意的是，尽管offset是相对起始位置、length仍有可能大于offset，也就是说当前字符串与匹配字符串可能存在重叠的区域。例如<3,5,C(d)>对于字符串brar首先需要向前找3位，找到子串rar，但是它的长度小于5，先把它复制下来，得到brar**rar*。此时长度就足够了，再拷贝两个字符，得到brarrarra。

LZ78编码

LZ77假定字符串具有局部性，相同的字符串会在小范围内多次出现。为了进一步扩大重用的范围，提出LZ78编码。LZ78不再设置搜索缓冲区，而是使用显式的字典存储过往出现过的字符串组合、编码器和解码器必须在传输的过程中同步建立这个字典。

算法： 如果新字符没有匹配，将字典中的原有词条+当前第一个没有匹配的字符得到字典的新词条。

二元输出格式：

<i, c>，其中：

i表示字典的索引，从1开始，0表示字典中没找到匹配的前缀

c表示第一个未匹配字符。

也就是说，每一次传输的数据都是一个字典中出现字符串构成的前缀加上一个没有命中的新码字构成的字符串。

例如，字典中索引为9的字符串是wab，而本次编码的字符串是wabcc…，那么从编码器的角度，就是组合这个wab和第一个未命中字符c，发出<9, C©>。从解码器的角度，就是读取索引为9的元素wab添加到字符串末尾，然后再添加新字符c。同时双方都要把这个新字符组合wabc添加到字典的末尾。

同时，应当注意如果当前字符串能够与字典中多个前缀匹配，我们应当选择最长的那个。

局限性：

按照这个编码规则，显然如果不断地编码，字典将会不断增大，可以选择停止增长字典、删除最近最少使用的项、清空整个字典的方法解决这个问题。同时，LZ78虽然把编码长度从3元降低到了2元，但仍存在优化的空间。

LZW编码

为了将LZ78编码的二元组合优化成一元形式，提出LZW编码。

LZW同样使用字典，但是需要先进行字典初始化，将单个信源符号按照符号顺序写入字典表（字典序号从1开始）。和LZ78不同的是，它不再输出那个未命中的字符，因为字典已被初始化，所有的单个字符必定命中，因此只需要发送字典的序号。

从编码器的角度来看，编码器在每一次编码的时候只发送匹配前缀的序号，然后把匹配前缀和第一个未匹配字符结合起来构成字典的新项插入。同时注意如果当前字符串能够与字典中多个前缀匹配，我们应当选择最长的那个。

从解码器的角度来看，每接收到一个索引，先按照索引从字典中取出那个字符串接到输出串的末尾，然后把它和上一个索引对应的条目组合起来构成新条目的内容插入回字典中，这里需要注意因为每一次新建条目只能增加1个字符，所以如果当前索引对应的条目包含多个字符，我们在拼接的时候只取第一个字符参与组合，简单来说，就是每一次都要取 上一个字典条目+当前新字典条目的首字符 作为字典的新条目插入字典。

解码器例题：

某信源符号串为：1，2，4，3，5，8，1，10，11，1

初始化字典为：

索引	条目
1	a
2	b
3	c

解码的字符串：

ababcbababaaaaaaa = “a” + “b” + “ab” + “c” + “ba” + “bab” + “a” + “aa” + “aaa” + “a”

字典：

索引	条目
1	a
2	b
3	c
4	ab
5	ba(上一个是b，当前是ab，取ab首字符a，组成ba)
6	abc(上一个是ab，当前是c，相加得abc)
7	cb(上一个是c，当前是ba，取ba首字符b构成cb)
8	ba?(?由下次解码的首字符决定，因为下次解码是它自己，因此是b)
9	baba
10	aa(字典中无10，前一个字符串是a，首字符是a，拼接得到aa)
11	aaa(字典中无11，前一个字符串是aa，首字符是a，拼接得到aaa)
12	aaaa