前言
这学期上了一门名为 Multimedia Technologies 的课，介绍了几种基础的压缩算法，工程师觉得有些许趣味，便想写下来分享给大家。
一个栗子
假设我们有一张尺寸为 16x8 的黑白图片，我们可以用 128 个 0 或 1 来表示：
0000000000000000
0000011111100000
0000100000110000
0000100011010000
0000100110010000
0000111000010000
0000011111100000
0000000000000000
我们可以简单地用数字来依次表示连续的 0 和连续的 1. 像这样 ↓
21 6 9 1 5 2 8 1 3 2 1 1 8 1 2 2 2 1 8 6 21
因为这一序列最大的数字为 21，用二进制来表示最少要 5 位，并且序列长度为 21，那么整张图片只需要 21 * 5 = 105 个二进制位来表示，比原来的 16 * 8 = 128 要省下 23 个二进制位。
读到这里，大家应该能明白，"压缩"其实就是替换符号的过程。用新的符号来表示原来的数据内容，同时达到缩小尺寸的效果。
然而，这种 0 和 1 编码的黑白图像其实非常不实用，因为对现在来说，我们的图片几乎全是彩色的。因此，人们又进一步研究出了各种各样的压缩算法，充满了各种骚操作，请往下阅读。
变动长度编码法
变动长度编码法是一种"使用变动长度的码来取代连续重复出现的符号"的压缩方法。虽然名字有点奇怪，其实是一种非常简单的编码方法。
我们来看下面这段文本 ↓
伞伞伞伞盖盖帽帽帽帽帽子
用变动长度编码法编码之后会成为下面这个序列 ↓
4伞2盖5帽1子
压缩后的编码长度很明显地缩小了，但是，这种方法也有弊端，如果文本是像 伞盖与帽子 这种单个符号连续出现的频率非常低的情况，会造成越压缩尺寸越大的的效果(1伞1盖1与1帽1子)。
可以看出，要提高压缩率，就要想办法把出现频率较高的符号用更短的形式替代。于是，人类想出了哈夫曼编码。
哈夫曼编码
哈夫曼编码的本质是，用短的编码来表示高频的符号，用长的编码来表示低频的符号。让我们继续举个例子来说明哈夫曼编码的过程，假设我们要对以下这段文本进行哈弗曼编码 ↓
“伞盖是伞盖，帽子是帽子，伞盖盖帽子，帽子罩伞盖。”
首先，我们需要统计这段文本里，每个字出现的频次。(我们先不考虑标点符号)
我们可以得出一张频次表 ↓
| 文字 | 频次 |
|---|---|
| 伞 | 4 |
| 盖 | 5 |
| 帽 | 4 |
| 子 | 4 |
| 是 | 2 |
| 罩 | 1 |
然后，我们需要基于这些文字的出现频次建一棵哈夫曼树，步骤如下 ↓
- 为每个符号建一个节点
- 找出频次最少的两个节点，组合成一棵二叉子树，父节点的频次为两个子节点的频次之和
- 重复步骤 2 直到只剩最后的根节点
过程可以参照这张动图 ↓
根据文字频率表，我们建成了如图这棵"伞盖帽子哈夫曼树" ↓
接着，我们从根节点出发，每次往左边就给路径标上 “1”，往右走就标上 “0”。然后就生成了一棵带有"权值"的"伞盖帽子哈夫曼树"了。
大家可以看到，每一个叶子节点都代表了原始文本的一个文字。而从根节点出发到每一个叶子节点的路径，就构成了这个文字的哈夫曼编码。
| 文字 | 次数 | 哈夫曼编码 |
|---|---|---|
| 伞 | 4 | 11 |
| 盖 | 5 | 00 |
| 帽 | 4 | 011 |
| 子 | 4 | 10 |
| 是 | 2 | 0101 |
| 罩 | 1 | 0100 |
到这里，我们造出了一张哈夫曼编码表。根据这张表我们就可以对刚才那段文本进行编码。
压缩前: 伞盖是伞盖帽子是帽子伞盖盖帽子帽子罩伞盖
压缩后: 11000101 11000111 00101011 10110000 01110011 10010011 00000000
有一些不了解计算机的同学可能会认为用 0 和 1 表示比原来的长度要长了。这里要补充一下，机器其实只认识 0 和 1，所有文本都是用 0 和 1来编码表示的。学过 C 语言的同学应该会记得，字母大写"A"对应的 ASCII 码是
65，"a"则是97。同样的，我们所使用的中文在计算机中其实也对应着一串数字，使用的是Unicode编码（现在比较常用）。此时，一个汉字就要用掉 16 个二进制位。而我们这里用哈夫曼编码之后，频率最低的"罩"字才只用了 4 个二进制位。
另外，比较注重细节的同学，会发现上面这段二进制编码其实末尾多了 6 个 “0”。这是为了补齐一个字节(8 个二进制位)。有学过 C 或者 C++ 的同学应该也有印象，我们处理字符串的过程中，可以操作的最小单位是
unsigned char，也就是一个字节(8 个二进制位)，即便可以用位运算来操作 2 位、7 位这种不对齐的情况，我们向操作系统申请内存的时候也是以字节为单位申请的。
我们前面所说的哈夫曼编码，在编码之前需要得到每个符号的出现频率，然后再进行压缩。然而，在实际情况中，我们并不能预先得到这些信息，于是，人类又想出了其他更为通用的压缩算法，比如 LZ77 和 LZ78 以及其衍生的改进算法。比较知名的 Unix 压缩工具 gzip 就使用到了 LZ77 衍生的 DEFLATE 算法。
LZ77
LZ77 算法是采用字典做数据压缩的算法，核心思想是"利用重复结构信息进行数据压缩"。
我们继续用"伞盖帽子"这句话来举例子。假设我们先获取到了前面10个字 ↓
| 伞 | 盖 | 是 | 伞 | 盖 | 帽 | 子 | 是 | 帽 | 子 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 6 | 7 |
那么，当我们对后面 10 个字进行处理的时候，如果有重复出现的文字，就可以用前面出现过的位置来表示。像这样 ↓
| 伞 | 盖 | 盖 | 帽 | 子 | 帽 | 子 | 罩 | 伞 | 盖 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 2 | 6 | 7 | 6 | 7 | 1 | 2 |
具体的压缩过程比较复杂，就不在这里展开了，有兴趣的同学可以自行使用搜索引擎继续研究。
LZ78
LZ77 算法是在 1977 年发表的，而 LZ78 则是在 1978 年发表的，这两个算法虽然名字相近，原理其实差别很大。LZ78 的压缩过程要比 LZ77 简单不少，实际上是维护一个动态词典，包括索引和内容。动态词典，顾名思义，这个词典会在压缩过程中发生变化。在压缩过程中，已经存在词典的词可以用来表示重复出现的内容，否则新出现的词会被添加到词典中。
压缩过程的主要步骤：
- 从原始内容读取待压缩的符号序列
- 从已有的词典查找最长匹配
- 存在匹配就和最长匹配的下一个符号组合成一个新的词并添加进词典
- 否则直接将单个符号添加到词典。
- 输出这一步的压缩内容
假设我们要用 LZ78 对一个将"伞盖帽子"重复若干次的文本进行压缩，如
"伞盖帽子伞盖帽子伞盖帽子伞盖帽子伞盖帽子…"
那么，每一次操作进行记录会生成这样一个表格 ↓
| 操作次序 | 文本输入 | 编码输出 | 词典索引 | 词典内容 |
|---|---|---|---|---|
| 1 | 伞 | (0,伞) | 1 | 伞 |
| 2 | 盖 | (0,盖) | 2 | 盖 |
| 3 | 帽 | (0,帽) | 3 | 帽 |
| 4 | 子 | (0,子) | 4 | 子 |
| 5 | 伞盖 | (1,盖) | 5 | 伞盖 |
| 6 | 帽子 | (3,子) | 6 | 帽子 |
| 7 | 伞盖帽 | (5,帽) | 7 | 伞盖帽 |
| 8 | 子伞 | (4,伞) | 8 | 子伞 |
| 9 | 盖帽 | (5,帽) | 9 | 盖帽 |
| 10 | 子伞盖 | (8,盖) | 10 | 子伞盖 |
| 11 | 帽子伞 | (6,伞) | 11 | 帽子伞 |
| 12 | 盖帽子 | (9,子) | 12 | 盖帽子 |
| 13 | 伞盖帽子 | (7,子) | 13 | 伞盖帽子 |
| 14 | 伞盖帽子伞 | (13,伞) | 14 | 伞盖帽子伞 |
| … | … | … | … | … |
表格介绍
- 表格的"文本输入"列从上到下就是我们输入的原始文本"伞盖帽子伞盖帽子伞盖帽子…"。
- “编码输出"列从上到下就是我们输出的压缩编码”(0,伞)(0,盖)(0,帽)(0,子)(1,盖)(3,子)(5,帽)…"。
- 表格的最后两列为词典，可以看到词典的大小随着压缩的进行一直在增长。
我们用操作次序 2 和 7 来讲解一下这个表格是如何生成的。
- 操作次序 2
待处理的文本为"盖帽子伞盖帽子伞盖帽子…"，此时词典中只有一个"伞"子，没有从"盖"字开始的序列，我们无法从词典中找出任何匹配，于是直接输出"(0,盖)"。同时把"盖"加入到词典中。 - 操作次序 7
经过前 6 步操作，待处理的文本为"伞盖帽子伞盖帽子伞盖帽子…"。我们从词典中找出最大的匹配是"伞盖"，索引为 5，并且匹配终止在"帽",于是输出编码"(5,帽)"。同时把"伞盖帽"加入到词典中。
关于几个基础的无损压缩算法就讲到这里啦，感兴趣的同学可以自行利用搜索引擎深入学习。: )
