企业官网建设流程全解析

一般所说的霍夫曼树，是指带权路径长度最小的二叉树。利用这棵树为每个符号分配的 0/1 编码，就是霍夫曼编码。出现越频繁的符号，其编码越短。

带权路径长度的计算方式是：将每个叶子的权值乘以它到根节点的距离，再全部累加。在压缩场景中，权值即该符号出现的次数。

构造时，每次选取当前权值最小的两棵树，合并为一棵新树，新树的权值为两者之和，如此反复，直到只剩一棵树为止。

假设有五个符号，出现次数分别为 A:1、B:1、C:2、D:3。

1. A 和 B 权值最小，先合并为权值为 2 的节点。此时剩余节点为 2、C:2、D:3。
2. 再合并两个权值为 2 的节点，得到权值为 4 的节点。此时剩余节点为 4 和 D:3。
3. 最后合并为根节点，权值为 7。

7

/ \

D:3 4

/ \

2 C:2

/ \

A:1 B:1

约定左边记 0，右边记 1：

D 出现次数最多，因此只占用 1 位；A 和 B 各只出现一次，需要 3 位。总长度为 3×1+2×2+1×3+1×3=13。由于任何一个符号的编码都不是另一个编码的前缀，因此这些编码连在一起时也能被逐个拆开。例如，011100对应的就是 D、C、A。

文件压缩、JPEG 以及 ZIP 中的定长符号表，都是采用这一思路，将高频内容编码为更短的位串。

传输出错代价高的编码。 网络协议和图片、音频里，高频符号用短码。HTTP/2 的头部压缩（HPACK）用一张固定的霍夫曼表编头部字段。JPEG、MP3 在量化之后，也用霍夫曼表把出现多的系数写成更少的位。传真里的改进型霍夫曼编码，用来压缩连续的黑白行程。

多次合并文件。 每次把两个最短的有序文件合成一个，合成代价按文件长度算。合并顺序正好和建霍夫曼树一样：总是先合最小的两个，总读写量最小。多个有序结果要归并成一个时，就按这个顺序做。

内存紧张时的前缀码。 只要符号出现次数差得比较大，就可以用这棵树做一套前缀编码，解码时从根往下走，走到叶子就得到一个符号，不需要在符号之间再加分隔符。