数据结构基础

【题目描述】哈夫曼编码（entropy）POJ 1521

你需要熟练掌握“无前缀可变长度”编码方式，即输入一个字符串，长度不超过100，仅由大写字母和下划线组成，试将所谓的“无前缀可变长度”编码来使长度最小。

在这种编码中，可以使用任意的位数来表示任何字符，不允许任意字符的编码是其他任何字符编码的前缀。

例如字符串“AAAAABCD”， 如果使用ASCII码方式保存，每个字符占8位，共需要64位。但如果考虑到各字符出现的频率，将"A"设为"0"，"B"设为"10"，"C"设为"110"，"D"设为"111"，长度只需要13位，即“0000010110111”，压缩比为4.9。

又如字符串“THE_CAT_IN_THE_HAT”，字母"T"和空格出现的频率最高，那么编码就最短，"I"和"N"只出现过一次，那么编码就最长，一个最佳的编码方案是空格设为"00"，"A"设为"100", "C"设为"1110"，"E"设为"1111"，"H"设为"110"，"I"设为"1010"，"N"设为"1011"，"T"设为"01"，这样长度只需要51位，压缩比为2.8。

【输入格式】

每行一个字符串，只包含大写英文字母和下划线，最后一行以“END”结束。

【输出格式】

每行三个数，即每行的原始长度、压缩长度和压缩比（精确到小数点一位）。

【输入样例】

AAAAABCD

THE_CAT_IN_THE_HAT

END

【输出样例】

64 13 4.9

144 51 2.8