1.3 关于数据压缩，你必须知道的

下面直接上干货。对数据进行压缩，通常有两个思路：

•减少数据中不同符号的数量（即让“字母表”尽可能小）；

•用更少的位数对更常见的符号进行编码（即最常见的“字母”所用的位数最少）。

好了，你需要知道的就是这些。

60年来的数据压缩研究都可以归结到上面两个重要思路上，数据压缩中的每一个算法都聚焦于解决这两件事情中的一件。每一个压缩算法，要么通过打乱符号或减少符号的数量，将数据转换得更便于压缩；要么利用其中一些符号比其他符号更常见的事实，通过用最少的位数编码最常见的符号，实现压缩的目的。

虽然数据压缩的思路简单明了，但在实际应用中数据压缩很复杂。其原因在于，由于要压缩的数据的类型不同，针对上述两条思路中的每一条，能采用的方法都有很多。因此，进行实际的数据压缩时，需要综合考虑以下些因素。

•不同数据的处理方法不同，比如压缩一本书中的文字和压缩浮点型的数，其对应的算法就大不相同。

•有些数据必须经过转换才能变得更容易压缩。

•数据可能是偏态的。例如，夏天的整体气温偏高，也就是说高气温出现的频率比接近零度的气温出现的频率高很多。

作为程序员，你面对的挑战就是，找出最好的方法或者方法组合来压缩用户给你的数据。而作为内容开发者，你面对的问题则是，如何在用户可接受的费用范围内将数据传递给用户。

亲爱的读者，这就是本书接下来的全部内容。它将作为指导手册，让你知道在数据压缩这一领域内有哪些知识值得关注，让你理解压缩算法理论上是怎样工作的，以便你能从中选择最适合的算法，并将它应用到你开发的那些酷炫的社交/移动/网络/多媒体应用程序数据上。

建立在数据压缩上的世界

我们需要知道这样一件事：我们当下生活在其中的这个计算世界，完全建立在数据压缩算法之上。

是的，每个部分都是如此。

每个网页、每个图像、每首歌、每个关于猫的视频、每个流媒体网络电影、每张自拍照、每次电子游戏下载、每个微型交易，甚至是操作系统的每次更新，所有这一切都得益于压缩算法。事实上，哪怕只是想通过互联网传输一个二进制位的数据，也离不开压缩的内容。

数据压缩技术最让人惊异之处在于，它与过去40年里个人计算的很多重大改变有关，但很少有人知道这一点。

例如，你是不是通常不买CD唱片，而是直接下载或在线听音乐？如果的确如此，那你需要感谢压缩算法。

1.音乐的压缩

时间回到1996年，一群来自不同公司的聪明人组成了一个联合工作组，推出了MP3这种文件格式。这种新的音频格式从此改变了计算机中音频的特性。当时，WAV格式才是创建、存储和传输音频数据的主流格式。几乎所有人在用WAV格式，但它存在一个很严重的问题，那就是文件特别大。一首3分钟的歌曲，文件的大小就将近30 MB，下载要花费9分钟左右，更别提流式播放了。

MP3格式出现之后，一首音频质量很好、3分钟左右的完整歌曲，文件大小只有1~3 MB。人们甚至可以将CD唱片放入计算机，并将其转换成MP3格式，以便以数字信号的形式来欣赏。

较小的文件大小与较高的音频质量，这两个优点相结合产生了我们这个时代最伟大的消费创新之一：Napster音乐共享平台。这项服务让音乐爱好者免费交换MP3文件成为可能。然而，由此也产生了一个很大的法律问题，那就是一些人在买了CD唱片之后将其转换为MP3，然后与朋友共享，这样他的朋友就可以免费听这些唱片了。如此一来，最终的结果你也能想象到，这种行为动了CD发行公司的奶酪，因而遭到了这些公司的强烈反对，他们动用了一切手段，最终成功地让Napster音乐共享平台关闭。

在20世纪90年代末至21世纪初，类似的法律纠纷很多，政府的政策也不断变化，试图阻止这种形式的音乐共享。甚至有人提出“使用MP3格式是非法的”的立法建议。

苹果公司没有参与打击这种新的数据格式，而是决定围绕它生产一个产品。1998年，苹果公司推出了iPod，这是最早的专门存储和播放MP3文件的便携式设备之一。随后，苹果公司又推出了iTunes商店，让顾客可以合法购买MP3文件供个人使用。

今天，数字音乐的发行已经成为新常态，很多公司尝试找到更好的方式来促进音乐的营销。

iPod这一产品的巨大成功，最终带来了iPhone的开发和发布，由此永远地改变了个人计算的面貌。（这是另外一个故事了。）

2.图像的压缩

让我们把时间再往回倒一些，回到互联网诞生的那一年，也就是1978年。当首批互联网连接建立起来的时候，能发送的数据量非常少。当时的用户也很少，网络主要用来发送和接收文本数据，或者如图1-1所示的完全用字符创建的图像。

当时的问题是，真实的图像信息以24位/像素格式存储，对早期的调制解调器来说这样的数据量实在是太大了。因此，压缩专家将图像压缩设为目标。为了测试新的图像压缩算法，他们需要一个图像语料库。在一个男性主导的行业中，他们更偏向于从男性杂志中寻找图片素材，最终选择了现在很著名的莱娜图（见图1-2），该图截取了1972年11月《花花公子》杂志中莱娜•瑟德贝里（Lena Söderberg）的一张照片的一部分。

在发表研究成果时，他们在论文中使用了裁剪后的PG-13版本的图像，并提供了原始的图像版本以供其他研究人员测试压缩算法。在很长一段时间内，莱娜图是用来测试图像压缩算法的标准测试图。幸运的是，从此以后，很少再出现这样有争议性的图像语料库。（我们两位作者则更喜欢使用柯达公司的图像测试集。）然而即使是今天，仍然有很多图像压缩方面的论文将莱娜图用作检验算法的标准。

3.视频的压缩

让我们快速回到2001年，这一年YouTube网站出现了，在这个网站上用户可以免费上传他们录制的任何视频，供所有人观看。

这时，视频信息的主流传输格式是MOV，然而因为这一格式不比将一系列JPG图像按顺序排列先进，所以相应的文件很大也就不足为奇了。因此，只加载网页就能观看视频的想法在当时实在是令人难以置信。

4.基因图谱

2008年，为了治疗人类疾病，降低疾病死亡率，科学家开始绘制和测试人类基因组。单个基因组序列就包含了大量的数据，仅仅是描述人类基因组成的数据就超过了14GB。这样的数据大小超出了大多数系统能处理的范围（当时云计算还不是热门话题）。

数据压缩再一次成为解决问题的利器。研究人员发现，BWT是最有效的存储DNA信息的压缩格式，甚至无须解压就能对数据进行操作。

到了2014年，研究人员通过将可扩展的云计算与主机之间的压缩数据传输结合起来，创造了全球最快的蛋白质折叠计算之一。

5.压缩与经济

通过前面的介绍，我们可以看到，数据压缩一直是推动计算技术与计算文化发生重大变化的核心力量。这背后的经济原理却很简单：压缩后的文件会变得更小。这也就意味着，同样的数据传输所需的时间会变短，相应的费用也会减少。分发者的分发成本会降低，消费者的支出也会减少。在当今这个计算时间就是金钱的时代，数据压缩可以说是缩短内容分发者和消费者之间距离最经济可行的方法。