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