试题-哈弗曼编码是一种无损二进制熵编码算法，其加权路径长度最小，字符串“alibaba”的二进制哈弗曼编码有___位（bit）

题目

哈弗曼编码是一种无损二进制熵编码算法，其加权路径长度最小，字符串“alibaba”的二进制哈弗曼编码有___位（bit）

A.11

B.12

C.13

D.14

上一题 暂无更多

解答

正确答案是 C

各字符出现的频率分别为： a (3), b (2), l (1), i (i)。

构造哈夫曼树：

/ \

(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

C 10条回复评论

阿然

没看这篇帖子之前完全不懂该咋答

发表于 2022-01-26 23:00:00

0 0

假期

Ccccccccc

发表于 2021-02-01 23:52:28

0 0

期待

最优二叉树算法

发表于 2021-02-01 11:09:10

0 0

子不语

哈弗曼编码又叫前缀编码，不能有任何一个编码是其他的前缀

发表于 2021-10-08 10:27:51

0 1

小茉莉

根据字符出现的次数，构造哈夫曼树

a出现3次 b出现 2 l出现 1 i出现 1

4 3

2 2

1 1 3+2*2+1*3+1*3 = 3+4+3+3 = 13

发表于 2018-10-13 11:46:55

0 0

人间喜剧

哈弗曼树又叫做最优二叉树，是权值越大的点离根节点越近，导致整个树权值最小方法：选择值最小的两个点作为左右节点，然后和作为父节点，在剩下的点以及父节点中选择最小的两个依次构造，形成哈弗曼树左边数值是0，右边是1 哈弗曼编码是将各个点的值加起来最小长度计算就是把各个点的值乘以路径长加起来例a(3),b(2),l(1),i(1) 长度就是3(l+i)+2b+1a;把abli换成他们对应的3 2 1 1就是13

发表于 2018-10-13 11:46:45

0 0

人间喜剧

先利用不同的字母的权重,构建最优Huffman树 ,然后进行Huffman编码,每一个不同的字符都是由一定的二进制数进行表示,然后进行相加
在本题中假如

a:1;一位

b:01;二位

i :001;三位

L:000;三位
则长度 alibaba 就是1*3+3+3+2*2=13

发表于 2018-10-13 11:46:34

0 0

皮皮鲁

应该选c，构造哈夫曼树的最短路径，越接近根节点，权值越小，a,b,l,i从多到少，从根节点开始，左0右1构造哈夫曼树，依次为a(0)b(10)l(110)i(111)这样哈夫曼编码为0 110 111 10 0 10 0共13位，此为最短