首页 > 试题广场 >

最优编码情况下该字串的长度是多少bit?

[单选题]
给字母重新进行二进制编码,以使得"MT-TECH-TEAM"(包含连字符,不包含引号)的长度最小.并能够根据编码,解码回原来的字符串.请问最优编码情况下该字串的长度是多少bit? 
  • 12
  • 33
  • 36
  • 84
  • 96
添加回答
推荐
SunburstRun头像 SunburstRun
答案是B
            字母有点多,T:3  E:2  M:2   --:2   C:1  A:1  H:1
形成哈夫曼树:
    
编辑于 2015-11-07 16:31:52 回复(3)
九鼎烹头像 九鼎烹
[大图]
发表于 2015-11-27 15:15:58 回复(0)
色诺芬头像 色诺芬
我也是服了……高票的两个哈夫曼树压根就是错的，每一层从左到右从小到大排序，不知道为什么还有这么多人点赞，也不自己思考一下……
发表于 2017-09-05 10:35:04 回复(6)
飞虹舞毓头像 飞虹舞毓
哈夫曼编码，统计每个单词出现的次数，进行排序，每次合并最小的两个，把合并的值带入，删除原来的两个值后，继续排序，直到最后只剩下一棵树

发表于 2016-03-20 21:54:08 回复(5)
Nicolos头像 Nicolos
发表于 2017-08-30 01:05:08 回复(0)
牛客541440号头像 牛客541440号
根据信息熵，这个字符串的信息量为：27.588bit（也就是压缩的极限），就预估了33
发表于 2016-04-07 22:08:27 回复(3)
huixieqingchun头像 huixieqingchun
最短的编码就是用哈夫曼编码的方式。
发表于 2016-06-02 20:47:50 回复(1)
逗比请来的猴子头像 逗比请来的猴子

构件霍夫曼树的过程参见

发表于 2018-03-21 13:17:06 回复(0)
Geek-头像 Geek-
字符串一共有12个char，8个不同的字符，等长编码情况下至少需要3个bit位(2^3>=8)，则等长编码情况下共需要12*3=36个bit。由此排除选项CD。对于选项A，12个bit编码长为12的字符串意味着每个字符只用了1个bit编码，显然不可能(2^1<8)。所以不用构造huffman树的情况下就可以选出B.
发表于 2017-04-01 12:47:33 回复(0)
明朗晨光头像 明朗晨光
 按照不同种类字符出现的次数构造哈夫曼树。路径即相应字母的二进制编码长度，每个字母出现的次数即权值。次数*每个字母的二进制编码长度=树的带权路径长度
编辑于 2016-02-26 19:06:34 回复(0)
KwonYuri头像 KwonYuri
其实就是构造哈夫曼树
发表于 2016-04-18 16:23:19 回复(0)
陳丶奕丶迅头像 陳丶奕丶迅
根据字母出现的次数构建哈夫曼树，求带权路径长度即可。
发表于 2022-08-05 12:08:50 回复(0)
大仙呀呀呀头像 大仙呀呀呀
霍夫曼编码不一定是最优的吧， 算术编码有可能更好点。 这一波站用信息熵得出答案的老哥。
发表于 2021-07-05 19:30:11 回复(0)
村长王兰花头像 村长王兰花
这道题应该有很多哈夫曼树吧 不止一种吧
发表于 2019-10-17 08:29:36 回复(0)
午夜阳光1头像 午夜阳光1
根据字母出现的次数进行哈夫曼编码
发表于 2018-09-05 15:01:36 回复(0)
星之刃头像 星之刃
哈夫曼编码，做出来了
发表于 2018-03-14 11:16:38 回复(0)
Linsanity头像 Linsanity
最优的编码就是用哈夫曼编码的方式，分别计算每个字符出现的次数，作为哈夫曼编码的值进行树的构造
发表于 2017-05-05 22:39:16 回复(0)
提交观点

问题信息

树
来自：美团2016研发工程师...
难度：
17条回答 15754浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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