数据压缩算法---霍夫曼编码（Huffman）

霍夫曼编码是一种基于最小冗余编码的压缩算法。最小冗余编码是指，如果知道一组数据中符号出现的频率，就可以用一种特殊的方式来表示符号从而减少数据需要的存储空间。

• 用较少的位对出现频率高的符号编码
• 用较多的位对出现频率低的符号编码

一个符号不一定必须是文本字符，它可以是任何大小的数据，但往往它只占一个字节。

Huffman Coding：译为哈夫曼编码、赫夫曼编码、霍夫曼编码。 是可变字长编码(VLC)的一种。用于无损数据压缩的熵编码（权编码）算法，是一种通过字符出现频率，根据二叉树实现。

编码示例

编码字符统计

熵和最小冗余

每个数据集都有一定的信息量，这就是所谓的熵。一组数据的熵是数据中每个符号熵的总和

1

Sz = -lg2 Pz

Pz 就数据集中z出现的频率

1

Su = -lg2(12/72) = 2.584 963位

72个字符的字符串中，U字符最少可以使用3位表示（四舍五入）

构造霍夫曼树

出现频率越多的会越在上层，编码也越短，出现频率越少的就越在下层，编码也越长

用霍夫曼树压缩数据，给定一个具体的符号，从树的根开始，然后沿着树的叶向叶子结点追踪。在向下追踪的过程中.

• 当向左分支移动时，向当前编码的末尾追加0；
• 当向右分支移动时，向当前编码的末尾追加1

编码表

编码效率

• 不压缩数据大小：72*8=576bit

• 压缩后数据大小：123+182+73+152+20*2=163bit

• 压缩比：1 - 163/576 = 71.7%

在通常情况下，霍夫曼编码并不是最高效的压缩方法，但它压缩和解压缩的速度非常快。

• 一般来说，造成霍夫曼编码比较耗时的原因是它需要扫描两次数据：一次用来计算频率；另一次才是用来压缩数据。
• 而解压缩数据非常高效，因为解码每个符号的序列只需要扫描一次霍夫曼树。

参考

• 霍夫曼编码压缩算法