霍夫曼树 -- 分层softmax(Hierarchical Softmax)，构造霍夫曼树来代替标准softmax

1 前言

霍夫曼树是二叉树的一种特殊形式，又称为最优二叉树，其主要作用在于数据压缩和编码长度的优化。

2 重要概念

2.1 路径和路径长度

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

图2.1

 

图2.1所示二叉树结点A到结点D的路径长度为2，结点A到达结点C的路径长度为1。

2.2 结点的权及带权路径长度

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
图2.2展示了一棵带权的二叉树

 

图2.2

2.3 树的带权路径长度

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
图2.2所示二叉树的WPL：
WPL = 6 * 2 + 3 * 2 + 8 * 2 = 34；

3 霍夫曼树

3.1 定义

给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为霍夫曼树(Huffman Tree)。
如图3.1所示两棵二叉树

 

图3.1

叶子结点为A、B、C、D，对应权值分别为7、5、2、4。
3.1.a树的WPL = 7 * 2 + 5 * 2 + 2 * 2 + 4 * 2 = 36
3.1.b树的WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3 = 35
由ABCD构成叶子结点的二叉树形态有许多种，但是WPL最小的树只有3.1.b所示的形态。则3.1.b树为一棵霍夫曼树。

3.2 构造霍夫曼树

构造霍夫曼树主要运用于编码，称为霍夫曼编码。现考虑使用3.1中ABCD结点以及对应的权值构成如下长度编码。
AACBCAADDBBADDAABB。
编码规则:从根节点出发，向左标记为0，向右标记为1。
采用上述编码规则，将图3.1编码为图3.2所示：

图3.2

 

构造过程：
3.1.a所示二叉树称为等长编码，由于共有4个结点，故需要2位编码来表示，编码结果为：

如果假设有AACBCAADDBBADDAABB

对应编码为：
00 00 10 01 10 00 00 11 11 01 01 00 11 11 00 00 01 01
长度为36。
3.1.b构造过程如下：
1）选择结点权值最小的两个结点构成一棵二叉树如图3.3：

 

图3.3

 

2）则现在可以看作由T1，A，B构造霍夫曼树，继续执行步骤1。
选则B和T1构成一棵二叉树如图3.4：

 

图3.4

3）现只有T2和A两个结点，继续执行步骤1。
选择A和T2构成一棵二叉树如图3.5：

 

图3.5

 

经过上述步骤则可以构造完一棵霍夫曼树。通过观察可以发现，霍夫曼树中权值越大的结点距离根结点越近。
按照图3.5霍夫曼树编码结果：

假设AACBCAADDBBADDAABB

对应编码为：
0 0 110 10 110 0 0 111 111 10 10 0 111 111 0 0 10 10
编码长度为35。
由此可见，采用二叉树可以适当降低编码长度，尤其是在编码长度较长，且权值分布不均匀时，采用霍夫曼编码可以大大缩短编码长度。

4 结语

本文主要介绍了霍夫曼树和如何构造一棵二叉树，霍夫曼编码实现过程中运用到了贪心算法。

原文链接：https://www.jianshu.com/p/5ad3e97d54a3