计算机速成课Crash Course - 21. 压缩

更多技术文章，全网首发公众号 “摸鱼IT” 锁定 -上午11点 - ，感谢大家关注、转发、点赞！

计算机速成课Crash Course - 21. 压缩 (qq.com)

今天继续计算机速成课Crash Course的系列讲解。

21. 压缩

上集我们讨论了文件格式，如何编码文字，声音，图片，还举了具体例子 .txt .wav .bmp。

这些格式虽然管用，而且现在还在用，但它们的简单性意味着效率不高。我们希望文件能小一点，这样能存大量文件，传输也会快一些。

解决方法是压缩，把数据占用的空间压得更小，用更少的位(bit)来表示数据。

听起来像魔法，但其实是计算机科学！

我们继续用上集的 吃豆人例子，图像是4像素x4像素，之前说过，图像一般存成一长串像素值。

为了知道一行在哪里结束，图像要有元数据，写明尺寸等属性，但为了简单起见，今天忽略这些细节。

如果红绿蓝都是255会得到白色，如果混合255红色和255绿色，会得到黄色。这个图像有16个像素(4x4)，每个像素3个字节，总共占48个字节（16x3=48），但我们可以压缩到少于 48 个字节。

一种方法是 减少重复信息。最简单的方法叫 游程编码(Run-Length Encoding)，适合经常出现相同值的文件。

比如吃豆人 有7个连续黄色像素，与其全存下来：黄色，黄色，黄色...，可以插入一个额外字节，代表有7个连续黄色像素，然后删掉后面的重复数据。

为了让计算机能分辨哪些字节是"长度" 哪些字节是"颜色"，格式要一致，所以我们要给所有像素前面标上长度，有时候数据反而会变多，但就这个例子而言，我们大大减少了字节数，之前是48 现在是24。

小了50％！省了很多空间！

还有，我们没有损失任何数据，我们可以轻易恢复到原来的数据，这叫"无损压缩"，没有丢失任何数据，解压缩后，数据和压缩前完全一样。

