哈夫曼编码的理解(Huffman Coding)

1、哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是Huffman于1952年提出的一种编码方式，可变字长编码(VLC)的一种。霍夫曼编码不仅会考察文本中有多少个不同字符，还会考察每个字符出现的频率，根据频率的不同，选择不同长度的编码。霍夫曼编码试图用这种不等长的编码方法，来进一步增加压缩的效率，广泛用于数据压缩中，其压缩率通常在 20%～90% 之间。有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

2、举例说明：
假设我有一个包含 1000 个字符的文件，每个字符占 1 个 byte（1byte=8bits），那存储这 1000 个字符就一共需要 8000bits。假设我们通过统计分析发现，这 1000 个字符中只包含 6 种不同字符，假设它们分别是 a、b、c、d、e、f。为了尽量减少存储空间，每个字符我们用 3 个二进制位（3bit）来表示：a(000)、b(001)、c(010)、d(011)、e(100)、f(101)【注：因为3 个二进制位（bit）就可以表示 8 个不同的字符】，那现在每个字符只需要3bit，存储这 1000 个字符只需要3*1000= 3000bits 就可以了，比原来的存储方式节省了5000bits空间。在解压缩的时候，我们每次从文本中读取 3 位二进制码，然后翻译成对应的字符即可。

但是，霍夫曼编码是不等长的！每次应该读取 1 位还是 2 位、3 位等等来解压缩呢？所以为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。 在解压缩的时候，我们每次会读取尽可能长的可解压的二进制串，所以在解压缩的时候也不会歧义。

假设这 6 个字符出现的频率从高到低依次是 a、b、c、d、e、f，我们把它们编码下面这个样子，经过这种（霍夫曼）编码压缩之后，这 1000 个字符只需要 2100bits 就可以了。

3、解释上边提及的，如何进行霍夫曼编码呢？
那如何给不同的字符进行不同长度的编码呢？简易的理解就是，根据出现的频率（即权值）放进优先队列,那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取e，f构成新树，其父结点为x(50)，然后再重复操作，取出x.d,构造父节点为y，以此类推，最后根节点权值为1000（字符串出现总数，即总频率）如图：

指向左子节点的边权值我们统统标记为 0，指向右子节点的边，权值我们统统标记为 1，那从根节点到叶节点的路径就是叶节点对应字符的霍夫曼编码。

4、小结： 根据例子我们看出原本1000 个字符的文件，普通字符存储需要8000bits，通过二进制位等长编码优化完，存储需要3000bits，进一步通过霍夫曼编码优化，需要2100bits 就可以了！