图解二进制哈夫曼编码

定义:哈夫曼编码是一种完全依据字符出现概率来构造异字头的平均长度最短的码字的方法(百度百科)

现有一段文言文,要通过二进制哈夫曼编码进行压缩。简单起见,假设这段文言文只由4个汉字“之”,“乎”,“者”,“也”组成,它们出现的次数分别为700,600,300,200。那么,“也”字的编码长度可能是

NOIP2011

我们可以把这几个字看成一个集合,先从大到小排序:之(700)  乎(600)  者(300)  也(200)

从中挑出最小的两个也(200)  者(300)

注意放到二叉树中要左小右大

这时候,集合就变成了之(700)  乎(600)  [者+也](500)

再次从大到小排序:之(700)  乎(600)  [者+也](500),从中挑出两个最小的[者+也](500)  乎(600)

这时候,集合变成了之(700)  [乎+[者+也]](1100)

同理,最后会变成

最后,我们给这棵二叉树标上值,左0右1

因此:

汉字对应的哈夫曼二进制的编码
0
11
101
100

所以这道题答案就是3

本站遵循「CC BY 4.0」创作共享协议,转载请注明出处