数据压缩/字典压缩

字典压缩

记住 士兵从麦克风点击中获得的信息量？对于某些类型的数据，如果您可以使用未存储在您正在压缩的实际数据文件中的信息来对数据进行编码，那么您可以显着减少已知形式的存储和通信需求，这是有意义的。一些算法通过包含一个内部数据表来复制此过程，通常称为字典，因此称为 *字典压缩*。

由于它允许在通信中使用时获得收益的固有特性，正如麦克风点击示例所示，发射器和接收器之间存在预先理解的代码系统，并且在发射器和接收器之间共享。大多数面向通信网络的压缩算法依赖于某种形式的字典压缩，并非没有道理。

一个例子是嵌入到压缩算法方案中的一个简单的字典。如果您已经知道特定类型数据的最紧凑的存储方案，那么您可以简单地用更紧凑的状态替换实际数据。考虑单词“supercalifragiliciousexpialadocious”。现在假设您的字典中只有 11 个以 super 开头的单词，这是第 11 个单词。嗯，显而易见的是，Super11 将足够唯一，以至于在解压缩时使用相同的字典，您可以毫无数据丢失地恢复完整的单词。但是对于 A 和 An，却不太明显，您可以将有关该单词的信息存储在比除一个字母单词之外的所有信息更小的空间中。

现在假设您有互联网，并且您想要存储 LaVogue 的一篇文章。您可以在自己的计算机上存储该文件，或者，您也可以存储一个指向该文件的链接，类似于您主页上的超文本链接。它是压缩吗？也许不是，但您可以稍作延迟即可恢复原始文本，因为它会下载。

压缩系统包含世界上所有知识的单一服务器场，并使用它来减少客户端计算机上的信息存储，令人难以置信。更奇妙的是，这样的系统会产生什么样的法律纠纷，以及与恢复最初为专有信息的压缩信息相关的隐私问题和经济成本。但一个网络感知的压缩服务器，可能能够实现真正激进的压缩率。本质上，家庭文件只需要包含触发特定数据云解压缩的密钥序列。家庭用户甚至可以压缩他的压缩文件，因为包含指向特定压缩文件结构的链接的多个文件本身可以变成一个包含所有复合文件压缩文件结构的单个文件。用户级别的无限压缩，但在服务器级别的真正庞大存储。

使用 4 位编码的文本压缩

Pike 的 1981 年压缩算法，像几个早期的文本压缩算法一样，使用了英语单词的或多或少字面的字典。

Pike 的算法使用了一个固定的字典，其中包含 205 个最流行的英语单词和 ASCII 字符。通过使用 4、8 或 12 位的可变长度编码来表示这些单词和其余的 ASCII 字符，以及对大写字母和单词之间空格的一些巧妙处理，Pike 的算法对典型的英语文本实现了 3.87 比特每字符的压缩率。

在字典中添加更多英语单词有助于压缩，但收益递减。在字典中添加某些非单词——常见字母对和三元组、常见前缀、常见后缀等——有助于压缩，因为它们可以用来至少部分压缩字典中没有的单词，但添加这些非单词也会带来收益递减。

后来的压缩算法保留了短代码字代表更长内容的想法，但将其泛化：字典编码器将代码字扩展为字节序列，该序列可能与英语单词边界对齐，也可能不对齐。

Smaz

Smaz 是一个简单的压缩库，适用于压缩非常短的字符串，例如 URL 和单个英语句子和简短的 HTML 文件。

与 Pike 的算法非常相似，Smaz 具有一个硬编码的内置常量代码本，其中包含 254 个常见的英语单词、词语片段、二元组和小写字母（除了 j、k、q）。Smaz 解码器的内部循环非常简单

• 从压缩文件中获取下一个字节 X。
  • X == 254 吗？单字节文字：获取下一个字节 L，并将其直接传递到解码文本。
  • 如果 X == 255，则直接将下一个字节 L 作为字面量字符串读取，然后将接下来的 L+1 个字节直接传递到解码后的文本中。
  • 如果 X 的值为其他任何值，则在代码本中查找第 X 个“单词”（该“单词”可以包含 1 到 5 个字母），并将该单词复制到解码后的文本中。
• 重复此过程，直到压缩文件中没有更多压缩字节。

由于代码本是固定的，因此 Smaz 解码器无法“学习”新单词并压缩它们，无论这些单词在原始文本中出现多少次。

自适应词典算法

大多数词典算法都是自适应的：与 Pike 算法中固定的、硬编码的词典不同，解码器在压缩文本时，遇到词典中尚不存在的字母三元组或整个单词时，会将其添加到词典中。

如果词典中存在太多罕见的三元组、音节或单词，则会增加更常见的三元组、音节或单词的代码字大小，从而降低压缩率。如果词典中遗漏了一些三元组、音节或单词，那么当它出现时，就无法用简单的词典引用来表示，必须使用更多位来拼写，这也降低了压缩率。这种平衡行为使得构建一个最佳词典变得很困难。^[3]

用于初始化数据压缩算法的硬编码词典对压缩过程早期阶段的压缩率有很大影响。自适应词典算法最终会将特定文本中使用的所有音节和常用单词添加到词典中，因此初始硬编码词典对大型文件压缩后期阶段的压缩率影响很小。^[3]

LZ77 算法

LZ77 类型的解码器通过将压缩文件中的“复制项”扩展成较长的字符串来扩展压缩文件。这使得“重复字符串消除”成为可能：仅将字符串的第一个副本存储在压缩文件中。所有其他副本都引用先前副本。

这些解码器具有以下通用算法

• 下一个项目是字面量吗？如果是，则将其直接从压缩文件复制到解码文本的末尾。
• 下一个项目是复制项吗？如果是，则将其分解成“长度”和“距离”。找到从解码文本当前末尾向前回溯“距离”的文本，并将从该先前解码文本中复制“长度”个字符到解码文本的末尾。
• 从头开始重复，直到压缩文件中没有更多项目。

