#SIMA0587. 合法哈夫曼
合法哈夫曼
题目背景
33DAI 最近做洛谷的 CSP-J 第一轮模拟赛时看到了下面这道题目。
假设有一组字符 {g,h,i,j,k,l}
,它们对应的频率分别为 。
请问以下哪个选项是字符 g,h,i,j,k,l
分别对应的一组哈夫曼编码?( )
- A.
g: 1100, h: 1101, i: 111, l: 10, k: 00, j: 01
- B.
g: 0000, h: 001, i: 010, l: 011, k: 10, j: 11
- C.
g: 111, h: 110, i: 101, l: 100, k: 01, j: 00
- D.
g: 110, h: 111, i: 101, l: 100, k: 0, j: 01
33DAI 发现直接哈夫曼树上构建的话,怎么都得不到某个选项。然后才学到了原来哈夫曼编码只需要保证长度没问题,且任意一个编码都不是其他编码的前缀即可。感谢洛谷带来的小知识。
题目描述
有 个单词,编号从 。第 个单词的出现的次数为 。
33DAI 对这些单词进行了二进制编码,第 个单词编码后的二进制数用一个字符串 表示。
请你判断 33DAI 的编码是不是这个出现次数下合法的哈夫曼编码。
- 如果是,输出
Yes
,并计算出按照这个编码的文章总长度(二进制位数)。 - 否则,输出
No
,并给出一组满足要求的哈夫曼编码。
注意:本题中只要保证了在该二进制编码下,文章总长度能达到最短;且任意一个编码都不是其他编码的前缀;就认为是一个合法的哈夫曼编码。
输入格式
第一行是 。
第二行为空格隔开的
接下来 行,第 行为
输出格式
按题目要求输出:
- 如果输入的是哈夫曼编码,输出两行:
- 第一行为
Yes
- 第二行为这个编码下的文章总长度
- 第一行为
- 如果输入的不是哈夫曼编码,输出 行:
- 第一行为
No
- 接下来 行第 行为第 个单词对应的哈夫曼编码。
- 如果有多种方案,输出任意一种即可。
- 第一行为
6
8 14 17 20 23 18
111
110
101
00
01
100
Yes
257
6
8 14 17 20 23 18
0000
001
010
11
10
011
No
111
110
101
00
01
100
1
99
0
Yes
99
数据规模与约定
对于 的数据,,,。保证 仅有字符 0,1
构成, 表示字符串 的长度。
- 子任务 1(10 分):保证 。
- 子任务 2(20 分):保证输入的编码是一套哈夫曼编码。
- 子任务 3(30 分):保证输入的编码任意一个都不是其他的编码的前缀。
- 子任务 4(40 分):没有特殊限制。
扩展阅读
以防你不知道怎么求出一种哈夫曼编码,下面是 OIWiki 中关于哈夫曼编码相关的介绍。
树的带权路径长度
设二叉树具有 个带权叶结点,从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为 树的带权路径长度(Weighted Path Length of Tree,WPL)。
设 为二叉树第 个叶结点的权值, 为从根结点到第 个叶结点的路径长度,则 WPL 计算公式如下:
如上图所示,其 WPL 计算过程与结果如下:
结构
对于给定一组具有确定权值的叶结点,可以构造出不同的二叉树,其中,WPL 最小的二叉树 称为 霍夫曼树(Huffman Tree)。
对于霍夫曼树来说,其叶结点权值越小,离根越远,叶结点权值越大,离根越近,此外其仅有叶结点的度为 ,其他结点度均为 。
霍夫曼算法
霍夫曼算法用于构造一棵霍夫曼树,算法步骤如下:
- 初始化:由给定的 个权值构造 棵只有一个根节点的二叉树,得到一个二叉树集合 。
- 选取与合并:从二叉树集合 中选取根节点权值 最小的两棵 二叉树分别作为左右子树构造一棵新的二叉树,这棵新二叉树的根节点的权值为其左、右子树根结点的权值和。
- 删除与加入:从 中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到 中。
- 重复 2、3 步,当集合中只剩下一棵二叉树时,这棵二叉树就是霍夫曼树。
霍夫曼编码
在进行程序设计时,通常给每一个字符标记一个单独的代码来表示一组字符,即 编码。
在进行二进制编码时,假设所有的代码都等长,那么表示 个不同的字符需要 位,称为 等长编码。
如果每个字符的 使用频率相等,那么等长编码无疑是空间效率最高的编码方法,而如果字符出现的频率不同,则可以让频率高的字符采用尽可能短的编码,频率低的字符采用尽可能长的编码,来构造出一种 不等长编码,从而获得更好的空间效率。
在设计不等长编码时,要考虑解码的唯一性,如果一组编码中任一编码都不是其他任何一个编码的前缀,那么称这组编码为 前缀编码,其保证了编码被解码时的唯一性。
霍夫曼树可用于构造 最短的前缀编码,即 霍夫曼编码(Huffman Code),其构造步骤如下:
- 设需要编码的字符集为:,他们在字符串中出现的频率为:。
- 以 作为叶结点, 作为叶结点的权值,构造一棵霍夫曼树。
- 规定哈夫曼编码树的左分支代表 ,右分支代表 ,则从根结点到每个叶结点所经过的路径组成的 、 序列即为该叶结点对应字符的编码。