哈夫曼编码和哈夫曼树
简介
哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。主要思想就是：依据编码内容出现的频率来控制编码的具体字符的长度，以此来达到控制存储空间的目的。
原理
哈夫曼树的构造原理上来讲就是，让二叉树具有最优带权路径，那么也就是权重越大的节点越靠近根节点，够早的过程就是一个依据权重来构建二叉树的过程
假设有4个结点 (a, b, c, d),权值分别为 (7, 5, 2, 4),构造以此4个结点为叶子结点的二叉树。
以上的都是最优二叉树，也就是哈夫曼树，构造一般来说的话，采取第二种，遵循左小右大的规则，契合于二叉搜索树的概念。
带权路径长度
我们规定一个概念：代全路径长度：
Now assign to each leaf of the tree a value, (f(c)), which is the frequency of occurrence of the character c represented by the leaf.
Let (d_T(c)) be the depth of character c’s leaf in the tree T.
所以我们带权路径长度的计算公式就是(B(T) =displaystylesum^{N}_{n=1,c in C}{f(c) imes d_T(c)})
关于哈夫曼输的注意点
满二叉树不一定是哈夫曼树
哈夫曼树中权越大的叶子离根越近（很好理解，WPL最小的二叉树）
具有相同带权结点的哈夫曼树不唯一
哈夫曼树的结点的度数为0或2，没有度为1的结点。
包含n个叶子结点的哈夫曼树中共有2n – 1个结点。
包含n棵树的森林要经过n–1次合并才能形成哈夫曼树，共产生n–1个新结点
哈夫曼建树和编码过程
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/96778.html