虽然所有 LZ77 样式的算法都具有相同的解码器结构，但解码器决定一个项目是字面量还是复制项的方法多种多样，而且它们从复制项中提取“长度”和“距离”的方法也多种多样。

许多解码器算法将 LZ77 与其他压缩思想结合起来。截至 2008 年，最流行的基于 LZ77 的压缩方法称为 DEFLATE；它将 LZ77 与 Huffman 结合起来。我们在本书的后面章节中讨论 DEFLATE，数据压缩/多重转换#DEFLATE。

LZSS 和 LZRW1-A

Lempel-Ziv-Storer-Szymanski (LZSS) 由 James Storer 和 Thomas Szymanski 于 1982 年创建。LZRW1-A 由 Ross Williams 于 1991 年发表。

LZSS 和 LZRW1-A 解压缩器具有非常相似的形式

对于每个复制项，从压缩文件中获取一个“字面量/复制”位。

• 0：字面量：解码器从压缩文件中获取下一个字节，并将其直接传递到解压缩文本中。
• 1：复制项：解码器从压缩文件中获取接下来的 2 个字节，将其分解成一个 4 位“长度”和一个 12 位“距离”。4 个“长度”位解码成 3 到 18 个字符的长度。然后找到从解码文本当前末尾向前回溯“距离”的文本，并将从该先前解码文本中复制“长度”个字符到解码文本的末尾。
• 从头开始重复，直到压缩文件中没有更多项目。

LZJB

LZJB^[4] 解码器从压缩文件中获取一个“字面量/复制”位。

• 0：字面量：解码器从压缩文件中获取下一个字节，并将其直接传递到解压缩文本中。
• 1：复制项：解码器从压缩文件中获取接下来的 2 个字节，将其分解成一个 6 位“长度”和一个 10 位“距离”。6 个“长度”位解码成 3 到 66 个字符的长度。然后找到从解码文本当前末尾向前回溯“距离”的文本，并将从该先前解码文本中复制“长度”个字符到解码文本的末尾。
• 从头开始重复，直到压缩文件中没有更多项目。

在从控制字中拉取 1 位后，复制项只有一种格式

• LLLLLLdd dddddddd : 从最近解码字节之前的 d 字节处复制 L+3 个字节。

LZ77

LZ77^[5] 原始 LZ77 解码器从压缩文件中获取一个“距离/长度/字面量”块。

LZ77 解码器算法为

• 找到从解码文本当前末尾向前回溯“距离”的文本，并将从该先前解码文本中复制“长度”个字符到解码文本的末尾。（有时“长度”为 0，因此此“复制”不会执行任何操作）。
• 然后将压缩文件中的字面量字符复制到解码文本的末尾。
• 从头开始重复，直到压缩文件中没有更多项目。

BARF

“BARF” 归档器^[6]（当它没有作弊时）使用简单的字节级 LZ77 类代码。内部循环为

• 获取一个字节 X。
  • X 在 0...31 范围内吗？字面量：将压缩流中的下一个 X 个字面量字节复制到解码文本的末尾。
  • X 在 32...255 范围内吗？复制项：复制解码文本中 X-32 个位置之前的两个字节。
• 从头开始重复，直到压缩文件中没有更多项目。

LZF

LZF 是一种快速压缩算法，它需要很少的代码空间和工作内存（假设我们可以访问最近解码的 8 kByte 文本）。

Marc Lehmann 的 LibLZF 被设计为一个非常小、非常快、非常便携的 LZF 压缩算法数据压缩库。

[3] LibLZF 源代码 [4] [5] [6] [7] [8] [9] [10] [11] [12]

LZF 用于 TuxOnIce 和许多其他应用程序。

LZF 解码器的内部循环如下：[13] [14] [15] 对于每个复制项，LZF 解码器首先从压缩文件中获取一个字节 X，并将字节 X 分解为一个 3 位长度和一个 5 位高距离。解码器有 3 种情况：长度 == 0、长度 == 7 和任何其他长度。

• • 长度 == 0？（即，X 在 0...31 范围内？）文字：从压缩流中复制接下来的 X+1 个文字字节，并将它们直接传递到解压缩流中的当前位置。
  • 长度在 1...6 范围内？短复制：使用该值作为长度（稍后解释为 3 到 8 字节的长度）。
  • 长度 == 7？长复制：获取一个新的长度字节并加上 7。新字节可以具有从 0 到 255 的任何值，因此总和为 7 到 262（稍后解释为 9 到 264 字节）。
  • 两种复制类型：获取一个低距离字节，并将其与 5 个高距离位组合起来，得到一个 13 位距离。（这意味着一个 2^13 = 8KByte 的窗口）。
  • 两种复制类型：找到从当前解码文本的结尾开始向后“距离”的文本，并将“长度+2”个字符从该先前解码的文本复制到解码文本的结尾。
• 从头开始重复，直到压缩文件中没有更多项目。

每个 LZF“项”都是这 3 种格式之一

• 000LLLLL <L+1>  ; 文字引用
• LLLddddd dddddddd  ; 从最近解码的字节之前 d 个字节复制 L+2 个字节
• 111ddddd LLLLLLLL dddddddd  ; 从最近解码的字节之前 d 个字节复制 L+2+7 个字节

FastLZ

FastLZ 由 Ariya Hidayat 开发，是一个免费的、开源的、可移植的实时压缩库，用于 FastLZ 算法。（Ariya Hidayat 显然是根据 LZF 算法开发了 FastLZ 算法？） FastLZ 是 Marc Lehmann 的 LibLZF 的直接替代品。它的压缩大小和压缩时间与 LibLZF 几乎相同，但解压缩速度显著提高，大约是 LibLZF 的 2/3。

FastLZ 解码器的内部循环与 LZF 内部循环非常相似

