若任一个字符的编码都不是其它字符编码的前缀,则称这种编码具有前缀特性。现有某字符集(字符个数≥2)的不等长编码,每个字符的编码均为二进制的0、1序列,最长为L位,且具有前缀特性。请回答下列问题:
⑴ 哪种数据结构适宜保存上述具有前缀特性的不等长编码?
⑵ 基于你所设计的数据结构,简述从0/1串到字符串的译码过程。
⑶ 简述判定某字符集的不等长编码是否具有前缀特性的过程。
(1)哈夫曼树。
(2)根据哈夫曼树的特性其译码过程为:从左至右依次扫描该0/1串,从根结点开始,若为0则进入左子树,若为1则进入右子树,遇到叶子结点,则保存叶子结点对应的字符,将0/1串的剩余部分从树的根结点开始扫描。重复上述过程直至0/1串遍历完毕。保存的字符串即为0/1串的译码。
(3)判断前缀特性的过程也是构建二叉树的过程,字符集的每一个编码应该对应一条路径。初始时,二叉树仅含有一个根结点,其左右指针为空。依次读入字符集中的编码,每读入一个编码从根结点开始,若为0则沿左指针向下移动,若为1则沿右指针向下移动,当指针指向的下一个结点为空且当前结点未标记,则创建一个结点并标记;若编码至最后一位且指针指向的是非空结点,则不具有前缀特性,返回;若当前编码没有至最后一位且遇到已标记的叶子结点,则不具有前缀特性,返回。当所有编码读入完毕且通过验证则具有前缀性。
解答:
⑴ 题目要求:&ld...
用户登录可进行刷题及查看答案
⑴ 题目要求:“若任一个字符的编码都不是其它字符编码的前缀,则称这种编码具有前缀特性。”
看到这里马上联想到前缀无关编码和哈夫曼树,或者前缀无关编码对应的二叉树。哈夫曼树是某一最优前缀无关编码对应的二叉树。
注:《数据结构(C语言版)》和《算法导论》第三版中称为前缀编码(prefix codes),《算法导论》第四版和《计算理论导论》第三版中都已经改成前缀无关编码(prefix-free codes),个人认为称为前缀无关编码更加准确,充分表达出定义中“不是”的含义。
这里可以构造一棵度为2的哈夫曼树,字符保存在叶结点中,左指针路径上标0,右指针路径上标1,从根结点到叶结点路径上的0或1组成的串即为该字符的前缀无关编码。
字符保存在叶结点中,左指针路径上标0,右指针路径上标1,从根结点到叶结点路径上的0或1组成的串即为该字符的前缀无关编码。
⑵ 按序遍历0/1串,对应从哈夫曼树中找一条从根结点开始的路径,到叶结点终止,输出叶结点对应的字符。然后重新从根结点开始重复这个过程。
⑶ 构造二叉树,由于任意一个字符编码不是另一个字符编码的前缀,字符信息只能存在叶结点中。如果构造成功,那么某字符集的不等长编码具有前缀特性。
登录后提交答案