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

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

　ハフマン木を書き込みましたので、いよいよファイルの圧縮になりますが、その前に１つやっておくことがあります。予め入力ファイルの文字が出力ファイルに書き込まれるビット列を決めておきましょう。メイン関数に文字変数 ptn を追加し、make_pattern関数を呼び出す様にします。ptn を２５６バイトとしたのは、ハフマン木が最悪の木になったときにはビット列が最大２５５になるからです。

　main()
　{
　　char ptn[256];

　　 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);

　　make_pattern(ltree,ptn,0);

　　fclose(out_fp);
　　fclose( in_fp);
　}

　make_pattern 関数の第１引数はハフマン木の根のインデックス番号、第２引数は出力するビット列を示す文字列、第３引数は第２引数の最後の要素のインデックス番号です。

make_pattern 本体は次のようになります。この関数も再帰呼び出しになっていますのでちょっと厄介ですが頑張って理解して下さい。

　make_pattern(int cur,char *ptn,int lptn)
　{
　　int lr;

　　if(tree[cur][1]==0　　　　　　 /* 左右の子がないので葉（文字） */
　　&& tree[cur][2]==0){
　　　ptn[lptn]='\0';　　　　　　　/* ptn の最後にヌルを追加 */

　　　　　　　　　　　　　　　　　 /* 文字の値に相当する pattern の要素位置に
　　　　　　　　　　　　　　　　　　　動的にメモリを確保してビットパターンを
　　　　　　　　　　　　　　　　　　　入れる */
　　　pattern[tree[cur][0]]=(char *)malloc(lptn+1);
　　　strcpy(pattern[tree[cur][0]],ptn);
　　　return 1;
　　}

　　for(lr=1;lr<=2;lr++){
　　　if(tree[cur][lr]){　　　　　 /* 左、右の子がある */
　　　　if(lr==1)ptn[lptn]='0';　　/* 左のときには ptn に '0' を追加 */
　　　　else　　 ptn[lptn]='1';　　/* 右のときには ptn に '1' を追加 */

　　　　make_pattern(tree[cur][lr]-1,ptn,lptn+1);
　　　}
　　}

　　return 1;
　}

　ハフマン木をファイルに出力する関数も、このビットパターンを生成する関数も再帰呼び出しを行なって計算するようにしているので、理解するにはややこしいのですが、驚くほどスッキリと記述することができます。再帰呼び出しを行なわずに記述することも勿論可能ですが、これほどスッキリとはいかないはずです。

　試しに make_pattern 関数で文字に対してどのようなパターンが生成されているのかを調べてみると、ABCDEABABBCBC のデータに対しては、

　A 01
　B 11
　C 10
　D 001
　E 000

となっていました。ということはこの文字列が圧縮されれば、

　A B C D　E　A B A B B C B C
　0111100010000111011111101110

というビット列になるはずです。バイト数にすれば、３バイトと４ビットになりますので圧縮されるはずです。

　最後に圧縮する機能を追加しましょう。ここまでくれば後は簡単です。メイン関数にcompress(); を追加します。

　main()
　{
　　char ptn[256];

　　 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);

　　make_pattern(ltree,ptn,0);

　　compress();

　　fclose(out_fp);
　　fclose( in_fp);
　}

関数 comoress は、次のように非常に簡単です。

　compress(char *fname,FILE *ofp)
　{
　　unsigned char c;
　　int i;

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

　　　add_bits(pattern[c]);
　　}

　　add_bits("0000000");

　　return 1;
　}

あまり説明する必要はありませんが、入力ファイルすべてを処理した後に

　add_bits("0000000");

としているのは、出力ファイルに出力されていない最後の１バイトを強制的に出力させるためです。これで完成ですので、全文を紹介します。

　#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()
　{
　　char ptn[256];

　　 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);

　　make_pattern(ltree,ptn,0);

　　compress();

　　fclose(out_fp);
　　fclose( in_fp);
　}

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

　　for(i=0;i<256;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;
　}

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

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

　make_pattern(int cur,char *ptn,int lptn)
　{
　　int lr;

　　if(tree[cur][1]==0
　　&& tree[cur][2]==0){
　　　ptn[lptn]='\0';

　　　pattern[tree[cur][0]]=(char *)malloc(lptn+1);
　　　strcpy(pattern[tree[cur][0]],ptn);
　　　return 1;
　　}

　　for(lr=1;lr<=2;lr++){
　　　if(tree[cur][lr]){
　　　　if(lr==1)ptn[lptn]='0';
　　　　else　　 ptn[lptn]='1';
　　　　make_pattern(tree[cur][lr]-1,ptn,lptn+1);
　　　}
　　}

　　return 1;
　}

　compress(char *fname,FILE *ofp)
　{
　　unsigned char c;
　　int i;

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

　　　add_bits(pattern[c]);
　　}

　　add_bits("0000000");

　　return 1;
　}

　今回までは圧縮のみですが、色々なファイルで実験してみて下さい。ただし小さいファイルに対しては、出力ファイルには入力ファイルのサイズ、ハフマン木の情報が入りますので逆に大きくなってしまいます。圧縮率はＬＨＡなどと比べてあまり大きくはありません。これについては後述します。

次回からは伸長するプログラムを作っていきましょう。