1. 编码含义

编码：给每一个对象标记一个二进制位串来表示一组对象。例：ASCII，指令系统。

2. 编码分类

• 等长编码：表示一组对象的二进制位串的长度相等
• 不等长编码：表示一组对象的二进制位串的长度不相等

3. 编码问题

• 等长编码什么情况下空间效率高？
  等长编码越短，占据空间越小
• 不等长编码什么情况下空间效率高？
  出现频率高的采用比较短的编码，出现频率低的采用比较长的编码。参考霍夫曼树的特性，符合霍夫曼树的性质的二叉树，即WPL最小权值路径条件的就是最短编码空间的占用情况，也是不等长编码最优的空间效率使用。
• 不等长编码如何保证解码的唯一性？
  编码不重复，没有二义性。参考霍夫曼树的特性，树干即编码，路径长度即编码长度，根据二叉树特性通过树干路径进行编码，它构成前缀编码的形式，即一组编码中任一编码都不是其他任何一个编码的前缀，前缀编码保证了在解码时不会出现有多种可能的情况，能够保证编码的唯一性。

等长编码和不等长编码的对比

3.1 等长编码

在数据传输格式上，等长编码需要进行分割，例如，ABC则用000，001，010表示，或用000 001 010表示，以上缺点是分隔符占用额外空间，且A到H共8个字符中如A可用二进制0表示，而不需要000,因此也是浪费空间，以此类推其他字符二进制表示方法的空间占用。

3.2 不等长编码

若要提高空间利用率减少空间占用，可以从减少额外分隔符、压缩单个字符不等长编码表示方式等入手，可优化如下：

若按照不等长编码方式去除分隔符的话，则编码出现不唯一情况，如表示ABC为0110，按照不等长编码值可有如下结果，即解密出现多种情况。

总结可知，等长编码无法实现编码压缩节约空间的目的，且需要间隔来避免编解码不唯一的问题。

3.3 哈夫曼编码

有没有可以压缩字符编码、不需要额外分隔符、解码保证唯一性的编码方式呢？
答案就是 ———— 哈夫曼树编码

如有 {A、B、C、D、E、F、G} 字符，出现次数为 {9、5、2、3、11、7、8} ，我们将字符出现次数设置为哈夫曼树中权值结点的权值，此时权值结点即字符，然后根据概念进行哈夫曼树的构建（哈夫曼树具体构建方式可点击此处）如下：

如上图，可得到字符与编码值的对应表如下：

我们再来按照去除分隔符的方式表示ABC，则为 000100110

以上只有一种解码可能，所以是解码具有唯一性，没有存在二义性，是可靠的。
不难发现，无论是从Root根结点到权值子结点，还是从权值子结点到Root根结点的编码，A至G的不等长编码值中任一字符的编码都不是其它字符的编码的前缀，满足该情况的编码则认为具有前缀编码特性，哈夫曼树编码则拥有该特性。

4. 编码压缩

上面我们了解了哈夫曼编码 ，下面来看看它是如何对编码进行压缩来减少空间占用的。示例对字符 ABCDEFG 进行二进制编码，如下

5. 总结

哈夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就称Huffman编码。在变字长编码中，如果码字长度严格按照对应符号出现的概率大小逆序排列，则其平均码字长度为最小。

6. 参考

https://baike.baidu.com/item/哈夫曼编码
https://www.cnblogs.com/hujiapeng/p/6208843.html
https://blog.csdn.net/xgf415/article/details/52628073
https://www.bilibili.com/video/BV1ke411s7Nk
https://blog.csdn.net/u013161278/article/details/111942554