数据压缩/多重变换

组合

早期的文本数据压缩技术被分为两种看似截然不同的方法

• 固定到可变解压缩器，将固定大小的“引用”解压缩为不同长度的明文字符串（齐夫和莱姆佩尔），以及
• 可变到固定解压缩器，将可变长度的“前缀码”或“算术码”解压缩为某个固定长度的明文字符串（马尔科夫）。

研究人员正在寻找一种将它们结合起来的方法，以获得两者的优势。

典型的文本段落有几种不同的模式。一些归档软件应用了一系列不同的变换，每个变换针对文本中的不同模式。

这种变换通常基于对文件生成方式的某种 模型。

压缩软件（尤其是图像压缩软件）通常将原始数据通过一个或多个去相关阶段——例如卡胡宁-洛夫变换、颜色空间变换、线性滤波、DFT、变换编码等——“预压缩”阶段——然后将结果馈送到熵压缩器中。

许多在压缩中使用的变换，与直觉相反，会产生需要更多位动态范围来存储的中间结果。将原始的 24 位 RGB 像素转换为 26 位 YCoCg-R 像素 或将原始的 16 位音频样本转换为 17 位 delta 编码差异，似乎“浪费”了位，但它提高了网络压缩性能：在许多情况下，熵压缩器在得到这种“去相关”的中间数据时，比在得到原始数据时，能得到更小的压缩文件大小。（这种变换导致的结果改进通常被称为“编码增益”。）

颜色变换

JPEG 2000 可逆颜色变换 (RCT) 是一种类似 YUV 的颜色空间，它不会引入量化误差，因此它是完全可逆的。

压缩器将 RGB 转换为 YCbCr，使用

$Y=\left\lfloor {\frac {R+2G+B}{4}}\right\rfloor ;C_{B}=B-G;C_{R}=R-G;$

然后压缩图像。

解压缩器解压缩图像，然后获取 YCbCr 像素，并使用以下公式恢复原始 RGB 图像

$G=Y-\left\lfloor {\frac {C_{b}+C_{r}}{4}}\right\rfloor ;R=C_{R}+G;B=C_{B}+G.$

JPEG 2000 YCbCr 格式中的一个像素需要 26 位来无损地表示。

图像的红色、绿色和蓝色层通常高度相关。因此，独立压缩 R、G 和 B 层最终会将相同数据存储 3 次。

即使将 24 位/像素的 RGB 图像“去相关”为 YCbCr 需要 *更多* 位（26 位）来保存每个像素，去相关也有助于压缩管道中的后续阶段做得更好。因此，独立压缩 Y、Cb 和 Cr 平面通常会导致比独立压缩相同文件的 R、G 和 B 层更小的压缩文件。

大多数（但不是全部！）无损颜色空间变换，包括 JPEG 2000 RCT，都是“扩展”的。“扩展”的颜色空间变换将 24 位 RGB 像素转换为需要 *超过* 24 位来无损表示的中间 YCbCr 像素。

一些无损颜色空间变换是非扩展的。“非扩展”的颜色空间变换将 24 位 RGB 像素转换为需要相同 24 位来无损表示的中间 YCoCg24 像素。

所有将 24 位 RGB 像素转换为小于 24 位/像素的颜色空间变换都是有损的。（我需要说明为什么吗？）。

音频变换

音乐

…（填写更多细节）…

大多数现代的有损音频编解码器使用修改后的离散余弦变换 (MDCT) 作为去相关阶段（如 Vorbis、AAC 和 AC-3）或作为去相关阶段之一（如 MP3 和 ATRAC）。

语音

语音压缩通常使用一个关于人声的相对简单的模型。声门以某种频率发出嗡嗡声。声道的共振或阻尼了该频率及其谐波。舌头和嘴唇偶尔发出嘶嘶的摩擦音和爆破音。

通过以每秒 30 到 50 帧的速度更新线性预测编码模型，可以以低比特率重建相当清晰的语音声音。

有几种方法可以表示线性预测滤波器系数。

虽然原则上线性预测滤波器系数可以直接传输，但通常系统被设置成这样（在熵解码后）接收到的比特表示反射系数， 对数面积比，线谱对，或滤波器系数的其他表示。

Codec2

... (填写详细信息) ...

