转载自：http://news.cnblogs.com/n/143406/
前两天发布那个 rsync 算法后，想看看数据压缩的算法，知道一个经典的压缩算法 Huffman 算法。你应该听说过 David Huffman 和他的经典的压缩算法—— Huffman Code，这是一种通过字符出现频率，Priority Queue，和二叉树来进行的一种压缩算法，这种二叉树又叫 Huffman 二叉树 —— 一种带权重的树。但是网上查了一下，中文社区内好像没有把这个算法说得很清楚的文章，尤其是树的构造，而正好看到一篇国外的文章《A Simple Example of Huffman Code on a String》，其中的例子浅显易懂，相当不错，我就转了过来。注意，我没有对此文完全翻译。
我们直接来看示例，如果我们需要来压缩下面的字符串：
“beep boop beer!”
首先，我们先计算出每个字符出现的次数，我们得到下面这样一张表 :
| 字符 | 次数 |
| ‘b’ | 3 |
| ‘e’ | 4 |
| ‘p’ | 2 |
| ‘ ‘ | 2 |
| ‘o’ | 2 |
| ‘r’ | 1 |
| ‘!’ | 1 |
最终我们可以得到下面这张编码表：
| 字符 | 编码 |
| ‘b’ | 00 |
| ‘e’ | 11 |
| ‘p’ | 101 |
| ‘ ‘ | 011 |
| ‘o’ | 010 |
| ‘r’ | 1000 |
| ‘!’ | 1001 |
这里需要注意的一点是，我们的 Huffman 对各个字符的编码是不会冲突的，也就是说，不会存在某一个编码是另一个编码的前缀，不然的话就会大问题了。因为 encode 后的编码是没有分隔符的。
于是，对于我们的原始字符串 beep boop beer!
其对就能的二进制为 : 0110 0010 0110 0101 0110 0101 0111 0000 0010 0000 0110 0010 0110 1111 0110 1111 0111 0000 0010 0000 0110 0010 0110 0101 0110 0101 0111 0010 0010 0001
我们的 Huffman 的编码为： 0011 1110 1011 0001 0010 1010 1100 1111 1000 1001
从上面的例子中，我们可以看到被压缩的比例还是很可观的。
作者给出了源码你可以看看（ C99 标准） huffman_string1
To be clearer since there have been comments on this. This article only illustrates how the algorithm works. To use this in a real scenario you need to add the Huffman tree you created at the end or at the start of your encoded string and the reciever should know how to interpret it in order to decode the message. A good way to do this is to build a string of bits by traversing the tree in any order you want (I prefer post-order) and concatenate a 0 for each node that is not a leaf and a 1 for each node that is a leaf followed by the bits representing the original symbol (in our case, 8 bits representing the ASCII char value). Placing this string of bits at the start of your encoded message is ideal. Once the reciever has build the tree, he will know how to decode the message to obtain the original one.
To read about a more advanced version of this algorithm, you can read our article on Adaptive Huffman Coding.