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

admin2019-07-12  41

问题 霍夫曼编码将频繁出现的字符采用短编码,出现频率较低的字符采用长编码。具体的操作过程为:i)以每个字符的出现频率作为关键字构建最小优先级队列;ii)取出关键字最小的两个节点生成子树,根节点的关键字为孩子节点关键字之和,并将根节点插入到最小优先级队列中,直至得到一棵最优编码树。霍夫曼编码方案是基于(64)策略的,用该方案对包含a到f六个字符的文件进行编码,文件包含100000个字符,每个字符的出现频率(用百分比表示)如表8—1所示,则与固定长度编码相比,该编码方案节省了(65)存储空间。

(65)

选项 A、0.21
B、0.27
C、0.18
D、0.36

答案C

解析 贪心算法在解决最优化问题上是仅根据当前已有的信息作出选择,即不是从整体最优考虑,它所作出的选择只是力求局部最优。本题给出的霍夫曼编码操作过程基于典型的贪心策略。采用固定长度编码,需要3位二进制数字来表示6个字符,即a=000,b=001,c=010,d=011,e=100,f=101。这种方法需要300000位来对整个源文件编码。采用霍夫曼编码,频繁出现的字符采用短编码,出现频率较低的字符采用长编码,这种编码方式需要(32*1+26*3+18*3+12*3+4*4+8*4)*1000
转载请注明原文地址:https://kaotiyun.com/show/5bCZ777K
0

最新回复(0)