• 获取一个字节 X。将字节 X 分解为 3 位长度和 5 位高距离。
  • 长度 == 0？（即，X 在 0...31 范围内？）文字：从压缩流中复制接下来的 X+1 个文字字节到解码文本的结尾。
  • 长度在 1...6 范围内？复制：使用该值作为长度（稍后解释为 3 到 8 字节的长度）。
  • 长度 == 7？复制：获取一个新的长度字节并加上 7。新字节可以具有从 0 到 254 的任何值，因此总和为 7 到 261（稍后解释为 9 到 263 字节）。
  • （当新字节为全 1（255）时，它用作更长长度的转义...）
  • 获取一个低距离字节，并将其与 5 个高距离位组合起来，得到一个 13 位距离。（这意味着一个 2^13 = 8KByte 的窗口）。
  • 如果距离为全 1（0x1FFF）：获取 2 个新的距离字节，得到一个完整的 16 位距离，并将其添加到 0x1FFF 全 1 距离。（这意味着一个 2^16 + 2^13 = 64 KByte + 8 KByte 的窗口）
  • 找到从当前解码文本的结尾开始向后“距离”的文本，并将“长度+2”个字符从该先前解码的文本复制到解码文本的结尾。
• 从头开始重复，直到压缩文件中没有更多项目。

如果压缩文件仅使用 2^13-1 窗口内的距离，并且长度小于 2^8+7，那么 FastLZ 和 LZF 解码器都将生成相同的解压缩明文。

每个 FastLZ“项”都是这 5 种格式之一（LZF 格式，以及一些扩展）

• 000LLLLL <L+1>  ; 文字引用
• LLLddddd dddddddd  ; 从最近解码的字节之前 d 个字节复制 L+2 个字节
• 111ddddd LLLLLLLL dddddddd  ; 从最近解码的字节之前 d 个字节复制 L+2+7 个字节
• LLL11111 11111111 dddddddd dddddddd ; 从最近解码的字节之前 d+0x1FFF 个字节复制 L+2 个字节
• 11111111 LLLLLLLL 11111111 dddddddd dddddddd ; 从最近解码的字节之前 d+0x1FFF 个字节复制 L+2+7 个字节

不清楚为什么 FastLZ 比 LZF 快得多。它的“扩展”似乎没有被使用，因为基准文件上的压缩文件大小并没有显著不同。 如果将相同的实现技术（只要可能就使用 16 位复制，专门针对“运行”（伪 RLE）等）应用于 LZF，它会一样快吗？ 还是这些“扩展”实际上被大量使用，并且它们以某种方式比 LZF 方法更快（但大小大致相同）？

miniLZO

LZO 是一种压缩数据格式，也是一个用 ANSI C 编写的可移植无损数据压缩库，由 Markus F.X.J. Oberhumer 开发和维护。 LZO 比 LZF 稍微慢一些，但产生的压缩文件大小略好。LZO 比 DEFLATE/gzip 快得多 - 它运行时间大约是后者的 1/2 - 并且产生的文件大小比 DEFLATE/gzip 稍差。 [16]

miniLZO 是 LZO 库的一个轻量级子集。

LZ4

LZ4 是一种压缩数据格式，也是一个由 Yann Collet 开发和维护的可移植无损数据压缩库。

LZ4 用于许多 压缩文件系统 中，包括 OpenZFS、GNU Grub、HAMMER 和 Squashfs。 各种语言和（跨平台）操作系统的开源实现可供使用，并且有一个活跃的讨论组。

LZ4 解码器的内部循环如下：

对于每个复制项，LZF 解码器首先从压缩文件中获取一个字节 X，并将字节 X 分解为一个 4 位文字长度和一个 4 位复制长度。

文字解码器有 2 种情况：文字长度 == 15 和任何其他长度。

• 文字长度 == 0...14？从压缩流中复制接下来的文字长度个文字字节，并将它们直接传递到解压缩流中的当前位置。（如果文字长度字段为 0，则没有文字）。
• 文字长度 == 15？长复制：获取一个新的长度字节并加上 15。新字节可以具有从 0 到 254 的任何值，因此总和为 15 到 269 字节的文字。

（... 说说文字长度 == 15 紧跟着任意数量的额外 255 字节的特殊情况...）然后从压缩流中复制总文字字节，并将它们直接传递到解压缩流中。

在文字字节（如果有）之后是距离的低字节，然后是距离的高字节。（这意味着一个 2^16 = 64KByte 的窗口）。距离为 1 表示“当前位置 - 1 个字节”；距离为 0xffff 表示“当前位置 - 65535 个字节”；距离为 0 无效，永远不会发生。要复制的实际字节数的解码方式类似于要复制的实际文字数的解码方式，只是匹配的最小长度为 4 个字节。

• 复制长度 == 0...14？长度总和 = 复制长度 + 4 个字节，即 4 到 18 个字节。
• 复制长度 == 15？长复制：获取一个新的长度字节。长度总和 = 该新的长度字节 + 复制长度 + 4 个字节。新字节可以具有从 0 到 254 的任何值，因此长度总和为 19 到 273 字节的文字。

（... 说说复制长度 == 7 紧跟着任意数量的额外 255 字节的特殊情况...）

• 两种复制类型：找到从当前解码文本的结尾开始向后“距离”的文本，并将“长度”个字符从该先前解码的文本复制到解码文本的结尾。
• 从头开始重复，直到压缩文件中没有更多项目。

与大多数 LZ77 风格的算法一样，LZ4 支持 伪 RLE - 长度总和可以大于偏移距离；匹配可以向前重叠。

伪 RLE 的一个常见情况是距离为“1”，解压缩器最终会重复最后一个字节“长度总和”次。

为了确保解码器永远不会读取超出输入缓冲区，也不会写入超出输出缓冲区，每个块都以一个“块大小”字段开头，该字段指示该块中 *压缩* 数据的字节数；并且该块的最后 5 个字节始终是文字。最后一个复制项不完整，在它的文字之后立即停止。

“LZ4-HC”（“高压缩”）和“LZ4”使用完全相同的格式和相同的解码函数；不同之处在于编码器。

QuickLZ

QuickLZ

LZS

LZS: Lempel–Ziv–Stac 压缩。LZS 压缩在各种互联网协议中被指定，包括 RFC 1967、RFC 1974、RFC 2395 和 RFC 3943。 Stac Electronics 起诉微软侵犯 LZS 专利。从那以后，其中一些专利已经过期。

