2024如何画哈夫曼树电文八个字母

一种构建极小多余编码的方法——哈夫曼树　　1952年，麻省理工学院的哈夫曼发表了一篇名为《一种构建极小多余编码的方法》的论文。提出了一种新编码方法。它基于有序频率二叉树编码的想法，自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树，并很快证明了这个方法是最有效的。所以又称为最优树，也叫哈夫曼树。　　正如论文标题，哈夫曼树最初的目的是为了解决当远距离通信数据传输二进制编码的最优化问题。　　例如：给定通信数据ABAABBABABBBBCCDFFGGAAAA…总计209个字符, 　　其中各字符个数为 A：60, B:45, C:13 D:69 E:14 F:5 G:3, 　　假设采用固定编码长度，表示7种字符至少需要3位，2的最小次方>=7, 　　编码表 A：000, B:001, C:011 D:010 E:110 F:101 G:111 　　最终二进制编码长度为209X3=627位　　现在给定如下编码表：　　字符编码A10B01C0011D11E000F00101G00100 　　最终二进制编码长度为60X2+45X2+13X4+69X2+14X3+5X5+3X5=482位　　那么会有个疑问，这么编码表不是最优的，不如我这个 A：01, B:0, C:10 D:1 E:110 F:101 G:111 　　这里涉及到另外一个问题: 保证长编码的不与短编码的字母冲突　　比如不能出现读码读到 01 还有长编码的字母为011，如果短编码为一个长编码的左起子串，这就是冲突，意思就是说读到当前位置已经能确定是什么字母时不能因为再读取一位或几位让这个编码能表示另外的字母。　　冲突情况：如果我们已经确定D，E，F，G 用 01 ，010 ，10，001的2进制编码来传输了。那么想传送FED时，我需要传送，接收方可以把它解析为FDG（10 01 001），当然也能解析为FED（10 010 01），他两编码一样的，这就是编码冲突。　　最优的编码表是如何构建的，为什么它是最优的，为什么它能保证长编码的不与短编码的字母冲突？　　首先统计出每种字符出现的权重，给出权重表：　　A：60, B:45, C:13 D:69 E:14 F:5 G:3, 　　第一步：找出字符中最小的两个，小的在左边，大的在右边，组成二叉树。在频率表中删除此次找到的两个数，并加入此次最小两个数的权重和。　　F和G最小，因此如图，从字符串频率计数中删除F与G，并返回G与F的和8给权重表

　　重复第一步：　　权重表 A：60, B:45, C:13 D:69 E:14 FG:8 　　最小的是FG：8与C：13，因此如图，并返回FGC的和：21给权重表。

　　重复第一步：　　权重表 A：60 B: 45 D: 69 E: 14 FGC: 21 　　如图

　　重复第一步　　权重表 A：60 B: 45 D: 69 FGCE: 35

　　重复第一步　　权重表 A：60 D: 69 FGCEB: 80

　　重复第一步　　权重表 AD：129 FGCEB: 80

　　添加 0 和 1，规则左0 右1

　　如上得到最优二叉树，也叫哈夫曼树，根据哈夫曼树得到的编码叫哈夫曼编码。　　回顾下算法步骤：　　(1)根据n个给定的权值{W1, W2,…,Wn}构成n棵二叉树的森林,F={T1, T2,…,Tn},其中Ti只有一个带权为Wi的根结点。构造森林全是根。　　(2)在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二又树的根结点的权值为其左右子树上根结点的权值之和。选用两小造新树。　　(3)在F中删除这两棵树，同时将新得到的二叉树加入森林中。删除两小添新人　　(4)重复(2)和(3),直到森林中只有一棵树为止，这棵树即为哈夫曼树。删除两小添新人　　哈夫曼算法口诀：①构造森林全是根;②选用两小造新树;③删除两小添新人;④重复2、3剩单根。　　为什么是最优二叉树（最优性的证明）　　要证明最优其实是要证明下面几个事情：

