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