LZS 解码器从压缩文件中获取“文字/复制”位。

• 0：字面量：解码器从压缩文件中获取下一个字节，并将其直接传递到解压缩文本中。
• 1: 复制项：解码器从压缩文件中获取下一个位。
  • 该位选择从文件中拉取多少位的“距离”。
    • 1: 解码器获取一个 7 位“距离”。
      • 如果此距离是不合理的“0”值，它实际上代表消息结束。退出循环。
    • 0: 解码器获取一个 11 位“距离”（这意味着一个 2 kibiByte 滑动窗口）。
  • 然后解码器从压缩文件中获取“长度”值。
    • 但是，长度不是在固定长度的字段中编码，而是在可变长度的模式中编码。
    • 00 表示长度 2
    • 01 表示长度 3
    • 10 表示长度 4
    • 1100 表示长度 5
    • 1101 表示长度 6
    • 1110 表示长度 7
    • 1111 0000 表示长度 8
    • 1111 0001 表示长度 9
    • 1111 1111 0010 表示长度 25
    • 一般来说，除了上面列出的前 6 个特殊情况外，"1111" 重复 N 次，然后是表示 0...14 范围内的值的 4 个位 Y，解码为长度值 (N*15 + Y - 7)。
  • 然后找到从当前解码文本结束位置向后“距离”的文本，并将“长度”个字符从该先前解码的文本复制到解码文本的结束位置。
• 从头开始重复，直到解码到特殊的“零距离”值。

LZS 中使用的复杂可变长度编码技术允许将“最近”的字节对压缩成 11 位，甚至将“不太近”的字节对压缩成 15 位，只要它们在 2 kibiByte 滑动窗口中。这种可变长度编码技术是“通用码”的几种类型之一，是许多种“固定霍夫曼编码”表的其中一种，我们将在本维基百科的 熵 章节中讨论。

在文本文件中，重复的字节对比更长的重复字符串更为常见。LZS 在这种常见的冗余形式上至少提供了 1 位的压缩。这使 LZS 优于无法压缩小于 3 个字符的重复字符串的压缩算法，因此必须按原样存储这些短重复，甚至通过一位来扩展它们。

Snappy

“Snappy”算法针对非常高的速度进行了优化（即使是以压缩效果中等为代价）。在基准文件上，Snappy 比 zlib 快一个数量级，但压缩文件比 zlib 大 20% 到 100%。 Snappy 比 LZF 更快。

“Snappy”解压缩器的内部循环解码总是以以下格式之一的标记字节开头的“元素”。

• xxxxxx00 ; 随后是文字
• xxxxxx01 ; 复制，偏移量为 1 字节
• xxxxxx10 ; 复制，偏移量为 2 字节
• xxxxxx11 ; 复制，偏移量为 4 字节

详情

• LLLLLL00 <L+1> ; 其中 L 在 0..59 之间：1...60（含）个文字字节的文字引用。
• LLLLLL00 <L-59> <长度> ; 其中 L 在 60..63 之间：这些特殊的“长度”分别表示 1、2、3 或 4 个实际的长度字节跟随标记字节。这些长度字节后面是文字本身。

• dddLLL01 dddddddd ; 复制，偏移量为 1 字节：从最近解码的字节前 d 个字节处复制 L+4 个字节。（为什么是 L+4，得到长度 4..11 ? L+3，得到长度 3..10，会得到更好的压缩吗？也许甚至是 L+2，允许我们偶尔复制字节对？）
• LLLLLL10 dddddddd dddddddd ; 复制，偏移量为 2 字节：从最近解码的字节前 d 个字节处复制 L+1 个字节。
• LLLLLL11 dddddddd dddddddd dddddddd dddddddd ; 复制，偏移量为 4 字节：从最近解码的字节前 d 个字节处复制 L+1 个字节。

PalmDoc

PalmDoc 将 LZ77 与一种简单的字节对压缩方式结合在一起。PalmDoc 算法：

PalmDoc 文件的解码方式如下

• 从压缩流中读取一个字节。如果字节是
  • 0x00: “1 个文字”将该字节不加修改地复制到解压缩流。
  • 0x09 到 0x7f: “1 个文字”将该字节不加修改地复制到解压缩流。
  • 0x01 到 0x08: “文字”：将该字节解释为 1 到 8 之间的计数，并将该数量的文字从压缩流不加修改地复制到解压缩流。
  • 0x80 到 0xbf: “长度、距离”对：丢弃此字节的 2 个最左边的位（'10'），并将接下来的 6 位与下一个字节的 8 位组合，形成一个 14 位的“距离、长度”项。将这 14 位分成 11 位的距离（从解压缩文本中的当前位置向后），以及 3 位的长度（从该位置复制，复制 n+3 个字节，3 到 10 个字节）。
  • 0xc0 到 0xff: “字节对”：将此字节解码为 2 个字符：一个空格字符，以及由该字节与 0x80 进行异或运算形成的字母。
• 从头开始重复，直到压缩文件中没有更多字节。

LZSA

LZSA 是一个字节对齐压缩格式的集合，专门针对 8 位系统上的超快速解压缩而设计。

LZSA1

LZSA1

... [待办事项：] ...

LZSA2

LZSA2 解压缩器的内部循环解码总是字节对齐的压缩“命令”，以“标记”字节开头：

• 标记：XYZ LL MMM

LL 是一个 2 位文字长度，值为 0 到 3。如果 LL 是 00，则没有文字，此命令仅处理匹配。如果 LL 是 1 或 2，则此标记后面跟 1 或 2 个文字值。如果 LL 是 3，则此标记后面跟“额外文字长度”的半字节或字节，解码为 3 到 0xFFFF 的文字数量，然后这些 3 到 0xFFFF 个文字字节紧随“额外文字长度”字节之后。

处理完文字（如果有）后，解码器会处理类似 LZ77 的匹配。匹配偏移量根据标记中的 XYZ 位进行解码。

