#A0587. 合法哈夫曼

合法哈夫曼

题目背景

33DAI 最近做洛谷的 CSP-J 第一轮模拟赛时看到了下面这道题目。

假设有一组字符 {g,h,i,j,k,l},它们对应的频率分别为 8%,14%,17%,20%,23%,18%8\%,14\%,17\%,20\%,23\%,18\%
请问以下哪个选项是字符 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 发现直接哈夫曼树上构建的话,怎么都得不到某个选项。然后才学到了原来哈夫曼编码只需要保证长度没问题,且任意一个编码都不是其他编码的前缀即可。感谢洛谷带来的小知识。

题目描述

nn 个单词,编号从 1n1\sim n。第 ii 个单词的出现的次数为 aia_i

33DAI 对这些单词进行了二进制编码,第 ii 个单词编码后的二进制数用一个字符串 sis_i 表示。

请你判断 33DAI 的编码是不是这个出现次数下合法的哈夫曼编码。

  • 如果是,输出 Yes,并计算出按照这个编码的文章总长度(二进制位数)。
  • 否则,输出 No,并给出一组满足要求的哈夫曼编码。

注意:本题中只要保证了在该二进制编码下,文章总长度能达到最短;且任意一个编码都不是其他编码的前缀;就认为是一个合法的哈夫曼编码。

输入格式

第一行是 nn

第二行为空格隔开的 a1ana_1\sim a_n

接下来 nn 行,第 ii 行为 sis_i

输出格式

按题目要求输出:

  • 如果输入的是哈夫曼编码,输出两行:
    • 第一行为 Yes
    • 第二行为这个编码下的文章总长度
  • 如果输入的不是哈夫曼编码,输出 n+1n+1 行:
    • 第一行为 No
    • 接下来 nn 行第 ii 行为第 ii 个单词对应的哈夫曼编码。
    • 如果有多种方案,输出任意一种即可。
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

数据规模与约定

对于 100%100\% 的数据,1n601 \le n \le 601ai10001\le a_i\le 10001si1001\le |s_i|\le 100。保证 sis_i 仅有字符 0,1 构成,si|s_i| 表示字符串 sis_i 的长度。

  • 子任务 1(10 分):保证 n=1n=1
  • 子任务 2(20 分):保证输入的编码是一套哈夫曼编码。
  • 子任务 3(30 分):保证输入的编码任意一个都不是其他的编码的前缀。
  • 子任务 4(40 分):没有特殊限制。

扩展阅读

以防你不知道怎么求出一种哈夫曼编码,下面是 OIWiki 中关于哈夫曼编码相关的介绍。

树的带权路径长度

设二叉树具有 nn 个带权叶结点,从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为 树的带权路径长度(Weighted Path Length of Tree,WPL)

wiw_i 为二叉树第 ii 个叶结点的权值,lil_i 为从根结点到第 ii 个叶结点的路径长度,则 WPL 计算公式如下:

WPL=i=1nwiliWPL=\sum_{i=1}^nw_il_i

如上图所示,其 WPL 计算过程与结果如下:

WPL=22+32+42+72=4+6+8+14=32WPL=2*2+3*2+4*2+7*2=4+6+8+14=32

结构

对于给定一组具有确定权值的叶结点,可以构造出不同的二叉树,其中,WPL 最小的二叉树 称为 霍夫曼树(Huffman Tree)

对于霍夫曼树来说,其叶结点权值越小,离根越远,叶结点权值越大,离根越近,此外其仅有叶结点的度为 00,其他结点度均为 22

霍夫曼算法

霍夫曼算法用于构造一棵霍夫曼树,算法步骤如下:

  1. 初始化:由给定的 nn 个权值构造 nn 棵只有一个根节点的二叉树,得到一个二叉树集合 FF
  2. 选取与合并:从二叉树集合 FF 中选取根节点权值 最小的两棵 二叉树分别作为左右子树构造一棵新的二叉树,这棵新二叉树的根节点的权值为其左、右子树根结点的权值和。
  3. 删除与加入:从 FF 中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到 FF 中。
  4. 重复 2、3 步,当集合中只剩下一棵二叉树时,这棵二叉树就是霍夫曼树。

霍夫曼编码

在进行程序设计时,通常给每一个字符标记一个单独的代码来表示一组字符,即 编码

在进行二进制编码时,假设所有的代码都等长,那么表示 nn 个不同的字符需要 log2n\left \lceil \log_2 n \right \rceil 位,称为 等长编码

如果每个字符的 使用频率相等,那么等长编码无疑是空间效率最高的编码方法,而如果字符出现的频率不同,则可以让频率高的字符采用尽可能短的编码,频率低的字符采用尽可能长的编码,来构造出一种 不等长编码,从而获得更好的空间效率。

在设计不等长编码时,要考虑解码的唯一性,如果一组编码中任一编码都不是其他任何一个编码的前缀,那么称这组编码为 前缀编码,其保证了编码被解码时的唯一性。

霍夫曼树可用于构造 最短的前缀编码,即 霍夫曼编码(Huffman Code),其构造步骤如下:

  1. 设需要编码的字符集为:d1,d2,,dnd_1,d_2,\dots,d_n,他们在字符串中出现的频率为:w1,w2,,wnw_1,w_2,\dots,w_n
  2. d1,d2,,dnd_1,d_2,\dots,d_n 作为叶结点,w1,w2,,wnw_1,w_2,\dots,w_n 作为叶结点的权值,构造一棵霍夫曼树。
  3. 规定哈夫曼编码树的左分支代表 00,右分支代表 11,则从根结点到每个叶结点所经过的路径组成的 0011 序列即为该叶结点对应字符的编码。