ハフマン符号のプログラム

Question

以下の問題に回答できる方，いらっしゃいましたらソースファイルと実行結果を送ってください。
　ファァイル（記号列）を読み込んで，ハフマン符号によりファイルを圧縮するプログラム（C言語）を作成する（プログラムは，圧縮を行うものと，解凍を行うものの2つ作る）。また，いくつか適当なファイルに対して，圧縮を行い圧縮率を測定する。
（1）圧縮プログラムについて
　圧縮のステップ
　（ａ）入力ファイルを読み込み各記号の出現頻度をカウントする。
　（ｂ）得られた出現頻度を使って各符号のハフマン符号を生成する。
　（ｃ）各符号の出現頻度を出力ファイルに書き出す。
　（ｄ）もう一度入力ファイルを読み込みながら各符号をハフマン符号で置き換え　　　　て出力ファイルに出力する。圧縮ファイルの形式は次のようになる。

　　0x00の　 0x01の  … 0xffの   先頭文字の 2文字目の … 終端文字の
　　出現頻度 出現頻度   出現頻度　符号語　　 符号語　　　　符号語
　　　（ｃ）で書きこむ部分　　　　　　（ｄ）で書きこむ部分

（2）解凍プログラムについて
　解凍のステップ
　（ａ）各符号の出現頻度を圧縮ファイルから読み込む。
　（ｂ）得られた出現頻度を使って各符号のハフマン符号を生成する。
　（ｃ）圧縮ファイルの符号語を読み込みながら各符号のハフマン符号と比較しも　　　　し一致したらその記号を解凍ファイルに出力する。
　（ｄ）(c)をファイルの終わりもしくは出現頻度をすべて足し合わせた記号数分処　　　理するまで繰り返す。
　関数について
　関数get_bit
　ファイルから1bit読み込んで戻り値として返す。
　（ファイルポインタはグローバル変数で用意する）

　関数put_bit
　引数として0，または1を渡すと1bitずつファイルに書き込む。
　（ファイルポインタはグローバル変数で用意する）

quenista · Accepted Answer

コンパイルが通る所迄は修正しましたが、分岐木の生成が正しく出来ていない感じがします。

この辺を、どの様に考えて作ろうとしているのか補足願えますか？
もしかしたら、私が考え方を間違って説明しているかも知れません。
生成されて来た分岐木データが、どうも単純にコードと対になって無い様子なのですが．．．。

取り合えず、現状のソースを張って置きます。
/* Quenista */
の入ってる行が、いじった所です。

/****************************************************

ハフマン符号

****************************************************/
#include <stdio.h>
#include <stdlib.h>
#include<string.h>/* Quenista*/

#define DEBUG
#define SIZE 256

/* 二分木 */
typedef struct _node {
unsigned int count; /* 頻度 */
int parent; /* 上の要素番号 */
int left; /* 左側を 0 */
int right; /* 右側を 1 */
} CODE;

CODE code[2*SIZE+1];
int mozi_count[SIZE];
int search_code; /* Quenista*/
int Hcode[SIZE][SIZE];
int hcode_count[SIZE]; /* ? */
int bit_count;
FILE *fp1,*fp2;

