Morris' Blog

2013-01-02 19:42:49Morris

[資料結構][作業] 霍夫曼編碼

留言 1 收藏 0 推薦 0

作業內容:

建構一個Huffman tree

並將依照輸入的元素以及其頻率(頻率為小數模式且其總和為1)

透過Huffman coding將其編碼

並輸出編碼

※請注意編碼時頻率較低的一邊應將其編為0

(例如:a 0.25 b 0.35 c 0.4 第一次編碼時a為0 b為1

第二次編碼時 (a & b) 0.6 c 0.4 則(a & b)為1 c為0

也就是最後的編碼為 a:10 b:11 c:0

輸入及輸出說明:

輸入為一個字元且其後面為該字元之出現頻率依此格式直到所有字元皆輸入

字元內容皆為小寫英文字母(a~z)

輸出為列出所有字元(以其字母順序排列)以及其Huffman code(以0、1表示)

sample input 1:

a 0.10 b 0.15 c 0.30 d 0.16 e 0.29

sample output 1:

a : 010
b : 011
c : 11
d : 00
e : 10

sample input 2:

a 0.8 b 0.12 c 0.42

sample output 2:

The sum of frequency is not equal to 1

繳交方式及期限:

deadline : 1/11 22:00

遲交一天扣成績10%

1/15 22:00後交不予計分

繳交一樣上傳到FTP的hw5資料夾下

補交也一樣上傳到FTP的補交資料夾內hw5補交資料夾中的對應日期資料夾下 (即為:補交/hw5補交/對應之日期)

請將code壓縮為rar/zip/7z後上傳

檔名格式為101522054_hw5_ver1.rar

(期限內如果想再重新上傳則命名為ver2 ver3依此類推

助教改作業時會以最後一版為準，檔名格式錯誤者不會被改到)

對這次作業有任何問題的同學請寄信或到lab來找助教

小光的疑點測資
a 0.10 b 0.15 c 0.30 d 0.16 e 0.29
a 0.8 b 0.12 c 0.42
a 0.2 c 0.2 d 0.2 b 0.2 e 0.2
a 0.49999999999 b 0.50000000001
a -1 b 2
ab 1 c 0
a 1 a 0

助教解析

測資不會出現有兩個頻率相同的狀況
以免造成建出來的huffman tree不同

這些分別來回答

1
a 0.49999999999 b 0.50000000001
的狀況這個超過float的範圍
因此兩個都會被視為0.500000

2
負的頻率是不被允許的
不過當初在製作sample檔時並未加入
感謝提醒

3
這個sample檔的確可以處理多個字元
(基本上數字或其他符號也行)
不過作業需求僅要求為小寫英文字母

4
重複的部分的確是會把它當作不同的兩個符號處理
不過在這次作業的測資也不會有這種狀況

如果有任何問題可以再來信，感謝

以下是小光代碼，請不要直接照抄上傳作業， ... 我想也不會有我們班的同學來看。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <sstream>
#include <map>
#include <queue>
#include <vector>
#define eps 1e-6
using namespace std;
struct ND {
    int l, r, ptr;
    string token;
    double p;
    void set(int a, int b, int c, string d, double e) {
        l = a, r = b, ptr = c;
        token = d;
        p = e;
    }
};
struct cmp {
    bool operator() (ND a, ND b) {
        return a.p > b.p;
    }
};
ND nd[1024];
char buf[128];
map<string, string> hufcode;
void dfs(int idx, int dep) {
    if(!idx)    return;
    buf[dep] = '0';
    dfs(nd[idx].l, dep+1);
    buf[dep] = '1';
    dfs(nd[idx].r, dep+1);
    if(!nd[idx].l) {
        buf[dep] = '\0';
        hufcode[nd[idx].token] = buf;
    }
}
int main() {
    puts("Input data (seperate by space):");
    string line, token;
    getline(cin, line);
    stringstream sin(line);
    int size = 0, i;
    double p, sump = 0;
    priority_queue<ND, vector<ND>, cmp> pQ;
    ND L, R;
    while(sin >> token >> p) {
        ++size;
        nd[size].set(0, 0, size, token, p);
        sump += p;
        pQ.push(nd[size]);
    }
    if(fabs(sump-1) > eps) {
        puts("The sum of frequency is not equal to 1");
        system("pause");
        return 0;
    }
    while(pQ.size() >= 2) {
        L = pQ.top(), pQ.pop();
        R = pQ.top(), pQ.pop();
        ++size;
        nd[size].set(L.ptr, R.ptr, size, "", L.p+R.p);
        pQ.push(nd[size]);
    }
    dfs(size, 0);
    for(map<string, string>::iterator it = hufcode.begin();
        it != hufcode.end(); it++) {
        cout << it->first << " : " << it->second << endl;
    }
    system("pause");
    return 0;
}

上一篇：[線性代數][作業] 旋轉矩陣

下一篇：[線性代數][作業] Gram Schmidt Process