我要招人

去企业版

首页 > 试题广场 >

用二进制来编码字符串 "abcdabaa"，需要能够根据编码

[单选题]

用二进制来编码字符串 "abcdabaa"，需要能够根据编码，解码回原来的字符串，最少需要()长的二进制字符串？

```
12
```
```
14
```
```
18
```
```
24
```

推荐

Jerry

这道题需要对abcd进行Huffman编码。首先根据权值建立Huffman树，得到最优编码：
a=0, b=10, c=110, d=111
然后数一下就行了。

发表于 2014-10-25 00:26:14 回复(7)

夏雨天

选择B：

发表于 2015-09-02 16:39:40 回复(3)

combatant

Huffman编码其他人已经给出，但结果不是唯一的。a：1位 b：2位 c: 3位 d：3位所以，abcdabaa一共占用 4 * 1 + 2 * 2 + 3 + 3 = 14

发表于 2015-07-17 05:10:19 回复(2)

了590

通过哈佛曼编码得： 4a*1 + 2b*2 + 1c*3 + 1d*1 = 14

发表于 2016-07-06 10:13:07 回复(0)

黏黏糖

此题考查哈弗曼编码。出现频率高的字符应离根节点近一些

发表于 2017-05-09 09:50:17 回复(0)

程序猿的程

即带权路径长度。

发表于 2017-05-05 00:02:48 回复(0)

绽放的四叶草

利用哈弗曼编码，可以算出a是1位，b是2位，c和d是3位，根据频率相加1*4+2*2+3+3=1

发表于 2015-12-29 10:51:43 回复(0)

石榴树

根据出现的频率进行霍夫曼树构造，最少需要二进制字符串的长度其实相当于求构造出的霍夫曼树的带权路径长度，可以自己动手写写，这个结构比较简单

发表于 2018-06-06 21:14:34 回复(0)

视觉算法工程师

最优的就是霍夫曼编码了，正好前两天在图像压缩的时候见到过，a=0, b=10, c=110, d=111 ，这个形式的就好。

发表于 2017-09-12 15:34:58 回复(0)

湘水西岸

二叉树如图所示，所以

a=1

b=01

c=000

d=001

编码不唯一。

发表于 2015-04-29 15:28:37 回复(5)

牛客541440号

按照信息论的思路，总的信息熵为H=-（1/2）log(1/2)-(1/4)log(1/4)-2*(1/8)log(1/8)=1.75。也就说每一位的信息量为1.75bit,总共有8位，总的信息量为：1.75*8=14bit。编码压缩的极限就是14bit了

发表于 2016-08-06 22:46:37 回复(11)

MSean

abcdabaa	a	b	c	d
频率	4	2	1	1
二进制字符	0	10	110	111

构建Huffman树，找到a、b、c、d对应二进制字符（上表所示），答案不唯一，求法可参考 @湘水西岸同学解法。

然后 a需要1位二进制字符，b需要2位，c和d各需要3位，总共至少：4 x 1 + 2 x 2 + 1 x 3 + 1 x 3 = 14

编辑于 2016-06-28 17:46:08 回复(1)

caojing

编码中学过等长编码与不等长编码不等长的就是将出现率高的设置为序列短的出现率低的设置为序列长的来保证整体的最短

发表于 2017-09-12 19:53:31 回复(0)

shiyan娃娃

a：1位 b：2位 c: 3位 d：3位所以，abcdabaa一共占用 4 * 1 + 2 * 2 + 3 + 3 = 14。

发表于 2017-08-24 23:01:03 回复(0)

Unicorn150

没说是按照字符编码的啊，我们为什么不能按照aa，ab，c，d编码呢？

发表于 2016-03-21 13:47:25 回复(3)

Amb

本题没说使用哈夫曼编码！所以为什么都说要使用哈夫曼?

难道用a=00，b=01，c=10，d=11，不能进行编码再还原？

或者我用1表示“abcdabaa”，那岂不是一位就能表示了！

题目有问题呀

发表于 2017-08-17 14:36:18 回复(4)

zhaowei11594

我压根就没想到这是用霍夫曼编码的方式来解决问题的....太菜
这道题需要对abcd进行Huffman编码。首先根据权值建立Huffman树，得到最优编码：
a=0, b=10, c=110, d=111
然后数一下就行了。图片说明

Huffman编码其他人已经给出，但结果不是唯一的。a：1位  b：2位  c: 3位  d：3位  所以，abcdabaa一共占用 4 * 1 + 2 * 2 + 3 + 3 = 14

发表于 2017-06-21 20:20:38 回复(1)

字节内推dd

首先计算各个字母出现的频度： A：4 B：2 C：1 D：1

二叉树如图所示，所以

a=1

b=01

c=000

d=001

编码不唯一。

所以说结果就是 1*4+2*2+3*1*2 = 4+4+6 = 14

发表于 2022-03-02 20:28:01 回复(0)

肉丸子fmh

哈夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

构造哈夫曼树来寻找存放一串字符所需要的最小二进制编码。（与之前常见题目相同：给定一组叶节点的权值，构造带权路径长度最短的二叉树。）

首先统计每个字符出现的次数，作为其权值，构造哈夫曼树，由此可以得到abcd四个字符分别的编码。

发表于 2021-06-25 17:52:47 回复(0)

少年泡

??这怎么解？四个不同的字符，不考虑/0,需要两位二进制编码，总共8个字符，不是16位吗？

发表于 2020-07-30 12:43:50 回复(0)

天尊墨宇

选B

发表于 2020-06-22 09:20:20 回复(0)

提交观点

问题信息

树

来自：Google2013笔试卷

难度：

41条回答 2906收藏 39509浏览

用二进制来编码字符串 "abcdabaa"，需要能够根据编码

问题信息

热门推荐

相关试题