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

～ハフマン法での圧縮ファイルを伸長する～

　前回まではハフマン法でファイルを圧縮するプログラムを作成しました。試してみましたか。まだ元に戻せないのであまり楽しくなかったと思います。それでは今回からは伸長するプログラムを作成していきましょう。

　まずグローバルな変数と定数の部分です。

　#include <stdio.h>

　#define　IN_FNAME "x.x"
　#define OUT_FNAME "y.y"

　FILE *ifp,*ofp;

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

　unsigned char in_char;
　int　　　　　 in_remain;

　unsigned long file_size;

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

ここまでは特に問題はないと思います。入出力ファイル名は圧縮プログラム同様に固定にしてあります。

　*ifp　　は入力ファイルのファイルポインタ。
　*ofp　　は出力ファイルのファイルポインタ。

　tree　　はハフマン木を入れる配列です。

　in_char は入力ファイルから読み込んだ文字で、そのビットの残りを示すのが　　　　　in_remain です。

　out_file_size
　　　　　は出力ファイルの文字数で入力ファイルの先頭に書かれている値です。

次はメイン関数です。メイン関数では入出力ファイルをオープンした後、入力ファイルの先頭に書かれている伸長後の出力ファイルの文字数を読み込みます。次にハフマン木の情報を読み込み圧縮したときの木を生成させています。

　main()
　{
　　ifp=fopen( IN_FNAME,"rb");
　　ofp=fopen(OUT_FNAME,"wb");

　　fread(&out_file_size,sizeof(out_file_size),1,ifp);

　　in_remain=0;

　　ltree=0;
　　tree[ltree][0]=0;
　　tree[ltree][1]=0;
　　tree[ltree][2]=0;

　　make_tree(ltree);

　　fclose(ifp);
　　fclose(ofp);
　}

　圧縮されたファイルに書かれているハフマン木の情報は、木の根からスタートして枝を順次通りすべての葉に辿り着くまでの道順と、葉の文字が記述しましたので、これを元のハフマン木に再現しなければなりません。

　ltree=0;
　tree[ltree][0]=0;
　tree[ltree][1]=0;
　tree[ltree][2]=0;

はハフマン木の根を最初に作成しています。圧縮時にはこの根が配列 tree の最後の要素になりましたが伸長時には最初の要素になります。このように圧縮時と伸長時で順番が違っていても、根から左右の子への道順が正しく再現されれば何も問題はありません。

　make_tree(ltree);

はハフマン木を再現する関数ですが、この関数は再帰呼び出しで順次木を成長させていきます。その最初としてハフマン木の根の要素番号を引数として渡します。

　実際に再現させる前にビット呼び込み関数を先に説明しましょう。

　get_bit()
　{
　　int ret;

　　if(in_remain<=0){
　　　in_char=fgetc(ifp);
　　　in_remain=8;
　　}

　　if(in_char & 0x80)ret=1;
　　else　　　　　　　ret=0;

　　in_char<<=1;
　　in_remain--;

　　return ret;
　}

この関数は特に難しいところはないと思います。圧縮時には最下位のビットからセットして上方向にシフトしていきましたので伸長時には最上位ビットから読み込んでいくことになります。ですので、

　in_char & 0x80

として最上位ビットがオンかオフかを調べた後、ビット列を上方向にシフトして、ビットの残り数を減らしていきます。残り数が０のときには入力ファイルから１文字読み込み残り数を８に戻します。

　忘れてはならないことは、ビットの残り数をカウントする in_remain の初期値を０にしておくことです。

それでは make_tree 関数の本体です。