• XYZ
• 00Z 5 位偏移量：读取一个半字节 + Z 以获取偏移量
• 01Z 9 位偏移量：读取一个字节 + Z 以获取偏移量
• 10Z 13 位偏移量：读取一个半字节 + 一个字节 + Z 以获取偏移量
• 110 16 位偏移量：读取 2 个字节以获取偏移量
• 111 重复偏移量：重复使用先前命令的偏移量值。

MMM 是一个 3 位匹配长度，值为 0 到 7。最小匹配长度为 2 个字节（编码为“000”）。如果 M 为 0 到 6，则实际匹配长度为 2 到 8。如果 M 为 7，则“额外匹配长度”的半字节或字节（紧随文字字节之后，如果有）将解码为 2 到 0xFFFF 的匹配长度。

对于大小优化的解压缩器，相同的代码可以用于解码两种类型的长度 - 匹配偏移量半字节或字节，以及文字长度半字节或字节。

字典算法

固定字节对编码

最简单的字典算法是使用固定字节对字典（二元组字典）的字节对编码。

简单的字节对编码，也称为双平铺编码或 DTE，通常用于压缩视频游戏 ROM 中的文本。

字节对解码器假设英文文本只使用相对较小的字母和符号“字母表”。字节对解码器假设某些字节从未出现在英文文本中（“高”字节 0x80 到 0xFF 和其他一些字节）。当压缩文本中出现“不可能”的字节时，解码器在固定字典中查找该字节，并发出相应的字节对。否则，解码器将压缩字节原封不动地复制到明文。通常，0x00 字节标记压缩字符串的结尾，因此标准 C 字符串处理例程可以重复用于处理压缩文本。字典应包含明文中使用频率最高的字母对（“th”、“he”、“t”等）。该算法有多种不同的实现方式，每种实现方式都使用不同的（不兼容的）字典。

字节对编码

DTE 可以一步解码 - 压缩文本的每个字节要么是代表自身的“正常”可打印字符，要么是代表两个“正常”可打印字符的“不可打印”字节。递归字节对编码放宽了此限制：使用递归字节对编码，“不可打印”字节代表两个字节。有时这两个字节都是正常的可打印字符，就像 DTE 一样。有时一个或两个字节可能是（其他）“不可打印”字节，需要重复解码过程，直到只剩下可打印字符。

SCZ 字节对编码

SCZ 是由 Carl Kindman 开发的一种动态字节对算法和压缩格式，他以 LGPL 许可发布了其中一种实现及其测试套件。

SCZ 压缩格式是一系列段。每个段都有几个字节的头部和尾部，包括迭代次数和校验和，围绕着一个重复压缩的块。

SCZ 解码器的内部循环给定一个包含 256 个条目的字典和一个特殊的转义符号。内部循环扫描“压缩段数据”块，并生成一个新的解压缩块，类似于这样

• 从压缩块中读取下一个字节。
• 如果读取的字节是特殊的转义字节，则丢弃转义字节并读取以下压缩字节作为文字字节，并将该文字字节写入解压缩块。
• 否则，在字典中查找该字节。
  • 如果该字节是“标记字符”，则字典包含一个字节对来替换它 - 将这两个字节写入解压缩块。
  • 否则，字典表明该字节是一个文字字节 - 将读取的字节写入解压缩块。
• 重复此操作，直到压缩块中没有更多数据。

“转义字节”使得能够压缩一个文件，该文件具有多次重复的字节对，即使该文件已经使用所有 256 个可能的字节值 - 压缩器故意将一些罕见的字节扩展为两个字节（转义字节和罕见的字节），以便重新使用该罕见的字节作为“标记字节”来表示该字节对（将这两个字节的每个实例压缩为一个字节）。

SCZ 解码器的中间循环给定一个迭代次数和一个数据块。中间循环生成相应的明文，类似于这样

• 如果迭代次数为零，则块的其余部分是完全解压缩的数据 - 完成！
• 从压缩块中读取头部
  • 从压缩块中读取一个字节；此字节成为新的转义符号。
  • 读取符号计数 N，并将 N 个字典条目读入字典。（每个条目是 3 个字节：存储在压缩文本中的“标记”字节，以及它在解压缩文本中表示的两个字节）。
• 将转义符号、字典和压缩块的其余部分（压缩段数据）传递给内部循环，将其解压缩为一个解压缩块。
• 将（现在为空的）压缩块与解压缩块交换。
• 递减迭代次数并从头开始重复。

SCZ 解码器的外部循环将文件分解成一系列段，将每个段分解成一个头部（其中包含迭代次数等）、一个压缩数据块（外部循环将其传递给内部循环进行解码）和一个尾部（其中包含用于检测问题的校验和）。

LZ78 算法

LZ78

LZW

基于字典的技术的一个著名例子是 LZW 数据压缩，因为它通过将本质上无限长的字符串替换为通常大小在 9 到 16 位之间的代码来运行。

LZW 算法，如 GIF 文件格式中所使用的那样，可能是最著名和最具争议的压缩算法。

在将一个代码字解码为一个包含一个或多个字母的“词”并将这些字母发出到明文流时，LZW 解压缩器会将一个新的“词”添加到字典中。新词是由先前解码的词与当前代码字表示的词的第一个字母连接而成的。

更大的代码字允许使用更大的字典，这通常会提高压缩率。

GIF

GIF 文件格式通常以 9 位代码字开头，并在必要时逐渐增加代码字的宽度，直到最大代码字宽度为 12 位。许多 GIF 实现静态分配一个包含 2^12 = 4096 个字典条目的字典，每个可能的代码字对应一个条目。

LZMW

LZMW（1985 年）由 V. Miller 和 M. Wegman 开发，是对 LZW 的修改。

在将一个代码字解码为一个包含一个或多个字母的“词”并将这些字母发出到明文流时，LZMW 解压缩器会将一个新的“词”添加到字典中。新词是由先前解码的词与当前代码字表示的整个词（可能是同一个词）连接而成的。这允许字典条目比 LZW 更快地增长。

LZAP

LZAP（1988 年）由 James Storer 开发，是对 LZMW 的修改。

