C++でハフマン符号にチャレンジ

　蟻本のコラムに載っていた「ハフマン符号」がおもしろそうだったのでチャレンジしてみました。
アルゴリズム自体はとてもシンプルですが、コーディングにハマってしまいました。
priority_queueのコンテナの中にポインタ変数を突っ込みたいとき、どうするの？ 「・・・・・」 そういや、やったことないな。。木を構築するときにnewするのはやめて、あらかじめ確保したメモリプール（vertexの配列）から値を取ってきて、left、rightには配列の添字を入れるという技で対応しようかと思いましたが、比較関数用のFunctor作ってあげればいいだけみたいです。

　比較関数を自分で定義しなくても、priority_queue<vertex *>でコンパイルエラーが出なかったのがハマってしまった原因でした。ポインタ変数なので、operator<が定義されてたってことか。。

アルゴリズム

wikipedia参照。

ソースコード

※今回はアルファベット小文字のみをエンコーディング対象としました。

#include <iostream>
#include <queue>
#include <map>
#include <cstdio>

using namespace std;

struct vertex {
    char c;
    vertex *left;
    vertex *right;
    int cost;

    vertex(char _c, vertex *_left, vertex *_right, int _cost) 
        : c(_c), left(_left), right(_right), cost(_cost) {}
};

struct vertexComp {
    bool operator()(const vertex *x, const vertex *y) const {
        return x->cost > y->cost;
    }
};

void getEncode(map<char, string> &encode, vertex *vp, string s) {
    if (vp == NULL)
        return;
    if (vp->c)
        encode[vp->c] = s;
    getEncode(encode, vp->left, s+'0');
    getEncode(encode, vp->right, s+'1');
}

void huffmanCoding(int cnt[]) {
    priority_queue<vertex*, vector<vertex *>, vertexComp> Q;
    for (int i = 0; i < 26; i++)
        Q.push(new vertex((char)('a'+i), NULL, NULL, cnt[i]));

    while (Q.size() > 1) {
        vertex *v1 = Q.top(); Q.pop();
        vertex *v2 = Q.top(); Q.pop();
        Q.push(new vertex(0, v1, v2, v1->cost + v2->cost));
    }
    
    map<char, string> encode;
    getEncode(encode, Q.top(), "");

    for (map<char, string>::iterator itr = encode.begin(); itr != encode.end(); itr++)
        printf("%c [%6d] -> %10s\n", itr->first, cnt[itr->first-'a'], itr->second.c_str());
}

int main() {
    int c, cnt[26] = {0};
    while ((c = getchar()) != EOF) {
        if ('a' <= c && c <= 'z')
            ++cnt[c-'a'];
    }

    huffmanCoding(cnt);
 
    return 0;
}

実行結果

適当なWEBページの文章を読み込んで、符号化してみました。頻度が高いものほど、コードが短くなっていることが確認できました。

a [  3255] ->       1101
b [   702] ->     010111
c [  2845] ->       1010
d [  1712] ->      11100
e [  4337] ->        001
f [   715] ->     110000
g [   855] ->     111110
h [  1760] ->      11101
i [  2962] ->       1011
j [   236] ->   11000101
k [   300] ->   11111111
l [  2022] ->       0100
m [  1563] ->      11001
n [  2700] ->       0111
o [  2664] ->       0110
p [  1869] ->      11110
q [    43] ->  110001000
r [  2734] ->       1000
s [  2801] ->       1001
t [  4153] ->        000
u [  1242] ->      01010
v [   666] ->     010110
w [   514] ->    1111110
x [   282] ->   11111110
y [   511] ->    1100011
z [    45] ->  110001001