哈夫曼编码思想

哈夫曼编码本质是“越重要越简洁”，越重要的对象表示越简洁。

什么是更重要的对象？可以根据具体的需求场景来选择对象的某个属性来作为判断的标准。

你会发现，人们日常书面交流的文字，使用频繁的书写相对简单，而偏僻字一般都笔画较多，日常不使用的英文专业词汇一般都比常用单词更长。使用越频繁的文字越重要。人们创造文字过程体现的就是一种原生的哈夫曼编码思想。

为什么需要这样设计？重要的对象编码短，可以降低存储空间，节省书写纸张，减少数据传输量，最终提高数据存储传输效率！

哈夫曼编码算法

算法思路

根据编码对象的可量化的重要性指标的大小构建二叉树（Huffman树），所有的编码对象都会成为该树的叶子节点。从哈夫曼树根节点开始到叶子节点最短路径就是相应对象的哈夫曼编码。

路径的标识可以将根节点到左节点设置为0，到右节点设置为1，路径的编码标识结果就是一个二进制数值。

哈夫曼树构建过程

1，将对象放入一个列表；

2，从列表中取出（删除）一对其重要性指标值最小及次之的对象，作为二叉树的左右节点，然后为其添加一个根节点；

3，将2中的根节点下子节点重要性指标值相加，结果作为根节点重要性指标值，并将该根节点作为一个虚拟对象，添加到步骤一构建的列表中；

4，如果列表的对象数目大于等于2，重复2，3，否则结束。

例子

哈夫曼编码特征

1，哈夫曼树根节点到达每个叶子节点（对象）的路径不一样，都是独一无二的，所以任一短的对像编码都不会成为其他长的对象编码的前缀，这种编码特性为前缀编码。

这一点与文字不同，如一些短的单词可能是长单词的前缀，比如do，就是doom的前缀。

单词因为在书写时会使用空格分开，所以不存在无法确定“do“，是单词do，还是单词doom的前缀的问题。

在面向数据流的编码中，数据被编码成了一串无分隔符分割的二进制流，所以数据前缀编码是必须的。

2，由于二叉树左右节点顺序并无规定，所以编码结果并不唯一。比如上述例子中，将C，D的根节点左移，产生的编码不同（如下图所示），但是节点的深度不变，所以编码长度不变， 编码效率不变。

3，事实上，根节点到左右节点路径标识哪边为0，哪边为1并不重要，最终的编码结果都是前缀编码。