在将一个代码词解码为一个或多个字母的“单词”并将这些字母输出到明文流时，LZAP 解压缩器至少会向字典中添加 1 个，通常更多的新“单词”。新单词是先前匹配与当前匹配的每个初始子字符串的串联。（“AP”指的是“所有前缀”。）例如，如果先前的匹配是“com”，当前的匹配是“press”，那么 LZAP 解压缩器会向字典中添加 5 个新的“单词”：“comp”、“compr”、“compre”、“compres”和“compress”，而 LZW 仅添加“comp”，LZMW 仅添加“compress”。

这使得字典中的单词数量增长速度远远快于 LZW 或 LZMW。

LZWL 和基于单词的 LZW

2005 年，Jan Lánský 引入了基于音节的压缩。

LZWL 压缩器使用音节检测器将明文分成音节。 当 LZWL 解压缩器从压缩文本中提取“短语索引”时，它会向字典中添加一个新短语——由整个先前短语与当前短语的第一个音节串联而成。当 LZWL 解压缩器从压缩文本中提取特殊的“空音节”短语索引时，它会向字典中添加一个新的音节——在紧随其后的压缩文本中以字符为单位进行编码。

类似的“基于单词的 LZW”将明文分成英文单词（通常情况下，交替出现的字母数字字符和非字母数字字符的最大字符串）。

基于字符的压缩在较小的文件上似乎能获得更好的压缩效果；基于单词的压缩在较大的文件上似乎能获得更好的压缩效果。一些研究人员建议，基于音节的压缩方法可能会在中等大小的文件（如 HTML 页面）上获得更好的压缩效果。

LZW 实现技巧

解压缩器使用的字典并不真正需要为每个字典条目存储一个文字字符串。由于每个字典条目都是由某个先前字典条目与单个字符串联而成的，因此解压缩器只需要为每个条目存储一个整数和一个字符：某个先前字典条目的索引，以及一个文字后缀字符。

这种紧凑的字典也适用于 LZAP。对于 LZMW，每个条目不再存储单个后缀字符，而是存储第二个整数：指向某个（可能相同）先前字典条目的索引。

对于解码器来说，通常将任何值为小于 256 的代码词进行特殊情况解码，并立即输出它所代表的文字字节，而不是经过查找字典中该代码词的过程，会更简单、更快。

一些 LZW 压缩器使用哈希表来快速将接下来的几个明文字符映射到字典条目。这与用于加速 LZ77 风格压缩器的哈希表的工作原理基本相同。

LZW 和其他 LZ78 变体的某些实现使用了一种特殊的搜索树，利用了字典结构。

LZX

（我们将在后面的章节中讨论 LZX，数据压缩/顺序/熵#LZX）

简化偏移 Lempel-Ziv (ROLZ)

上面提到的 LZ77 的 LZ77 变体对一个线性、未编码、固定长度的偏移进行编码。在任何特定解码时刻，该偏移的可能值通常包含许多永远不会被使用的值。例如，一旦解压缩器提取了长度为 4 的复制长度，它可能会在文本中看到数十个“the ”和“and ”的复制，但它知道压缩器总是会选择最新的一个——所有选择其他“the ”或“and ”复制的值将永远不会出现。

如果我们能够以某种方式“跳过”这些不可能的偏移，我们就可以用更少的位数对偏移进行编码，并且仍然能够使用与上述 LZ77 编码器相同的（偏移量，长度）短语。

此外，偏移量的许多可能值极不可能出现。例如，一旦解码器完成了一个以“ch”结尾的短语的输出，在正常的英文文本中，下一个字符几乎永远不会是另一个辅音。因此，所有指向以某个辅音开头的短语的偏移量几乎永远不会被使用。通过跳过这些极不可能出现的偏移，我们可以用更少的位数对下一个短语的偏移量进行编码，并且几乎总是能够复制与上述 LZ77 编码器相同的（偏移量，长度）短语。（在一些罕见的情况下，上述 LZ77 编码器选择了 ROLZ 算法认为“不可能”的某些短语并跳过，迫使我们复制其他较短的短语；但希望在这些情况下牺牲几个位数可以弥补在几乎所有其他情况下节省的几个位数）。

“简化偏移”是指与使用线性、未编码、固定长度的偏移量相比，我们减少了压缩文件中用于选择特定偏移量的位数。我们并不意味着最大可能的偏移量会减少——事实上，大多数 ROLZ 压缩器可以从比线性、未编码偏移量的典型 2^10 或 2^12 字节限制更远的偏移量复制短语。

使用线性、未编码、固定长度偏移量以外的其他方法，必然需要在解码时进行更多计算，将该压缩选择值转换为已解码文本中的实际位置。这又是速度和压缩率之间的另一种权衡。

Ross Williams 指出，所有 LZ77 和 LZ78 算法都可以转换为马尔可夫算法的形式。

Malcolm Taylor 在 WinRK 压缩套件中编写了第一个 ROLZ 实现。Ilia Muraviev 编写了第一个开源的 ROLZ 压缩实现。

LZRW3-a 在 LZRW 系列“快速”数据压缩器中，LZRW3-a(8) 在大型文本基准测试中提供了最佳压缩效果。与大多数其他 ROLZ 压缩器不同，它完全忽略了最近解码的明文上下文字节。LZRW3-a 解码器的内部循环首先从压缩文件中获取一个“文字/复制”位。

• 0：文字：解码器从压缩文件中获取下一个字节，它代表它本身。将其直接传递到解压缩文本中。每个文字字节都是“有趣的”，因此指向该字节的指针最终会被添加到“之前解码文本中 2^12 个有趣位置的表中”。希望下次可以将该字节通过该指针作为长短语的一部分复制，而不是再次费力地用文字拼写出来。
• 1：复制项：解码器从压缩文件中获取接下来的 2 个字节，它们代表一个短语。解码器将其分解为 4 位“长度”和 12 位选择器。
• 4 个“长度”位被解码为 3 到 18 个字符的长度。
  • 它使用该 12 位选择器从“之前解码文本中 2^12 个有趣位置的表中”选择一个位置，并从该位置复制长度个字符到解码文本的末尾。此外，在表中添加指向该短语开头的指针。
