问题 Z: 哈夫曼编码

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:82 通过:36

题目描述

哈夫曼编码是一种编码方式, 是可变字长编码的一种, 由 Huffman 于 1952 年提出。该方法完全依据字符出现概率来构造异字头的平均长度最短的码字, 有时称之为最佳编码,一般就叫 Huffman 编码。简单地来说,就是出现概率高的字符使用较短的编码, 反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低, 从而达到无损压缩数据的目的。
现在请你模拟这样的原则对给定的一个字符串进行字母统计。

输入格式

只有一行,是一个字符串,由小写英文字母组成,长度不超过255 个字符。

输出格式

有若干行,每行有两部分组成:一个字母和该字母出现的频率,中间用一个空格分隔,并按频率高低排列,频率相同时则按字母的 ASC 码的先后顺序排列。

输入样例 复制

soon

输出样例 复制

o 2
n 1
s 1