題目：
Huffman ： 維基百科
霍夫曼樹經常被用來作資料壓縮，將字串資料轉成霍夫曼碼以減少字串資料所佔的空間大小，其詳細作法如下：
(1)字串中所有的字母元素都放在最底層的葉節點上，節點中的值為此字母的出現次數。
(2) 每次從尚無父節點的所有節點中，尋找值最小（出現次數最少）的兩個節點來建立霍夫曼樹，
產生其父節點的值為兩個節點值相加的和。最後只剩下根節點沒有父節點。
(3) 從根節點開始往下編碼，左分支為 0，右分支為 1，每個葉節點的字母元素會產生一個霍夫
曼碼（由 0 和 1 所組成），字母元素出現的頻率越高則霍夫曼碼越短。
我們這題需要計算一個字串轉成霍夫曼碼的壓縮率。假設有個字串"queue"，則此字串會佔5 bytes = 40bits空間，
轉成霍夫曼碼後應為"00011011"，只需要8個bits就可儲存，因此壓縮率為(40-8)/40 * 100% = 80%。
輸入：
輸入一列字串(長度最多100字元，且不含空格)。
輸出：
依序輸出此字串壓縮前的bit數、壓縮後的bit數、壓縮率百分比(格式為⌊n⌋%，即n向下取整)。
queue
abadcafcabfdec
aaaaaaamcmhhhhhmkkkkkkkkmbbmdddddddmyymppppp
BCBBB
Ex 1 Output:
40 8 80%
Ex 2 Output:
112 35 68%
Ex 3 Output:
352 132 62%
Ex 4 Output:
40 5 87%
題解：
題目沒說字串中大小寫是否要算成同一字母，因此先視為不同的來處理。
霍夫曼編碼是出現頻率越多次的編碼越短，而越少就越長，
可以利用priority_queue(優先佇列)對字母出現的頻率進行排序，
而建立Huffman Tree只要依序拿取優先佇列中的值並相加就好，
字串原bit數就是字串長度*8，因為1bytes = 8bits。
壓縮後bit數就是一直疊加自己與父節點的值就是答案。
上程式碼：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include<bits/stdc++.h>
using namespace std;
template<class T> long long Mod(T a,T b){return ((a%b)+b)%b;}
#define endl '\n'
#define ll long long
#define IO ios_base::sync_with_stdio(0); cin.tie(0);
#define GETOUT cout.tie(0);
#define gc getchar()
#define cendl cout << endl;
#define fr(bob,n,l) for(int bob=(n);bob<(l);++bob)
#define fra(ns,a) for(auto (ns):a)
#define frc(bot,ns,l) for(int bot=(ns);bot<=(l);++bot)
#define frx(i,ns,l) for(int i=(ns);i<(l);++i)
const int MAX=1e9+7;
const int MOD=998244353;
inline int nextint(){
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){
if(ch == '-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=getchar();
return x*w;
}
struct huff{
int feq;
char key;
};
struct cmp{
bool operator()(huff i,huff j){
return i.feq > j.feq;
}
};
inline void solve(){
string s;
cin >> s;
int len = s.size();
int bitlen = len*8;
int feqs[1000]={0};
priority_queue<huff,vector<huff>,cmp> huffman;
for(int i=0;i<len;i++){
feqs[s[i]]++;
}
for(int i=0;i<1000;i++){
if(feqs[i]!=0){
huff h;
h.feq = feqs[i];
char k = i;
h.key = k;
huffman.push(h);
}
}
int ans=0;
while(huffman.size()>=2){
huff now = huffman.top();huffman.pop();
huff next = huffman.top();huffman.pop();
huff cal;cal.feq = now.feq + next.feq;
huffman.push(cal);
ans+=cal.feq;
}
double rate = (bitlen-ans)/(double)bitlen;
cout << bitlen << ' ' << ans << ' ' << floor(rate*100) << '%' << endl;
}
signed main(){
IO;
GETOUT;
int t;
t=1;
while(t--)solve();
return 0;
}
|
