数据压缩/评估压缩效率

当应用程序程序员决定使用哪种压缩算法时，需要权衡许多因素：

• 速度：它有多快？
• 压缩率：如果它不能使我们的数据比未压缩大小更小，那就没有意义。
• 复杂度：可执行文件有多大？（这既有硬成本——软件使用多少 ROM 或磁盘空间？——也有软成本——如果我需要更改它，需要多长时间才能浏览所有源代码以找到要更改的正确内容，以及更改后，需要多长时间才能测试代码的每个部分以确保更改不会破坏其他内容？）
• 空间：运行需要多少 RAM？
• 延迟：我需要等待多久才能听到歌曲的第一段？
• 互操作性：我生成的的文件可以被任何标准归档实用程序读取吗？

当压缩库程序员调整了压缩算法并试图确定它是否真的更好或者他是否应该恢复到以前的版本时，他会使用相同的标准。

速度

在评估数据压缩算法时，速度始终以每秒处理的未压缩数据量来衡量。

${\rm {speed}}={\frac {\rm {Uncompressed\;bits}}{\rm {seconds\;to\;process}}}$

对于流式音频和视频，

速度 = 一秒钟内可以处理的未压缩位数。

一些应用程序即使有足够的 RAM 和磁盘空间，也不需要缩小文件大小，也会使用数据压缩技术。文件压缩和增量压缩通常用于加快从慢速连接的一端到另一端的复制文件速度。即使在单台计算机上，某些类型的操作在压缩版本的数据上执行时也要比直接在未压缩数据上执行快得多。 特别是，一些压缩文件格式的设计使得压缩模式匹配——在压缩文本文件的压缩版本中搜索短语——比在原始未压缩文本文件中搜索相同的短语快得多。

（“zgrep”或“zcat”在这里相关吗？）

一些专门用于压缩位图的压缩算法——字节对齐位图代码 (BBC)、字对齐混合代码 (WAH)、位置列表字对齐混合代码 (PLWAH)、压缩自适应索引 (COMPAX) 和压缩 'n' 可组合整数集 (CONCISE)——允许将位运算直接应用于压缩数据。 这可能比解压缩数据、应用位运算，然后重新压缩结果快得多。

（FIXME：将以上内容的一部分移动到压缩域处理。）

解压缩速度

${\rm {speed}}={\frac {\rm {Compressed\;bits}}{\rm {seconds\;to\;decompress}}}$

在许多应用中，解压缩速度至关重要。如果在原型便携式音乐播放器硬件上运行的音频解压缩器特定实现无法持续向耳机提供 1.4 Mbit/s 的数据流，那么它就无法使用。除非您切换到不同的实现或更快的硬件（或两者兼而有之），否则没有人会购买它，这些硬件能够跟上标准立体声音频的速度。

压缩速度

${\rm {speed}}={\frac {\rm {Uncompressed\;bits}}{\rm {seconds\;to\;compress}}}$

在一些应用中，压缩速度至关重要。如果在原型语音记录器上运行的音频压缩器特定实现无法持续从麦克风向存储器提供 7 bits/sample/channel x 1 channel x 8 kSamples/s = 56 kbit/s 的数据流，那么它就无法使用。没有人希望他们的录音中出现静默间隙，因为硬件无法跟上。除非您切换到不同的实现或更快的硬件（或两者兼而有之），否则没有人会购买它，这些硬件能够跟上标准电话级语音速度。

解压缩速度和压缩速度

速度在不同机器之间，不同实现之间差异很大。即使在同一台机器上，使用同一基准文件和同一实现源代码，使用不同的编译器也可能使解压缩器运行速度更快。

压缩器的速度几乎总是比其对应解压缩器的速度慢。

即使使用现代快速 CPU，压缩文件系统的性能通常受压缩算法速度的限制。许多现代嵌入式系统（以及许多早期开发数据压缩算法的计算机）在速度上受到严格限制。只有少数压缩算法足够快，可以在速度极其受限的系统上使用：

• RLE；
• LZSS 家族中的算法；
• LZW 家族中的算法；
• 固定字节对编码，例如 PalmDoc；
• 增量编码 + 自适应霍夫曼。

… 还有其他吗？…

空间

许多现代嵌入式系统（以及许多早期开发数据压缩算法的计算机）在 RAM 方面受到限制。当可用 RAM 太小，无法容纳解压缩文本和单独的字典（例如 GIF 解码器为 LZW 字典所需的 12 KB 字典）时，很少有压缩算法能够在这种限制下工作。 由于 RAM 太少，

• 如果我们需要将整个解压缩文本保存在 RAM 中（例如自解压缩可执行文件），那么我们不得不排除 LZW，并使用解压缩文本作为字典，例如 LZ77 和 Pucrunch。
• 如果我们不需要将整个解压缩文本保存在 RAM 中（例如，外部调制解调器在将明文转发到 PC 之前，通过“慢速”电话链路解压缩发送的数据），那么对于任何给定的 RAM 量，LZW 类型的压缩格式通常比 LZ77 类型的压缩格式提供更好的压缩。对于典型的英文文本，在解压缩器的字典中存储的单词和短语越多，压缩效果就越好。LZ77 使用大量 RAM 来保存经常重复出现的常用词。LZW 使用可用 RAM 来存储每个唯一词一次，因此在 RAM 受到限制时，压缩效果比 LZ77 好。

在设计压缩文件格式时，通常会在变长格式和字节对齐格式之间进行速度/空间权衡。大多数系统可以更快地处理字节对齐格式。变长格式通常提供更好的压缩。字节对齐格式可以使用除 8 位数据以外的数据大小。 例如，许多 LZ77 类型的解压缩器使用字节对齐格式，其中包含 16 位“项目”，解压缩器将其分解为 3 位长度和 13 位偏移量。一些解压缩器使用 1 位、8 位和 16 位项目的组合，其中（为了速度）1 位项目小心地打包到 8 位“控制字节”中，因此其他所有内容都可以保持字节对齐。（在本书的后面，我们将更详细地讨论字节对齐格式：数据压缩/字典压缩#实现技巧和窍门）。

评估压缩率

在本书中，我们将压缩率定义为

${\rm {Compression\;Ratio}}={\frac {\rm {Uncompressed\;Size}}{\rm {Compressed\;Size}}}$

能够将 2 MB 压缩文件解压缩为 10 MB 文件的算法的压缩率为 10/2 = 5，有时写为 5:1（读作“五比一”）。

对于流式音频和视频，压缩率是根据未压缩和压缩比特率而不是数据大小来定义的

${\rm {Compression\;Ratio}}={\frac {\rm {Uncompressed\;Data\;Rate}}{\rm {Compressed\;Data\;Rate}}}$