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

概念

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

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

生成

  1. 从节点集合S中取出权值最小的两个节点a,b作为左右子节点建立二叉树T,并从S中删除a,b
  2. 将二叉树T的根节点重新加入集合S,其权值为a,b权值相加
  3. 重复前两步操作直至集合S为空,此时得到的二叉树即为一棵哈夫曼树
  4. 以左子节点为0右子节点为1即可依次读出树中子节点的编码

实例

已知

(数字为节点的权值)
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
依次读出

节点 编码 权值
a 0000 1
f 0001 1
d 001 2
b 010 3
g 011 2
c 10 6
e 11 7