简述
LZ77是以色列计算机科学家Abraham Lempel与 Jacob 在1977 年发表之论文中的无损数据压缩算法。是大多数LZ算法变体如LZW、LZSS以及其它一些压缩算法的基础。
LZ77
定义
此过程将字符串 $S[1\ldots{n}]$ 分解为非空序列 $\{w_1,w_2,\ldots,w_k\}$，对于 $w_i$，有两者可能：
- 新字符短语：$w_i$ 是当前未在已编码部分 $S[1\ldots p]$ 中出现的新字符，其中 $p$ 是当前位置前的索引。
- 引用短语：$w_i$ 是当前字符起点向前最长匹配的子串，它在已编码的部分中至少出现一次。
$w_i$ 被称为因子或短语。
$S[i\ldots{j}]$ 表示位置 $i$ 到 $j$ 的子串，$S[i]$ 是 $i$ 处的字符
算法
计算 LZ77 压缩的算法核心思想是将已处理的字符串用作字典。为了限制搜索时间，实际应用中通常限制字典的大小，因此通常使用滑动窗口（sliding window）。滑动窗口被分割为字典区和预览缓冲区。压缩过程中，字符逐步从预览缓冲区移动到字典中。实际应用中，字典缓冲区通常包含数千个字符，而预览缓冲区则包含约100个字符或更少。
算法输出由三元组组成，可以用来恢复原始文本。对于因子 $w_i$ 的三元组形式为 $(pos,len,\lambda)$：
- $pos$：$w_i$ 在字典中的先前位置
- $len$：匹配长度
- $\lambda$： 当前匹配后紧跟的字符。
注：对于新字符因子，三元组形式为 $(0, 0, w_i)$。
压缩算法
以字符串 $S = \text{aacaacabcabaaac}$ 为例，说明 LZ77 压缩过程。
假设滑动窗口的字典区长度为 12（紫色区域），预览缓冲区长度为 10（黄色区域）。
算法输出的三元组如下（$pos$ 为当前编码位置向前偏移量）：
| 三元组 $(pos, len, \lambda)$ | 说明 |
|---|---|
| (0, 0, a) | 新字符 a，无匹配 |
| (1, 1, c) | 匹配前面 1 个字符，长度 1，下一字符 c
|
| (3, 4, b) | 匹配向前偏移 3，长度 4，下一字符 b
|
| (3, 3, a) | 匹配向前偏移 3，长度 3，下一字符 a
|
| (12, 3, end) | 匹配向前偏移 12，长度 3，文本结束 |
注：偏移量 $pos$ 是相对于当前位置向前计算的，
λ为匹配结束后紧跟的字符。
解压算法
解压算法相较于压缩算法更加简单，其运行时间为 $O(n)$，对当前长度为 $n$ 字符串 $S$，迭代元组序列且对于任意元组 $(pos,len,\lambda)$：
- 若 $pos = 0$，则将字符 $\lambda$ 追加到 $S$ 的末尾；
- 若 $pos \neq 0$，则对 $i = 1$ 到 $len$：
$S \leftarrow S \cdot S[n - pos + i]$
若 $\lambda \neq \text{end}$，则将 $\lambda$ 追加到 $S$ 的末尾。