简述
LZ77是以色列计算机科学家Abraham Lempel与 Jacob 在1977 年发表之论文中的无损数据压缩算法。是大多数LZ算法变体如LZW、LZSS以及其它一些压缩算法的基础。
LZ77
定义
此过程将字符串 $S[1\ldots{n}]$ 分解为非空元素集合 $\{w_1,w_2,\ldots,w_k\}$，对于 $w_i$，有两者可能：
- 一个新字符，$w_i\in{S[1\ldots{n}]}$ 且 $w_i\not\in{S[1\ldots{n-1}]}$
- $w_i$ 是 $\{w_1,\ldots,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$ 在字典中的先前位置（若无则为0）
- $len$：先前出现的长度（若为新字符则为0）
- $\lambda$： 匹配失败的字符（下一个字符）。
压缩算法
以字符串 $aacaacabcabaaac$ 为例说明 LZ77 压缩的计算过程，算法采用字典长度为12（紫色区域）和预览缓冲区（黄色区域）长度为10的滑动窗口模型。算法输出的三元组包括：
- (0, 0, a)
- (1, 1, c)
- (3, 4, b)
- (3, 3, a)
- (12, 3, end)
以下是算法过程演示：
解压算法
解压算法相较于压缩算法更加简单，其运行时间为 $O(n)$，对当前长度为 $n$ 字符串 $S$，迭代元组序列且对于任意元组 $(pos,len,\lambda)$：
- 若 $pos=0$，则 $S\leftarrow{\lambda}$
- 若 $pos\neq0$，则 for $1$ to $len$ do $S\leftarrow{S[n-pos+1]}$，然后若 $\lambda\neq{end}$ 则 $S\leftarrow{\lambda}$
无滑动窗LZ77
此方法无需使用滑动窗来计算所需元组，它的方法是：
- 设待压缩长为 $n$ 字符串为 $S$ 且 $S_x$ 为 $S[x\ldots{n}]$ 后缀。
- 要计算字符串在 $k$ 位置对应的元组，需要找到最接近的 $S_i$、$S_j$ 且满足 $S_i<S_k,i\lt{k}$、$S_j>S_k,j\lt{k}$，然后计算 $(S_i, S_k)$ 和 $(S_j, S_k)$ 的最长公共前缀，从两个结果中选择较长的一项作为最长公共子串。
- 这个算法的思想是：两个后缀的字典序大小越接近，则它们的公共前缀越长，此方法是从 $k$ 处向前寻找最长公共子串。