Description

hdu1053

熵编码器是一种数据编码方法，通过将“浪费的”或“额外的”信息删除，从而实现无损数据压缩。换句话说，熵编码消除了最初不必要的信息，以便准确地对消息进行编码。高熵意味着消息有大量的浪费信息；用ASCII编码的英文文本是具有高熵的消息类型的示例。已经压缩的消息，例如JPEG图形或ZIP归档，具有非常小的熵，并且不能从熵编码的进一步尝试中受益。

在计算机中，一个英文字符用八个比特表示，如00110111,11100111等，如 AAAAABCD 每个字符占八个比特，一共八个字符
占64个比特。但是若用 00 表示A,用 01 表示B,用 10 表示C,用 11 表示D。则原字符串只占16个比特。
若用 0 表示 A, 10 表示 B，110 表示 C, 111 表示D, 则A出现了五次，占5个比特，B出现了1次,占2个比特，
C出现了一次，占3个比特，D出现了一次，占3个比特。一共占13个比特。
现在给一个只包含26个大写字母和下划线 "_"的字符串，使每个出现的字符都对应一个二进制串，且不能存在一个二进制串
是另一个二进制串的前缀。如若用 001表示A,0010表示B则不合法，因为001是0010的前缀。
要求在符合要求的前提下最少要多少个比特可以存得下这个字符串。

Input Format

输入数据有多组，每组一个字符串，包含大写字母和下划线，以"END"为结束符。

Output Format

对于每个字符串输出一行，包含三个数字，a,b,c。

a为每个字符都占八个比特时的所占用的比特数，b为最少占用多少比特数，c为a/b,

c结果保留一位小数。

AAAAABCD
THE_CAT_IN_THE_HAT
END

64 13 4.9
144 51 2.8

Source

未分类