void put_bit(unsigned int bit);
void /*Quenista*/
main()
{
int i, total = 0;
char input_fname[] = "read.txt";
char output_fname[] = "out2.txt";

int min1, min2, freeNode, root;

#ifdef DEBUG
printf("a");/* Quenista Debug */
#endif
/* データの初期化 */
for( i = 0; i < 2*SIZE+1; i++ ) code[i].count = 0;
for( i = 0; i < SIZE; i++ ) mozi_count[i] = 0;
memset((char *)&hcode_count[0],0,sizeof(hcode_count));/* Quenista */

/* 文字頻度をカウント */
if((fp1 = fopen(input_fname,"r")) == NULL){
fprintf(stderr,"%s: can't opn file\n", input_fname);
exit(1);
}

while((i=fgetc(fp1)) !=EOF){
code[i].count++;
mozi_count[i]++;
total++;
}
fclose(fp1); /* Quenista(ファイルは、使わなくなった時点でクローズする方が良い) */

#ifdef DEBUG
printf("b");/* Quenista Debug */
#endif
/* ハフマン符号を生成する */

/* ハフマン木をつくる */
code[2*SIZE].count = 0x100; /* 番兵 */
for (freeNode = SIZE; ; freeNode++) {
min1 = min2 = 2*SIZE;
for (i = 2*SIZE-1; i >= 0; i--)
if (code[i].count > 0) {
if (code[i].count < code[min1].count) {
min2 = min1;
min1 = i;
} else if (code[i].count < code[min2].count)
min2 = i;
}
if (min2 == 513 - 1) break;
code[freeNode].count = code[min1].count + code[min2].count;
code[freeNode].left = min1;
code[freeNode].right = min2;

code[min1].parent = code[min2].parent = freeNode;
code[min1].count = code[min2].count = 0;
}
root = min1;

#ifdef DEBUG
for(i=0;i<512;i++){printf("[%3d：親%3d]\n",i,code[i].parent);} /* Quenist Debug */
#endif

for(i=0;i<256;i++){ /* コードの回数分のループを行う。 */
search_code=i; /* ←ここで、次に検索するコードを保存して置く */
while(code[search_code].parent<0x100&&code[search_code].parent!=0){ /* ←ここで、戻れなくなるまで探し続ける（親を訪ねて３千里。） *//* Quenista Offset加算 */
if(code[code[search_code].parent].left==search_code){ Hcode[i][hcode_count[i]]=0; } /* ここで、左に分岐しているのか調べ、左なら０ *//* Quenista Offset加算 */
else{ Hcode[i][hcode_count[i]]=1; } /* 右なら１を保存 */
search_code=code[search_code].parent; /* 一つ上に戻る *//* Quenista Offset加算 */
hcode_count[i]++; /* ビット数を、数えて置く */
}
}
/* (c) */
#ifdef DEBUG
printf("c");/* Quenista Debug */
#endif
if((fp2 = fopen(output_fname,"w")) == NULL){
fprintf(stderr,"%s: can't opn file\n", output_fname);
exit(1);
}
#ifdef DEBUG
fprintf(fp2,"Header:\n"); /*Quenista Debug */
#endif
for(i=0;i<SIZE;i++){
fprintf(fp2,"%d ", mozi_count[i]);
}
#ifdef DEBUG
fprintf(fp2,"\n"); /*Quenista Debug */
#endif
if((fp1 = fopen(input_fname,"r")) == NULL){ /* Quenista(再オープンが必要) */
fprintf(stderr,"%s: can't opn file\n", input_fname); /* Quenista */
exit(1); /* Quenista */
} /* Quenista */
#ifdef DEBUG
fprintf(fp2,"Data:\n"); /*Quenista Debug */
#ifdef endif
bit_count=0;
while(!feof(fp1)){/*Quenista*/
search_code=fgetc(fp1);/*Quenista*/
for(i=hcode_count[search_code];i>0;i--){ /*Quenista */
put_bit(Hcode[search_code][i-1]); /* Quenista*/
bit_count++;
}
}
#ifdef DEBUG
printf("d");/* Quenista Debug */
#endif
for(i=0;i<(7-(bit_count&0xF));i++) put_bit(0); /* Quenista */
fclose(fp1);
fclose(fp2);
}

void put_bit(unsigned int bit)
{
static unsigned int mask = 0x80;
static unsigned int byte = 0x00;

if(bit != 0){
byte = byte | mask;
}
mask = mask >> 1;

//8bit貯まったか
if(mask == 0x00){
if(fputc(byte,fp2) == EOF){
printf("Can't write \n");
exit(1);
}
mask = 0x80;
byte = 0x00;
}
}
/* end of file */

quenista · Answer

先ず、紛らわし表記を使ったのが不味かったのですね。
ごめんなさい。

