数据压缩/流压缩

文件与流压缩

许多数据压缩算法是面向文件的。它们假设底层传输协议已无误地传输了压缩数据文件的每个位。

一些数据压缩算法被设计用于与流式单向广播一起使用。例如，几乎所有地面数字电视使用的 MPEG-2 压缩算法。接收机可以在任何时间打开并开始收听广播。为了使接收机能够在流的中间启动——或在几秒钟的严重传输错误后恢复——这类系统通常将流分解成“块”。解码器使用同步标记或校验和来检测下一个块的开始，并从那里开始解码。在每个新块中，它会重新初始化并重新启动解码过程。使用静态每块字典或静态哈夫曼表的块解码器会忘记旧的字典或表，并在每个块的开头读取新的字典或表。使用自适应字典的块解码器会忘记旧的字典，重新初始化默认字典，并开始构建新的字典。

块大小是在压缩（更长的块通常会提供更好的压缩）和快速重启（更短的块允许解压缩器在发生错误或打开后更快地重启）之间的一种折衷方案。由于实际上所有错误都可以用 CRC 代码检测到，因此流式解码器知道哪些块有错误，通常会拒绝整个块。流式音频解码器使用各种技术来掩盖此类错误——它们可能会尝试使用对先前音调将持续的预测来“填补”。为了避免“咔嗒声”，它们可能会选择在最后一个有效块的末尾将音量调低以静音，在错误块期间播放静音，然后在下一个有效块的开头将音量调回到正常音量。

关于“块”的替代方案的研究很少。有些人推测，与使用 B 字节的块大小相比，使用经过设计的（非阻塞）收敛解码器，可能能够实现更好的压缩以及同样快的重启，这种解码器设计为无论何时打开解码器，最终都会在最多 B 字节后收敛到同一个自适应字典上。自适应块解码器在每个块的开头几乎没有上下文（压缩效果很差），并在块的末尾逐渐增加上下文（压缩效果更好）。非自适应块解码器在每个块的开头都有字典或哈夫曼表的开销（实际上，在字典或表期间压缩率为零，而在块剩余部分的数据期间压缩率很高）。理论上，收敛解码器在任何时候都具有一定的中间上下文（以及一定的中间压缩率），没有字典或表开销或压缩率低的时期。

数据包压缩

当数据作为小数据包交换时，通过使用数据包压缩，可以在给定的通信链路上传递更多同步会话。两种方法——报头压缩和有效载荷压缩——用于使数据包更小。

数据包头压缩

数据包有效载荷压缩

[待办：简单介绍一下“用于分组网络的延迟字典压缩”和其他分组感知有效载荷压缩算法]

我们将在本书中其他地方讨论的 PPP 预测压缩协议 是早期的数据包有效载荷压缩算法。

磁带存储压缩

数据压缩的最早应用之一是压缩用于备份磁带的数据。许多磁带驱动器在其固件中嵌入了一个数据压缩算法的实现。（对于现代计算机，可以通过关闭这种“硬件压缩”并使用现代“软件压缩”算法来获得更好的压缩。软件压缩算法利用了主处理器比磁带驱动器内部处理器快得多的 CPU 和大得多的 RAM。早期的计算机无法使用软件压缩，因为它们的速度不够快，无法跟上磁带的速度）。

许多磁带驱动器制造商使用 LZ 算法。IBM 和 QIC 使用 ALDC 算法。 Exabyte 使用 IDRC 算法。DLT 使用 DLZ1 算法。

VXA 磁带备份格式（由 Ecrix 开发，由 Exabyte 生产）使用 ALDC 数据压缩。

自适应无损数据压缩算法 (ALDC) 由 ECMA-222 标准化。

“线性磁带开放”（LTO）磁带备份格式（由多个制造商生产）使用 LTO-DC 数据压缩，也称为流式无损数据压缩 (SLDC)。

由于法律原因，许多数据压缩算法专利被描述为此类磁带备份存储系统的一部分。

实现细节

结束处理

大多数数据压缩算法都是用无限长度的抽象“数据流”来描述的。在实践中，数据几乎总是以具有明显开头和结尾的有限长度块的形式出现。压缩和解压缩此类数据的系统最终会到达数据块的末尾。

解压缩器如何知道何时停止？

有些人认为结束处理是“超出数据压缩范围的”。因此，许多程序员使用“单一职责原则”尝试将“结束处理”代码与“解压缩”代码分开——“结束处理”被认为是协议栈中其他层的职责。（这些其他层在其他书籍中进行了更详细的描述，例如 数据编码理论，通信网络，串行编程 等）。

存档文件格式通常将压缩数据存储在“容器格式”中，该格式存储压缩数据块以及一些元数据。 有 5 种流行的方法来实现此类存档格式和流协议。

1. 元数据包括

• 压缩长度（这使得更容易跳过存档中的压缩文件以仅解压缩一个所需文件），以及
• 解压缩长度（这使得解压缩器的实现更简单）

2. 元数据准确描述了*解压缩*数据中有多少位/字节/符号/像素。 解码容器格式的软件将此“未压缩长度”和压缩数据传递给解压缩器，解压缩器会准确记录到目前为止已生成多少位/字节/符号/像素，并在生成足够数量时停止。（有时，允许解压缩器将几个额外的位/字节/符号/像素解码到临时缓冲区中，然后将正确数量复制到最终输出中会更简单）。在某些系统中，解压缩器需要返回它消耗了多少*压缩*字节的计数，以便容器处理程序知道从哪里继续解码文件的下一部分。

3. 压缩数据存储在某种“容器格式”中，该格式包含描述*压缩*数据中到底有多少个有效位数的元数据。 解码容器格式的软件将此“压缩长度”和压缩数据传递给解压缩器，解压缩器会准确记录到目前为止它消耗了多少位。在某些系统中，解压缩器需要返回它生成的*解压缩*字节的计数，以便容器处理程序知道缓冲区中多少个解压缩字节是“真实”数据。

4. 压缩数据存储在某种“容器格式”中，该格式包含描述*压缩*数据中有多少字节的元数据，但最后一个字节中有效位的数量未知。（通常，压缩器会用 0 位填充压缩数据，直到它填满一个完整的字节。 解压缩器必须以某种方式弄清楚“这是一个恰好以一些（有效）零结尾的代码字”——特别是全零代码字——与“这不是一个真实的代码字，而仅仅是零填充”之间的区别。 处理这种区别的软件在所有情况下都 notoriously 难以完全正确且没有错误）。在某些系统中，解压缩器需要返回它生成的*解压缩*字节的计数，以便容器处理程序知道缓冲区中多少个解压缩字节是“真实”数据。

5. 压缩数据以一种既不知道“压缩长度”也不知“未压缩长度”的方式存储或传输，并且解压缩器必须以某种方式检测到结束并返回解压缩数据和“结束点”元数据给其他软件。

容器格式有时被描述为具有独立的“元数据部分”和“压缩数据部分”。 但是，在评估压缩效率时，我们必须将所有传递给解压缩器的*数据*视为“压缩大小”或“压缩率”——包括“压缩数据部分”和“未压缩数据大小”、“压缩大小（字节）”和“压缩大小（位）”等数据，这些数据通常被视为“元数据部分”的一部分。

有些人更喜欢这样设计的压缩数据格式，即将许多压缩文件连接成一个大文件，然后解压缩该大文件，“正常工作”——即它会生成一个大的解压缩文件，该文件与将所有原始解压缩文件连接成一个大输出文件相同。

进一步阅读

• 数字电视