首页 > 编程语言 >【POJ 1521】Entropy 题解(贪心算法+优先队列+哈夫曼树)

【POJ 1521】Entropy 题解(贪心算法+优先队列+哈夫曼树)

时间:2023-09-23 10:32:20浏览次数:48  
标签:编码 pq 前缀 哈夫曼 题解 sum Entropy 文本 ASCII

熵编码器是一种数据编码方法,通过对删除了“浪费”或“额外”信息的消息进行编码来实现无损数据压缩。换句话说,熵编码去除了最初不需要的信息,以准确编码消息。高度的熵意味着一条消息包含大量浪费的信息;以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

相关文章

  • 题解 CF1873H Mad City
    题意描述马塞尔和瓦勒里乌(Valeriu)所在的疯狂城市由\(n\)栋建筑和\(n\)条双向道路组成。马塞尔和瓦勒里乌(Valeriu)分别从\(a\)号和\(b\)号建筑开始。马塞尔想赶上瓦勒里乌(换句话说,与他在同一栋楼里或在同一条路上相遇)。在每次移动过程中,他们都会选择前往当前建筑的邻近建......
  • 'main' attribute cannot be used in a module that contains top-level code 问题解
    核心是@main注解在main.swift文件中,可以重新命名下参考资料https://stackoverflow.com/questions/73431031/swift-cli-app-main-attribute-cannot-be-used-in-a-module-that-contains-top-leve......
  • CF1842F Tenzing and Tree 题解
    TenzingandTree感觉很典型的题,就是树的重心+绝对值等式解法:以每个点\(i\)为根分别\(bfs\),得到一个距离数组\(dis\),取前\(k\)个值的权值为和,更新\(w[k]\)的值,\(n\)个点分别为根,更新\(n\)遍之后,得到\(w\)数组,则\((n-1)\timesi-w[i]\),即为\(i\)个点时候的......
  • 砝码称重 题解
    砝码称重题解前言这道题时限完全可以开到1s,空间也开不到1024kb白想那么多优化(不过这个复杂度可能是目前来看最合理(算出来保证能过)的。题意简述有一个长度为\(n\)的序列\(a\),有两种操作:把\(l\)到\(r\)的所有数改为\(x\);查询用\(l\)到\(r\)的所有数(每个数可......
  • 题解 AtCoder Beginner Contest 267 A~H
    ABC267solutionhttps://atcoder.jp/contests/abc267/ProblemA.Saturday题目描述输入一个表示星期的英文字符串,输出:还有多少天到星期六?solution依题意模拟。\(O(1)\)。ProblemB.Split?题目描述Robin有十个小球,如图排列成这样,然后Robin将一些球击飞了,他告诉你哪些......
  • Django跨域问题解决
    Django跨域问题解决今天在学习前端Vue框架的过程中,遇到了跨域相关问题问题1详情:AccesstoXMLHttpRequestat'http://127.0.0.1:8000/book/'fromorigin'http://localhost:63342'hasbeenblockedbyCORSpolicy:No'Access-Control-Allow-Origin'headerispre......
  • P5836 [USACO19DEC] Milk Visits S - 洛谷题解
     题目链接:[P5836] USACO19DEC] MilkVisitsS-洛谷|计算机科学教育新生态(luogu.com.cn)这道题可以用并查集来解决。题目中每个结点只有两个状态:H和G。那么我们可以推断出,只有当起点和终点间每个结点的状态相同但是起点(或者终点或起点到终点之间的某一点)与所需状态不同......
  • 苏格拉底问答,问题解决
     ......
  • 题解 P8670 [蓝桥杯 2018 国 B] 矩阵求和
    题目描述\[\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)^2\]具体思路solution1显然可以每次枚举\(\gcd(i,j)\)的取值。\[\sum_{k=1}^nk^2\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=k]\]令\(i=\lfloor\frac{i}{k}\rfloor\),\(j=\lfloor\frac{j}{k}\rfloor\)。\[\sum......
  • 【UVA 11175】From D to E and Back 题解(图论)
    取具有n个顶点和m条边的任意有向图D。你可以在以下方式。E将有m个顶点,每个顶点对应于D的每条边。例如,如果D有一条边uv,那么E将有一个叫做uv的顶点。现在,每当D有边uv和vw时,E就会有边顶点uv到顶点vw。E中没有其他边。你将得到一张E图,并且必须确定E是否有可能是某些有向图D的图的卧......