DEFLATE

DEFLATE 将 LZ77 与霍夫曼编码相结合。它在 RFC 1951 中有说明。

它被广泛用于解码 ZIP 文件、gzip 文件和 PNG 图像文件。

zlib

"zlib 压缩数据格式规范" 是一种标准化方式，用于将压缩数据打包到文件中，它有一个简单的头文件，用于指示压缩类型并帮助检测最常见的 数据损坏类型。它通常用于存储用 DEFLATE 压缩的数据，窗口大小高达 32K。

"zlib 压缩数据格式规范" 在 RFC 1950 中有说明。

LZX

LZX 文件格式和压缩算法是由 Jonathan Forbes 和 Tomi Poutanen 发明的。LZX 用于流行的独立 AMIGA 文件存档器。Microsoft 压缩 HTML 帮助 (CHM) 文件使用 LZX 压缩。Windows Imaging Format (".WIM") 文件支持多种数据压缩方法，包括 LZX。Xbox Live Avatars 使用 LZX 压缩。

LZX 同时使用 LZ77 样式的滑动窗口压缩和动态霍夫曼代码，有点类似 DEFLATE 同时使用两者。LZ77 样式的窗口大小 (WINDOW_SIZE) 是 2 的幂，至少是 2^15，最大是 2^21。LZX 使用多个霍夫曼树结构，每个结构都是规范的。

LZX 中最重要的霍夫曼树是 "主树"，它由 256 个元素组成，对应所有可能的 ASCII 字符，另外还有 8*NUM_POSITION_SLOTS 个元素，对应匹配项。（NUM_POSITION_SLOTS 的范围在 30 个槽到 50 个槽之间）。LZX 中第二重要的霍夫曼树是 "长度树"，它由 249 个元素组成。其他树的作用较小。

LZX 压缩器任意地将一个文件分成一个或多个块。每个块有 3 种类型："逐字块"、"对齐偏移块"、"未压缩块"。"未压缩块" 在头文件中包含更多内容，然后是未压缩数据的逐字副本。

在 "逐字块" 和 "对齐偏移块" 块的数据部分中，LZX 使用长度受限的霍夫曼码字；LZX 将每个码字限制在最多 16 位宽。每个 "逐字块" 和 "对齐偏移块" 都有一个更大的头文件，用于提供信息（以非常紧凑的差分压缩形式）供解码器生成用于该块的各种霍夫曼树。

头文件被解码以获取每个符号的码字长度，长度为 0 到 16 位（含），其中 "0 位" 表示相应的符号在该块中从不出现，"16 位" 用于非常罕见出现的符号。使用各种技术将头文件压缩成相对较少的位。

当 "距离" 值被解码时，存在一些特殊值。英文文本中两个长短语 *几乎* 相同的情况很常见，但中间可能存在一个小小的拼写错误或替换。使用原始 LZ77，结果是 3 个复制项：[到第一部分的长距离 X，第一部分的长度]、[到插入的距离 Y，插入的长度]、[与开始处的第二部分完全相同的长距离 X，第二部分的长度]。LZX 不会重复完全相同的长距离 X 两次，而是使用一个特殊的 "距离" 值来指示我们正在 "继续" 复制前面的块，并在中间进行替换。（特殊距离值最终占用的位数少于完整长距离）。

• "距离" == 0："重复最近的匹配距离，它本身不是重复距离"
• "距离" == 1："重复第二最近的匹配距离，它本身不是重复距离"
• "距离" == 2："重复第三最近的匹配距离，它本身不是重复距离"
• 距离 == 3：从 1 字节前开始复制，最近解码的字节（字节上的伪 RLE），最接近的允许值。
• 距离 == 4：从 2 字节前开始复制，第二最近解码的字节（字节对上的伪 RLE）
• 距离 == 5：从 3 字节前开始复制
• 距离 == 6：从 4 字节前开始复制
• ...
• 距离 == 1000：从 998 字节前开始复制
• ...
• 距离 = x+2：从 x 字节前开始复制
• ...
• 距离 == WINDOW_SIZE-1（所有位都高）：从 WINDOW_SIZE-3 字节前开始复制，最远的复制可能。

解码器使用块头文件设置所有树后，解码器在逐字块中的主循环为

