描述
熵编码是一种通过去除消息中的"冗余"或"额外"信息来实现无损数据压缩的编码方法。简而言之，熵编码会移除那些原本对准确编码消息非必要的信息。高熵值意味着消息包含大量冗余信息——例如用$ASCII$编码的英文文本就是典型的高熵消息。而已压缩的消息（如$JPEG$图像或$ZIP$文件）熵值极低，无法通过进一步熵编码获益。

$ASCII$编码的英文文本具有高熵值，因为所有字符均采用相同的$8$比特固定长度编码。事实上，字母$E$、$L$、$N$、$R$、$S$和$T$在英文中的出现频率远高于其他字母。若能将这些高频字母改用$4$比特编码，新编码方案将更紧凑、保留全部原始信息且熵值更低。但ASCII采用固定比特数有其优势：处理固定位宽的字符编码更简单。那么，如何区分$4$比特编码和$8$比特编码？这个难题可通过"前缀无关变长编码"解决。

在该编码体系中：

1. 各字符可使用任意比特数表示，未出现的字符无需编码
2. 任何字符的编码位模式不得成为其他字符编码的前缀（关键约束）
3. 解码时按位读取，遇到有效编码立即解析

例如文本$AAAAABCD$：

• $ASCII$编码需$64$比特
• 若采用$A=00$，$B=01$，$C=10$，$D=11$的固定$2$比特编码，仅需$16$比特（$0000000000011011$）
• 更优方案：高频字符用更短编码，如$A=0$，$B=10$，$C=110$，$D=111$，仅需$13$比特（$0000010110111$），压缩比达$4.9:1$

再如文本$THE\_CAT\_IN\_THE\_HAT$（下划线代表空格）：

• 最优编码方案：空格$=00$，$A=100$，$C=1110$，$E=1111$，$H=110$，$I=1010$，$N=1011$，$T=01$
• 仅需$51$比特，相比$ASCII$的$144$比特，压缩比$2.8:1$

输入
输入包含多个文本字符串（每行一个），仅由大写字母、数字和下划线（代替空格）组成。以单独一行$END$标记输入结束（不处理该行）。

输出
对每个字符串，输出三个值：

1. $8$比特$ASCII$编码的比特数
2. 最优前缀无关变长编码的比特数
3. 压缩比（保留一位小数）

输入数据 1

AAAAABCD  
THE\_CAT\_IN\_THE\_HAT  
END  

输出数据 1

64 13 4.9  
144 51 2.8  

来源
Greater New York 2000