哈夫曼树简介及C++代码实现 1. 哈夫曼树简介 节点的权重：在实际应用中，通常要给树中节点赋予有意义的值，称为节点权重（如度、访问频率等）。 树的带权路径长度WPL：weighted path length of tree。一个节点和根之间的路径长度与这个节点的权的乘积称为该节点的带权路径长度。树中所有叶子的带权路径长度之和称为树的带权路径长度。 
其中 代表叶子数目， 和 分别代表第 个叶子的权和它的路径长度。 最优二叉树（哈夫曼树）：在叶子数目为 ，其权分别为、 到 的所有二叉树中，树的带权路径长度WPL最小的树称为最优二叉树，即哈夫曼树。 例如，给定4个叶子，其权分别为7、5、2和4，图1显示了3棵带权路径长度不同的二叉树。
图1. 不同WPL的二叉树 哈夫曼树优点：权越大的叶子离根越近，权越小的叶子离根越远。例如键盘上的字符的排列规则为，使用频率越高的离食指越近。 2. 哈夫曼算法 哈夫曼算法：用于构造最优二叉树的算法。设长度为N的数组中存储了N个权重。 算法流程：构建哈夫曼树步骤如下： （1）由每个权重生成一个仅含根节点的二叉树，然后将根指针推入小根堆中。（2）以下操作重复多次，直到小根堆中仅存一个节点为止：从小根堆中删除2个节点，分别作为左右孩子，由它们的权重之和生成父节点，并将新建的二叉树根指针推入小根堆中。（3）将小根堆中仅存的一个结点返回，即为哈夫曼树的根节点指针。
图2. 哈夫曼树的构造过程 代码实现 运行结果 观察结果可知：对于测试用例，叶子3、6和7能够搜索到，从根到叶子结点权重累加和分别为100、103、95。如图3所示：
图3. 测试用例{20, 10, 7, 3, 6}构建的哈夫曼树 3. 哈夫曼算法应用 上文介绍的知识，主要是为这一部分作铺垫。笔者主要从事人工智能算法工作，对于算法从业者而言word2vec模型一定不陌生。word2vec模型本质是一个多分类模型，分类数等于词表大小 。当 很大时，word2vec的前向传播和反向传播计算量巨大，使得工程上基本不可行。针对这个痛点，作者提出几点工程优化思路：负采样 和 分层Softmax。而后者正是通过将原本的 输出 参数矩阵 转换为一棵 哈夫曼树（本质是将多分类转换为多个二分类），以达到降低计算复杂度的效果，优化后从 降到 。 以CBOW为例，如图4和图5所示。分层Softmax主要优化了输出 参数矩阵，将原本的输入 维向量和 矩阵的乘积+Softmax，优化为从根节点到叶子结点的Sigmoid值连乘。
图4. CBOW原始结构
图5. CBOW采用分层Softmax结构 具体思路为：将词表中的 个词作为叶子结点，按照每个词在训练语料中出现的频次构建哈夫曼树，高频词距离根节点较近，低频词距离根节点较远。完成哈夫曼树的构建后，在前向传播和反向传播过程分别如下：前向传播：输入样本为” eeimg=”1″> 时，将输入 参数矩阵的第 行取出，得到 并输入根节点。从根节点开始搜索 ，并将沿途经过的每个节点输出的sigmoid值进行连乘，作为输出词 的预测值。计算复杂度最坏为 ，如果输出词 所在层数较浅（距离根节点较近）则更低。反向传播：仅仅更新从根节点到叶子结点经过的节点的 参数（最多为个），没有经过的节点参数不会更新。这样就大大减少了梯度的计算量。 4. 总结 哈夫曼算法原理简单，代码实现也很直接。在数据结构的学习中也许觉得枯燥且无用，但是如果能在合适的场合进行合适应用，就会发现其神奇之处，算法能在生产中发挥巨大的价值（知识就是力量）！
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/70384.html
