熵编码器是一种数据编码方法,通过对删除了“浪费”或“额外”信息的消息进行编码来实现无损数据压缩。换句话说,熵编码去除了最初不需要的信息,以准确编码消息。高度的熵意味着一条消息包含大量浪费的信息;以ASCII编码的英文文本是具有极高熵的消息类型的示例。已经压缩的消息,如JPEG图形或ZIP存档,熵很小,无法从熵编码的进一步尝试中获益。 用ASCII编码的英文文本具有高度的熵,因为所有字符都使用相同的位数(8位)进行编码。众所周知,字母E、L、N、R、S和T的出现频率远高于英语文本中的大多数其他字母。如果能找到一种方法,用四位编码这些字母,那么新的编码将更小,包含所有原始信息,熵也更小。然而,ASCII使用固定位数是有原因的:这很容易,因为人们总是使用固定位数来表示每个可能的字形或字符。对上述字母使用四位的编码方案如何区分四位代码和八位代码?这个看似困难的问题是通过所谓的“无前缀可变长度”编码来解决的。 在这样的编码中,可以使用任意数量的比特来表示任何字形,而消息中不存在的字形也不会被编码。然而,为了能够恢复信息,不允许对字形进行编码的位模式作为任何其他编码位模式的前缀。这允许逐位读取编码的比特流,并且每当遇到表示字形的一组比特时,可以对该字形进行解码。如果没有强制执行无前缀约束,那么这种解码是不可能的。 考虑文本“AAAAA BCD”。使用ASCII编码,需要64位。相反,如果我们用位模式“00”编码“A”,用“01”编码“B”,用10编码“C”,用11编码“D”,那么我们只能用16位编码文本;得到的位模式将是“0000000000011011”。然而,这仍然是固定长度编码;我们每个字形使用两位而不是八位。既然字形“A”出现的频率更高,我们能用更少的比特来编码它吗?事实上,我们可以,但为了保持无前缀编码,其他一些位模式将变得比两位长。最佳编码是将“A”与“0”编码,将“B”与“10”编码,“C”与“110”编码,以及将“D”与“111”编码。(这显然不是唯一的最佳编码,因为很明显,对于任何给定的编码,B、C和D的编码都可以自由交换,而不增加最终编码消息的大小。)使用这种编码,消息仅以13位编码为“0000010110111”,压缩比为4.9比1(即,最终编码消息中的每个比特表示与原始编码中的4.9比特相同的信息)。从左到右阅读此位模式,您将看到无前缀编码使将其解码为原始文本变得简单,即使代码具有不同的位长度。 第二个例子是“帽子里的猫”。在本文中,字母“T”和空格字符都以最高的频率出现,因此它们在最佳编码中显然具有最短的编码位模式。然而,字母“C”、“I”和“N”只出现一次,因此它们的代码最长。 有许多可能的无前缀可变长度比特模式集,它们将产生最佳编码,也就是说,允许以最少的比特数对文本进行编码。一种这样的最佳编码是用“00”、“A”和“100”、“C”和“1110”、“E”和“111”、“H”和“110”、“I”和“1010”、“N”和“1011”以及“T”和“01”对空间进行编码。因此,与使用8位ASCII编码(压缩比为2.8比1)对消息进行编码所需的144位相比,最佳编码只需要51位。
输入 输入文件将包含文本字符串列表,每行一个。文本字符串将仅包含大写字母数字字符和下划线(用于代替空格)。输入的结束将由一行发出信号,该行仅包含单词“end”作为文本字符串。不应处理此行。 输出 对于输入中的每个文本字符串,输出8位ASCII编码的位长度、最佳无前缀可变长度编码的位长以及精确到小数点的压缩比。
Sample Input AAAAABCD THE_CAT_IN_THE_HAT END
Output 64 13 4.9 144 51 2.8
思路
8位ASCII编码的位长度:即字符种类数乘8。 最佳无前缀可变长度编码的位长:即哈夫曼编码的长度sum。 精确到一个小数点的压缩比:8位ASCII编码的位长度除以最佳无前缀可变长度编码的位长,用格式化输出的转换说明来保留一位小数。
输入字符,用map统计每个字符的频数。输入完成后,将字符的频数放入最小值优先的优先队列。如果优先队列只有一个元素,则将其加到sum中。如果优先队列的元素个数大于1,则从优先队列中让两个元素出队,相加后得到的和加到sum中,再把和放回优先队列中,重复该过程直到优先队列中仅剩一个元素。
AC代码
#include <iostream>
#include <sstream>
#include <map>
#include <queue>
#include <cstdio>
#define AUTHOR "HEX9CF"
using namespace std;
int main()
{
char ch;
string str;
while (cin >> str)
{
int cnt = 0;
int sum = 0;
map<char, int> mw;
priority_queue<int, vector<int>, greater<int>> pq;
if ("END" == str)
{
break;
}
stringstream ss(str);
while (ss >> ch)
{
mw[ch]++;
// cout << ch;
cnt++;
}
for (map<char, int>::iterator it = mw.begin(); it != mw.end(); it++)
{
pq.push(it->second);
// cout << it->first << " " << it->second << endl;
}
// cout << pq.top();
if(1 == pq.size()){
sum += pq.top();
}
while (pq.size() > 1)
{
int a, b, c;
a = pq.top();
pq.pop();
b = pq.top();
pq.pop();
c = a + b;
sum += c;
pq.push(c);
}
printf("%d %d %.1lf\n", cnt * 8, sum, cnt * 8 / (double)sum);
}
return 0;
}
标签:编码,pq,前缀,哈夫曼,题解,sum,Entropy,文本,ASCII
From: https://blog.51cto.com/HEX9CF/7576523