[演算法][程式作] huffman code 解＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2012-11-18 16:27:29| 人20,032| 回2 | 上一篇 | 下一篇

[演算法][程式作] huffman code 解

推 0 收藏 0 0 站台

根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;
}