[ZJ][三年後修訂] d371. 3. Huffman 編碼中的編碼效能問題＠Morris' Blog

2012-11-08 20:19:57| 人氣2,325| 回應0 | 上一篇 | 下一篇

[ZJ][三年後修訂] d371. 3. Huffman 編碼中的編碼效能問題

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

為了用0 與1 的位元串表示電腦中所需使用的符號，常見的編碼法可分為兩大類：固定長度編碼法與非固定長度編碼法。

固定長度編碼法指的是，將每個符號用相同長度的位元串表示。

例如，要以二進位的0 與1 位元串表示{a, b, c, d, e } 5個符號

每個符號最少需要以3 個位元來編碼成{000, 001, 010, 011, 100}。

但如果我們已知這些符號在多數資料中出現的頻率不同，就可用非固定長度編碼法更有效地表示這些資料

而Huffman 編碼法就是非固定長度編碼法中最常使用的方法。

例如，已知{a, b, c, d, e}這5 個符號的出現頻率由大至小如表一所示。

則Huffman 編碼法利用建立二元樹的方式，首先將每個符號以一個自由節點(freenode)表示

這些自由節點的權重(weight)即是符號的頻率。

接著，從自由節點中找出權重最小的兩個節點，為這兩個節點做一個父節點，此父節點的權重則為這兩個子節點的權重和。

之後，將父節點加入自由節點的行列，並將兩個子節點從自由節點的行列中去除。

接著，重覆選取兩個權重最小的節點，造出父節點並更新自由節點的過程，直到最後只剩一個自由節點為止。

當得到這棵編碼樹後，我們就可以從二元樹的根結點(root node)開始往下走

每往左子樹(left subtree)走一層就給定一個位元的編碼0

每往右子樹(right subtree)走一層就給定一個位元的編碼1

依此方式逐層往下走並同時編碼直到走到葉節點(leaf node)為止。

圖一、二所示即為依表一頻率表所建造的不同Huffman 編碼樹。

雖然圖一和圖二的編碼結果不同，但檢視其編碼效能，如表二所示，可發現這兩個編碼所得到的總位元數是相同的:

16+24+16+16+16+16=32+16+16+12+12=88。

請撰寫一個程式，根據已知的頻率表(尚未排序過)，計算以Huffman 編碼後的總位元數。

輸入說明：

第一行為一個整數n，代表共有幾個符號。(n<=2^k，k 為正整數，1<k<=16)。

接下來的n 個數字代表這n 個符號的頻率，每個數字為介於1 與2¹⁶ 之間的正整數，每兩個數字以一個空格隔開。

輸出說明：

對每一個輸入的頻率表，計算以Huffman 編碼後的總位元數。

範例輸入：

5
16 8 8 4 4

範例輸出：

提示：

出處：

97全國能力縣賽 (管理：pcshic)

/**********************************************************************************/
/* Problem: d371 "3. Huffman 編碼中的編碼效能問題" from 97全國能力縣賽*/
/* Language: CPP (1293 Bytes)                                                    */
/* Result: AC(4ms, 771KB) judge by this@ZeroJudge                                */
/* Author: morris1028 at 2012-11-08 20:14:38                                     */
/**********************************************************************************/

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct ele {
    int nd;
    long long v;
};
struct NODE {
    int l, r;
    long long v;
    char c;
};
struct cmp {
    bool operator() (ele a, ele b) {
        return a.v > b.v;
    }
};
NODE ND[99999];
long long ans;
void dfs(int nd, int dep) {
    if(!ND[nd].l && !ND[nd].r)
        ans += dep*ND[nd].v;
    if(ND[nd].l)
        dfs(ND[nd].l, dep+1);
    if(ND[nd].r)
        dfs(ND[nd].r, dep+1);
}
int main() {
    int n, A[99999];
    int i;
    while(scanf("%d", &n) == 1) {
        priority_queue<ele, vector<ele>, cmp> pQ;
        ele l, r, e;
        for(i = 1; i <= n; i++) {
            scanf("%d", &A[i]);
            e.nd = i, e.v = A[i];
            ND[i].l = 0, ND[i].r = 0;
            ND[i].v = A[i];
            pQ.push(e);
        }
        int size = n;
        while(pQ.size() > 1) {
            l = pQ.top(), pQ.pop();
            r = pQ.top(), pQ.pop();
            size++;
            e.nd = size, e.v = l.v+r.v;
            ND[size].l = l.nd;
            ND[size].r = r.nd;
            ND[size].v = l.v+r.v;
            pQ.push(e);
        }
        ans = 0;
        dfs(size, 0);
        printf("%lld\n", ans);
    }
    return 0;
}

我要檢舉

#d371#3. Huffman#編碼中的編碼效能問題

台長： Morris

您可能對以下文章有興趣

[ZJ][Math] a348. 1. 貪食蛇

a081. NOI2000 Day2.2.青蛙过河

b067. 6. 下棋問題

[ZJ][數學解] a534. IOI2008 Day2.1.花園問題

人氣(2,325) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[PTC][201211] PA Circular Matrix Product
此分類上一篇:[PTC][201210][搜索] Princess's Marriage

回應(0)