404021 - 哈夫曼编码

你需要熟练掌握“无前缀可变长度”编码方式，即输入一个字符串，长度不超过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”结束。

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