我们来看另一种无损压缩，它用更紧凑的方式表示数据块,有点像 "别忘了变厉害"(don't forget to be awesome) 简写成 DFTBA.

为此，我们需要一个字典，存储"代码"和"数据"间的对应关系。我们看个例子：

我们可以把图像看成一块块，而不是一个个像素，为了简单，我们把2个像素当成1块（占6个字节），但你也可以定成其他大小。

我们只有四对：白黄、黑黄、黄黄、白白，我们会为这四对，生成紧凑代码(compact codes)，有趣的是，这些块的出现频率不同。

1950年代 大卫·霍夫曼 发明了一种高效编码方式，叫"霍夫曼树"（Huffman Tree） 当时他是麻省理工学院的学生，算法是这样的：

首先，列出所有块和出现频率，每轮选两个最低的频率，这里 黑黄 和 白白 的频率最低，它们都是 1，可以把它们组成一个树，总频率 2，现在完成了一轮算法。

现在我们重复这样做，这次有3个可选，就像上次一样，选频率最低的两个，放在一起，并记录总频率，好，我们快完成了。

这次很简单，因为只有2个选择，把它们组合成一棵树就完成了！

现在看起来像这样，它有一个很酷的属性：按频率排列，频率低的在下面。

现在有了一棵树，你可能在想 "怎么把树变成字典？"我们可以把每个分支用 0 和 1 标注，就像这样，现在可以生成字典。

黄黄 编码成 0，白黄 编码成 10，黑黄 编码成 110，白白 编码成 111。

酷的地方是它们绝对不会冲突，因为树的每条路径是唯一的。意味着代码是"无前缀"的，没有代码是以另一个代码开头的。

现在我们来压缩！

注意是位(bit)！不是字节(byte)！14位(bit) 还不到2个字节(byte)！

字典也要保存下来，否则 14 bit 毫无意义，所以我们把字典 加到 14 bit 前面，就像这样，现在加上字典，图像是 30 个字节(bytes)，比 48 字节好很多。

"消除冗余"和"用更紧凑的表示方法"，这两种方法通常会组合使用，几乎所有无损压缩格式都用了它们，比如 GIF, PNG, PDF, ZIP。

游程编码 和 字典编码 都是无损压缩，压缩时不会丢失信息，解压后，数据和之前完全一样，无损对很多文件很重要，比如我给你发了个压缩的 word 文档，你解压之后发现内容变了，这就很糟糕了。

但其他一些文件，丢掉一些数据没什么关系，丢掉那些人类看不出区别的数据，大多数有损压缩技术，都用到了这点，实际细节比较复杂，所以我们讲概念就好。

以声音为例，你的听力不是完美的，有些频率我们很擅长，其他一些我们根本听不见，比如超声波，除非你是蝙蝠。

举个例子，如果录音乐，超声波数据都可以扔掉，因为人类听不到超声波，另一方面，人类对人声很敏感，所以应该尽可能保持原样，低音介于两者之间，人类听得到，但不怎么敏感，一般是感觉到震动。

有损音频压缩利用这一点，用不同精度编码不同频段，听不出什么区别，不会明显影响体验，音乐发烧友估计要吐槽了！

日常生活中你会经常碰到这类音频压缩，所以你在电话里的声音和现实中不一样，压缩音频是为了让更多人能同时打电话。

如果网速变慢了，压缩算法会删更多数据，进一步降低声音质量，所以 Skype 通话有时听起来像机器人，和没压缩的音频格式相比，比如 WAV 或 FLAC( 这下音乐发烧友满意了），压缩音频文件如 MP3，能小10倍甚至更多。省了超多空间！

这种删掉人类无法感知的数据的方法，叫"感知编码"，它依赖于人类的感知模型，模型来自"心理物理学"领域。

这是各种"有损压缩图像格式"的基础，最著名的是 JPEG，就像听力一样，人的视觉系统也不是完美的。

我们善于看到尖锐对比，比如物体的边缘，但我们看不出颜色的细微变化，JPEG 利用了这一点，把图像分解成 8x8 像素块，然后删掉大量高频率空间数据。

举个例子，这是导演的狗，超可爱！

我们来看其中一个 8x8 像素，几乎每个像素都和相邻像素不同，用无损技术很难压缩，因为太多不同点了，很多小细节，但人眼看不出这些细节，因此可以删掉很多，用这样一个简单的块来代替，这看起来一样，但可能只占10％的原始数据。

我们可以对所有 8x8 块做一样的操作，图片依然可以认出是一只狗，只是更粗糙一些。

以上例子比较极端，进行了高度压缩，只有原始大小的八分之一。通常你可以取得平衡，图片看起来差不多，但文件小不少。

你看得出两张图的区别吗？

估计看不出，但我想提一下，视频压缩也造成了影响，视频只是一长串连续图片，所以图片的很多方面也适用于视频，但视频可以做一些小技巧，因为帧和帧之间很多像素一样，比如我后面的背景！这叫 时间冗余。

视频里不用每一帧都存这些像素，可以只存变了的部分，当帧和帧之间有小小的差异时，比如后面这个频率发生器，很多视频编码格式，只存变化的部分，这比存所有像素更有效率，利用了帧和帧之间的相似性，更高级的视频压缩格式会更进一步，找出帧和帧之间相似的补丁，然后用简单效果实现，比如移动和旋转，变亮和变暗。

如果我这样摆手，视频压缩器会识别到相似性，用一个或多个补丁代表我的手，然后帧之间直接移动这些补丁，所以你看到的是我过去的手（不是实时的），有点可怕，但数据量少得多。

MPEG-4 是常见标准，可以比原文件小20倍到200倍，但用补丁的移动和旋转来更新画面，当压缩太严重时会出错，没有足够空间更新补丁内的像素，即使补丁是错的，视频播放器也会照样播放，导致一些怪异又搞笑的结果，你肯定见过这些。

总的来说，压缩对大部分文件类型都有用，从这个角度来讲，人类不完美的视觉和听觉也算有用，学习压缩非常重要，因为可以高效存储图片，音乐，视频。

如果没有压缩，在 YouTube 看"明星拼车唱歌"几乎不可能，因为你的带宽可能不够（会很卡），而且供应商不愿意免费传输那么多数据，现在你知道为什么打 Skype 电话，有时像在和恶魔通话。

---

以上内容就是?21.压缩?的内容，感兴趣的同学记得点赞、关注、转发、收藏哦！

我会不定期发布课程的讲解！

更多技术文章，全网首发公众号 “摸鱼IT” 锁定 -上午11点 - ，感谢大家关注、转发、点赞！