java数据结构
假定用与通信的电文仅由6个字母ABCDEF组成,各字母在点稳重的出现频率分别是2781515305,请你设计它们的霍夫曼编码...
假定用与通信的电文仅由6个字母ABCDEF组成,各字母在点稳重的出现频率分别是27 8 15 15 30 5,请你设计它们的霍夫曼编码
展开
展开全部
首先明确,带权路径长度WPL最小的二叉树称作最优二叉树或哈夫曼树
那么比如说有4个节点,分别带权7,5,2,4如下ab两图
WPLa=7*2+5*2+2*2+4*2=36
WPLb=7*1+5*2+2*3+4*3=35
可以看到,出现概率越小的越应该放在下面(也就是说被遍历的概率小就可以代价大一点,而容易便利到的一定要减少开销)
其实是有一套算法的...从底往上,找最小的两个节点做和,做和得到的新结点和未被计算的节点重复“最小两节点做和”操作 最终结果:
WPL=30*2+5*5*4+8*4*15*3+15*2+27*2=
不算了 口算不行... 看上式也知道你出现的概率越大,相当于基地越大,就给你乘个小的代价,必然是最优的。
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询
广告 您可能关注的内容 |