NРYРYРNР 优秀Р 及格Р不及格Р 良好Р Р Р假设学生成绩对于不及格,及格,中等,良好和优秀的分布概率分别为5%,15%,40%, 30%,10%,以它们做为叶子的权值来构造哈夫曼树,如图所示.此时带权路径长最短,其值210%.它可以使大部分的分数值经过较少的比较次数得到相应的等级.但是,事物往往不是绝对的,此时每个判断的框内条件都较为复杂,需比较两次,反而降低运行效率.所以我们采用折中作法,调整后得图判定树,更加切合实际.РX<80РYРNРX<70РX<90РYРNРYРNРX<60Р中等Р良好Р优秀РYРNР不及格Р及格Р3.2 用于通信编码Р在电报通讯中,电文是以二进制的序列传送的.在发送端需要将电文中的字符序列转换成二进制的序列,而在接收端又需要把接收的序列转换成对应的字符序列.Р例如给出一段电文:Р Р电文中只使用了这四种字符,各字符出现的频度分别是,若进行等长编码,需要两位二进制位,可依次编码为Р Р则所发电文是:Р Р采用不等长编码要避免译码的二义性.例如,字符的编码是字符的编码的前缀部分.这样对于代码串,既是的代码,也是和的代码,因此,这样的编码不能保证译码的唯一性.Р所以,若对某一字符集进行不等长编码,可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树,且约定左子树表示字符,右子树表示字符,则可以用从根结点到叶结点路径上的分支字符组成的字符串作为该叶子结点字符的编码.为了获得传送电文的最短长度,可将每个字符出现的频率作为字符结点的权值赋给该结点,从而求出此树的最小带权路径长度就等于求出了传送电文的最短长度.Р因此,求传送电文的最短长度问题就转化为求由字符集中所有字符作为叶子结点和由字符的出现频度作为其权值所产生的哈夫曼树的问题.Р例如,,各字符出现的概率为,对各概率取整,得到各字符的权值,利用它们构造哈夫曼树,如图所示,则各字符的编码为:.
全文预览
