题目描述

哈夫曼编码是一种数据编码方法，通过对“浪费”或“多余”信息删除的消息进行编码来实现无损数据压缩。 换句话说，哈夫曼编码去除了最初不需要精确编码消息的信息。 如果没有强制执行前缀自由约束，那么这样的解码是不可能的。 考虑文本“aaaabcd”。 使用ASCII编码，这需要64位。 如果我们用位模式“00”、“B”用“01”、“C”用“10”和“D”用“11”编码“A”，那么我们只能用16位编码该文本； 得到的位模式将是“000000000011011”。然而，这仍然是一种固定长度的编码；我们使用的是每个字形2位，而不是8位。 既然glyph“a”出现的频率更高，我们能用更少的位来编码它吗？ 事实上，我们可以，但是为了保持无前缀编码，其他一些位模式将变得比两个位长。 最佳编码方式是用“0”对“A”进行编码，用“10”对“B”进行编码，用“110”对“C”进行编码，用“111”对“D”进行编码。 （这显然不是唯一的最佳编码，因为很明显，对于任何给定的编码，B、C和D的编码都可以自由交换，而不会增加最终编码消息的大小。） 使用此编码，消息的编码仅为13位到“0000010110111”， 压缩比为4.9比1（即最终编码的消息表示的信息量与原始编码中的4.9位相同）。 从左到右仔细阅读这个位模式，您会发现无前缀编码使得将其解码为原始文本变得简单， 即使代码有不同的位长度。 作为第二个例子，考虑文本“THE_CAT_IN_THE_HAT”。 在本文中，字母“T”和空格字符都以最高的频率出现，因此它们在最佳编码中具有最短的编码位模式。 然而，字母“c”、“i”和“n”只出现一次，因此它们的代码最长。 有许多可能的无前缀可变长度位模式集，它们将产生最佳编码，也就是说， 允许文本以最少的位数进行编码。 一个这样的最佳编码是用“00”、“A”和“100”、 “C”和“1110”、“E”和“1111”、“H”和“110”、“I”和“1010”、“N”和“1011”以及“T”和“01”对空格进行编码。 因此，与144相比，最佳编码只需要51位，而144位是使用8位ASCII编码对消息进行编码所必需的，压缩比为2.8比1。 现在你需要编写一个程序来求出压缩比。

输入格式

END代表结束 一行由一个字符串组成"_"代表空格(为了降低难度，输入的字符只包含大小写字母与数字以及空格)

输出格式

在一行中写出 ascii编码的大小，哈夫码编码压缩后大小，以及压缩比，压缩比保留一位小数

AAAAABCD
THE_CAT_IN_THE_HAT
END

64 13 4.9
144 51 2.8

提示

转自hdu1053