点击查看【bilibili】

压缩的作用：

• 将文件占用的空间压得更小，用更少的位(bit)来表示数据，能存更多的文件
• 使得传输更快 下面用来举例说明的原始数据如下图所示，是一张4×4的图像，每个像素由RGB三个值（各8位）组成。总共4×4×3 = 48个字节
  

无损压缩

定义：不损失任何数据，可以轻易恢复到原来的数据。解压缩后，数据和压缩前完全一致。

游程编码——消除冗余

英文：Run-Length Encoding
机制：消除冗余，简单地减少重复信息。插入额外数据表示重复的长度
优点：

• 适合经常出现相同值的文件
• 是无损压缩

实例：

• 可以看到例子中的图像由连续7个像素都是黄色，可以插入一个额外的字节表示连续黄色像素的长度。
• 不过，要给所有不重复颜色的像素前面都加上长度，使得格式一致，才能让计算机分辨哪些字节表示长度，哪些字节表示颜色
• 因此，游程编码适合经常出现相同值的文件；否则，有时候可能数据反而会变多
• 上面的例子字节数由48压缩到24

字典编码（霍夫曼树）——更紧凑的表示方法

英文：Huffman Tree
机制：使用更紧凑的编码方式来表示数据块。需要一个字典，存储 编码 和 数据 间的对应关系。
实例：

• 简单起见，在这里我们把图像看成一块块，而不是一个个像素。将两个像素（6个字节当作一块），这里只有四对：白黄 黑黄 黄黄 白白，为这4对生成紧凑代码。
• 霍夫曼树是一种高效的编码方式，各个数据块出现频率不同，编码的长度也不同。
• 首先，列出所有块和出现频率，每轮选两个最低的频率，组成一个树，这棵树合并两个子树的频率作为自身频率。不断重复，直到全部合并。
• 把每个分支的左子树标为0，右子树标为1，就可以生成字典，频率大的编码短，频率低的编码长。而且，这些编码绝对不会冲突，因为树的每条路径是唯一的，意味着代码是”无前缀”的，没有代码是以另一个代码开头的。

• 生成哈夫曼树：

• 生成字典：

• 根据字典对数据进行压缩：

• 数据压缩成了14bits编码：10110000111100，不到2字节；还要在前面加上字典，28字节。最终压缩为30字节

组合 消除冗余 + 更紧凑的表示方法

• 前面提到的两种无损压缩方式，游程编码是消除冗余，字典编码（霍夫曼树）是使用更紧凑的表示方法。
• 通常会组合使用 消除冗余 和 使用更紧凑的表示方法
• 几乎所有无损压缩格式都用了这两个的组合，比如 GIF, PNG, PDF, ZIP

有损压缩

定义：一些文件，丢掉一些数据没什么关系，可以丢掉一些存在与否人体都感知不到区别的数据

感知编码

定义：对感知敏感程度不同的数据进行不同精度的编码（删掉人类无法感知的数据）。
实例：

• 声音压缩
  • 你的听力不是完美的，一些频率我们根本听不见，比如超声波，因此可以丢掉音乐文件中的超声波数据；而我们对人声很敏感，因此应该尽可能保持原样；低音介于两者之间，人类听得到，但不怎么敏感，一般是感觉到震动。因此，可以用不同精度编码不同频段，我们也听不出什么区别，不会明显影响体验。
• 图像压缩
• 视频压缩
  • 帧和帧之间很多像素一样，即存在 时间冗余。视频里不用每一帧都存画面里的所有像素，可以只存变了的部分
  • 更高级的视频压缩格式会更进一步，找出帧和帧之间相似的补丁，然后用简单效果实现，比如移动和旋转