哈夫曼编码

哈夫曼(Huffman)编码是一种常用的压缩编码方法，是Huffman于1952年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。举个例子：假设一个文件中出现了8种符号S0,S1,S2,S3,S4,S5,S6,S7，那么每种符号要编码，至少需要3比特。假设编码成000,001,010,011,100,101,110,111(称做码字)。那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成000001111000001110010010011100101000000001，共用了42比特。我们发现S0，S1，S2这三个符号出现的频率比较大，其它符号出现的频率比较小，如果我们采用一种编码方案使得S0，S1，S2的码字短，其它符号的码字长，这样就能够减少占用的比特数。例如，我们采用这样的编码方案：S0到S7的码字分别01,11,101,0000,0001,0010,0011,100，那么上述符号序列变成011110001110011101101000000010010010111，共用了39比特，尽管有些码字如S3，S4，S5，S6变长了(由3位变成4位)，但使用频繁的几个码字如S0，S1变短了，所以实现了压缩。

上述的编码是如何得到的呢？随意乱写是不行的。编码必须保证不能出现一个码字和另一个的前几位相同的情况，比如说，如果S0的码字为01，S2的码字为011，那么当序列中出现011时，你不知道是S0的码字后面跟了个1，还是完整的一个S2的码字。我们给出的编码能够保证这一点。

下面给出具体的Huffman编码算法。

(1)              首先统计出每个符号出现的频率，上例S0到S7的出现频率分别为4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。

(2)              从左到右把上述频率按从小到大的顺序排列。

(3)              每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。

(4)              重复(3)，直到最后得到和为1的根节点。

(5)              将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0,1序列串起来，就得到了各个符号的编码。

上面的例子用Huffman编码的过程如图9.1所示，其中圆圈中的数字是新节点产生的顺序。可见，我们上面给出的编码就是这么得到的。

 http://www-scf.usc.edu/~flv/ipbook/chap09.files/image001.gif

 Huffman编码的示意图

产生Huffman编码需要对原始数据扫描两遍。第一遍扫描要精确地统计出原始数据中，每个值出现的频率，第二遍是建立Huffman树并进行编码。由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但简单有效，因而得到广泛的应用。