哈夫曼编码原理

参考：

• 百度百科
• 哈夫曼（huffman）树和哈夫曼编码
• 关于哈夫曼树编码

1. 简介

定义

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是Huffman于1952年提出的一种编码方式，是一种可变字长编码(VLC)。该方法完全依据字符出现概率进行构造的平均长度最短的编码，因此也称之为最佳编码。

应用

得益于哈夫曼编码可以得到一个平均长度最短的码文，因此应用场景很多，在此列举三个：

• apache负载均衡的按权重请求策略的底层算法
• 路由器的路由算法
• zip文件的其中一种压缩算法

2. 编码原理

哈夫曼编码大致分为三步：

① 统计字符出现频率；

② 根据频率构造一颗哈夫曼树，这也是一颗最优二叉树。

③ 对哈夫曼树进行01编码，得到最后的码文。

最优二叉树的定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树。

假设一条文本内容(100 bytes)如下：

AAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCDDDEEEEEEEEEEEFFFFFFFFFFFFFFGGGGGGGHHHHHHHH
           

步骤一：统计字符出现频率

字符	频数（便于观察，频数当作频率）
A	5
B	29
C	23
D	3
E	11
F	14
G	7
H	8

步骤二：构造哈夫曼树

赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。

构造过程如下图：

步骤三：进行01编码

根据最终得到的哈夫曼树，向左为0，向右为1，可得到每个字符的编码如下表：

字符	频数（便于观察，频数当作频率）	编码
A	5	00001
B	29	01
C	23	11
D	3	00000
E	11	101
F	14	001
G	7	0001
H	8	100

最终得到码文为：

0000100001000010000100001010101010101010101010101010101010101010101010101010101010111111111111111111111111111111111111111111111110000000000000001011011011011011011011011011011010010010010010010010010010010010010010010010001000100010001000100010001100100100100100100100100
           

最后，我们比较一下编码前后的长度：

编码前：100 bytes
编码后：25+58+46+15+33+42+28+24=271/8 = 33.875 bytes
           

实际上，对于同一组频数(也称频率或权值)，存在不同构的哈夫曼树，例如任意非叶结点的左右子树交换后仍是该组频数的哈夫曼树，但最终编码长度是相同的。同时，哈夫曼编码也是一种非前缀码，要求任一字符的编码都不能是另一字符编码的前缀。

未完待续：哈夫曼编码算法实现