• 从头开始重复，直到压缩文件中没有更多项目。

LZRW3-a(8) 试图（近似地）保留每个在明文中出现的 3 字节短语的最近 8 个实例。（解压缩器将指针添加到哪个分区以及当分区已满时用于丢弃旧指针的伪随机替换的具体细节超出了本文档的范围）。（实际上，解压缩器将 12 位代码扩展为 20 位未编码偏移量到 1 MB 明文缓冲区中）。（细节太多）

LZRW4 (Ross Williams, 1991) 可以被看作是一种 ROLZ 算法。与每个短语的线性、未编码偏移量不同，偏移量由一个 5 位值表示。在每个短语的开头，LZRW4 解码器对前两个字符进行哈希运算，以获得一个分区号。5 位值选择上下文选择的 partition 中的 32 个指针之一。它指向 1 MB 明文缓冲区中以前解码的位置。（实际上，解压缩器已将 5 个编码位扩展为 20 位未编码偏移量）。然后解压缩器从压缩文本中提取 3 位，并将其解码为 8 个可能的长度值（2、3、4、5、6、7、8、16），然后将选定的（偏移量、长度）短语复制到明文。然后更新上下文分区。由于“复制项”只有 9 位（标志位 + 偏移量选择器 + 长度），因此它可以很好地压缩常见的字节对。文字项也是 9 位（标志位 + 文字八位字节）。（为了提高速度，Williams 不会在分区表中存储指向 *每个* 2 字节上下文的指针，而只会存储在短语 *末尾* 出现的 2 字节上下文）。（为了减少内存使用，Williams 不会使用 2^16 个分区来跟踪 *确切的* 2 字节上下文，而是将前 2 个字节的上下文哈希为一个 12 位上下文，具有 2^12 个分区）。（细节太多……）

也许“缩减偏移量”的最极端形式是将偏移量缩减为 0 位。ROLZ 的这种特殊情况称为 LZP。

LZP

LZP 压缩由 Charles Bloom 发明。 LZP 解压缩器检查当前上下文（可能是前 3 个字节），在明文中找到该上下文的最近出现（或某种近似），并且仅使用该一个固定偏移量。这给了我们一个非常短的压缩短语（一个标志位 + 一个匹配长度）。在某些情况下，该一个固定偏移量与 LZ77 将使用的偏移量相同——在这些情况下，我们节省了很多位，因为我们没有存储偏移量。在其他情况下，该一个固定偏移量与 LZ77 将使用的偏移量不完全相同，而是一个更大的偏移量，它为我们提供了完全相同的复制短语——同样，我们也节省了很多位。不可避免地，有时该一个固定偏移量提供的有用字节比 LZ77 选择的偏移量少——在最坏的情况下，为 0 个有用字节。LZP 需要比 LZ77 在这种情况下所需的更多位来编码这些字节。但总的来说，LZP 通常比 LZ77 压缩得更好。

一些实现确保上下文表始终准确地指向每个 3 字节上下文的最近出现——这要求在解压缩器发出的每个字节上更新上下文表。许多 LZP 实现通过仅在短语或文字的开头更新表来近似此操作，跳过在该短语期间复制的所有字节的更新。这加快了解压缩速度，并且 Arturo San Emeterio Campos 声称它实际上提高了较长文件的压缩率，尽管它损害了较短文件的压缩率。

LZP 解码器的工作方式如下

• 在上下文表中查找当前上下文以获取 Position。如果此上下文 *从未* 出现过，那么我们有一个文字。否则，从压缩文件中获取一个“文字/复制”位。
• （无论哪种情况，请记住 Position，但更新上下文表以指向解压缩文本中的当前位置。下次我们有相同上下文时，我们将获得此位置，而不是那个较早的 Position）
• 0：字面量：解码器从压缩文件中获取下一个字节，并将其直接传递到解压缩文本中。
• 1: 复制项：解码器从压缩文件中获取一些位并将它们解码为长度。从此上下文之前出现的位置开始，将以前解码文本中的“长度”个字符复制到解码文本的末尾。然后从压缩文件中获取下一个文字字节，并将其直接传递到解压缩文本中。
• 从头开始重复，直到压缩文件中没有更多项目。

一些文档 描述了 LZP 的字节级版本

• 在上下文表中查找当前上下文以获取 Position。（记住 Position，但更新上下文表以指向解压缩文本中的当前位置。下次我们有相同上下文时，我们将获得此位置，而不是那个较早的 Position）。
• 从压缩文本中获取下一个字节。
• 如果此上下文 *从未* 出现过，*或者* 获取的字节不是转义字节，那么我们有一个文字；否则，我们有一个复制项。（压缩器应该为转义字节选择一个在明文中很少出现的的值）。
• 文字：将其直接传递到解压缩文本中。
• 复制项：丢弃转义字节，并获取长度字节。从此上下文之前出现的位置开始，将以前解码文本中的“长度”个字符复制到解码文本的末尾。然后从压缩文件中获取下一个文字字节，并将其直接传递到解压缩文本中，即使它恰好是转义字节。（有时长度将为 0，例如当解压缩文本 *需要* 包含我们用作转义字节的特殊字节时）。
• 从开头重复，直到压缩文件中没有更多项目。

统计 Lempel Ziv

统计 Lempel-Ziv 最初由 Yu Fan Ho 提出，作为他在 Sam Kwong 博士指导下攻读计算机科学硕士学位的研究课题。他们最初将其作为个人数字助理的应用发表。 后来 Yu Fan Ho 将其应用于手机铃声，在压缩率和解压缩速度方面优于其他可用的无损压缩器。统计 Lempel Ziv 对旋律数据的应用已获得专利。

