哈夫曼树 #
Lead in
对于一段报文CAST CAST SAT AT A TASA
usu, consider to encode as A 00 T 10 C 01 S 11
{C,A,S,T} as each ch‘s frequency {2,7,4,5}
to encode them as A 0 T 10 C 110 S 111
len = 7x1+5x2+(2+4)*x3 = 35 < 18 * 2
review
加权路径长度
- 叶子的深度*权值
树的外部路径权值/加权路径长度
- 所有叶子的~之和
Def #
给定
$$n_0$$个叶子带权值叶子结点的二叉树，存在一棵 加权路径长度最小 的树，称作最优树，也即哈夫曼树。
- 叶结点的权值越小，离根越远
- 越大，越近
- 是满二叉树FBT
- 是必要条件
构造：
- 根据给定的n个符号权值对{$s_i,w_i$}，造n棵二叉树的集合F={$T_1,T_2,...,T_n$}，其中每棵二叉树中均只含一个符号权值对为（$s_i,w_i$）的根节点，其左右子树均为空树
- 在F中选取根结点权值最小的两棵二叉树，分别作为**左（最小）右（次小）**子树构造新树，置该树根结点权值为左右子树权值之和。
- 从F中删除这两棵树，加入刚生成的新树。
- Rep until one tree left
哈夫曼编码 #
利用哈夫曼树可以构造一种不等长的二进制编码，使得它是一种最优前缀编码，即所传电文的总长度最短。
前缀编码：任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。
- 将每个字符的频度作为权值，构造哈夫曼树
- 将每个内部结点左右两条边赋上0、1的权值
- 将每个叶结点从根开始路径上的权值按顺序排列，即得该结点对应的字符编码码字
编码
- 求码字
- 把字符串->比特流