读改变未来的九大算法笔记01_数据压缩.png

1. 起源

1.1. 香农–法诺编码（Shannon-Fano Coding）

1.1.1. 克劳德·香农

1.1.1.1. 1948年论文创建信息理论领域的贝尔实验室科学家

1.1.2. 麻省理工学院教授罗伯特·法诺（Robert Fano）

1.2. 霍夫曼编码

1.2.1. 大卫·霍夫曼

1.2.1.1. 法诺的一位学生

1.2.2. 一种基础压缩算法，它被广泛用于通信和数据存储系统

1.2.3. Huffman Coding

1.3. LZ77算法

1.3.1. 以色列计算机科学家亚伯拉罕·伦佩尔（Abraham Lempel）

1.3.2. 雅各布·齐夫（Jacob Ziv）

1.3.3. 1977年

2. 错误印象

2.1. 压缩对绝大多数人没有影响

2.2. 事实

2.2.1. 几乎所有软件都是以压缩格式被下载的

2.2.1.1. 这意味着下载和转移文件的速度要比不压缩时快数倍

2.2.2. 你对着电话讲话时，你的声音也经过了压缩

3. 纠错码和压缩算法是同一枚硬币的两面

3.1. 来自冗余的想法

3.1.1. 如果一个文件有冗余，它就比必要的长度长

3.2. 纠错码能被视为向消息或文件中添加冗余的原则性方法

3.3. 压缩算法正好相反：它们会从消息或文件中移除冗余

3.3.1. 基本思想是发现数据中彼此相同的部分，并运用某种把戏更高效地描述这些部分

3.4. 好的压缩算法会移除低效冗余，而纠错编码会增加另一种更高效的冗余

3.5. 首先压缩一条信息，再往里面添加一些纠错码的做法非常常见

4. 无损压缩

4.1. 终极免费午餐

4.2. 无损压缩算法并不能为所有文件节省大量空间

4.3. 一种好的压缩算法能为特定大类的文件节省大量空间

5. 计算机中的数据压缩

6. 行程长度编码

6.1. Run-length Encoding

6.2. 将重复的“行程”和行程的“长度”编码在了一起

6.2.1. ABABAB

6.2.2. 3AB

6.3. 只在压缩非常特殊的数据种类上有用

6.4. 大部分时候只是和其他压缩算法结合起来使用

6.5. 传真机就将行程长度编码和另一种被称为霍夫曼编码的技术结合

6.6. 传真是黑白文件，文件会被转换成许多点，每个点都是非黑即白。当你按顺序阅读这些点（从左到右，从上到下）时，你会遇到大段白点（背景）以及小段黑点（前景文本或笔迹），这让使用行程长度编码变得非常有效

7. 同前把戏

7.1. Same-as-earlier Trick

7.2. 往回数27个字母，然后复制从那一点开始往下的8个字母

7.2.1. back 27，copy 8

7.2.1.1. b27c8

7.3. FG-FG-FG-FG-FG-FG-FG-FG

7.3.1. FG-FG-FG-FG-b8c8

7.3.2. back 2，copy14

7.3.2.1. 数回2个字母，直至抄到第14个字母

7.3.2.2. b2c14

7.3.2.3. FG-b2c14

7.4. Ab1c250

7.4.1. 251个A

8. 更短符号把戏

8.1. Shorter-symbol Trick

8.2. 如果你使用某样东西足够多次，给它起个简短缩写名是很值得的

8.2.1. United States of America

8.2.2. USA

8.3. 两个常用字母的代码被缩短了，代价是用更大的数字增长了不常用符号的代码

8.3.1. 结果是大部分消息的总长度都有所缩短

9. 实施步骤

9.1. 计算机使用同前把戏传输未经压缩的原文件，让文件中绝大多数重复数据由短得多的指令取代，这些指令会返回并拷贝其他地方的数据

9.2. 计算机会检查传输后的文件，选出经常出现的符号。

9.2.1. 用短数字码代表经常用到的符号，用更长的数字码代表极少用到的符号

10. 有损压缩

10.1. 简单且有效的方法是直接“抛弃”一些数据

10.1.1. 会导致解压后的原始文件发生一些小改变

10.2. 抛弃对成品影响很小的信息

10.3. 压缩缺陷

10.3.1. Compression Artifact

10.3.2. 不仅仅是细节的损失，而且有损压缩的某种方法会在接下来的解压中引入明显的新特征

11. 抛弃把戏

11.1. Leave-it-out Trick

11.2. JPEG图像压缩格式

11.2.1. 整张图片划分为8像素×8像素的小方块

11.2.1.1. 每个方块都会被单独压缩

11.2.2. 如果方块恰好只有一种颜色，整个方块就能由一个数字代表，而计算机就能“抛弃”63个数字

11.2.3. 如果方块的大部分是由一种颜色组成的，只有少数像素的颜色略有不同（也许一片天空的灰度都相同），计算机也可以用单个数字代表方块，让方块得到好的压缩结果，并在稍后解压时只出现少量错误

11.2.4. 如果8×8方块从一种颜色渐变为另一种颜色（比如左边是深灰色，右边是浅灰色），那么64个数字也许能被压缩到只有2个：一个深灰的值和一个浅灰的值

11.3. 音频压缩格式

11.3.1. 音频也会被划分成“块”，每个“块”都会被单独压缩

11.3.2. 能利用与人耳有关的已知事实

11.3.2.1. 有些种类的声音对人只有很小的影响或没有影响

11.3.2.2. 压缩算法能在不降低输出质量的情况下消除这些声音