search_code=code; 
parent_code=code[code].parent; 
while(code[code].parent!=0x100){ 
ここで使っている[code]は、検索すべき値が順次入るコードを入れて欲しかったのです。
つまり、もう少し前後を含め分岐木を辿る部分を書くと、

for(i=0;i<256;i++){ /* コードの回数分のループを行う。 */
parent_code=i; /* ←ここで、次に検索するコードを保存して置く */
while(code[parent_code].parent!=0x100){  /* ←ここで、戻れなくなるまで探し続ける（親を訪ねて３千里。） */
if(code[code[parent_code].parent].left==parent_code){ Hcode[i][hcode_count[i]]=0; }  /* ここで、左に分岐しているのか調べ、左なら０ */
else{ Hcode[i][hcode_count[i]]=1; } /* 右なら１を保存 */
parent_code=code[parent_code].parent; /* 一つ上に戻る */
hcode_count[i]++;  /* ビット数を、数えて置く */
} 
}

と言う感じだと思います。
少し気になったのは、この辺の動きを理解されているか解らないので、出来るだけ説明の１つのコードの部分に絞って記述した見てたのです。
search_codeについては、検索コードを明示的に書いただけです。
parent_codeいついては、code[].parentの型
つまりint型で定義すれば良いですね。

hcode_countについては、各コードのビット数をカウントして置く場所ですので、コードの数。つまり２５６個の箱が有れば良い事に成ります。
又、このソースからは、ビット数が２５６を越える事は無いのでchar型でも良いのですが、数値を入れるのでint型で取る方が良いと思います。
つまり、
int hcode_count[256];
で良いですね。
後、初期化は最初はビット数は０としたいので、
memset((char *)&hcode_count[0],0,sizeof(hcode_count));
として初期化して置いてやれば良いと思います。

絵には描き難いのですが．．．。

親―子―孫Ａ
　＼　＼
　　子　孫Ｂ
　　｜＼
　　孫　孫Ｃ
　　Ｄ

と言う感じで分岐木が出来ているのを、孫から親に辿って行く作業を行っています。
それを孫から戻る時に孫は子の左右のどちらに居るかを、コードとして拾っています。
又、子から親に戻る時も親のどちら側に居るかを辿って居ます

例えば、孫Ｃから戻ると子の右側に繋がって居て、その子は親の左側に繋がっている事になり、それをこのコードで表すと、[0]，[1]となります。
それを逆から読んだ物がハフマン符号になります。
(つまり、[10]）
この戻った回数が、ビット数として保存して置いてます。
ビット数は、出現頻度の高いデータは短く、出現頻度の少ないデータは多くなる事になりますね。

ハフマン符号の分岐木の生成とデータ分布率の部分は、少し考えないと難しいかも知れませんが、良く理解してコードに落として行って下さいね。

もしこの辺が解りにくい場合は、絵に書く等して見ると解りやすいかも知れません。

＞よろしかったらデバックしてください。
少し忙しくなって来てまして余り早く回答出来ないかも知れませんが、こちらでも確認して見ます。

それと、このプログラムコードはまだまだ改善出来る個所が多々有りそうですので、全体の動作を良く押えて見て下さいね。

quenista · Answer

for(loop=0;loop<(bit_count&0xF);loop++) bit_put(0); 
ここ、間違ってました。

足りない分を補うので、
for(loop=0;loop<(7-(bit_count&0xF));loop++) bit_put(0); 
が正しいですね。

検証してないので、他にもバグってるかも知れません。
注意して下さいね。

quenista · Answer

全体のソースでは無い様ですし、全てのロジックを確認した訳では無いので、一つ一つの動作は御自分で確認して見て下さい。

/* 各符号から上の要素番号をたどれなくなるまでたどりながら、自分が左側にいたら0を右側にいたら1を並べていくと、その逆順がその記号のハフマン符号となる。*/
/* これを各符号に対して行い，それぞれのハフマンコードを２次元配列Hcodeに格納する。
/* 例えば，記号('A' = 65)のハフマンコードが"011"の場合　Hcode[65][0] = 0; Hcode[65][1] = 1; Hcode[65][2] = 1; */ 
先ず、Hcode[][]の配列がこのプログラム中には無いですが、他に有るのですね？
parentに値が有る間（0x100以外の時）は、何処かの分岐木の下で有ると言う事です。
このソースの場合、デーブル・チェーン構造になってますので、それを辿って下さいと言う事です。
例えば、あるコード一つで見てみると、code[(コード)].parentの中に上位のコード番号が入っています。
そのコードに戻ると、.left或いは.rightの中にコード番号が入っています。
つまり、
    search_code=code;
    parent_code=code[code].parent;
    while(code[code].parent!=0x100){
        if(code[code[parent_code].parent].left==parent_code){   Hcode[search_code][0]=0;    }
        else{   Hcode[search_code][0]=1;   }
        parent_code=code[parent_code].parent;
        hcode_count[search_code]++;
    }
と言う様な事を、256文字分行えば良いと思います。
hcode_countは、後で使う為に追加しました。（0初期化）

fclose(fp2);
↑put_bit関数の中が解らないのですが、データを書き込んでからクローズした方が良いのでは？

/* (d) */ 
/* もう一度ファイルを読み込み，その記号に対応するハフマンコードをファイルに書いていく。 */ 
/* (d)の書き込みにはput_bit関数を使って書き込むことができる。 */
/* また注意点として，put_bit関数は8bitたまった時点でファイルに書き込みを行うので，ファイルの記号をすべて処理した時に，最後に8bitたまっていない場合残りのbitに'0'を書き込む必要がある。*/ 
ファイルのオープンは解って居られると思いますので、他の部分だけ．．．。
上記のロジックで、Hcodeにハフマンコードが、hcode_countにハフマンコードのビット数が入ってます。
それを、Fileに書き出せば良いのです。
又、書き出したビット数を数えて置くと、空白を埋めるビット数は解ると思います。

    bit_count=0;
    while((i=fgetc(fp1))!=EOF){
        for(hcode_count[i]-1;loop>=0;loop++){
            bit_put(Hcode[search_code][loop]);
            bit_count++;
        }
    }
    for(loop=0;loop<(bit_count&0xF);loop++)    bit_put(0);
てな感じですかね？

最後に、ファイルのクローズを忘れずに．．．。

一つ一つの動きを良く理解出来ますよう、頑張って下さいね。

quenista · Answer

＞実は（ａ）からあまりよく理解していなかったようで・・・。
では、順に行きましょう。

先ず、ターゲット（圧縮するファイル）の分布を洗い出す為に、ファイルを一度なめると言う動作を考えます。
色々な考え方などが有りますが、取り敢えず一番単純な１バイト単位で考えてみます。
すると、ファイルから１バイトづつ読みながらカウントすれば良いですよね？
つまり２５６個の領域を取って置いて、加算して行けば良いだけです。

こんどは、この２５６個のデータをソートして、加算された順に並べます。

そして、この２５６個のデータにハフマンの分岐木を割り当てて行けば良いのです。（勿論、ビットの少ない方から。）
そして、そのヘッダー部分を出力形式に変換しながらファイル出力します。
最後にデータの先頭に戻って、各データをビット毎にファイルに出力して行けば良いのです。（シフト等を使いながら。）

逆に解凍の場合は、先にビットパターンからバイトに変換するテーブルを作成し、
１ビット毎に比較（こちらも、シフトとマスクを使って、比較を行えば良い。）を行ない、元のバイトデータに戻して行きます。

これで、詰まった所を教えて頂けますか？

quenista · Answer

＞（ｃ）から先はよく分かりません。 
先ず、単純にファイルを舐めながら、変数に加算して行けば良いと思います。
それを最後に並べ直せば、出現頻度順に並べる事が出来ますので、それをフォーマットに沿った形で吐いてやれば、良いですね。

後は、ハフマンの分岐木を生成して、出現頻度順に割り当ててを行い、
そのルールでビットへ変換して行けば良いでしょう。

後、辞書圧縮は行わないで良いのですよね？

quenista · Answer

流石に、ココでソースを書くのは結構困難ですので、
先ず、何処で詰っているか補足頂けますか？

不明個所についてなら、アドバイスが出来るかも知れません。

又、一言でハフマン圧縮と言っても、種類が有りますが、
動的ハフマンですか？
静的ハフマンですか？

ハフマン符号のプログラム

コンパイルが通る所迄は修正しましたが、分岐木の生成が正しく出来ていない感じがします。

先ず、紛らわし表記を使ったのが不味かったのですね。

for(loop=0;loop<(bit_count&0xF);loop++) bit_put(0);

全体のソースでは無い様ですし、全てのロジックを確認した訳では無いので、一つ一つの動作は御自分で確認して見て下さい。

この回答への補足

＞実は（ａ）からあまりよく理解していなかったようで・・・。

この回答への補足

＞（ｃ）から先はよく分かりません。

この回答への補足

流石に、ココでソースを書くのは結構困難ですので、

この回答への補足

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング