Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

根據Huffman code 編碼法

寫 一壓縮程式  與 一解壓縮程式 

能將任一檔案給定檔名的檔案壓縮後存成  另一新檔

此新檔案能再解壓縮還原成原檔案

並 附note檔 說明 如何儲存 codeword tree. 處理Header 等等

用中序的做法存 codeword tree，0就是葉節點，1就是內節點。

header 不必處理，只要用二元檔的方式讀進來，就不用考慮 header 得問題。

上次學長們好幾個做出非遞迴的 merge sort 實在讓我大開眼界，原來學長們那麼厲害。


#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
struct ele {
    int nd;
    long long v;
};
struct NODE {
    int l, r;
    long long v;
    unsigned char c;
};
struct cmp {
    bool operator() (ele a, ele b) {
        return a.v > b.v;
    }
};
NODE ND[1024];
unsigned char code[1000];
unsigned char mapcode[512][515];
FILE *fin, *fout;
int push_buf(int bit) {
    static int idx = 7, now = 0;
    static unsigned char bufcode = 0;
    bufcode |= bit<<idx;
    idx--;
    if(idx < 0) {
        fwrite(&bufcode, 1, 1, fout);
        idx = 7;
        bufcode = 0;
        now++;
    }
}
void dfs(int nd, int dep) {
    if(ND[nd].l == 0 && ND[nd].r == 0) {
        code[dep] = '\0';
        for(int i = 0; i <= dep; i++)
            mapcode[ND[nd].c][i] = code[i];
        push_buf(0);
        for(int i = 7; i >= 0; i--)
            push_buf((ND[nd].c>>i)&1);
        return;
    }
    push_buf(1);
    code[dep] = '0';
    dfs(ND[nd].l, dep+1);
    code[dep] = '1';
    dfs(ND[nd].r, dep+1);
}
int main(int argc, char* argv[]) {
    if(argc != 2) {
        puts("argc error");
        return 0;
    }
    int file_length;
    unsigned char *buf;

    fin = fopen(argv[1], "rb");
    string filename(argv[1]);
    filename += ".morris";
    fout = fopen(filename.c_str(), "wb");

    if(fin == NULL || fout == NULL) {
        puts("fopen r/w fail");
        return 0;
    }
    fseek(fin, 0, SEEK_END);
    file_length = ftell(fin);
    rewind(fin);

    printf("file size %d\n", file_length);
    buf = new unsigned char[file_length];
    fread(buf, 1, file_length, fin);

    int i, j, ASCI[256] = {}, n;
    for(i = 0; i < file_length; i++)
        ASCI[buf[i]]++;
    ele l, r, e;
    priority_queue<ele, vector<ele>, cmp> pQ;
    for(i = 0, n = 0; i < 256; i++) {
        if(ASCI[i]) {
            e.nd = ++n, e.v = ASCI[i];
            ND[n].l = 0, ND[n].r = 0;
            ND[n].v = e.v;
            ND[n].c = 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);
    }

    dfs(size, 0);

    for(i = 31; i >= 0; i--)
        push_buf((file_length>>i)&1);
    int percent = 0;
    for(i = 0; i < file_length; i++) {
        for(j = 0; mapcode[buf[i]][j]; j++)
            push_buf(mapcode[buf[i]][j]-'0');
        if(i*100/file_length > percent) {
            percent += 10;
            printf("%d%% ...\n", percent);
        }
    }
    for(i = 0; i < 8; i++)
        push_buf(1);
    fclose(fin);
    fclose(fout);
    delete[] buf;
    return 0;
}

---

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;
struct NODE {
    int l, r;
    unsigned char c;
};
NODE ND[1024];
unsigned char mapcode[515][515];
FILE *fin, *fout;
unsigned char *buf;
int pop_buf() {
    static int idx = 7, now = 0, ans;
    ans = (buf[now]>>idx)&1;
    idx--;
    if(idx < 0)
        idx = 7, now++;
    return ans;
}
int size;
void build(int nd) {
    int l, r;
    l = r = pop_buf();
    if(l == 0 && r == 0) {
        ND[nd].l = ND[nd].r = 0;
        ND[nd].c = 0;
        for(int i = 7; i >= 0; i--)
            ND[nd].c |= pop_buf()<<i;
        return;
    }
    ND[nd].l = ++size;
    build(size);
    ND[nd].r = ++size;
    build(size);
}
int main(int argc, char* argv[]) {
    if(argc != 3) {
        puts("argc error");
        return 0;
    }
    int file_length;

    fin = fopen(argv[1], "rb");
    fout = fopen(argv[2], "wb");

    if(fin == NULL || fout == NULL) {
        puts("fopen r/w fail");
        return 0;
    }

    fseek(fin, 0, SEEK_END);
    file_length = ftell(fin);
    rewind(fin);

    buf = new unsigned char[file_length];

    fread(buf, 1, file_length, fin);

    size = 1;
    build(size);
    int i, j, n, idx;
    for(i = 31, n = 0; i >= 0; i--)
        n |= (1&pop_buf())<<i;

    int percent = 100, on = n;
    while(n--) {
        idx = 1;
        while(1) {
            if(!ND[idx].l && !ND[idx].r) {
                fwrite(&ND[idx].c, 1, 1, fout);
                break;
            }
            i = pop_buf();
            if(i)   idx = ND[idx].r;
            else    idx = ND[idx].l;
        }
        if(n*100/on < percent) {
            percent -= 10;
            printf("%d%% ...\n", 100-percent);
        }
    }
    fclose(fin);
    fclose(fout);
    delete[] buf;
    return 0;
}