Description

熵编码是一种数据编码方法，通过对去除“冗余”或“额外”信息的消息进行编码来实现无损数据压缩。

为了能够恢复信息，编码字形的位模式不允许作为任何其他编码位模式的前缀，称之为“无前缀可变长度”编码。只允许逐位读取编码的比特流，并且每当遇到表示字形的一组比特时，都可以解码该字形。如果不强制使用无前缀约束，则不可能进行这种解码。

第1个例子，考虑文本“AAAAABCD”，对其使用8位ASCII编码需要64位。如果用“00”对“A”编码，用“01”对“B”编码，用“10”对“C”编码，用“11”对“D”编码，那么只需16位编码，得到的位模式将是“0000000000011011”。不过，这仍然是固定长度的编码；使用的是每个字形两位，而不是八位。

既然字形“A”出现的频率更高，那么能用更少的位来编码它吗？

实际上可以，但为了保持无前缀编码，其他一些位模式将变得比两位长。

最佳编码是将“A”编码为“0”，将“B”编码为“10”，将“C”编码为“110”，将“D”编码为“111”（这显然不是唯一的最佳编码，因为B、C和D的编码可以在不增加最终编码消息大小的情况下自由地交换给任何给定的编码）。使用此编码，消息仅以13位编码到“0000010110111”，压缩比为4.9:1（即最终编码消息中的每一位表示的信息与原始编码中的4.9位表示的信息相同）。从左到右阅读这个位模式，将看到无前缀编码使得将其解码为原始文本变得简单，即使代码的位长度不同。

第2个例子，考虑文本“THE CAT IN THE HAT”。字母“T”和空格字符都以最高频率出现，因此它们在最佳编码中显然具有最短的编码位模式。字母“C”、“I”和“N”只出现一次，因此它们的代码最长。有许多可能的无前缀可变长度位模式集可以产生最佳编码，也就是说，允许文本以最少的位进行编码。其中一种最佳编码是：空格:00、A:100、C:1110、E:1111、H:110、I:1010、N:1011、T:01。因此，这种最佳编码只需51位，与用8位ASCII编码对消息进行编码所需的144位相比，压缩比为2.8:1。

Format

Input

输入文件包含一个字符串列表，每行一个。

字符串将只包含大写字母、数字字符和下画线（用于代替空格）。

以字符串“END”结尾，不应处理此行。

Output

对于每个字符串，都输出8位ASCII编码的位长度、最佳无前缀可变长度编码的位长度及精确到一个小数点的压缩比。

Samples

AAAAABCD
THE_CAT_IN_THE_HAT
END

64 13 4.9
144 51 2.8

来源

POJ1521