• 使用主树从压缩文本中读取一个码字，并将其解码成一个 "主元素"。
• 如果 "主元素" 小于 256，则将 "主元素" 作为逐字明文字节发出。
• 如果 "主元素" 大于或等于 256，我们将有一个复制项。
  • 将 "主元素 - 256" 分成两部分："槽" 和 3 位 "长度"。
  • 如果 "长度" 是特殊的全 1 值 "7"，则使用 "长度树" 从压缩文本中读取另一个码字，并将其解码成一个 "长长度"；将其添加到长度中已有的 7。
  • 如果 "槽" 的范围是 0..3，则将距离设置为与槽相同。
  • 如果 "槽" 的范围是 4..37，则需要 extra = ((slot >> 1) - 1) 个额外位才能获得确切的距离。
    • 从压缩文本中读取这些额外的原始 "尾部" 位（不使用任何霍夫曼树，只读取原始位）。距离（以二进制形式）是一个隐含的 1 位，后跟 (slot & 1) 位，然后是额外的原始尾部位。
  • 如果距离是 0..2，它表示一个 "重复距离"（如上所述）-- 用我们之前使用的实际距离替换它。
  • 从先前解码的明文中进行正常的 LZ77 样式复制：从距离（如上所述）复制 "长度 + 2" 个字节到解码的明文中。
• 重复，直到我们解码了头文件中指定的未压缩明文应包含的总字节数。

解码器使用块头文件设置所有树后，解码器在对齐块中的主循环为

• 使用主树从压缩文本中读取一个码字，并将其解码成一个 "主元素"。
• 如果 "主元素" 小于 256，则将 "主元素" 作为逐字明文字节发出。
• 如果 "主元素" 大于或等于 256，我们将有一个复制项。
  • 将 "主元素 - 256" 分成两部分："槽" 和 3 位 "长度"。
  • 如果 "长度" 是特殊的全 1 值 "7"，则使用 "长度树" 从压缩文本中读取另一个码字，并将其解码成一个 "长长度"；将其添加到长度中已有的 7。
  • 如果 "槽" 的范围是 0..3，则将距离设置为与槽相同。
  • 如果 "槽" 的范围是 4..37，则需要 extra = ((slot >> 1) - 1) 个额外位才能获得确切的距离。
    • 如果 extra > 3，则从压缩文本中读取 (extra - 3) 个原始 "尾部" 位（不使用任何霍夫曼树，只读取原始位）。然后使用 "对齐树" 从压缩文本中读取另一个码字，并将其解码成 3 位（0 到 7）。距离（以二进制形式）是一个隐含的 1 位，后跟 (slot & 1) 位，然后是 (extra - 3) 个原始尾部位，最后是 3 个对齐位。
    • 如果 extra = 3，则使用 "对齐树" 从压缩文本中读取另一个码字，并将其解码成 3 个对齐位（0 到 7）。距离（以二进制形式）是一个隐含的 1 位，后跟 (slot & 1) 位，然后是 3 个对齐位。
    • 如果 extra 是 1 或 2 位，则从压缩文本中读取这些额外的原始 "尾部" 位（不使用任何霍夫曼树，只读取原始位）。距离（以二进制形式）是一个隐含的 1 位，后跟 (slot & 1) 位，然后是额外的原始尾部位。
  • 如果距离是 0..2，它表示一个 "重复距离"（如上所述）-- 用我们之前使用的实际距离替换它。
  • 从先前解码的明文中进行正常的 LZ77 样式复制：从距离（如上所述）复制 "长度 + 2" 个字节到解码的明文中。（最小复制长度为 2 个字节）。
• 重复，直到我们解码了头文件中指定的未压缩明文应包含的总字节数。

Microsoft "cabinet" (".CAB") 压缩存档文件格式支持 3 种数据压缩方法：DEFLATE、LZX 和 Quantum 压缩。将可执行文件放入 ".CAB" 存档的压缩器可以可选地 "检测 "CALL" 指令"，将其操作数从相对寻址转换为绝对寻址，因此对相同位置的调用会产生压缩器可以匹配的重复字符串，从而提高 80x86 二进制代码的压缩率。"。CAB" 解压缩器在执行上述 LZX 解压缩后，如果头文件中的 "预处理" 位被设置为 1，则必须将这些操作数转换回相对寻址。我们将在后面的章节中更详细地讨论这种预处理器/去相关器，以及 可执行文件压缩。

