首页 > 试题广场 >

哈弗曼编码是一种无损二进制熵编码算法，其加权路径长度最小，字

[单选题]
哈弗曼编码是一种无损二进制熵编码算法，其加权路径长度最小，字符串 "alibaba" 的二进制哈弗曼编码有___位（bit） 
  • 11
  • 12
  • 13
  • 14
查看答案及解析
添加回答
楚云天头像 楚云天
构造哈弗曼树：
1、首先a(3)、b(2)、i(1)、l(1)分别单独构成一个树（节点），节点的权重是字符出现的频率；
2、先将权重最小的两个节点结合组成一个新的节点（新节点的权重为子节点的权重之和），然后依次这样进行，最终所有的节点组成一个树；
3、对于每个节点，其左边值为0，右边值为1；所有的叶节点均为文本中出现的字符。
   weight(2)                                     weight(4)                                         weight(7)                                 
                                                      0/            \1                                           0/    \1
     0 /   \ 1                ->    weight(2)                  b(2)     ->                   weight(4)    a(3)
                                       0 /   \1                                                            0/   \1
     l(1) i(1)                     l(1)    i(1)                                              weight(2)    b(2)
                                                                                                        0 /  \1
                                                                                                       l(1)   i(1)

所以，对于a/b/l/i 他们对应的霍夫曼编码
a:1;
b:01;
i :001;
L:000;
长度：1+3+3+2+1+2+1=13
发表于 2015-12-08 20:25:55 回复(2)
更多回答
推荐
Naruto头像 Naruto
C 13个。
各字符出现的频率分别为： a (3), b (2), l (1), i (i)。
构造哈夫曼树：
        7
     /     \
(1)4      a(0)
   /  \
 2     b
/ \
l  i

a: 0         
b: 10
l: 111
i: 110

alibaba编码长度为：  1+3+3+2+1+2+1 = 13




编辑于 2016-02-27 15:30:13 回复(12)
948937912头像 948937912
哈弗曼树又叫做最优二叉树，是权值越大的点离根节点越近，导致整个树权值最小
方法：选择值最小的两个点作为左右节点，然后和作为父节点，在剩下的点以及父节点中选择最小的两个依次构造，形成哈弗曼树
左边数值是0，右边是1
哈弗曼编码是将各个点的值加起来最小
长度计算就是把各个点的值乘以路径长加起来
例a(3),b(2),l(1),i(1)

长度就是3(l+i)+2b+1a;把abli换成他们对应的3 2 1 1就是13
发表于 2016-12-08 18:02:32 回复(5)
wangChaoNK头像 wangChaoNK
先利用不同的字母的权重,构建最优Huffman树 ,然后进行Huffman编码,每一个不同的字符都是由一定的二进制数进行表示,然后进行相加
在本题中 假如
a:1;一位
b:01;二位
i :001;三位
L:000;三位
则长度 alibaba 就是1*3+3+3+2*2=13
发表于 2017-04-09 14:42:07 回复(2)
牛客979335号头像 牛客979335号
应该选c，构造哈夫曼树的最短路径，越接近根节点，权值越小，a,b,l,i从多到少，从根节点开始，左0右1构造哈夫曼树，依次为a(0)b(10)l(110)i(111)这样哈夫曼编码为0 110 111 10 0 10 0共13位，此为最短
编辑于 2015-10-15 13:15:04 回复(1)
唐飞dream头像 唐飞dream

分析：构造哈夫曼树：l(1)、i(1)、b(2)、a(3) 

7
/ \
4 a
/ \
2  b
/\ 
l  i

a 0

b 01

l 000

i 001

带入alibaba字符串后的“1+3+3+2+1+2+1=13”

发表于 2015-11-04 22:49:03 回复(1)
rppp头像 rppp
根据字符出现的次数，构造哈夫曼树
a出现3次       b出现 2       l出现 1      i出现 1
             7
        4        3
   2      2
1   1                       3+2*2+1*3+1*3 = 3+4+3+3 = 13
发表于 2017-07-27 21:43:55 回复(0)
夏墨1头像 夏墨1
         7
  [0]/       \ [1]   
   a         4   
          [0]/  \ [1]
           2     b
      [0]/ \ [1]
         l  i
发表于 2021-03-13 23:16:17 回复(0)
mmm_mmm头像 mmm_mmm
二进制哈弗曼编码有多少位就是"求其最小带权路径长度 ",简单点,出题的方式简单点......
发表于 2018-08-20 20:08:06 回复(0)
夏花爱秋叶头像 夏花爱秋叶
3个a,2个b， 3×1（a）+2×2（b）+1×3+1×3
发表于 2018-02-20 20:51:49 回复(0)
苔上雪告诉我头像 苔上雪告诉我
哈弗曼树又叫做最优二叉树，是权值越大的点离根节点越近，导致整个树权值最小 方法：选择值最小的两个点作为左右节点，然后和作为父节点，在剩下的点以及父节点中选择最小的两个依次构造，形成哈弗曼树 左边数值是0，右边是1 哈弗曼编码是将各个点的值加起来最小 长度计算就是把各个点的值乘以路径长加起来 例a(3),b(2),l(1),i(1) 长度就是3(l+i)+2b+1a;把abli换成他们对应的3 2 1 1就是13
发表于 2017-08-13 22:21:59 回复(0)
xuhongyanphp头像 xuhongyanphp
各字符出现的频率分别为： a (3), b (2), l (1), i (i)。
构造哈夫曼树：
        7
     /     \
(1)4      a(0)
   /  \
 2     b
/ \
l  i

a: 0         
b: 10
l: 111
i: 110

alibaba编码长度为：  1+3+3+2+1+2+1 = 13

发表于 2016-07-06 10:14:09 回复(0)
HeroMan头像 HeroMan
哈夫曼树是怎么画的
发表于 2015-10-12 20:54:40 回复(0)
muyi头像 muyi 
答案给错了，正确答案应该是C

发表于 2015-09-20 17:14:17 回复(0)
发条毛虫头像 发条毛虫
哈弗曼编码又叫前缀编码，不能有任何一个编码是其他的前缀
发表于 2015-08-31 21:00:16 回复(0)
偶尔做天使头像 偶尔做天使
构造哈夫曼树：l(1)、i(1)、b(2)、a(3) -> 3+3+2+2+1=11
7
/ \
4 a
/ \
2  b
/\ 
l  i
编辑于 2015-04-14 15:40:46 回复(0)
提交观点

问题信息

树
上传者：飞鱼
难度：
16条回答 8781浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号