题目描述

使用哈夫曼编码原理对文本进行压缩

1. 读入文本，获取文本中各字符出现的频率

2. 以频率为权值，构建哈夫曼树，得到每个字符的哈夫曼编码

3. 将文本转为哈夫曼编码，保存，该二进制串即为压缩后的数据。

求该压缩的压缩率（压缩后的数据大小 / 压缩前的数据大小)。

例：有一个段文本："abcc"

1. 统计各字符频率：a:1, b:1, c:2

2. 构建哈夫曼树，得到哈夫曼编码： a: 00, b:01, c:1

3. 将原文本转为哈夫曼编码，为：000111

压缩前数据长度：4字节，32位，压缩后：6位， 压缩率：6/32 = 0.188(保留3位小数)

输入格式

一行字符串（字符串长度小于等于1000，字符串中都是ASCII码表中的字符，可能有空格）

输出格式

对该字符串进行哈夫曼压缩后的压缩率，保留3位小数（压缩后的数据大小 / 压缩前的数据大小)

abcc

0.188

提示

注意处理输入字符串为类似"aaaa"的情况。