n叉哈夫曼树算法研究

《n叉哈夫曼树算法研究》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、题目的阐述：　　　以Ｎ进制编码方式对一个英文字串中的字符进行编码，每个不同的字符其编码不同．使得由新的编码替代原串后总码长最小，且输入０，１，２，．．．，Ｎ－１构成的数字串后，依照该编码方式可以正确的对译出唯一的英文原串．　　如：　Ｎ＝３　英文原串为　ＡＢＢＣＢＡＤＤＡＣＥ　　其对应的一种编码方式为　　Ａ：００　　Ｂ：０１　　Ｃ：０２０　　Ｄ：０２１　　Ｅ：０２２　　原串对译后的编码为０００１０１０２００１０００２１０２１０００２００２２　　其码长为２７　　若输入编码串　　　　０１０２００２２００　　则对应的英文原串为　ＢＣＥＡ

2、分　析：　　假设英文原串中的字符存放于字符集Ｓ中，‖Ｓ‖＝　Ｘ，每个字符在字串中出现的概率为Ｗ［ｉ］，Ｌ［ｉ］为字符ｉ的编码长．　　依题意得，对Ｓ集合中的不同字符进行Ｎ进制编码后要求　　　　１）新字串的码长最短　　　　　　　　　　ＷＰＬ＝∑Ｗ［ｉ］＊Ｌ［ｉ］（ｉ∈１．．Ｘ）　　　　　　　　使得在ＷＰＬ是所有编码方式中的最小值　　　　２）编码无二义性　　　　　　　　任意一字符编码都不为其它字符编码的前缀　　此题以哈夫曼树来解答是非常适宜的．Ｎ为此哈夫曼树的分叉数，Ｓ字符集里的元素即为此　　Ｎ叉哈夫曼树的叶子，概率Ｗ［ｉ］即为叶子结

3、点的权重，从根结点到各叶子结点的路径长即为该叶子结点的编码长Ｌ［ｉ］．由哈夫曼树的思想可以知道哈夫曼树的建立是一步到位的贪心法，即权重越大的结点越靠近该树的根，这样，出现频率越大的字符其编码就越短．　　　　但具体应该怎样建立起此Ｎ叉哈夫曼树呢？我们首先以Ｎ＝２为例　：　　Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ｝　　Ｗ＝［３，１，２，１］　　　首先从Ｗ中选出两个最小权，１，１，将其删去，并以２（即１＋１）替代　　　　Ｗ＝［３，２，２］；　　再从新的Ｗ中取出两个最小权，２，２，将其删去，并以４（即２＋２）替代　　　　Ｗ＝［３，４］；　　依此类推，直到

4、Ｗ中只一个值时合并结束，此时　Ｗ＝［７］　　以上两两合并的过程即为二叉哈夫曼树的建立过程，每一次的合并即是将两棵子树归于一个根结点下，于是可以建立二叉树如下：　　　　　　　　　　　　　　　　　　　　　　　　m　　　　　　　　　　　　　　　　　　　　　　０å　　æ１　　　　　　　　　　　　　　　　　　　　　　m　　　m　　　　　　　　　　　　　　　　　　　　　Ａ　　０å　　æ１　　　　　　　　　　　　　　　　　　　　　　　m　　　　m　　　　　　　　　　　　　　　　　　　　　　　Ｃ　　０å　　æ１　　　　　　　　　　　　　　　　　

5、　　　　　　　　　　　　　　　　　　　　　　　　　　　　　m　　　　　m　　　　　　　　　　　　　　　　　　　　　　　　　Ｂ　　　　　　Ｄ　　ＭＩＮ－ＷＰＬ＝３＊１＋１＊３＋２＊２＋１＊３＝１３　从某一根结点出发走向其左子树标记为０，走向其右子树标记为１，则可以得到以下编码　Ａ，Ｂ，Ｃ，Ｄ对应的编码为　　　Ａ：０　　　Ｂ：１１０　　　Ｃ：１０　　　Ｄ：１１１　Ｎ＝３时又是怎样一种情况呢？　　设　Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ｝　　　　Ｗ＝［７，４，２，５，３｝　　则按权重排序可得　　　　Ｓ＝｛Ｄ，Ｂ，Ｅ，Ｃ，Ａ｝　　　　　　　　　Ｗ＝

6、［７，５，４，３，２］　　那么此哈夫曼树的树形应为怎样呢？　　是以下的左图，还是右图，或是两者均不是　　　　　　　　　　　m　　　　　　　　　　　　　　　　　　　m　　　　　　　　å　　â　　　æ　　　　　　　　　　　　　　　å　æ　　　　　　　m　　　m　　　l　　　　　　　　　　　　　　l　　m　　　　　　å　æ　　å　æ　　Ｃ　　　　　　　　　　　　　　　Ａ　å　æ　　　　　　　　　　　　　l　　l　l　　l　　　　　　　　　　　　　　　　　　l　　m　　　　　Ａ　　Ｄ　Ｂ　　Ｅ　　　　　　　　　　　　　　　　　　Ｄ　å　

7、æ　　　　　　　　　　　　　　　　l　　　m　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Ｂ　　å　æ　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　l　l　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Ｅ　Ｃ　显然，要带权路径长ＷＰＬ最短，那么，此树的高度就应尽可能的小，由此可知将此树建成丰满Ｎ叉树是最合理的，于是我们尽量使树每一层都为Ｎ个分枝．　　对于这道题的情况，我们具体来分析．　　按照哈夫曼树的思想，首先从Ｗ中取出权最小的三个值，即２，３，４，并以９（２＋３＋

8、４）来代替，得到新的Ｗ＝［９，７，５］；再将这三个值合并成９＋７＋５＝２１这个结点．于是得到三叉哈夫曼树如下：　　　　　　　　　　　　　　　　　　　　　　　　　　m　　　　　　　　　　　å　　â　　æ　　　　　　　　　　l　　　l　　　m　　　　　　　　　　Ｄ