传统的基于 LZ 的技术利用了数据的重复特性。解压缩过程可以通过根据压缩数据中的索引从搜索窗口复制重复数据来简单地完成。在窗口中找不到的数据在压缩数据中保持未压缩状态。然后将未压缩数据移入搜索窗口，以进行下一个重复，依此类推。数据无条件地移入窗口，而不考虑统计信息。由于搜索窗口的大小有限，因此当窗口已满时，第一个进入的数据将无条件地移出。窗口很可能被无用（非重复）数据占用，而有用（要重复）的数据则被剔除。为了提高压缩率，应该使用更大的搜索窗口，因此解压缩器需要更多内存。

统计 Lempel Ziv 是一种类似于 LZ 的无损压缩算法，但它也考虑了统计信息来识别应该放入字典（搜索窗口）中的有用数据。与 LZ77 相比，它提高了压缩率，因为可以将更多有用数据保存在字典中。字典的大小可以更小，以保存有用数据，因此解压缩器所需的内存更少。由于并非所有数据都必须移入窗口，因此解压缩器所需的处理能力更少。

ACB

Buyanovsky 的关联编码 (ACB) 从类似 LZ77 的压缩器开始，并做了很多事情来消除 (偏移量、长度) 项目中的大量冗余。

Tunstall 代码

霍夫曼算法给出了一种固定到可变长度的代码，该代码（在某些约束下）是最佳的。

Tunstall 算法给出了一种可变到固定的长度代码，该代码（在某些约束下）是最佳的。

实现技巧和窍门

压缩格式技巧和窍门

大多数数据压缩解压缩算法最自然地用将压缩文件作为未区分的位流（位流）读取来描述。大多数编程语言一次一个字节地执行文件 I/O。

因此，解压缩实现通常会保留一个单独的“位缓冲区”（最初为空）。 当您想要读取一个位时，如果位缓冲区为空，则从压缩字节流中读取一个（字节对齐的）字节，将最后未使用的 7 位存储在位缓冲区中，并使用第一个位。 否则从位缓冲区读取下一个位。

许多文件格式旨在尽可能保持“8 位对齐”（有些甚至尝试保持“16 位对齐”），以通过减少位移位的数量来加速处理。

通常在解压缩时，您已经读取了一些奇数个位，抽象解压缩算法会提到类似“读取下一个 8 位并将该字面字节直接传递到输出”的内容。 有三种可能的方式来设计文件格式来处理“读取下一个 8 位”

• “无差异位流”：获取位缓冲区中的剩余位，重新加载位缓冲区，并获取更多位，然后移位和对齐以重新组装字节。
• 丢弃位缓冲区中剩余的“填充位”，并简单地从压缩字节流中读取下一个（字节对齐的）字节。 比位流方法更快，但未使用的位会损害压缩率，因此我们不再讨论这种方法。
• “字节对齐”：暂时忽略位缓冲区；直接从压缩字节流中读取（字节对齐的）字节。（仅在解压缩算法读取一两位或七位时才使用位缓冲区）。

与无差异位流格式相比，压缩文本的字节对齐格式具有完全相同的字节数和完全相同的位；位只是以略微不同的顺序排列。 因此，选择字节对齐格式可以获得完全相同的压缩率，并且通常可以提高速度。

压缩器实现提示和技巧

缓慢的朴素方法

实现 LZ77 样式（偏移量，长度）压缩器的显而易见的方法是，针对我们最终写入压缩文件的每个短语，扫描整个窗口以查找与以下明文的匹配。 然后选择最长（和最近）的匹配。

实现 LZ78 样式（字典条目）压缩器的显而易见的方法是，针对我们最终写入压缩文件的每个字典索引，扫描整个字典以查找与以下明文的匹配。

对于长度为 N 的文件，这对于每个压缩短语都是 O(N)。 这需要 O(N^2) 来压缩长度为 N 的文件。（Schlemiel 画家的算法）。（我假设 LZ77 窗口至少覆盖了文件的一半，并假设压缩率大致恒定）。 这是非常慢的。

加速

大多数 LZ77 样式和 LZ78 样式压缩器实现使用加速技巧：每当它们输出压缩短语时，它们都会执行一些 O(1) 的“额外”工作来更新一些数据结构——通常是 Trie 或哈希表。 然后，他们不再顺序扫描整个窗口以查找匹配，而是查找该数据结构中的以下明文（通常是接下来的 3 个字节）。

Trie

一些 LZ77 样式和 LZ78 样式压缩器实现使用 Trie 数据结构.

哈希表

大多数 LZ77 样式和 LZ78 样式压缩器实现使用 哈希表。 然后，他们不再顺序扫描整个窗口以查找匹配，而是查找哈希表中的以下明文（通常是接下来的 3 个字节）。 在哈希表中，搜索立即成功或失败，时间复杂度为 O(1)，因此压缩整个文件只需要 O(N)。 速度快得多。

许多 LZ77 样式压缩器有意通过两种方式牺牲最大可能的压缩率：（a）一些压缩器只在每个短语更新一次哈希表，而不是每个字节更新一次。（b）一些压缩器使用直接索引缓存——一个非常简单的哈希表，没有冲突检测——表只记住具有该哈希索引的单个最新项目——而不是记住具有该哈希索引的*所有*项目的标准哈希表。 通常，（a）或（b）中的每一个都会降低压缩率几个百分点，但可以将压缩器的速度大致提高两倍或三倍。 许多 LZ77 样式压缩器同时执行 (a) 和 (b)，降低压缩率几个百分点，但速度大约提高四倍或十倍。

伪 RLE

RLE 可以使用大多数 LZ77 类型的解压缩器中的重叠副本模拟（“伪 RLE 模式”）。 解压缩器必须使用一种能够正确处理这种重叠副本的方法——特别是，解压缩器不能对这种重叠副本使用 memcpy() 或 memmove()。 在某些机器上，只需对所有副本使用相同的“一次复制一个字节”copy_bytes() 例程更快。 在其他机器上，程序员发现 memcpy() 比这快得多，如果解压缩器包含额外代码，可以针对每个复制项判断它是否重叠，并在 memcpy() 不起作用时仅使用较慢的 copy_bytes()，则可以减少总解压缩时间。