ハフマンコード表作り
そういえば俺がコンピュータほげほげにはまったキッカケの一つって、「圧縮」がすごいおもしろかったから、だったよなあ。今をときめくK.INABAさんを知ったのもそれでだ。「今をときめく」ってどういう表現だ？ と思い、教えてgoo辞書さん「ときめく」したら、「胸がどきどき」じゃない方のときめくだった。将来恥かかんですんだ。今恥を晒してるけど。
圧縮技術の説明をしてるサイトはやまざきさんとこ、DO++さんとこなどなど、色々あります。や、不思議ですもんね。
奥村先生の昔話なんてのも読んでて楽しいですね。
たぶん、そのうちいいかげんな圧縮技術の解説を試みる。俺が書く圧縮技術解説文章に価値があるからではない。技術解説文章を捏造することが、俺にとって理解を深める助けになるんではあるまいかとの思いによる。
ああ、そういえばこれも課題だ。とはいえ、課題の方はまだ全然読んでないから、仕様だ要求だとか全然違うだろうけど。キッカケをありがとう＞大学の課題
ええいそんなことはあとまわしで、とりあえずプログラム書いてみた。まずは基本ということで、ハフマン圧縮です。よくわからないですが適当にハフマンコード表をつくってみましょう。
とりあえず実行結果は以下のように。
% echo -n 'aabbccddeeff' |./a.out /dev/stdin 00 00000000000000000000000000000000000000000000000... ... ff 0001 61 001 62 01 65 100 66 101 63 110 64 111
0x61 = a, 0x62 = b, ...ですから、なんかまあちゃんとしたコード表ができてるんじゃないかな。わあすごい！ bは8ビットのデータなのに、01というたったの2ビットで表現できてるじゃないか！
#include <stdio.h>
#include <string.h>
#define HCODEMAX 256
typedef struct{
unsigned char c;
int count;
} item;
struct node{
item data;
struct node *lbranch, *rbranch;
};
struct node** isort(struct node *table[], int length){
int i, j;
struct node *tmp;
for(i=1;i<length;++i){
for(j=i;j>0 && table[j-1]->data.count>table[j]->data.count;--j){
tmp = table[j-1];
table[j-1] = table[j];
table[j] = tmp;
}
}
return table;
}
struct node* mknode(item data, struct node *lbranch, struct node *rbranch){
struct node *n;
n = (struct node *)malloc(sizeof(struct node));
n->data = data;
n->lbranch = lbranch;
n->rbranch = rbranch;
return n;
}
struct node* mktree(struct node *table[], int length){
struct node *top_node;
item tmp;
if(length == 1) return table[0];
tmp.count = table[0]->data.count + table[1]->data.count;
table[1] = mknode(tmp, table[0], table[1]);
isort(&table[1], length-1);
top_node = mktree(&table[1], length-1);
return top_node;
}
int print_hcode(FILE *fh, struct node *top_node, char *precode){
char lcode[HCODEMAX], rcode[HCODEMAX];
strcpy(lcode, precode);
strcpy(rcode, precode);
if(top_node->lbranch != NULL)
print_hcode(fh, top_node->lbranch, strcat(lcode, "0"));
if(top_node->rbranch != NULL)
print_hcode(fh, top_node->rbranch, strcat(rcode, "1"));
if(top_node->lbranch == NULL && top_node->rbranch == NULL)
fprintf(fh, "%02x %s\n", top_node->data.c, precode);
return 1;
}
int compress(char *plainname){
char archname[256], codename[256];
int c, i, j, length;
FILE *plain, *arch, *code;
struct node *table[256], *top_node;
item tmpitem;
length = 256;
if((plain = fopen(plainname, "r")) == NULL){
perror("cannot open plain");
return -1;
}
for(i=0;i<length;++i){
tmpitem.count = 0;
tmpitem.c = i;
table[i] = mknode(tmpitem, NULL, NULL);
}
while((i=fgetc(plain)) != EOF) ++table[i]->data.count;
isort(table, length);
top_node = mktree(table, length);
print_hcode(stdout, top_node, "");
fclose(plain);
return 1;
}
int main(int argc, char *argv[]){
if(argc>1)
if(!compress(argv[argc-1]))
puts("cannot compress");
return 0;
}コード表を出力することしか考えずにプログラムを書いてしまった。二分木とかうろおぼえでも意外とそれっぽくできるなあと思った。プログラムは上手に書くことはとても重要だと思うけれども、最初はまず書いてみないと始まらないのですね。
いきなり線形数学の問題を延々とやらされるより、GoogleのPageRankの解説を聞いて「へえ、固有値計算って数学者のおもちゃじゃなかったのね」と知ってからやった方がやる気でねえっすか？ という話です。
よしここは一気にファイルの圧縮までやってしまおう、と思ったけどここから先は普通にむずかしそうなのでまた明日。何が難しいかというと、8ビット単位じゃないデータを扱うこと。今のコンピュータは8ビットが基本なのですきっと。ビット演算ってよくわからんし。
[追記] 間違いがあった。
よく考えれば、考えるまでもなく出現しないデータのビット列は出力する必要が無い。compress()のmktree呼び出し前にほげればいけるな。
isort(table, length); for(i=0;table[i]->data.count == 0;++i); // 追記した部分 top_node = mktree(&table[i], length-i);
実行してみよう。
そういえば、isortは挿入ソートです。
% echo -n 'aba' |./a.out /dev/stdin 62 0 61 1 % echo -n 'aaabbc' |./a.out /dev/stdin 63 00 62 01 61 1
うん、今度こそいけたっぽいぞ。
