试题详情
简答题 考虑用哈夫曼算法来找字符a，b，c，d，e，f的最优编码。这些字符出现在文件中的频数之比为20：10：6：4：44：16。要求： （1）简述使用哈夫曼算法构造最优编码的基本步骤； （2）构造对应的哈夫曼树，并据此给出a，b，c，d，e，f的一种最优编码。
  • 1）哈夫曼算法是构造最优编码树的贪心算法。其基本思想是，首先所有字符对应n棵树构成的森林，每棵树只有一个结点，根权为对应字符的频率。然后，重复下列过程n-1次：将森林中的根权最小的两棵树进行合并产生一个新树，该新树根的两个子树分别是参与合并的两棵子树，根权为两个子树根权之和。
    2）根据题中数据构造哈夫曼树如下图所示。

    由此可以得出a，b，c，d，e，f的一组最优的编码：01，0000，00010，00011，1，001。

  • 关注下方微信公众号，在线模考后查看

热门试题