首页
登录
从业资格
已知某文档仅包含6种不同的字符,其每个字符出现的频率如下表所示,采用霍夫曼编码对
已知某文档仅包含6种不同的字符,其每个字符出现的频率如下表所示,采用霍夫曼编码对
免费题库
2022-08-02
67
问题
已知某文档仅包含6种不同的字符,其每个字符出现的频率如下表所示,采用霍夫曼编码对该文档压缩存储,则单词“face”的编码为( ),该文档的压缩比为( )。
问题1选项A.110001001101B.101000010100C.001101001100D.110101001100问题2选项A.20%B.25%C.30%D.40%
选项
答案
AB
解析
哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+…+ Wn*Ln),N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明哈夫曼树的WPL是最小的。构造哈夫曼树的算法如下:1)对给定的n个权值{W1,W2,W3,…,Wi,…,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,…,Ti,…, Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。2)在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。3)从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。4)重复2)和3),直到集合F中只有一棵二叉树为止。用二叉树设计二进制前缀编码:以电文中的字符作为叶子结点构造二叉树。然后将二叉树中结点引向其左孩子的分支标 ‘0’,引向其右孩子的分支标 ‘1’; 每个字符的编码即为从根到每个叶子的路径上得到的 0, 1 序列。如此得到的即为二进制前缀编码。构造的哈弗曼树和节点编码如下所示:
对应各字符的编码为:a(0)、b(101)、c(100)、d(111)、e(1101)、f(1100)face的编码为:1100 0 100 1101平均码长 =0.45╳1+0.12╳3+0.13╳3+0.16╳3+0.05╳4+0.09╳4=0.45+0.36+0.39+0.48+0.20+0.36=2.24由于6个字符,至少需要3位二进制才能完成编码。压缩比为:1-2.24/3=0.25
转载请注明原文地址:https://tihaiku.com/congyezige/2418134.html
本试题收录于:
中级 软件评测师题库软件水平考试初中高级分类
中级 软件评测师
软件水平考试初中高级
相关试题推荐
关于软件文档的叙述,“()”是错误的。A.文档就是指软件的操作说明书 B.文档
通常在软件开发过程的()阶段,无需用户参与。A.需求分析 B.维护 C.编码
设正规式S=(a|ba)*,则其对应正规集的字符串()。A.长度必须是偶数
有关哈夫曼编码方法,以下说法正确的是()。A.哈夫曼编码是一种用于校验的编码方法
以下关于HTML文档的说法,正确的是()。A.HTML是一种动态网页设计语言
关于汉字编码的叙述,错误的是()。A.采用矢量法表示汉字时,若两个汉字的笔画
在Word2003编辑状态下,若要将另一个文档的内容全部添加到当前文档的光标所
在Word2003编辑状态下,若要将另一个文档的内容全部添加到当前文档的光标所
在Word中建立新“文档1”,再选择“保存”命令,将();若单击标题栏右边显
音频信息数字化的过程不包括()。A.采样 B.量化 C.编码 D.调频
随机试题
Amillionmotoristsleavetheircarsfilledupwithpetrolandwiththekeys
[audioFiles]audio_eufm_j14_001(20082)[/audioFiles]A、Helikestogooutoftown.
下列有关暂列金额的说法中,正确的是( )。A.暂列金额没有包含在工程量清单中的
Afterwardstherewasjustafeelingofl
Thechangeinthatvillagewasmiraculou
群众对领导干部的不满,不仅产生于领导的作为和业绩,而且很大程度上是由于对领导的期
汇率的波动性越小,期权价格越低。()
?关于我国的赦免制度,以下说法正确的是:A.我国的特赦决定机关是全国人大常委会。
实施监理的工程,办理工程质量监督注册手续需提供的资料有( )A.必要的施工图纸
《特种设备安全监察条例》所称的特种设备是指()、危险性较大的设备和设施。A
最新回复
(
0
)