　make_tree(int cur)
　{
　　int old,kind;　　　　　　　　　　　/* kind は道順、old は１つ前の道順 */

　　old=0;　　　　　　　　　　　　　　 /* 最初は１つ前の道順がないので 0 にして
　　　　　　　　　　　　　　　　　　　　　おきます */

　　while(1){
　　　kind=get_bit(ifp)*10 + get_bit(ifp);
　　　　　　　　　　　　　　　　　　　 /* 道順を取得。道順は２ビットで表現して
　　　　　　　　　　　　　　　　　　　　　いるので計算を簡単にするために最初の
　　　　　　　　　　　　　　　　　　　　　ビットに１０を掛けたものに次のビット
　　　　　　　　　　　　　　　　　　　　　を加算し、１０進数で表現します。*/

　　　if(kind==11 && old==11)return 0; /* １つ前の道順が１１、現在の道順が
　　　　　　　　　　　　　　　　　　　　　１１のときには圧縮時の約束ではハフマ
　　　　　　　　　　　　　　　　　　　　　ン木の情報の終了を示しているので、こ
　　　　　　　　　　　　　　　　　　　　　れで終了 */

　　　if(kind==10　　　　　 )return 1; /* 道順が１０のときには１つ上（根の方向
　　　　　　　　　　　　　　　　　　　　　に戻る。*/

　　　if(kind==0 || kind==1){　　　　　/* 道順が０のときには左の子へ、１のとき
　　　　　　　　　　　　　　　　　　　　　には右の子へ進む。*/
　　　　if(!tree[cur][kind+1]){　　　　/* 生成中のハフマン木に行くべき子がない
　　　　　　　　　　　　　　　　　　　　　ときには、新たに子を生成する */
　　　　　ltree++;

　　　　　tree[ltree][0]=0;
　　　　　tree[ltree][1]=0;
　　　　　tree[ltree][2]=0;

　　　　　tree[cur][kind+1]=ltree;
　　　　}

　　　　　　　　　　　　　　　　　　　 /* 指定された子に行く */
　　　　if(!make_tree(tree[cur][kind+1]))return 0;
　　　}
　　　else if(kind==11){　　　　　　　 /* 道順が１１のときには葉（文字）*/
　　　　int i;

　　　　　　　　　　　　　　　　　　　 /* 文字は８ビットで表現されているので
　　　　　　　　　　　　　　　　　　　　　８ビット連続して取得し、順次上方向
　　　　　　　　　　　　　　　　　　　　　にしていくことで文字を木の葉に設定
　　　　　　　　　　　　　　　　　　　　　します。*/
　　　　for(i=0;i<8;i++)tree[cur][0]=(tree[cur][0]<<1) | get_bit(ifp);
　　　}

　　　old=kind;　　　　　　　　　　　　/* 終了を判定するために現在の道順を　　　　　　　　　　　　　　　　　　　　　old に入れる。*/
　　}
　}

　再帰呼び出しで実行しますので、ちょっと難しいかもしれませんがじっくり見て理解して下さい。この関数では道順の２ビットを１０進数で表現して処理しましたが、２進数のままで行なうには、

　kind=get_bit(ifp)*10 + get_bit(ifp);

を、

　kind=get_bit(ifp)<<1 | get_bit(ifp);

として行ないます。どのようにするかは好みですが、１０進にした方が、ビットの状態をそのまま数字で表現できるので理解しやすいと思います。

　この関数でハフマン木が再現できましたが、圧縮時には tree の配列の最初の部分に葉になる文字が入り、その後葉に近い木、最後に根という順番になっていましたが、伸長時には先頭に根、その次からは木と葉が混在したような順番になります。このように順番に違いがあっても根から辿る道順は完全に再現されています。

　次に伸長する部分です。メイン関数に expand(); を追加します。

　main()
　{
　　ifp=fopen( IN_FNAME,"rb");
　　ofp=fopen(OUT_FNAME,"wb");

　　fread(&out_file_size,sizeof(out_file_size),1,ifp);

　　in_remain=0;

　　ltree=0;
　　tree[ltree][0]=0;
　　tree[ltree][1]=0;
　　tree[ltree][2]=0;

　　make_tree(ltree);

　　expand();

　　fclose(ifp);
　　fclose(ofp);
　}

expand() 本体は、単純なループです。

　expand()
　{
　　int cur;　　　　　　　　　　 /* tree のインデックス番号 */

　　while(out_file_size>0){　　　/* 出力ファイルにすべての文字を書き込むまで
　　　　　　　　　　　　　　　　　　繰返す */

　　　cur=0;　　　　　　　　　　 /* tree の根から辿るため tree のインデックス番
　　　　　　　　　　　　　　　　　　号を０にする */
　　　while(1){
　　　　cur=tree[cur][get_bit(ifp)+1];
　　　　　　　　　　　　　　　　 /* ビットを１つ取得し、左または右の子に行く。
　　　　　　　　　　　　　　　　　　ビットが０のときには左ですので、tree[][1]
　　　　　　　　　　　　　　　　　　のインデックス、１のときには tree[][2]の
　　　　　　　　　　　　　　　　　　インデックス番号が子になる */

　　　　if(tree[cur][1]==0
　　　　&& tree[cur][2]==0){　　 /* 左右に子がないときには葉（文字）ですので、
　　　　　　　　　　　　　　　　　　葉の文字を出力ファイルに書き込む */
　　　　　fputc(tree[cur][0],ofp);
　　　　　break;
　　　　}
　　　}

　　　out_file_size--;　　　　　 /* 出力ファイルの文字数を１つ減らす */
　　}
　}

実はこれだけのものです。これで伸長が完了です。最後に全文です。

　#include <stdio.h>

　#define　IN_FNAME "x.x"
　#define OUT_FNAME "y.y"

　FILE *ifp,*ofp;

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

　unsigned char in_char;
　int　　　　　 in_remain;

　unsigned long out_file_size;

　main()
　{
　　ifp=fopen( IN_FNAME,"rb");
　　ofp=fopen(OUT_FNAME,"wb");

　　fread(&out_file_size,sizeof(out_file_size),1,ifp);

　　in_remain=0;

　　ltree=0;
　　tree[ltree][0]=0;
　　tree[ltree][1]=0;
　　tree[ltree][2]=0;

　　make_tree(ltree);

　　expand();

　　fclose(ifp);
　　fclose(ofp);
　}

　get_bit()
　{
　　int ret;

　　if(in_remain<=0){
　　　in_char=fgetc(ifp);
　　　in_remain=8;
　　}

　　if(in_char & 0x80)ret=1;
　　else　　　　　　　ret=0;

　　in_char<<=1;
　　in_remain--;

　　return ret;
　}

　make_tree(int cur)
　{
　　int old,kind;

　　old=0;

　　while(1){
　　　kind=get_bit(ifp)*10 + get_bit(ifp);

　　　if(kind==11 && old==11)return 0;
　　　if(kind==10　　　　　 )return 1;

　　　if(kind==0 || kind==1){
　　　　if(!tree[cur][kind+1]){
　　　　　ltree++;

　　　　　tree[ltree][0]=0;
　　　　　tree[ltree][1]=0;
　　　　　tree[ltree][2]=0;

　　　　　tree[cur][kind+1]=ltree;
　　　　}

　　　　if(!make_tree(tree[cur][kind+1]))return 0;
　　　}
　　　else if(kind==11){
　　　　int i;

　　　　for(i=0;i<8;i++)tree[cur][0]=(tree[cur][0]<<1) | get_bit(ifp);
　　　}

　　　old=kind;
　　}
　}

　expand()
　{
　　int cur;

　　while(out_file_size>0){
　　　cur=0;
　　　while(1){
　　　　cur=tree[cur][get_bit(ifp)+1];

　　　　if(tree[cur][1]==0
　　　　&& tree[cur][2]==0){
　　　　　fputc(tree[cur][0],ofp);
　　　　　break;
　　　　}
　　　}

　　　out_file_size--;
　　}
　}

　ハフマン法は文字の出現頻度を利用した古典的な圧縮アルゴリズムです。それほど圧縮率は高くはありませんが、プログラム自体は簡単に作成することができます。ハフマン法で圧縮したファイルを再びハフマン法で圧縮すると再び圧縮されることもありますので、これ以上圧縮されなくなるまで繰り返し、圧縮ファイルには何回圧縮したかを書き込んでおけばその回数だけ繰返して元に戻すことも可能です。

それではまた次回。