LZX DELTA

LZX DELTA (LZXD) 是 LZX 的变体，经过修改以支持有效的增量压缩（修补）。

LZX DELTA 解压缩器接收某个明文文件的旧版本（必须与压缩器使用的旧版本完全相同）和 LZXD 压缩的补丁文件，并使用它们生成该明文文件的新版本。

LZXD 和 LZX 之间的主要区别在于，窗口预先加载了参考文件，解压缩器将输出文件的第一个字节解码到窗口中，该位置紧接在参考文件的最后一个字节之后。正常的 LZX 复制项的距离最大为回到输出文件的第一个字节的完整距离；LZXD 允许距离远得多，以允许从参考文件中进行复制。

LZXD 支持更多 "槽"，最多 290 个槽，它们被编码到主树中。这允许 LZXD 复制项从更远的过去获取内容，使其能够利用非常长的参考文件。

LZXD 还支持更大的 "长度" 值。与 LZX 具有 0 到 7 的 "短长度" 一样，其中 "7" 用作转义符，以从 7 到 255 获取 "长长度"，LZXD 使用相同的 "短长度" 和 "长长度"，并更进一步，使用 "257" 的长长度作为转义符，以获得 "超长长度"，可以在单个复制中复制 32 KByte。

LZARI

LZARI 使用 LZSS 预处理器，然后进行算术编码。LZARI 由奥村晴彦开发。

LZH

LZH 使用 LZSS 预处理器，然后进行霍夫曼编码。LZH 由吉崎春康为 LHA 归档器开发，基于 LZARI。

LZB

LZB 压缩器使用 LZSS 预处理器，然后对“匹配长度”和“偏移量”进行 Elias gamma 编码。（此附加步骤使 LZB 比单独的 LZSS 具有更好的压缩率，但运行速度更慢）。

LZB 的压缩率与 LZH 和 LZARI 大致相同，但更简单、更快， 因为像 Elias gamma 编码这样的通用代码比霍夫曼编码或算术编码（分别）更简单、更快速地解码。

LZMA

Lempel-Ziv-Markov 链算法 (w:LZMA) 使用一种类似于 LZ77 的压缩算法，其输出通过范围编码进行编码。

LZMA 是开源 7-Zip 文件归档器中使用的压缩方法之一。

LZMA 的类似 LZ77 的压缩部分与 LZX 的类似 LZ77 的压缩部分有许多相似之处。LZMA 不使用霍夫曼代码——而是使用上下文编码的二元算术代码。

LZHAM

LZHAM（LZ、霍夫曼、算术、马尔可夫）是 Richard Geldreich, Jr. 的通用无损数据压缩库。LZHAM 的不稳定/实验版本和“比特流兼容性”稳定版本都根据 MIT 许可发布。

LZW 和霍夫曼编码

有些人将 LZW 和霍夫曼编码结合在一起。

此类系统的解码器从压缩文件中读取一系列霍夫曼代码。解码器将每个可变长度的霍夫曼代码解码成一个中间固定长度的 12 位索引。对于典型的纯文本文件，这些 12 位数字中有一些的使用频率远高于其他数字，因此被分配了小于 12 位的霍夫曼代码。然后，解码器使用 LZW 解码器来恢复与该中间索引相关的原始可变长度的纯文本（1 个或多个字符）。

实施技巧

许多压缩文件格式必须使用熵解码器解压缩，然后进行一系列转换——一种 维基百科：管道（软件）。

有 4 种方法可以实现此类解压缩器（以及相应的压缩器）

• 多遍压缩：每个内部转换从某个临时文件读取所有输入，并将所有输出写入某个临时文件，然后下一阶段开始。
• 几乎同时运行每个阶段
  • 使用协程或线程或进程或 Unix 管道。遗憾的是，这些技术在许多嵌入式系统环境中不受支持。
  • 使用解压缩函数调用“向下”以获取更多数据。外部应用程序仅直接调用最终转换阶段，该阶段调用某个中间转换阶段，该阶段调用另一个中间转换阶段，该阶段调用管道开始处的熵解码器，该解码器调用从文件获取字节的例程。外部应用程序反复调用该最终转换阶段，直到所有数据都被处理。
  • 使用解压缩函数返回“向上”以获取更多数据。外部应用程序直接依次调用每个阶段。每个阶段从其输入缓冲区读取数据，更新其内部状态，并将数据写入其输出缓冲区。该输出缓冲区是下一阶段的输入缓冲区。外部应用程序反复循环遍历所有阶段，直到所有数据都被处理。

