Description

哈夫曼编码是一种最优编码方法。根据已知源字母表中字符的出现频率，将源字母表中的字符编码为目标字母表中的字符，最优的意思是编码信息的平均长度最小。在该问题中，需要将N 个大写字母（源字母S1 …S N 、频率f1 …f N ）转换成R 进制数字（目标字母T1 …T R ）。

当R =2时，编码过程分几个步骤。在每个步骤中都有两个最低频率的源字母S1 和S2 ，合并成一个新的“组合字母”，频率为S1 和S2 的频率之和。如果最低频率和次低频率相等，则字母表中最早出现的字母被选中。经过一系列步骤后，最后只剩两个字母合并，将每次合并的字母都分配一个目标字符，将较低频率的分配0，将另一个分配1。如果在一次合并中，每个字母都有相同的频率，则将最早出现的分配0。出于比较的目的，组合字母的值为合并中最早出现的字母的值。源字母的最终编码由每次形成的目标字符组成。

目标字符以相反的顺序连接，最终编码序列中的第1个字符为分配给组合字母的最后一个目标字符。

下面的两个图展示了R =2的过程。

当R >2时，对每一个步骤都分配R 个字母。由于每个步骤都将R 个字母或组合字母合并为一个组合字母，并且最后一次合并必须合并R 个字母或组合字母，源字母必须包含k ×(R -1)+R 个字母，k 为整数。由于N 可能不是很大，因此必须包括适当数量具有0频率的虚拟字母。这些虚拟字母不包含在输出中。进行比较时，虚拟字母晚于字母表中的任何字母。

哈夫曼编码的基本过程与R =2的过程相同。在每次合并中都将具有最低频率的R 个字母合并，形成新的组合字母，其频率等于在组合字母中包括的字母频率的总和。被合并的字母被分配目标字母符号0～R-1。0被分配给具有最低频率的组合中的字母，1被分配给下一个最低频率，等等。如果字母组合中的几个字母具有相同的频率，则字母表中最早出现的字母被分配较小的目标符号，以此类推。

下图说明了R =3的过程。

Format

Input

输入将包含一个或多个数据集，每行一个。每个数据集都包含整数值$R$ $（2≤R ≤10）$、整数值$N$$（2≤N ≤26）$和整数频率$f1…f N$ ，每个都为$1～999$。整个输入数据都以$R$ 为$0$结束，它不被认为是单独的数据集。

Output

对每个数据集都在单行上显示其编号（编号从1开始按顺序排列）和平均目标符号长度（四舍五入到小数点后两位）。然后显示N个源字母和相应的哈夫曼代码，每行都有一个字母和代码。在每个测试用例后都打印一个空行。

Samples

2 5 5 10 20 25 40
2 5 4 2 2 1 1
3 7 20 5 8 5 12 6 9
4 6 10 23 18 25 9 12
0

Set 1; average length 2.10
       A: 1100
       B: 1101
       C: 111
       D: 10
       E: 0
       
Set 2; average length 2.20
       A: 11
       B: 00
       C: 01
       D: 100
       E: 101
       
Set 3; average length 1.69
       A: 1
       B: 00
       C: 20
       D: 01
       E: 22
       F: 02
       G: 21
       
Set 4; average length 1.32
       A: 32
       B: 1
       C: 0
       D: 2
       E: 31
       F: 33
       
————————————————
版权声明：本文为CSDN博主「爱编程的大李子」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/LXYDSF/article/details/113921931

来源

UVA240