一、什么是哈夫曼树（Huffman Tree）
哈夫曼树是在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。
首先说说什么是带权路径长度：
权 指的是结点上的权重，图中仅展现出叶子结点的权重，叶子结点即一棵树最末端的结点，图中的叶子结点有：H,I,E,F,G。当然除了叶子结点以外的结点，也可以有权重~
路径长度 指的是从一个结点到另一个结点（不一定是叶子结点）所经过的“边”的数量
结点的带权路径长度 指的是树的根结点到该结点的路径长度，和该结点权重的乘积，即：根结点到该结点的边数 x该节点权重
比如，F结点的带权路径长度为：2*4（A到F的边数 x F结点权重）
树的带权路径长度 指的是所有 叶子结点的带权路径长度之和，简称为WPL。
比如，这个图1所示的树的带权路径长度为3X3 + 6X3 + 1X2 + 4X2 + 8X2 = 53。
哈夫曼树 指的是带权路径长度最小的二叉树
我们知道，给定叶子结点以及结点上的权重，能构造出不同的二叉树，比如下面图2这样，左边那棵树的带权路径长度为46，右边那棵树的带权路径长度为53，那么怎么才能构造出带权路径长度最小的二叉树呢？
二、哈夫曼树的构建
第一步：将叶子结点按权重从小到大排列，如图1左边队列
第二步：将权重最小的两个叶子结点从队列中拿出，构建二叉树生成新的父结点，将父结点插入队列中，使得队列依旧是从小到大排列。
第三步：重复上述步骤，从队列取出最小两个结点，加入二叉树，将生成的新父结点插回队列，使队列依旧是从小到大排列：
直到队列中仅剩下一个新生成的父结点，说明整个森林已经合并成了一颗树，而图11这棵树就是我们想要的哈夫曼树。由于每两个结点都要进行一次合并，因此，若叶子结点的个数为n，则构造的Huffman树中新增结点的个数为n-1
三、哈夫曼编码——以word2vec为例
Huffiman编码 指的是利用Huffman树设计的二进制前缀编码
在很多情况下，比如发电报，我们需要把文字转成编码，并且希望编码的长度越短越好，接下来我们思考这样一个问题：将"AFTER DATA EAR ARE ART AREA"这串文字利用二进制转换为0，1编码，这里用到的字符集为"A, E, R, T, F, D"，要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制(2^3=8>6)，可分别用000, 001,010,011, 100, 101对"A, E, R, T, F, D"进行编码发送，但这样的编码方式会随着出现的字母增多，使得每个字母的编码长度均都增长，有没有什么方法可以缩短编码长度呢？
emmm......使用哈夫曼编码。
在实际应用中,各个字符的出现频度或使用次数是不相同的，上述"AFTER DATA EAR ARE ART AREA"字符集为"A, E, R, T, F, D"，各字母出现的次数为8, 4, 5, 3, 1, 1，那么在编码的时候，自然会想到，可以让使用频率高的用短码，使用频率低的用长码,以优化整个报文编码。
怎么使用呢.....?
将文中出现的每个字符作为叶子结点，其结点权重就是该字符在文中出现的频率。因为将字符作为叶子结点可以保证一个字符的编码不是另一个字符编码的前缀，利用词频作为权重构建Huffman树，即构建带权路径长度最小的树，可以使得词频高的字符编码长度短，这样一来发送的报文总长就缩短了。
举个栗子吧......！
图12给出了六个词的Huffman编码，其中我们约定在构建Huffman树时，词频较大的叶子结点为左孩子且编码为1，词频较小的叶子结点为右孩子且编码为0（当然你也可以反着来，只是为了方便统一），这样一来, “我”、“喜欢”、“观看”、“巴西”、“足球”、“世界杯”这六个词的Huffman编码分别为0, 111, 110, 101, 1001和1000。
四、word2vec中Huffman编码的应用
我们先简单回忆一下传统的word2vec模型吧......
word2vec根据输入输出的不同分为CBOW(Continuous Bag-of-Words词袋模型)与Skip-Gram两种模型。CBOW模型的训练输入是某一个特征词的上下文相关的词对应的词向量，而输出就是这特定的一个词的词向量。Skip-Gram模型思路是反着来的，即输入是特定的一个词的词向量，而输出是特定词对应的上下文词向量。
1、输入层：上下文单词的onehot. {假设单词向量空间dim为V，上下文单词个数为C}
2、所有onehot分别乘以共享的输入权重矩阵W. {VxN矩阵，N为自己设定的数，初始化权重矩阵W}
3、所得的向量 {因为是onehot所以为向量}相加求平均作为隐层向量, size为1xN.
4、乘以输出权重矩阵W' {NxV}
5、得到向量 {1xV}激活函数处理得到V-dim概率分布,其中的每一维斗代表着一个单词
6、在训练阶段：利用交叉熵损失进行反向传播更新网络。在预测阶段：概率最大的index所指示的单词为预测出的中间词（target word）
1、输入层：中心词的onehot. {假设单词向量空间dim为V}
2、中心词的onehot乘以权重矩阵W. {dxV矩阵，d为自己设定的数，初始化权重矩阵W}
3、所得的向量作为隐层向量, size为dx1.
4、乘以c个不同的输出权重矩阵W' {Vxd}，c为需要预测的上下文单词数
5、得到c个向量 {Vx1}激活函数处理得到c个V-dim概率分布,其中的每一维斗代表着一个单词
6、在训练阶段：利用极大似然 maxP(w1,w2...wc∣wt)作为损失，利用朴素贝叶斯的独立性假设将损失简化为max∏P(wi∣wt)，其中wt为中心词，wi为窗口内出现的上下文，进行损失的反向传播更新网络。在预测阶段：概率最大的index所指示的单词为预测出的上下文词。
接下来介绍改进版的word2vec模型......
为了避免要计算隐藏层到输出层的所有词的softmax概率，word2vec采样了huffman树来代替从隐藏层到输出softmax层的映射。
以CBOW为例子，看看word2vec怎么应用huffman的吧：
1、用c个上下文的one-hot编码分别乘上矩阵W，得到c个隐藏层编码v后求平均得到如下图的隐藏层编码θ
2、将词库所有词做为叶子结点，其词频作为叶子结点权重，构建一棵huffman树
3、由于CBOW的目标是找到一个叶子结点（就是要找到最有可能的中心词），考虑huffman树是一棵二叉树，所以从根节点到叶子结点的每一步都是在做一个二分类的选择，那么选择一个最有可能的叶子结点的过程可以分解成从根结点0出发到其孩子结点1，再从1到其孩子结点2，.....直到最后叶子结点k，这个过程写成数学公式就是：
P(叶子结点k |根节点0) = P(结点1∣根结点0) x P(结点2∣结点1) x P(结点3∣结点2) x ....P(叶子结点k∣结点k-1)
因为是二叉树，可以用sigmoid函数去做二分类，获取P(结点i∣结点i-1)的概率 ，sigmoid公式如下：
其中的x为隐藏层编码θ，w为需要更新参数，P(选择右孩子) = 1 - P(选择左孩子)，这是因为我们约定sigmoid计算出的概率为选择左孩子的概率
！！注意：每个结点内储存的sigmoid参数w是不一样的，是随机初始化且可以被训练的参数
测试阶段：
1、从根节点开始，x=隐藏层编码θ，w=该节点存储的参数(参数个数与隐藏层编码维度一致)，计算sigmoid结果，结果大于0.5，则选择左孩子，记录编码1；反之选择右孩子，记录编码0，假设此时到达结点1
2、从结点1开始，x=隐藏层编码θ，w=该节点存储的参数(参数个数与隐藏层编码维度一致)，计算sigmoid结果，结果大于0.5，则选择左孩子，记录编码1；反之选择右孩子，记录编码0，假设此时到达结点2
3、重复上述步骤，直到根结点，获取的编码即为huffman编码，找到对应的字符即为模型的预测结果
训练阶段：
我们首先获取标签的huffman编码，根据huffman编码从根结点到标签叶子结点的概率，举个栗子，标签编码为010，那么：
1、从根节点开始，x=隐藏层编码θ，w=该节点随机初始化参数(参数个数与隐藏层编码维度一致)，计算sigmoid结果P，记作P1(注意我们约定P是走向左孩子结点的概率！)，由于第一位编码是0，为右孩子，所以得到0的概率为1-P1
2、重复上述步骤，得到第二位编码1的概率为P2，得到第三位编码0的概率为1-P3
3、最终我们可以计算出得到标签编码的概率为(1-P1) x P2 x (1-P3)，为什么只需要计算走到标签叶子结点而不需要结算走到其他叶子结点的概率呢，因为交叉熵损失只需要用到label为1处的概率~
4、最后计算交叉熵，进行损失的反向传播，更新网络参数和每个结点上存着的sigmoid函数的w向量参数
Skip-Gram模型对huffman的应用是一样的，就不再赘述了....
