本节书摘来自异步社区《计算机科学概论（第12版）》一书中的第1章1.9节数据压缩，作者【美】J. 格伦•布鲁克希尔（J. Glenn *shear） , 丹尼斯•布里罗（Dennis Brylow）,更多章节内容可以访问云栖社区“异步社区”公众号查看。
*1.9 数据压缩
为了存储或传输数据，在保留原有内容的同时，缩小所涉及数据的大小是有益的（有时也是必须的）。用于完成这一过程的技术称为数据压缩（data compression）。本节，我们首先要学习一些普通的数据压缩方法，然后要了解一些为特殊应用设计的方法。
1.9.1 通用的数据压缩技术
数据压缩方案有两类，一类是无损的（lossless），另一类是有损的（lossy）。无损方案在压缩过程中是不丢失信息的，有损方案在压缩过程中会丢失信息。通常有损技术比无损技术更能压缩，因此在可以容忍小错误的应用中很流行，如图像和音频压缩。
对于被压缩数据由一长串相同的数值组成的情况，普遍使用称为行程长度编码（run-length encoding）的压缩技术，这是一种无损方法。它的过程是，将一组相同的数据成分替换成一个编码，指出重复的成分以及其在序列中出现的次数。例如，指出一个位模式包括253个1，接着118个0，接着87个1，这样要比实际列出458个位节省空间。
另外一种无损数据压缩技术是频率相关编码（frequency-dependent encoding），在这个系统里，用于表示数据项的位模式的长度与这个项的使用频率是反相关的。这种编码是变长编码的例子，意思是项由不同长度的模式表示。戴维·赫夫曼的功劳是发现了一般用于开发频率相关编码的算法，人们一般称用这种方法开发的编码为赫夫曼编码（Huffman code）。因此，现在使用的大多数频率相关编码都是赫夫曼编码。
让我们看一个频率相关编码的例子，考虑一下编码英文文本的任务。在英文中，字母e、t、a和i的使用频率要大于字母z、q和x。因此，当为英文文本编码时，如果用短位模式表示前面的字母，用长位模式表示后面的字母，那么就能节省空间。结果得到的编码中，英文文本的表示长度要比用统一长度编码时的短。
在某些情况下，压缩的数据流由各个数据单元组成，每一个数据单元与其前面一个差别很小。动画的连续帧就是一个例子。这时，使用相对编码（relative encoding）——也称为差分编码（differential encoding）——技术是很有用的。这些技术记录下了两个连续数据单元之间的区别，而不是全部单元；也就是说，每个单元是根据其与前一个单元的关系被编码的。相对编码用无损形式或有损形式都可以实现，具体取决于两个连续数据单元之间的差别是精确编码还是近似编码。
还有其他流行的基于字典编码（dictionary encoding）技术的压缩系统，这里的术语字典（dictionary）指的是一组构造块，压缩的信息通过它们建造起来，而信息本身被编码成字典的一系列参照符。我们一般认为字典编码系统是无损系统，不过在学习图像压缩时我们将看到，有时候字典条目仅仅是正确数据成分的近似值，这就使其成了有损压缩系统。
字处理程序可以使用字典编码来压缩文本文档，因为这些字处理程序中已经包含了用于拼写检查的字典，而这些字典都是出色的压缩字典。特别值得一提的是，一个完整的单词可以编码成字典的一个单独参照符，而不是像使用UTF-8系统那样编码成一系列单独的字符。在字处理程序中，一个典型的字典大约有25 000个条目，这就意味着，单个的字典条目可以用0到24999范围内的整数来标识。也就是说，字典中的一个特定条目用15位的模式就足可标识。相反，如果用到的单词包括6个字母，则它的逐字符编码在使用UTF-8时需要48位。
字典编码的一个变体是自适应字典编码（adaptive dictionary encoding，也称动态字典编码）。在自适应字典编码系统中，字典在编码过程中是可以改变的。一个流行的例子是LZW编码（Lempel-Ziv-Welsh encoding），这个编码的名称是根据它的创造者Abraham Lempel、Jacob Ziv和Terry Welsh的姓氏命名的。要用LZW对信息编码，首先要从包含基础构造块的字典开始，用字典中的构造块来构造信息。但是，当人们在信息中发现更大的单元时，会把它们加到字典上——这意味着，这些单元在未来出现时可以被编码为一个（而不是多个）字典参照符。例如，当对英文文本编码时，人们首先要从包含单独字符、数字和标点符号的字典开始。但是，当信息中的单词被标识后，会被加到字典中。因此，随着信息的不断编码，字典会不断增大，而随着字典的不断增大，信息中会有更多的单词（或者重复的单词模式）被编码为单个的字典参照符。
结果是，信息用一部相当大的、完全针对本信息的字典进行编码。但是在对这条信息进行解码时，不必用这个大字典，只需要用原始的小字典即可。事实上，解码过程可以与编码过程用同一个小字典。接着，随着解码进程的继续，会遇到编码过程中发现的相同单元，因此可以将它们加到字典中，作为未来编码过程的参照符。
举例说明，考虑对下列信息应用LZW编码：
xyx xyx xyx xyx
首先从一个只有3个条目的字典开始，第1个条目是x，第2个条目是y，第3个条目是空格。我们先将xyx编码为121，意思是这个信息的第一个模式依次包括第一个字典条目、第二个字典条目、第一个字典条目。接着，空格被编码产生结果1213。但是因为有了一个空格，我们知道前面的字符串已经形成了一个单词，所以我们将模式xyx加到字典里作为第4个条目。继续使用这种编码方式，整个信息将被编码为121343434。
如果我们现在从原始的3条目字典开始对这条信息进行解码，那么我们首先要将起始的1213串解码为xyx加1个空格。这时我们意识到xyx串形成了一个单词，因此将其加到字典中作为第4个条目，同编码过程中所做的一样。我们接着对这个信息解码，发现信息中的4指的是这第4个新条目，将其解码为单词xyx，因此产生模式：
xyx xyx
继续使用这种解码方式，我们最终把121343434串解码为：
xyx xyx xyx xyx
这就是原始信息。
1.9.2 图像压缩
在1.4节中，我们已经看到如何用位图技术对图像编码。不过，得到的位图通常是非常大的。因此，人们专门为图像表示开发出了许多压缩方案。
一种称为GIF（是graphic interchange format的缩写，即图像交换格式，一些人将其读作“Giff”，还有一些人将其读作“Jiff”）的系统是一个字典编码系统，由CompuServe公司研制开发。它处理压缩问题的方法是，将赋予一个像素的颜色数量减少到只有256个。每一种颜色的“红—绿—蓝”组合都用3个字节编码，这256个编码被存储在一个称为调色板的表格（一个字典）里。图像中的每个像素都可以用一个字节表示，该字节的值指出了这个像素的颜色是由256个调色板条目中的哪一个表示的。（回顾：一个字节能够包括256个不同位模式中的任意一个。）需要注意的是，在将GIF应用于任意图像时，它是一个有损压缩系统，因为调色板中的颜色可能与原始图像中的颜色不一致。
通过使用LZW技术将这个简单的字典系统扩展为自适应字典系统，GIF可以进一步压缩。尤其是，编码过程中遇到的像素模式可以被加到字典中，使得这些模式在将来出现时可以被更加高效地编码。因此，最终的字典是由原始调色板和一组像素模式构成的。
GIF调色板中的某一个颜色通常会被赋予值“透明”，意思是背景色可以透过每一个被赋予该“颜色”的区域表现出来。这个选择，与GIF系统的相对简便性相结合，使得GIF成为简单动画应用（这动画应用中的多重图像必须在计算机屏幕上移动）的合理选择。另一方面，它只能够对256种颜色编码，这使得它不适合精确度要求较高的应用，如摄影领域。
另外一种流行的图像压缩系统是JPEG（读作“JAY-peg”）。它是由ISO中的联合图像专家组（Joint Photographic Experts Group，标准因此得名）研制开发的标准。JPEG已经被证明是压缩彩色照片的一种有效标准，并被广泛用于摄影业，这一点可由大多数数码相机都将JPEG作为它们默认的压缩技术这一事实来证明。
JPEG标准实际上包含多种图像压缩方法，每种都有它自己的目标。在需要绝对精确的情况下，JPEG可提供无损模式。不过，相对于JPEG的其他模式，JPEG的无损模式不能形成高级别的压缩。而且，JPEG的其他模式已被证明很成功，这就意味着人们很少使用其无损模式。相反，称为JPEG基线标准（也称为JPEG的有损顺序模式）的JPEG模式已经成为许多应用的选择标准。
使用JPEG基线标准的图像压缩有几个步骤，其中有一些是利用人眼的局限性设计的。尤其是，相对于颜色的变化，人眼对亮度的变化更为敏感。因此，我们首先来看一幅用亮度成分和色度成分进行编码的图像。第一步是在一个2×2的像素方块中求色度的平均值。这能将色度信息的大小减小为$\frac{1}{4}$，同时保留所有的原始亮度信息。结果是，在没有明显损失图像质量的情况下获得了很高的压缩率。
下一步是将图像划分成8×8的像素块，然后将每一个块作为一个单元来压缩信息。这是通过一种称为离散余弦转换的数学技术实现的，我们现在不需要关心这个转换的细节。更重要的是，这种转换将原始的8×8块变成了另外一种块（这种块中的条目反映了原始块中的像素之间是如何相互联系的），而不是实际像素值。在这个新块里，那些低于预定极限的数值将被0替代，反映的是这些数值所表示出的变化非常小，人眼无法觉察。例如，如果原始块中包含一个棋盘（checkerboard）模式，那么新块就可能表现为平均色。（一个典型的８×８像素块表示的是图像中一个非常小的方块，因此人眼根本不能够识别棋盘的外观。）
这时候，可以应用更传统的行程长度编码、相对编码以及变长编码技术进行进一步的压缩。总之，JPEG基线标准一般能在没有明显质量损失的情况下，将彩色图像压缩至少10倍，有时甚至能压缩30倍。
另外一个数据压缩系统是TIFF（tagged image file format的缩写，即标记图像文件格式）。不过，TIFF最普遍的应用不是数据压缩，而是存储照片及其相关的信息（如日期、时间以及相机设置）的一个标准格式。在存储照片时，图像本身通常会被存储为没有压缩的红、绿、蓝像素成分。
TIFF标准集合里的确有数据压缩技术，其中大多数是为在传真应用中压缩文本文档的图像设计的。为了利用文本文档包含长串的白色像素这一事实，这些标准使用了行程长度编码的变体。TIFF标准中的彩色图像压缩选择是以类似于GIF所使用的技术为基础的，因此并没有被广泛应用于摄影业。
1.9.3 音频和视频压缩
音频及视频的编码和压缩最常用的标准是由ISO领导的运动图像专家组（Motion Picture Experts Group，MPEG）研制开发的，因此这些标准称为MPEG。
MPEG包含许多不同应用的各种标准。例如，高清晰度电视（high definition television，HDTV）广播的要求与视频会议的就不同，广播信号必须找到在各种容量可能很有限的通信路径上传输的方式。另外，这两种应用又都不同于存储视频的应用，它的有些部分可以被重放或略过。
MPEG使用的技术已经超出了本书的范围，但是一般说来，视频压缩技术是以图片序列构建成的视频为基础的，与将运动图像录制到胶片上的方式基本相同。为了压缩这些序列，只有一部分称为I帧（I-frame）的图片是被整个编码的。在两个I帧之间的图片是采用相对编码技术进行编码的，即并没有对整个图片进行编码，而只是记录了与前一个图片的差别。I帧本身经常使用类似于JPEG的技术压缩。
最著名的音频压缩系统是MP3，它是在MPEG标准中开发出来的。事实上，MP3是MPEG layer 3的缩写。与其他压缩技术相比，MP3利用人耳的特性，删除了人耳觉察不到的细节。其中一个特性称为暂时模糊（temporal masking），指的是在一次巨大声响后，短时间内人耳觉察不到本可以听见的轻柔声音。另一个称为频率模糊（frequency masking），指的是某一频率的声音可能掩盖相近频率的轻柔声音。利用这些特性，可以通过MP3获得显著的音频压缩，而且保持接近CD的音质。
使用MPEG和MP3压缩技术，摄像机用128 MB的存储空间就可以录制长达1小时的视频，便携音乐播放器用1 GB的存储空间就可以存储多达400首流行歌曲。但是，不同于其他压缩目的，音频和视频的压缩目的不一定是节省存储空间。真正重要的是获得编码，使得信息能够通过现在的通信系统得到及时的传输。如果每一个视频帧需要1 MB的存储空间，而传播帧的通信路径每秒只能传输1 KB，那么根本无法实现成功的视频会议。因此，除了被认可的复制质量，音频和视频压缩系统的选择还要看及时数据通信的传输速度。这些速度通常用比特每秒（bits per second，bit/s）来度量。常见的单位包括Kbit/s（kilo-bps的简写，即千比特每秒，等于103 bit/s）、Mbit/s（mega-bps的简写，即兆比特每秒，等于106bps）和Gbit/s（giga-bps的简写，即吉比特每秒，等于109 bit/s）。使用MPEG技术，视频展示可以在40 Mbit/s传输速率的通信路径上成功传输。MP3录制需要的传输速率一般不超过64 Kbit/s。
问题与练习
1．列出4种通用的压缩技术。
2．如果使用LZW压缩，并且最初字典只包含x、y和一个空格（如文中所述），对下列信息编码，结果是什么？
xyx yxxxy xyx yxxxy yxxxy
3．在对彩色卡通编码时，为什么GIF比JPEG要好？
4．假设你是航天器设计团队的一员，要设计能驶向其他星球并发回照片的航天器。那么，为了减少存储和传输图像所需的资源，使用GIF或JPEG的基准标准压缩照片是否是一个好主意？
5．JPEG的基准标准利用了人眼的什么特性？
6．MP3利用了人耳的什么特性？
7．说出一种在把数字信息、图像和声音编码为位模式时常见的麻烦现象。