{"trustable":false,"sections":[{"title":"题目描述","value":{"format":"HTML","content":"熵编码器是一种数据编码方法,它通过编码删除“浪费”或“额外”信息的消息来实现无损数据压缩。换句话说,熵编码删除了一开始对消息进行准确编码所不必要的信息。高熵意味着信息中有大量被浪费的信息;用ASCII编码的英文文本是具有非常高熵的消息类型的一个例子。已经压缩的消息,如JPEG图形或ZIP存档,熵很小,并且不会从进一步尝试熵编码中获益。\n\n用ASCII编码的英文文本具有高度的熵,因为所有字符都使用相同的位数8进行编码。众所周知,E, L, N, R, S和T在英语文本中出现的频率比大多数其他字母要高得多。如果能找到一种方法,用4位来编码这些字母,那么新的编码就会更小,包含所有的原始信息,熵也会更小。但是,ASCII使用固定数量的位是有原因的:它很简单,因为总是要处理固定数量的位来表示每个可能的字形或字符。使用4位的编码方案如何区分4位码和8位码?这个看似困难的问题可以使用所谓的“无前缀变长”编码来解决。\n\u003cbr\u003e\n\u003cbr\u003e在这种编码中,可以使用任意数量的比特来表示任何符号,并且消息中不存在的符号根本不编码。但是,为了能够恢复信息,不允许编码字形的位模式成为任何其他编码位模式的前缀。这允许对编码的比特流进行逐位读取,每当遇到表示字形的一组位时,就可以对该字形进行解码。如果没有强制前缀自由约束,那么这样的解码将是不可能的。\n\u003cbr\u003e\n\u003cbr\u003e以文本“AAAAABCD”为例。如果使用ASCII编码,则需要64位。相反,如果我们用位模式“00”来编码“A”,用“01”来编码“B”,用“10”来编码“C”,用“11”来编码“D”,那么我们可以只用16位来编码这个文本;得到的位模式将是“0000000000011011”。然而,这仍然是一个固定长度的编码;我们每个字形使用两个比特而不是八个。由于字形“A”出现的频率更高,我们可以用更少的比特来编码它,但是为了保持无前缀的编码,一些其他的位模式会变得比两个位长。最优的编码方式是用“0”编码“A”,用“10”编码“B”,用“110”编码“C”,用“111”编码“D”。(这显然不是唯一的最佳编码,因为很明显,B, C和D的编码可以自由地交换任何给定的编码,而不会增加最终编码消息的大小。)使用这种编码,消息只编码13位到“0000010110111”,压缩比为4.9比1(也就是说,最终编码消息中的每个比特表示的信息量与原始编码中的4.9位表示的信息量一样多)。\n\u003cbr\u003e\n\u003cbr\u003e作为第二个例子,考虑文本“the CAT IN the HAT”。在本文中,字母“T”和空格字符都以最高的频率出现,因此在最佳编码中,它们显然具有最短的编码位模式。然而,字母“C”、“I”和“N”只出现一次,所以它们的代码最长。\n\u003cbr\u003e\n\u003cbr\u003e有许多可能的无前缀变长位模式集可以产生最佳编码,也就是说,可以用最少的位数对文本进行编码。一种这样的最佳编码是用“00”编码空格,用“100”编码“A”,用“1110”编码“C”,用“1111”编码“E”,用“110”编码“H”,用“1010”编码“I”,用“1011”编码“N”,用“01”编码“T”。因此,最佳编码只需要51位,而用8位ASCII编码编码消息需要144位,压缩比为2.8比1。"}},{"title":"输入","value":{"format":"HTML","content":"输入文件将包含一个文本字符串列表,每行一个。\n\u003cbr\u003e\n\u003cbr\u003e文本字符串将仅由大写字母数字字符和下划线(用于代替空格)组成。\n\u003cbr\u003e\n\u003cbr\u003e输入的结束将由仅包含单词“end”作为文本字符串的一行来表示,这一行不被处理。"}},{"title":"输出","value":{"format":"HTML","content":"对于输入中的每个文本字符串,输出8位ASCII编码的长度(以位为单位)、最佳无前缀变长编码的长度(以位为单位)以及精确到小数点的压缩比。"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003e输入样例\u003c/th\u003e\n \u003cth\u003e输出样例\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eAAAAABCD\nTHE_CAT_IN_THE_HAT\nEND\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e64 13 4.9\n144 51 2.8\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}