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

admin2019-07-12  38

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

选项 A、21%
B、27%
C、17%
D、36%

答案C

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

相关试题推荐
随机试题
最新回复(0)