# 哈夫曼编码和游程编码

## Huffman encode(哈夫曼编码)

Huffman 编码的基本思想就是用短的编码表示出现频率高的字符，用长的编码来表示出现频率低的字符，这使得编码之后的字符串的平均长度、长度的期望值降低，从而实现压缩的目的。 因此 Huffman 编码被广泛地应用于无损压缩领域。 可以看出， huffman 编码是**一种可变编码**，而不是固定长度编码。

Huffman 编码的过程包含两个主要部分：

* 根据输入字符构建 Huffman 树
* 遍历 Huffman 树，并将树的节点分配给字符

上面提到了他的基本原理就是`用短的编码表示出现频率高的字符，用长的编码来表示出现频率低的字符`，因此首先要做的就是统计字符的出现频率，然后根据统计的频率来构建 Huffman 树（又叫最优二叉树）。

![Huffman-tree](https://p.ipic.vip/v13yj7.jpg)

如图，**huffman 树以一颗二叉树**。 其中节点的左子节点路径用 0 表示，右子节点用 1 表示，节点的值表示的是其权重，权重越大深度越小。深度表示的其实就是编码的长度。通常我们使用字符出现的频率作为权重。真正执行编码的时候，类似字典树，节点不用来编码，节点的路径用来编码.

> 如果计算机使用三进制，而不是二进制，那么 huffman 树就应该是一个三叉树。

## 实例

比如我们对一个字符串的频率统计的结果如下：

| character | frequency |
| :-------: | :-------: |
|     a     |     5     |
|     b     |     9     |
|     c     |     12    |
|     d     |     13    |
|     e     |     16    |
|     f     |     45    |

* 将每个元素构造成一个节点，即只有一个元素的树。并构建一个最小堆，包含所有的节点，该算法用了最小堆来作为优先队列。
* `选取两个权值最小的节点`，并添加一个权值为 5+9=14 的节点，作为他们的父节点。并`更新最小堆`，现在最小堆包含 5 个节点，其中 4 个树还是原来的节点，权值为 5 和 9 的节点合并为一个。

结果是这样的：

![huffman-example](https://p.ipic.vip/bn2vws.jpg)

| character | frequency | encoding |
| :-------: | :-------: | :------: |
|     a     |     5     |   1100   |
|     b     |     9     |   1101   |
|     c     |     12    |    100   |
|     d     |     13    |    101   |
|     e     |     16    |    111   |
|     f     |     45    |     0    |

## run-length encode(游程编码)

游程编码是一种比较简单的压缩算法，其基本思想是将重复且连续出现多次的字符使用（连续出现次数，某个字符）来描述。

比如一个字符串：

```
AAAAABBBBCCC
```

使用游程编码可以将其描述为：

```
5A4B3C
```

5A 表示这个地方有 5 个连续的 A，同理 4B 表示有 4 个连续的 B，3C 表示有 3 个连续的 C，其它情况以此类推。

但是实际上情况可能会非常复杂，我们可以对单个字符进行编码，也可以对多个字符进行编码。 因此如何提取子序列就是一个问题。这并没有看的那么简单。还是以上面的例子来说，我们有也可以把`AAAAABBBBCCC`整体看成一个子序列，这样编码的长度就有所编码。究竟使用哪种方法，取决于压缩的时间和压缩的比例等。 更复杂的情况还有很多，这里不做扩展。

对文件进行压缩比较适合的情况是文件内的二进制有大量的连续重复，一个经典的例子就是具有大面积色块的 BMP 图像，BMP 因为没有压缩，所以看到的是什么样子存储的时候二进制就是什么样子

> 这也是我们图片倾向于纯色的时候，压缩会有很好的效果

思考一个问题， 如果我们在 CDN 上存储两个图片，这两个图片几乎完全一样，我们是否可以进行优化呢？这虽然是 CDN 厂商更应该关心的问题，但是这个问题对我们影响依然很大，值得思考。

## 总结

游程编码和 Huffman 都是无损压缩算法，即解压缩过程不会损失原数据任何内容。 实际情况，我们先用游程编码一遍，然后再用 Huffman 再次编码一次。几乎所有的无损压缩格式都用到了它们，比如 PNG，GIF，PDF，ZIP 等。

对于有损压缩，通常是去除了人类无法识别的颜色，听力频率范围等。也就是说损失了原来的数据。 但由于人类无法识别这部分信息，因此很多情况下都是值得的。这种删除了人类无法感知内容的编码，我们称之为“感知编码”（也许是一个自创的新名词），比如 JPEG，MP3 等。关于有损压缩不是本文的讨论范围，感兴趣的可以搜素相关资料。

实际上，视频压缩的原理也是类似，只不过视频压缩会用到一些额外的算法，比如“时间冗余”，即仅存储变化的部分，对于不变的部分，存储一次就够了。

## 相关题目

[900.rle-iterator](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/900.rle-iterator)