POJ 1521 - Entropy

http://poj.org/problem?id=1521

概要

文字列が与えられ、それを ASCII として表現したときに必要なビット数と、ハフマン符号で圧縮したときに必要なビット数と、その圧縮率を答える。

解法

やるだけ。入力アルファベットが1種類しかないときに注意。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 #include <functional>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 struct node
 9 {
10   int c;
11   node *left, *right;
12   node(int a) : c(a), left(0), right(0) {}
13   node(node *l, node *r) : c(0), left(l), right(r) {}
14   ~node() { delete left; delete right; }
15   void assign(int *d, int x = 0) const
16   {
17     if (c == 0) {
18       left->assign(d, x+1);
19       right->assign(d, x+1);
20     } else {
21       d[c] = x;
22     }
23   }
24 };
25 
26 int huffman(const string& s)
27 {
28   static int a[256];
29   fill_n(a, 256, 0);
30   for (string::const_iterator it = s.begin(); it != s.end(); ++it) {
31     ++a[int(*it)];
32   }
33   priority_queue<pair<int,node*>, vector<pair<int,node*> >, greater<pair<int,node*> > > q;
34   for (int i = 0; i < 256; i++) {
35     if (a[i] > 0) {
36       q.push(make_pair(a[i], new node(i)));
37     }
38   }
39   if (q.size() == 1) {
40     return q.top().first;
41   }
42   while (q.size() > 1) {
43     const pair<int,node*> l = q.top();  q.pop();
44     const pair<int,node*> r = q.top();  q.pop();
45     q.push(make_pair(l.first + r.first, new node(l.second, r.second)));
46   }
47   static int d[256];
48   node *root = q.top().second;
49   root->assign(d);
50   delete root;
51   int ans = 0;
52   for (int i = 0; i < 256; i++) {
53     ans += a[i] * d[i];
54   }
55   return ans;
56 }
57 
58 int main()
59 {
60   for (string s; cin >> s && s != "END";) {
61     int x = huffman(s);
62     printf("%lu %d %.1f\n", 8*s.size(), x, 8.0*s.size()/x);
63   }
64   return 0;
65 }