夫曼树是带权路径长度最小的二叉树,用途是平均查找信息的代价最小。 普通二叉树的用途也普通,比较通用,就是信息存储和查找。 普通二叉树可能有的只有一个子节点,而哈夫曼树一定有两个。题目的阐述: 以n进制编码方式对一个英文字串中的字符进行编码,每个不同的字符其编码不同.使得由新的编码替代原串后总码长最小,且输入0,1,2,...,n-1构成的数字串后,依照该编码方式可以正确的对译出唯一的英文原串. 如: n=3 英文原串为 abbcbaddace 其对应的一种编码方式为 a:00 b:01 c:020 d:021 e:022 原串对译后的编码为000101020010002102100020022 其码长为27 若输入编码串 0102002200 则对应的英文原串为 bcea 分 析: 假设英文原串中的字符存放于字符集s中,‖s‖= x,每个字符在字串中出现的概率为w[i],l[i]为字符i的编码长. 依题意得,对s集合中的不同字符进行n进制编码后要求 1)新字串的码长最短 wpl=∑w[i]*l[i] (i∈1..x) 使得在wpl是所有编码方式中的最小值 2)编码无二义性 任意一字符编码都不为其它字符编码的前缀 此题以哈夫曼树来解答是非常适宜的.n为此哈夫曼树的分叉数,s字符集里的元素即为此 n叉哈夫曼树的叶子,概率w[i]即为叶子结点的权重,从根结点到各叶子结点的路径长即为该叶子结点的编码长l[i].由哈夫曼树的思想可以知道哈夫曼树的建立是一步到位的贪心法,即权重越大的结点越靠近该树的根,这样,出现频率越大的字符其编码就越短. 但具体应该怎样建立起此n叉哈夫曼树呢?我们首先以n=2为例 : s={a,b,c,d} w=[3,1,2,1] 首先从w中选出两个最小权,1,1,将其删去,并以2(即1+1)替代 w=[3,2,2]; 再从新的w中取出两个最小权,2,2,将其删去,并以4(即2+2)替代 w=[3,4]; 依此类推,直到w中只一个值时合并结束,此时 w=[7] 以上两两合并的过程即为二叉哈夫曼树的建立过程,每一次的合并即是将两棵子树归于一个根结点下,于是可以建立二叉树如下: m 0? ?1 m m a 0? ?1 m m c 0? ?1 m m b d min-wpl=3*1+1*3+2*2+1*3=13 从某一根结点出发走向其左子树标记为0,走向其右子树标记为1,则可以得到以下编码 a,b,c,d对应的编码为 a:0 b:110 c:10 d:111 n=3时又是怎样一种情况呢? 设 s={a,b,c,d,e} w=[7,4,2,5,3} 则按权重排序可得 s={d,b,e,c,a} w=[7,5,4,3,2] 那么此哈夫曼树的树形应为怎样呢? 是以下的左图,还是右图,或是两者均不是 m m ? a ? ? ? m m l l m ? ? ? ? c a ? ? l l l l l m a d b e d ? ? l m b ? ? l l e c 显然,要带权路径长wpl最短,那么,此树的高度就应尽可能的小,由此可知将此树建成 丰满n叉树是最合理的,于是我们尽量使树每一层都为n个分枝. 对于这道题的情况,我们具体来分析. 按照哈夫曼树的思想,首先从w中取出权最小的三个值,即2,3,4,并以9(2+3+4)来代替,得到新的w=[9,7,5];再将这三个值合并成9+7+5=21这个结点.于是得到三叉哈夫曼树如下: m ? a ? l l m d b ? a ? l l l e c a wpl=1*7+1*5+2*2+2*3+2*4=30 以0..n-1依次标记每个根结点的n个分枝,则可以得到每个字符相对应的编码: a:22 b:1 c:21 d:0 e:20 我们发现对于这种情况恰巧每层均为n个分枝,但事实上并非所有的n叉哈夫曼树都可得到每层n个分枝.例于当n=3,‖s‖=6时就不可能构成一棵每层都为三个分枝的三叉树.如何来处理这种情况呢? 最简单的处理方式就是添加若干出现概率为0的空字符填补在n叉树的最下一层,这些权为0的虚结点并无实际意义但却非常方全便于这棵n叉树的建立.空字符的添加个数add的计算如下: y=‖s‖ mod (n-1) add=0 (y=1) add=1 (y=0) add=n-y (y>1) 虚结点的加入使得权重最小的n-add个字符构成了距根结点最远的分枝,使其它字符构成的n叉树保持了丰满的n叉结构. 例: n=3 s={a,b,c,d,e,f} w=[1,2,3,4,5,6} 则 y:=6 mod (3-1)=0 add=1 于是构成n叉树如下: -为虚结点 ? ? a ? l l m f e ? a ? l l m d c ? a ? b a - wpl=1*6+1*5+2*4+2*3+3*2+3*1+3*0=33 对应编码为: a:221 b:220 c:21 d:20 e:1 f:0