首页 > 代码库 > 霍夫曼编码求节省空间

霍夫曼编码求节省空间

霍夫曼编码将频繁出现的字符采用短编码,出现频率较低的字符采用长编码。具体的操作过程为:i)以每个字符的出现频率作为关键字构建最小优先级队列;ii)取出关键字最小的两个结点生成子树,根节点的关键字为孩子节点关键字之和,并将根节点插入到最小优先级队列中,直至得到一棵最优编码树。

    霍夫曼编码方案是基于______策略的。用该方案对包含a到f6个字符的文件进行编码,文件包含100000个字符,每个字符的出现频率(用百分比表示)如表1-3所示,则与固定长度编码相比,该编码方案节省了______存储空间。

表1-3  某文件中每个字符出现的频率

 

字符

a

b

c

d

e

f

出现频率(%)

18

32

4

8

12

26

 

64、 A.分治    B.贪心    C.动态规划    D.回溯

65、 A.21%    B.27%    C.18%    D.36%

1.在刷软件设计师题的时候碰到了上面这个题目,后面的答案简单的介绍了一下,没有介绍21%这个值是怎么算来的,所以想一探究竟(其实很简单,只能说自己基础差了)

64、B    

65、A

[解析] 依题意,霍夫曼编码方案是基于贪心策略的。用该方案对包含a~f6个字符的文件进行编码,文件包含100000个字符,每个字符的出现频率(用百分比表示)如表1-3所示,则与固定长度编码相比,该编码方案节省了21%的存储空间。

2.题目的关键点在与最优编码树,所以要先构建这个最优编码树。

技术分享

 

 

 最终得到结果18*2(00)+26*2(10)+32*2(11)+12*3(011)+4*4(0100)+8*4(0101)=236*1000

固定长度编码所以得知原来的编码结果为300*1000

236/3≈79;100-79=21;所以结果是A

总结:蹭一蹭,也许能发现其中的道理。

霍夫曼编码求节省空间