将软件从“调用向下以获取更多数据”的 API 转换为“返回向上以获取更多数据”的 API 很困难。

加密

由于先加密后压缩不会使文件变小，因此许多人使用先压缩后加密。

由于现代 CPU 处理数据的速度快于从旋转磁盘或大多数外部闪存驱动器读取数据的速度，因此有可能在比读取和写入包含相同数据的普通纯文本文件所需的时间更短的时间内读取和写入压缩的加密文件。

一些人正在研究同时压缩和加密的算法。

一些研究人员通过尝试压缩加密数据来测试加密算法。许多加密算法专门设计用于产生“与随机噪声无法区分”的密文。 当尝试实施此类算法时，如果压缩产生的压缩输出文件小于加密的输入文件，则表明加密软件存在缺陷——要么是实现中的错误，要么是安全算法的正确实现。

实施技巧

一些使用无损压缩的人更喜欢使用“幂等”（有没有更好的术语？）压缩软件，即使压缩时间稍微长一些。 换句话说，他们期望当你用“最大压缩”（通常是“-9n”）压缩一个文件以创建一个压缩文件，然后解压缩它，然后重新压缩它时，他们期望得到的第二个压缩文件与第一个压缩文件相同。

（这“幂等”是否与其他人所说的“确定性”相同？ ）

这通常要求每个转换实现（至少在传递“-9n”选项时）都是幂等的。一些非幂等的因素（因此应避免，至少在传递“-9n”选项时）是

• 一些压缩器在压缩文件中存储原始文件名和未压缩文件的日期戳。为了幂等，要么压缩器必须省略名称和日期戳（这就是“-n”通常做的事情），要么解压缩器必须恢复原始名称和日期戳。
• 颜色转换（如果有）应该是可逆的（无损）
• 对于任何给定的解压缩算法实现，几乎总是有很多不同的方法来表示原始文件——有很多压缩文件会产生完全相同的输出文件。（例外是“双射压缩”。）当试图获得“最大压缩”时，我们选择最短的方法——但即使那样，通常也会有几种方法会得到相同的压缩文件大小。为了幂等，压缩器的实现必须始终选择相同的方法。

一些信息论术语

(待办事项: 将上面的“幂等”替换为“非漂移有损”，如下定义？或者有更好的术语？)

一些信息论专家 将变换分类为 4 类损耗

• 双射 (ED = 1 且 DE = 1)
• 幂等 (无损但不是双射: ED = 1 但 DE !=1)。几乎所有为文本或可执行代码设计的压缩算法都属于此类。
• 非漂移有损 (EDE = E)。大多数为音频、视频和静止图像设计的压缩算法都属于此类。量化是非漂移有损变换。从初始图像 I0 开始，第一个编码/解码循环会得到一张稍微不同的图像 I1（希望只有正常人不太可能注意到的差异）。从 I1 开始，编码/解码生成 I2，然后编码/解码 I2 生成 I3，不会产生更多损失: I1 == I2 == I3 == I4 ...
• 一般情况: 退化。每个编码/解码循环通常都会生成一张略微不同的图像（例如一系列传真传输或使用物理纸张复印机进行多代复制）。

有些变换已知不能完全消除所有冗余。特别是，研究人员设计了特殊的 LZ77 编码器和 LZW 编码器，这些编码器在选择复制副本时对额外的“冗余位”进行编码，这种方法是向后兼容的: 标准 LZ77 或 LZW 解码器可以提取原始文件。特殊的 LZ77 或 LZW 解码器可以提取原始文件以及这些额外的“冗余位”。这些额外位可用于 Reed-Solomon 或其他形式的纠错，或用于存储有关原始文件的信息，例如公钥签名或消息身份验证代码。

网络稀疏化

网络稀疏化在数据压缩中有应用。