PJ-利用霍夫曼樹進行資料壓縮

2022.11.11 PM 09:00 by CBJ

來源 : https://drive.google.com/file/d/1CMnis82zw9hGQHW1pRv3LFXACoUGA90Y/view
出題者 : 108資訊學科能力競賽複賽-彰雲嘉
標籤 : 建樹(結構struct)、優先佇列+自定義排序、DFS(深度優先搜尋)
難易度 : 6
解題想法 : 實際建出一棵霍夫曼樹,再用dfs遍歷並編碼,最後將字串轉換成編碼,並計算壓縮率( (原字串bit數-壓縮後bit數) / 原字串bit數 )
//C++ language
//solution link(含註解): https://github.com/CBJ0519/CBJsProgramDiary.com/blob/main/%E8%B3%87%E8%A8%8A%E5%AD%B8%E7%A7%91%E8%83%BD%E5%8A%9B%E7%AB%B6%E8%B3%BD/108%E5%BD%B0%E9%9B%B2%E5%98%89/PJ-%E5%88%A9%E7%94%A8%E9%9C%8D%E5%A4%AB%E6%9B%BC%E6%A8%B9%E9%80%B2%E8%A1%8C%E8%B3%87%E6%96%99%E5%A3%93%E7%B8%AE.cpp

#include<iostream>
#include<map>
#include<string>
#include<unordered_set>
#include<queue>
using namespace std;
struct tree{
    int cnt=0;
    char elm='\0';
    tree* left=nullptr;
    tree* right=nullptr;
};
struct cmp{
    bool operator()(tree *a, tree *b){
        return a->cnt > b->cnt;
    }
};
map<char,string>huffman;
void dfs(tree *now,string code){
    if(now->elm!='\0'){
        huffman[now->elm]=code;
        return;
    }
    if(now->left){
        dfs(now->left,code+"0");
    }
    if(now->right){
        dfs(now->right,code+"1");
    }
}
int main(){
    string s;cin>>s;
    unordered_set<char>st;
    map<char,tree*>mp;
    for(char c:s){
        st.insert(c);
    }
    for(char c:st){
        mp[c]=new tree;
        mp[c]->elm=c;
    }
    for(char c:s){
        mp[c]->cnt++;
    }
    priority_queue<tree*,vector<tree*>,cmp>pq;
    for(char c:st){
        pq.push(mp[c]);
    }
    while(pq.size()>1){
        tree *a=pq.top(); pq.pop();
        tree *b=pq.top(); pq.pop();
        tree *c=new tree;
        c->cnt=a->cnt+b->cnt;
        c->left=a;
        c->right=b;
        pq.push(c);
    }
    dfs(pq.top(), "");
    int bits=0;
    for(char c:s){
        bits+=huffman[c].length();
    }
    int before=s.length()*8;
    cout<<before<<" "<<bits<<" "<<(before-bits)*100/before<<"%\n";
    return 0;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *