第104回 プログラミングについて『ファイルを圧縮してみよう！ その3』

～ハフマン法で圧縮する ２～

　前回まではハフマン木を生成するところまでプログラムを作りました。今回は出力ファイルにデータを書き込んでいきましょう。

まず出力ファイルに必要なものは入力ファイルのファイルサイズです。というのも、ハフマン法ではこれまでの説明でもお分かりだと思いますが、圧縮されたデータは可変長ですので、圧縮されたファイルの最後の部分に無意味なビット列が含まれる可能性があります。この無意味なビット列を伸長しないために元データのサイズが必要になるのです。そこでメイン関数に元ファイルのサイズを書き込みましょう。

　main()
　{
　　 in_fp=fopen( IN_FNAME,"rb");
　　out_fp=fopen(OUT_FNAME,"wb");

　　make_tree();
　　　　　　　　　　　　　　　　　　　　　　　　/* 元ファイルのサイズ */
　　fwrite(&in_file_size,sizeof(in_file_size),1,out_fp);

　　fclose(out_fp);
　　fclose( in_fp);
　}

　ファイルサイズは make_tree で取得していますのでこれで済みます(ファイル入出力のエラー処理は行なっていません）。

　次に問題なのが、前回作成したハフマン木も圧縮ファイルに書き込まなければならないことです。この情報がないと元には戻せません。ハフマン木は、

　int　tree[512][3];
　int ltree;

と定義していましたので、最も簡単に行なうには、tree の最初から最後の要素までを書き込む方法です。

　fwrite(tree,sizeof(tree[0]),ltree+1,out_fp);

とすればそのまま書き込めるのですが、ltree が５００で、int 型が４バイトのときには、５００＊４＊３＝６０００ バイトになり、膨大なバイト数が必要になってしまいます。これではファイルの圧縮どころか元ファイルよりも大きくなってしまう可能性が非常に大きくなってしまいますので工夫が必要です。

　色々と考えてみたのですが、次のような方法にしました。

　ハフマン木の根から節を順番に通りすべての葉に辿り着くまでの道順を圧縮ファイルに書き込む。

　という方法です。左側の子に行くのが０で右が１なので必要なビット数がかなり削減されるはずです。だからと言って単純には行なえません、道順の他に葉の文字が何であるのか、ハフマン木の終了がどこなのかが分からなければなりません。そこで、道順を２ビット使用することにしました。葉の文字には当然８ビットが必要です。

　道順を示す２ビットを次のように決めます。

　00 左下の子に行く。
　01 右下の子に行く。
　10 上に上がる。
　11 葉（文字）。
　11 終了。

２ビットで表す事ができる状態は 00、01、10、11 の４つしかありませんので終了を示すには１つ足りません。上の様に決めたのにはちょっと説明が必要です（終了を示すのが11というのは、決して間違いではありません）。

前回の ABCDEABABBCBC のときのハフマン木で考えてみましょう。

　　┌A
　┌┤
　││┌D
　│└┤
　┤　└E
　│┌B
　└┤
　　└C

木の根から辿っていくと、上で決めた約束に沿ってデータにしてみると、

　00 00 11 C
　10 01 11 B
　10 10 01 00 00 E
　10 01 11 D
　10 10 01 A

となります（他にも辿り方は色々あります）。このデータでも想像できると思いますが、11 の次の文字の後にはかならず上に上がるコード（ 10 ）しかないはずです。ですので、最後を示すには 10 以外ならばなんでもいいことになります。ということで 11 と決めました。
　この例のハフマン木では tree の要素数は９個でしたので、単純に書き込む方法では９＊４＊３＝１０８バイト必要だったのが、この方法では９バイト＋２ビットしか必要としません。

　ハフマン木の書き込みの前にビット出力の関数を考えましょう。ビット出力と言っても、ビット単位でファイルに書き込むのではありません。ファイルに書き込める最小単位はバイト単位（８ビット）です。次に示すのがビット出力関数です。

　unsigned char out_char;
　int　　　　　 out_remain;

　out_remain=8;

　add_bits(char *pattern)
　{
　　int i;

　　while(*pattern){
　　　out_char<<=1;
　　　out_remain--;

　　　out_char|=(*pattern++ -'0');

　　　if(out_remain==0){
　　　　fputc(out_char,out_fp);

　　　　out_remain=8;
　　　}
　　}
　}

　この関数では、out_char と out_remain がグローバルで既に定義してありますので特に問題はありませんが、ビット単位で出力を開始する最初に out_remain を８にしておくことを忘れてはいけません。最初は out_char の８ビットすべてが残っていますので、初期化を忘れると正しく出力されませんので注意が必要です。

　この関数名が add_bits と複数形になっているのは、この関数の１度の呼び出しで１つ以上のビット（ビット列）を出力できるようになっているからです。引数のに文字列でに "0010" などと指定できるようにしてあります。関数内では、この引数の文字列を順番にビット列に変換し、out_char の８ビットすべてを使い切ったときにファイルに出力します。

　out_char<<=1;

は out_char のビット列を左に（上位方向）１つシフトしています。

　out_char|=(*pattern++ -'0');

はビット列を１つシフトしたことによって空いた最下位のビットを設定しています。ちょっと分かりづらいかも知れませんので、この式を２つに分解して考えてみると、

　out_char|=(*pattern -'0');
　pattern++;

となり、*pattern - '0' は *pattern が '0' のときには 0、'1' のときには 1 になるので論理和演算子を使って最下位ビットを設定するという仕組みになっています。

　それでは次は、ハフマン木を書き込むためにメイン関数に store_tree を追加します。
out_remain=8; を忘れてはいけません。

　main()
　{
　　 in_fp=fopen( IN_FNAME,"rb");
　　out_fp=fopen(OUT_FNAME,"wb");

　　make_tree();

　　fwrite(&in_file_size,sizeof(in_file_size),1,out_fp);

　　out_remain=8;

　　store_tree(ltree);

　　fclose(out_fp);
　　fclose( in_fp);
　}

追加された store_tree(ltree); の引数の ltree はハフマン木の根のインデックス番号です。そして store_tree 本体です。この関数は再帰呼び出しを行なってハフマン木のすべての節と葉を辿のでちょっと難しいかも知れません。

　store_tree(int cur)
　{
　　　　　　　　　　　　　　　　　　　　　　　/* 左右の子がないので葉（文字） */
　　if(tree[cur][1]==0 && tree[cur][2]==0){
　　　char c,chr[9];
　　　int　i;

　　　add_bits("11");　　　　　　　　　　　　 /* 葉を示す 11 を出力 */

　　　for(c=tree[cur][0],i=0;i<=7;i++,c<<=1){ /* 葉の文字のビット列を生成 */
　　　　if(c & 0x80)chr[i]='1';
　　　　else　　　　chr[i]='0';
　　　}

　　　chr[i]='\0';

　　　add_bits(chr);　　　　　　　　　　　　　/* 文字のビット列を出力 */

　　　　　　　　　　　　　　　　　　　　　　　/* 元ファイル内のすべての文字を出
　　　　　　　　　　　　　　　　　　　　　　　　 力したら終了を示す 11 を出力し
　　　　　　　　　　　　　　　　　　　　　　　　 終了 */
　　　if(--total_infile_char_kind==0){
　　　　add_bits("11");
　　　　return 1;
　　　}
　　}
　　else{
　　　int lr;

　　　for(lr=1;lr<=2;lr++){
　　　　if(tree[cur][lr]){　　　　　　　　　　/* 左右の子があれば再び store_tree
　　　　　　　　　　　　　　　　　　　　　　　　を呼び出し木の枝を進む */
　　　　　if(lr==1)add_bits("00");
　　　　　else　　 add_bits("01");

　　　　　　　　　　　　　　　　　　　　　　　/* 戻り値が 1 のときには出力終了 */
　　　　　if(store_tree(tree[cur][lr]-1))return 1;

　　　　　add_bits("10");　　　　　　　　　　 /* 子の枝から戻ったときには根の方
　　　　　　　　　　　　　　　　　　　　　　　　 向に１つ戻る */
　　　　}
　　　}
　　}

　　return 0;
　}

　ビット列を考えたり、再帰呼び出しを考えたりしなければならないのでだいぶ難しいのですが頑張って理解して下さい。ここまでの全文です。

　#include <stdio.h>

　#define　IN_FNAME "z.z"
　#define OUT_FNAME "x.x"

　FILE * in_fp;
　FILE *out_fp;

　int　tree[512][3];
　int ltree;

　int　total_infile_char_kind;

　char *pattern[256];

　unsigned char out_char;
　int　　　　　 out_remain;

　unsigned long in_file_size;

　main()
　{
　　 in_fp=fopen( IN_FNAME,"rb");
　　out_fp=fopen(OUT_FNAME,"wb");

　　make_tree();

　　fwrite(&in_file_size,sizeof(in_file_size),1,out_fp);

　　out_remain=8;

　　store_tree(ltree);

　　fclose(out_fp);
　　fclose( in_fp);
　}

　make_tree(char *fname)
　{
　　unsigned int　freq[512];
　　unsigned char c;
　　int i;

　　for(i=0;i<=255;i++)freq[i]=0;

　　in_file_size=0;

　　while(1){
　　　c=fgetc(in_fp);
　　　if(feof(in_fp))break;

　　　　　 freq[c]++;
　　　in_file_size++;
　　}

　　rewind(in_fp);

　　ltree= -1;
　　for(i=0;i<=255;i++){
　　　if(freq[i]){
　　　　ltree++;
　　　　tree[ltree][0]=i;
　　　　tree[ltree][1]=0;
　　　　tree[ltree][2]=0;
　　　　freq[ltree]　 =freq[i];
　　　}
　　}

　　total_infile_char_kind=ltree+1;

　　while(1){
　　　int i1,i2;
　　　unsigned int m1,m2;

　　　i1= -1; i2= -1;
　　　m1= -1; m2= -1;

　　　for(i=0;i<=ltree;i++){
　　　　if(freq[i]==0)continue;

　　　　if(i1== -1 || freq[i]<=m1){
　　　　　if(i2== -1 || m1<m2){
　　　　　　i2=i1;
　　　　　　m2=m1;
　　　　　}

　　　　　i1=i;
　　　　　m1=freq[i];
　　　　}
　　　　else if(i2== -1 || freq[i]<m2){
　　　　　i2=i;
　　　　　m2=freq[i];
　　　　}
　　　}

　　　if(i2== -1)break;

　　　ltree++;

　　　tree[ltree][0]=0;
　　　tree[ltree][1]=i1+1;
　　　tree[ltree][2]=i2+1;
　　　freq[ltree]　 =freq[i1]+freq[i2];
　　　freq[i1　 ]　 =0;
　　　freq[i2　 ]　 =0;
　　}

　　return 1;
　}

　add_bits(char *pattern)
　{
　　int i;

　　while(*pattern){
　　　out_char<<=1;
　　　out_remain--;

　　　out_char|=(*pattern++ -'0');

　　　if(out_remain==0){
　　　　fputc(out_char,out_fp);

　　　　out_remain=8;
　　　}
　　}
　}

　store_tree(int cur)
　{
　　if(tree[cur][1]==0 && tree[cur][2]==0){
　　　char c,chr[9];
　　　int　i;

　　　add_bits("11");

　　　for(c=tree[cur][0],i=0;i<=7;i++,c<<=1){
　　　　if(c & 0x80)chr[i]='1';
　　　　else　　　　chr[i]='0';
　　　}

　　　chr[i]='\0';

　　　add_bits(chr);

　　　if(--total_infile_char_kind==0){
　　　　add_bits("11");
　　　　return 1;
　　　}
　　}
　　else{
　　　int lr;

　　　for(lr=1;lr<=2;lr++){
　　　　if(tree[cur][lr]){
　　　　　if(lr==1)add_bits("00");
　　　　　else　　 add_bits("01");

　　　　　if(store_tree(tree[cur][lr]-1))return 1;

　　　　　add_bits("10");
　　　　}
　　　}
　　}

　　return 0;
　}

次回で圧縮を終了させましょう。