序

我第一次编程时，连数据压缩是什么都不知道，更谈不上认识到它的重要性了。幸运的是，我的Apple II Plus计算机内存有0.000 048GB（约48 KB），这在1979年算是很大的内存了，足够让我去探索编程和计算机图形学。我当时完全没有意识到程序和数据在后台是不断压缩和解压缩的，从而减小了它们在内存中的大小。说到这里，真要感谢Woz ！

有了几年的编程经验后，我发现：

•数据压缩需要花费时间并可能会导致软件变慢；

•改变数据的组织结构可以让数据压缩得更小；

•复杂的数据压缩算法各式各样。

这使我意识到压缩不是一个刚性的黑盒，相反，它是一个灵活的工具，可以极大地影响软件的质量。我们可以通过以下几种方式运用压缩：

•改变压缩算法有可能让软件运行得更快；

•针对数据的组织结构选择正确的压缩算法，可以使数据变得更小；

•选择不匹配的数据组织结构或压缩算法，可能会导致数据变大或运行变慢。

如今我明白数据压缩为什么重要了。如果数据太大、内存不够，或者解压缩太慢，可以稍微改变一下数据的组织结构，以使它更好地适应压缩算法。比如，我会将数单独放在一组，字符串放在另一组，为重复出现的数据类型建表，或者将分数截断为整数。如果能让数据与算法匹配，我就无须去做评估与采用新的压缩算法这样的苦差。

后来，我开始做专业的电子游戏，大部分游戏数据是由艺术家、设计师和音乐家这样的非技术人员生成的。结果表明，数学不是他们最喜欢讨论的话题，而且他们对改变游戏数据以便更好地利用我的单向压缩算法不太感兴趣。好吧，既然数据的组织结构无法改善，剩下能做的就是选择最合适的压缩算法来与这些“伟大的”艺术数据匹配了。

我调查了各种数据压缩算法，发现有两大类很适合电子游戏数据：

无损方法

•去掉重复数据（LZ算法）

•熵压缩（哈夫曼编码、算术编码）

有损方法

•降低精度（截断或降采样）

•图像 / 视频压缩

•音频压缩

对文本字符串和二进制数据使用LZ算法，可以将完全重复的数据压缩掉。对像素数据使用有损的矢量量化（vector quantization，VQ）算法，可以将像素映射为调色板。对音频数据使用有损的降采样和线性预测编码（linear predictive coding，LPC）算法，可以减少每秒的二进制位数。如果CPU足够快，前述所有这些压缩算法的输出都可以再用无损的哈夫曼算法进行一次额外的统计熵压缩。

20世纪八九十年代，我参与制作了大约30个游戏，其中大多数使用的是这些算法，外加简单的数据构造工具对数据的组织结构进行有限的优化。

但是到了2000年左右，情况变得复杂起来。数据生成工具与数据展示和分析工具之间展开了持续的竞争。其结果是软件性能、存储大小、网络拥塞，以及压缩算法与数据组织结构的有效配对。

这种数据洪流被更大的存储空间（蓝光光盘、TB级的硬盘以及云存储）、更快的多核CPU、新的无损压缩算法（如BWT、ANS和PAQ），以及针对图像、视频、音频等数据的有损编解码器的巨大性能提升部分抵消了。然而，由于数据每年的增长速度太快，相比之下，网络带宽的增加、压缩算法的性能提升以及存储容量增长的速度就太慢了。

这些因素造成了我们的现状，这也是本书内容之所以重要的原因。

程序员怎么才能知道为数据选择哪种压缩算法，以及对数据做什么样的改变能使特定的算法表现得更好或更差呢？其实真正有帮助的是对主要的数据压缩算法进行介绍，指导开发人员从众多可用的算法中选择最合适的。大部分开发人员其实并不需要掌握实现这些算法所需要的所有理论和数学细节，他们只要知道这些算法的优缺点，以及在特定场景中怎样充分利用它们即可。

我很高兴在过去的37年里一直在实现和使用不同的数据压缩算法，并看到它们的发展变化。我希望这本书能揭开数据压缩的神秘面纱，为软件开发人员学习压缩算法提供一个起点，同时帮助他们开发出更好的软件。

John Brooks

Blue Shift公司首席技术官