什么是哈夫曼编码？

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码(有时也称为霍夫曼编码)。

哈夫曼编码的原理

哈夫曼编码的基本思路：输入一个待编码的串，首先统计串中各字符出现的次数，称之为频次，假设统计频次的数组为count[]，则哈夫曼编码每次找出count数组中的值最小的两个分别作为左右孩子，建立父节点， 循环这个操作2*n-1-n次，这样就把霍夫曼树建好了，建树的过程需要注意，首先把count数组里面的n个值初始化为霍夫曼树的n个叶子节点，他们的孩子节点标号初始化为-1，父节点初始化为他本身的标号。接下来是编码，每次从霍夫曼树的叶子节点出发，依次向上找，假设当前的节点标号是i，那么他的父节点必然是myhuffmantree[i].parent,如果i是myhuffmantree[i].parent的左节点，则该节点的路径为0，如果是右节点，则该节点的路径为1。当向上找到一个节点，他的父节点标号就是他本身，就停止。

哈夫曼编码的具体步骤

1、准备待编码的字符串；

2、统计字符串中每个字符出现的次数；

3、根据上面的数组，生成节点；

4、构建霍夫曼树，每次删除链表中的两个节点，生成一个新节点，并将这个节点重新插入到链表合适位置；

5、通过前序遍历，求出每个字符的二进制编码，同样设置一个长度为256的数组，下标为字符对应的ASCII码，没出现的字符编码为null，不考虑；

6、根据求出的二进制编码替换原来的每个字符，得到整个字符串对应的二进制编码；

7、将二进制编码按照没8位生成一个新字符，最后剩的不足8位的在后面补上count个0，计算一个新字符，补0的个数解码时需要使用；

8、将生成的新字符替换二进制编码字符串，即可得到编码后的内容，长度将在一定程度变短；

哈夫曼编码的特点

1、哈夫曼编码方式保证了概率大的符号对应短码，概率小的符号对应长码，充分利用了短码；

2、哈夫曼是一种即时码：由于代表信源符号的节点都是终端节点，因此其编码不可能是其他终端节点对应的编码的前缀，即哈夫曼编码所得的码字为即时码；

3、哈夫曼编码是一种分组码，各个信源符号都被映射成一组固定次序的码符号；

4、哈夫曼编码是一种唯一可解的码，任何符号序列只能以一种方式译码；

哈夫曼编码的实现