因此 Huffman 编码被广泛地应用于无损压缩领域。 可以看出， huffman 编码是**一种可变编码**，而不是固定长度编码。

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

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

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

| character | frequency |

| :-------: | :-------: |

- `选取两个权值最小的节点`，并添加一个权值为 5+9=14 的节点，作为他们的父节点。并`更新最小堆`，现在最小堆包含 5 个节点，其中 4 个树还是原来的节点，权值为 5 和 9 的节点合并为一个。

| character | frequency | encoding |

| a | 5 | 1100 |

| b | 9 | 1101 |

| c | 12 | 100 |

| d | 13 | 101 |

| e | 16 | 111 |

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

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

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

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

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

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