哈夫曼编码

毕业多年发现写业务写废了，需要重新捡回算法。

概念

哈夫曼编码是利用哈夫曼树生成的编码方式，其特点是编码长度最短，常用于数据压缩。哈夫曼树是带权路径总长度最小的树，又称为最优二叉树，所谓最优二叉树是指所有叶子节点的带权路径和最小的树。树中一个节点的带权路径就是该点的权值乘以其到根节点的距离。
即：

WPL = W1 * L1 + W2 * L2 + ... + Wn * Ln

(数字为节点的权值)
S = {a1, b3, c6, d2, e7, f1, g2}

{(a1/\f1)2, b3, c6, d2, e7, g2}
{((a1^f1)2/\d2)4, b3, c6, e7, g2}
{((a1^f1)2/\d2)4, (b3/\g2)5, c6, e7,}
{(((a1^f1)2^d2)4/\(b3^g2)5)9, c6, e7}
{(((a1^f1)2^d2)4/\(b3^g2)5)9, (c6/\e7)13}
((((a1^f1)2^d2)4^(b3^g2)5)/\(c6^e7)13)22

^表示一个二叉树的左右子节点连接
/\表示一个二叉树的根节点
数字为左侧结构的根节点权值
加粗为当前步骤生成的二叉树部分
最后一步集合为空，得到的二叉树即为哈夫曼树

((((a1^f1)2^d2)4^(b3^g2)5)/\(c6^e7)13)22
依次读出

版权属于：一名宅。
本文链接：https://zhaiyiming.com/archives/huffman.html
转载时须注明出处及本声明