# 3.4 压缩（Compression）

## 3.4.1 游程编码（Run-Length Encoding）

游程编码（Run-Length Encoding）适用于经常出现重复值的文件中，比如下图中有 7 个连续黄色像素，可以插入额外的字节表示有连续 7 个黄色像素，接着删除重复数据。

![游程编码](https://275040345-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FycDQGvckh16RY095vh62%2Fuploads%2FMRAgTkaqzZFt5XVSgVUR%2F0.png?alt=media)

但需要为了能让计算机分辨出“长度”和“字节”，所以需要为所有不同颜色的像素标上长度，有时反而会使得数据量变多。

## 3.4.2 DFTBA

DFTBA 有点像“Don’t forget to be awesome”（别忘了变厉害）的缩写，使用字典（dictionary）来存储代码和数据之间的对应关系，使得数据的表示更为紧凑，同样是无损压缩。

首先将数据分块计算组合出现的频率，使用「霍夫曼树」（Huffman Tree）进行编码——由大卫·霍夫曼（David Huffman）发明于 1950s，具体步骤如下：

列出所有分块组合以及其出现频率，每轮选中最低的两个频率组成一个树的节点，重复组成最终的霍夫曼树。其特点在于出现频率最低的排列在树的最底端，数字也越大。

![DFTBA](https://275040345-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FycDQGvckh16RY095vh62%2Fuploads%2FO7ah6CZTDixLPmjE237W%2F1.png?alt=media)

根据霍夫曼树对分块组合进行编码，因树的每条路径唯一，所以编码也不会有冲突。接着根据组合的对应将像素数据替换成相应的 code，如将两个黄色的像素替换为 00。同时将保存对应关系的字典也存储在编码数据前即可。

![字典编码](https://275040345-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FycDQGvckh16RY095vh62%2Fuploads%2F9vK9GG5xkigS57KXzwSr%2F2.png?alt=media)

## 3.4.3 有损压缩

解压前后数据完全一致的压缩方法，称为「无损压缩」（lossless compression）。常常组合使用“消除冗余”和“使用更紧凑的表示方式”两者压缩方法来实现，如 GIF, PNG, PDF, ZIP 。

在一些人类看不出区别的时候，使用有损压缩（lossy compression）会更有效率。比如人类无法听到超声波数据，其对人声较为敏感，而对低音只能感觉得到震动。音频有损压缩会利用人类这种感知特性，使用不同的精度来编码不同的频段，比如在网络通话时会根据网速来视情况降低声音质量。

这种通过删除人类无法感知到的数据的编码方式，称为「感知编码」（perceptual coding），属于心理物理学（Psychophysics）领域，依赖于人类的感知模型。

与声音类似，人类的视觉系统也更善于看到尖锐对比（比如物体边缘），而对颜色的细微变化无法感知。因此 JPEG 会利用这种特性，将图片分解为 8×8 的像素块后，删除大量人眼无法分辨的高频率空间数据。

视频作为一长串图片的组合，帧和帧之间有很多像素是一致的，这种情况称为「时间冗余」（temporal redundancy）。

在存储视频时，有些视频编码格式会利用这种相似性，只存储帧与帧之间变化了的部分。更高级些的编码格式——比如视频压缩的常见标准 MPEG-4 ，会找出帧和帧之间变化部分中相似的补丁（patches），然后用简单效果（如移动、旋转等）来实现这种变化。比如用一些补丁代表 up 主手的移动，然后在帧之间直接移动补丁。

但随之而来的问题是，当压缩过于严重时，没有足够空间来更新补丁内的像素，但播放器也依然会照常播放，画面就会错乱。