算法：哈夫曼编码（Huffman Coding）

1. 哈夫曼编码？

• 是 Huffman 于 1952 年提出一种编码方法。
• 是一种无损编码方式，是可变字长编码 (VLC) 的一种。
• 编码策略基于信源的概率统计模型：出现概率大的信源符号编长码，出现概率小的信源符号编短码，从而使平均码长最短。
• 编码属于“无前缀编码”，即：任一字符的编码都不是另一个字符编码的前缀。
• 可借助“最优二叉树（Huffman ）”实现；
• 常应用于数据压缩。

2. 最优二叉树？

• 路径：树中一个结点到另一个结点之间的分支序列；
• 路径长度：路径上的分支数目；
• 树的路径长度：树根到每个结点的路径长度的和；
• 结点带权路径长度：结点到树根的路径长度与结点的权的乘积；
• 树的带权路径长度：树中所有叶子结点的带权路径长度之和（WPL）；
• 最优二叉树：WPL最小 的二叉树；

最优二叉树构造过程：

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

• 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

图1

• 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
• 从森林中删除选取的两棵树，并将新树加入森林；

图2

• 重复上面 2 步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

图3

图4

图5：最优二叉树构造完成

3. 哈夫曼编解码过程？

编码：

1. 读入待编码源文件；
2. 第一次扫描：统计文件中各字符的出现频率；
3. 构建 Huffman 树；
4. 遍历 Huffman 树，获得各字符的码表；
5. 第二次扫描：对源文件的每个字符编码；

解码：

1. 读入编码后的文件；
2. 获取 Huffman 树；
3. 从根节点开始依据从文件中读取的 Huffman 码值沿树行走，至叶结点时完成一个字符的解码，并返回根节点；
4. 重复上述过程，完成所有字符的解码；

4. 程序代码？

例：用哈夫曼编码压缩字符串 “ABCACCDAEAE”；

图：编码过程构建的最优二叉树

图：JS 代码