首页 > 试题广场 >

用二进制来编码字符串“xyzwxyxx”，需要能够根据编码解

[单选题]
用二进制来编码字符串“xyzwxyxx”，需要能够根据编码解码回原来的字符串，则我们最少需要多长的二进制字符串 
  • 12
  • 14
  • 15
  • 18
  • 24
查看答案及解析
添加回答
ridikuius头像 ridikuius
答案：B
xyzwxyxx：x：4位、y：2位、z：1位、w：1位
用4、2、1、1构造哈夫曼树


编辑于 2015-10-11 08:37:45 回复(7)
SynchronizedHe头像 SynchronizedHe
哈夫曼编码的问题 x出现4次 y2次 w1次 z1次
x用0
y用10
w用110
z用111
w和z的编码方案可以互换
length=1*4+2*2+1*3+1*3=14
发表于 2015-09-15 16:21:41 回复(3)
0xEFBFBD头像 0xEFBFBD
这道题应该是使用信息论中信息熵来解决

信息熵表示一个字符串中每个字符的平均编码长度的理论极限值

根据信息熵计算的公式： 
所以这个题中  x,y,z,w出现的概率为1/2, 1/4, 1/8, 1/8

所以信息熵为 1/2 * log(1/2) + 1/4 * log(1/4) +  1/8 * log(1/8) +  1/8 * log(1/8) = 1.75 bit/symbol

即  每个字符最少占用1.75个bit

题目中字符串中含有8个字符，所以理论编码长度的极限为  1.75 * 8 = 14

发表于 2017-02-09 18:02:41 回复(2)
藤和艾莉欧。头像 藤和艾莉欧。
考察哈夫曼的编码方式，它是根据字符出现频率构建的带权重二叉树确定每个字符编码的。
本题图解如下

发表于 2019-07-15 11:30:53 回复(2)
痴心布偶头像 痴心布偶
先构造编码树，得到x=0 y=10 z=110 w=111 然后根据 字符出现的频率*字符的码字的长度 即x:4*1 + y:2*2 + z:1*3 + w:1*3 字符的二进制码字用从根节点到该字符叶结点的简单路径表示， 其中0意味着“转向左孩子” 1意味着“转向右孩子” 二叉树，叶结点为给定字符。字符的二进制码字用从根节点到该字符叶结点的简单路径表示。注意编码树不是二叉搜索树。 huffman cold
编辑于 2016-06-29 20:27:33 回复(1)
真新镇小智要成为宝可梦大师头像 真新镇小智要成为宝可梦大师
4次x,2次y,1次z,1次w,根据出现次数构造哈夫曼树，设左边为1,右边为0,最终把边上数值连起来得到x为0,y为10,z为110,w为111，x的编码长为1,y为2,z为3,w也为3，所以答案为每个符号编码长乘以次数的和为14
发表于 2022-09-07 14:47:42 回复(0)
Java开发外卖员头像 Java开发外卖员
xyzwxyxx：x4、y2、z1、w1
用4，2，1，1构造哈夫曼树
结果：（1+1）*3+2*2+4*1=14
发表于 2022-08-08 18:00:50 回复(0)
陳丶奕丶迅头像 陳丶奕丶迅
根据字符串中字符出现的次数构建哈夫曼树即可
编辑于 2022-07-19 16:56:23 回复(0)
EdisonPan头像 EdisonPan
这种编码是怎么确定的?
发表于 2016-08-30 19:02:16 回复(1)
牛客96407160号头像 牛客96407160号
我还想 xy，z，w， xx为四种不同的字符串两位二进制表示，xy, z, w,xy,xx有五个，2*5=10个二进制字符串就可以表示，当然，这是特例，但也是最少
发表于 2022-09-02 11:58:54 回复(0)
学术废物头像 学术废物
哈夫曼树
发表于 2022-03-19 14:02:59 回复(0)
技术菜菜菜财头像 技术菜菜菜财
最少二进制 哈夫曼编码
发表于 2022-02-25 12:55:38 回复(0)
WA的一声哭出来头像 WA的一声哭出来
最低编码
发表于 2021-11-14 16:44:21 回复(0)
环201711251539622头像 环201711251539622
xyzwxyxx：x：4位、y：2位、z：1位、w：1位
用4、2、1、1构造哈夫曼树
发表于 2017-11-25 16:08:52 回复(0)
扛竹子的伙夫头像 扛竹子的伙夫
上面几个回答简略了哈夫曼树的构造过程，补充一下：
a:4
b:2
c:1
d:1
将出现次数最少的（其实是出现频率最低的）两个数作为起始点相加，得到结果集合{4,2,2}，然后以此类推，得到{4,4}，在得到{8}，构造成哈夫曼树。
最后以向左的边（或向右均可，但固定一个方向为1，另一个方向为0）为0，向右为1，连接而成的01组成的代码就是对应的编码。
相关介绍：
发表于 2017-08-28 09:41:35 回复(0)
country_sing头像 country_sing
哈夫曼编码。。
发表于 2015-09-27 08:16:22 回复(0)
提交观点

问题信息

字符串
来自：美团2016研发工程师...
难度：
16条回答 16779浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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