哈夫曼编码

时间:2024-04-08 13:46:01

技术之瞳 阿里巴巴技术笔试心得习题2.71:
  字符串”alibaba”的二进制哈夫曼编码有(C)位。
  A、11   B、12   C、13   D、14

  分析:
  这题是考察哈夫曼的编码方式,它是根据字符出现频率构建的带权重二叉树确定每个字符编码的。首先我们统计“alibaba”各个字符出现频率:a-3,b-2,l-1,i-1。由出现的频率我们有以下哈夫曼二叉树:


哈夫曼编码

  对应每个字符编码为:

哈夫曼编码

  所以最终“alibaba”整个字符串的编码为0 100 101 11 0 11 0。也就是说该字符串二进制哈夫曼编码位数为13位。

  关于哈夫曼编码详细内容请另阅博文:
  http://blog.csdn.net/fx677588/article/details/70767446