1、前言：

1、参考了：

https://www.cnblogs.com/pinard/p/7160330.html

2、真的前言

前面在复习fasttext和word2vec的时候都提到了层次softmax，而层次softmax是建立在霍夫曼树的基础上的，所以下面简单复习一下霍夫曼树。

2、正经的：

霍夫曼树的建立过程：

1、输入：权重为（w1,w2,...,wn）的n个节点
2、输出就是对应的霍夫曼树
3、将（w1,w2,...,wn）看做是有n棵树的森林，每棵树只有一个节点
4、找森林中权重最小的两棵树，将他们合并，组成一个新的树，左右子树就是这两棵树，根节点就是这棵树的权重之和。
5、将刚才已经合并的两棵树，从整个森林中删掉。再把4中得到的合成的新树加入整个森林
6、重复4和5直至森林中就剩下一棵树为止，得到的这棵树就是霍夫曼树。
7、举例：假设我们有(a,b,c,d,e,f)共6个节点，节点的权值分布是(20,4,8,6,16,3)

丑图

什么是霍夫曼编码？

对每个字符设计不同的编码，让出现较多的字符，采用尽可能短的编码，利用霍夫曼树生成的二进制编码，叫霍夫曼编码。
对于路径上的各个分支，左子树的分支用0表示，右子树的分支用1表示。

image.png