　　1.先证明权最小的两个数是最底层的兄弟节点　　因为V L m a x V_{L_{max}}VLmax是通路长度最长的的分支点，则其子节点必为叶子节点。假设 V L m a x V_{L_{max}}VLmax 只有一个叶子节点， V w x V_{w_x}Vwx ，则可以用子节点 V w x V_{w_x}Vwx代替分支节点 V L m a x V_{L_{max}}VLmax 得到新树 T n ∗ T_{n}^*Tn∗ ，则有：W ( T n ∗ ) = W ( T n ) − w x W ( T_{n}^*) = W ( T_n ) − w_xW(Tn∗)=W(Tn)−wx,与有 T n T_nTn 为最优树相矛盾。那么最底层一定有两个叶子节点。　　如果这两个节点不是最小的，那么把最小的和这两个点交换，则带权路径一定会减小，又与最优树矛盾。，所以得到结论：权最小的两个数是最底层的兄弟节点。　　2.证明最优树收缩和展开后仍然是最优的　　(在这里需要注意到每个存放数据的节点都是叶子节点，所以可以随意的展开和合并而不影响到其他节点）　　将V w 1 、 V w 2 V_{w_1}、V_{w_2}Vw1、Vw2 两个叶子节点收缩得到新树 T n − 1 ∗ （ w L m a x = w 1 + w 2 ) T_{n-1}^*（w_{L_{max} } = w_1+w_2)Tn−1∗（wLmax=w1+w2) ，令带权为{ w 3 、 w 4 . . . . w n 、 w 1 + w 2 w_3、w_4….w_n、w_1+w_2w3、w4….wn、w1+w2}的最优树为T n − 1 T_{n-1}Tn−1,反向展开得到的树为 T n ∗ T_n^*Tn∗。则有：W ( T n ) = W ( T n − 1 ∗ ) + ( w 1 + w 2 ) W(T_n)=W(T_{n-1}^*)+(w_1+w_2)W(Tn)=W(Tn−1∗)+(w1+w2)W ( T n − 1 ) = W ( T n ∗ ) − ( w 1 + w 2 ) W(T_{n-1})=W(T_n^*)-(w_1+w_2)W(Tn−1)=W(Tn∗)−(w1+w2)整理得：W ( T n ) − W ( T n ∗ ) + W ( T n − 1 ) − W ( T n − 1 ∗ ) = 0 W(T_n)-W(T_{n}^*)+W(T_{n-1})-W(T_{n-1}^*)=0W(Tn)−W(Tn∗)+W(Tn−1)−W(Tn−1∗)=0因为 T n 、 T n − 1 T_n、T_{n-1}Tn、Tn−1是最优树，当且仅当 W ( T n ) = W ( T n − 1 ∗ ) W(T_n) = W(T_{n-1}^*)W(Tn)=W(Tn−1∗)且W ( T n − 1 ) = W ( T n − 1 ∗ ) W(T_{n-1}) = W(T_{n-1}^*)W(Tn−1)=W(Tn−1∗) 时等式成立。即 T n ∗ 、 T n − 1 ∗ T_n^*、T_{n-1}^*Tn∗、Tn−1∗也是最优树。命题得证。　　3.哈夫曼树的创建现在我们获得了一些权重，我们想要把他放到最优编码树中，根据上面的结论，我们的构造原则就是：找到最小的两个，作为最底层的叶子节点；把他俩收缩（加起来），和剩余的权重混在一起，反复操作。其实这就是最开始给出的哈夫曼树的构造原则。　　综上我们得到了哈夫曼树为最优编码树的结论。　　为什么哈夫曼树能保证长编码的不与短编码的字母冲突　　哈夫曼树的它的字母都在叶子节点上，因此不会出现一个字母的编码为另一个字母编码左起子串的情况。　　哈夫曼树的java代码实现：　　相关引用：　　哈夫曼树原理，及构造方法_Anakki的博客-CSDN博客　　【数据结构】哈夫曼树的理解和最优性的证明_哈夫曼树怎么证明_鹏程不会飞的博客-CSDN博客

2024如何画哈夫曼树电文八个字母

相关推荐