计算机科学入门
上次我们讨论了文件格式，如何编码 文字 ， 声音 ， 图片 ，还举了具体例子 .txt .wav .bmp 。
这些格式虽然管用，而且现在还在用，但它们的简单性意味着 效率不高 ，我们希望文件能小一点，这样能存大量文件，传输也会快一些。
解决方法是 压缩 （compression），把数据占用的空间压得更小，用更少的位 (bit) 来表示数据。
图片压缩
无损压缩
游程编码
我们继续用 吃豆人 例子，图像是 4 像素 x 4 像素。
之前说过，图像一般存成一长串像素值。
为了知道一行在哪里结束，图像要有元数据，写明 尺寸 等属性，忽略这些细节。
每个像素的颜色，是三种 原色 的组合：红、黄、蓝 ，每个颜色用 1 个字节存，数字范围是 0 到 255 。
如果红绿蓝都是 255 会得到白色，如果混合 255 红色和 255 绿色，会得到黄色，这个图像有16个像素(4x4), 每个像素3个字节，总共占48个字节（16x3=48），但我们可以压缩到少于 48 个字节，一种方法是 减少重复信息 ，最简单的方法叫 游程编码 (Run-Length Encoding)，适合经常出现 相同值 的文件。
比如吃豆人有 7 个 连续 黄色像素，与其全存下来：黄色，黄色，黄色……
可以插入一个额外字节，代表有 7 个连续黄色像素，然后删掉后面的重复数据。
为了让计算机能分辨哪些字节是 长度 哪些字节是 颜色 ，格式需要 一致 ，所以我们要给所有像素前面标上长度。
有时候数据反而会变多 ，但就这个例子而言，我们大大减少了字节数，之前是 48， 现在是 24 ，小了 50％ ！省了很多空间！
还有，我们没有损失任何数据，我们可以轻易恢复到原来的数据，这叫 无损压缩 （lossless compression），没有丢失任何数据，解压缩后，数据和压缩前完全一样。
字典编码
我们来看另一种无损压缩，它用更紧凑的方式表示数据块，有点像 don't forget to be awesome 简写成 DFTBA（首字母）。
为此，我们需要一个 字典 ，存储 代码 和 数据 间的对应关系。
我们可以把图像看成一块块，而不是一个个像素，为了简单，我们把 2 个像素当成 1 块（红黄蓝 x2 ，占 6 个字节）。但你也可以定成其他大小，我们只有四对： 白黄 黑黄 黄黄 白白。我们会为这四对生成 紧凑代码 (compact codes)。
有趣的是，这些块的出现频率不同，4 个黄黄，2 个黄白，1 个黑黄，1 个白白。
因为黄黄最常见，因此要用最紧凑的方式（最少的 0 和 1 ）代表它，而黑黄和白白出现的次数最少，因此可以用稍长的方式。
霍夫曼树
1950年代 大卫·霍夫曼 发明了一种高效编码方式叫 霍夫曼树（Huffman Tree） 当时他是麻省理工学院的学生，算法是这样的。
首先，列出所有块和出现频率，每轮选两个 最低 的频率，这里 黑黄 和 白白 的频率最低，它们都是 1 。
可以把它们组成一个树，总频率 2 。
现在完成了一轮算法，现在我们重复这样做。
这次有 3 个可选，就像上次一样，选频率最低的两个。
放在一起，并记录总频率。
这次很简单，因为只有 2 个选择，把它们组合成一棵树就完成了！
现在看起来像这样，它有一个很酷的属性：按频率排列 ，频率低的在下面。
现在有了一棵树，我们可以把 每个分支 用 0 和 1 标注，就像这样。
现在可以生成字典，黄黄 编码成 0 。
白黄 编码成 10 。
黑黄 编码成 110 。
白白 编码成 111 。
酷的地方是，它们绝对不会冲突，因为树的每条路径是唯一的，意味着代码是 无前缀 的，没有代码是以另一个代码开头的。
现在我们来压缩！将所有的像素对根据上述规则表示后如下。
这仅用了 14 位，注意是位(bit)！ 不是字节(byte)！ 14 位(bit) 还不到 2 个字节(byte)！
字典也要保存下来，否则 14 bit 毫无意义，所以我们把字典 加到 14 bit 前面，就像这样。
现在加上字典，图像是 30 个字节(bytes) ，比 48 字节好很多。
消除冗余 和 用更紧凑的表示方法 ，这两种方法通常会组合使用，几乎所有无损压缩格式都用了它们，比如 GIF, PNG, PDF, ZIP。
有损压缩
游程编码 和 字典编码 都是无损压缩，压缩时不会丢失信息，解压后，数据和之前完全一样，无损对很多文件很重要，比如我给你发了个压缩的 word 文档你解压之后发现内容变了，这就很糟糕了。
但其他一些文件，丢掉一些数据没什么关系，丢掉那些人类 看不出区别 的数据，大多数有损压缩技术，都用到了这点。
这种删掉人类无法感知的数据的方法，叫 感知编码 （perceptual coding），它依赖于人类的 感知模型 ，模型来自 心理物理学 领域，这是各种 有损压缩图像格式 的基础，最著名的是 JPEG 。
就像听力一样，人的视觉系统也不是完美的，我们善于看到尖锐对比，比如物体的 边缘 ，但我们看不出颜色的细微变化。
JPEG 利用了这一点，把图像分解成 8x8 像素块，然后删掉大量高频率空间数据。
举个例子，这是一只狗。
我们来看其中一个 8x8 像素，几乎每个像素都和相邻像素不同，用无损技术很难压缩，因为太多不同点了，很多小细节，但人眼看不出这些细节。
因此可以删掉很多，用这样一个简单的块来代替，这看起来一样，但可能只占 10％ 的原始数据。
我们可以对所有 8x8 块做一样的操作，图片依然可以认出是一只狗，只是更粗糙一些。
以上例子比较极端，进行了高度压缩，只有原始大小的八分之一，通常你可以取得 平衡 ，图片看起来差不多，但文件小不少。
音频压缩
你的听力不是完美的，有些频率我们很擅长，其他一些我们根本听不见，比如 超声波 。
举个例子，如果录音乐，超声波数据都可以扔掉，因为人类听不到超声波。
另一方面，人类对人声很敏感，所以应该尽可能保持原样。
低音介于两者之间，人类听得到，但不怎么敏感，一般是感觉到 震动 。
有损音频压缩利用这一点，用不同精度编码不同频段，听不出什么区别，不会明显影响体验。
日常生活中你会经常碰到这类音频压缩，所以你在电话里的声音和现实中 不一样 ，压缩音频是为了让更多人能同时打电话，如果网速变慢了，压缩算法会删更多数据，进一步降低声音质量，所以 Skype 通话有时听起来像机器人。
和没压缩的音频格式相比，比如 WAV 或 FLAC ，压缩音频文件如 MP3，能小10倍甚至更多，省了超多空间！
视频压缩
视频压缩也造成了影响，视频只是 一长串连续图片 ，所以图片的很多方面也适用于视频。
但视频可以做一些小技巧，因为帧和帧之间很多像素一样，这叫 时间冗余 （temporal redundancy）。
视频里不用每一帧都存这些像素，可以只存 变了的部分 ，当帧和帧之间有小小的差异时，很多视频编码格式，只存变化的部分。
这比存所有像素更有效率，利用了帧和帧之间的 相似性 ，更高级的视频压缩格式 会更进一步，找出帧和帧之间相似的部分，然后用简单效果实现，比如 移动 和 旋转 ， 变亮 和 变暗 。
比如挥手，视频压缩器会识别到相似性，用一个或多个小块代表手，然后帧之间直接移动这些小块。
MPEG-4 是常见标准，可以比原文件小 20 倍到 200 倍。
但是，用补丁的移动和旋转来更新画面时，当压缩太严重时会出错，没有足够空间更新补丁内的像素，即使补丁是错的，视频播放器也会照样播放，导致一些怪异又搞笑的结果，你肯定见过这些。
总的来说，压缩对大部分文件类型都有用，从这个角度来讲，人类 不完美 的视觉和听觉也算有用。
学习压缩非常重要，因为可以高效存储图片，音乐，视频。如果没有压缩，在直播平台看直播几乎不可能，因为你的带宽可能不够（会很卡），而且供应商不愿意免费传输那么多数据。