ハフマン符号プログラムの作成と圧縮率の測定

質問

• ハフマン符号によるファイルの圧縮をC言語で行うプログラムを作成し、圧縮率を測定する。
• 圧縮プログラムでは、入力ファイルを読み込んで各記号の出現頻度をカウントし、ハフマン符号を生成し出現頻度を出力ファイルに書き出す。
• 解凍プログラムでは、圧縮ファイルから各符号の出現頻度を読み込み、ハフマン符号を生成して解凍ファイルに出力する。

回答No.4

quenista

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

/* 各符号から上の要素番号をたどれなくなるまでたどりながら、自分が左側にいたら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);
てな感じですかね？

最後に、ファイルのクローズを忘れずに．．．。

一つ一つの動きを良く理解出来ますよう、頑張って下さいね。

補足

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

CODE search_code;
int parent_code;

と定義すると，parent_code=code[code].parent; のところで
error C2107: ポインタでない式に、添字が使われました。
error C2231: '.parent' : 左のオペランドが 'struct' へのポインタです。'->' を使用してください。
とエラーになってしまいました。

int *parent_code;

と定義すると，また parent_code=code[code].parent; のところで
error C2107: ポインタでない式に、添字が使われました。
error C2231: '.parent' : 左のオペランドが 'struct' へのポインタです。'->' を使用してください。
warning C4047: '=' : 間接参照のレベルが 'int *' と 'int ' で異なっています。

とエラーになってしまいました。
どうすればよいのでしょうか。

また，hcode_countはどのように定義すればよいのでしょうか。とりあえず，いまの段階までのプログラムを送ります。よろしかったらデバックしてください。
/****************************************************

ハフマン符号

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

#define SIZE 256

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

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

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

int min1, min2, freeNode, root;

/* (a) */
/* データの初期化 */
for( i = 0; i < 2*SIZE+1; i++ ) code[i].count = 0;
for( i = 0; i < SIZE; i++ ) mozi_count[i] = 0;

/* 文字頻度をカウント */
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++;
}

/* (b) */
/* ハフマン符号を生成する */

/* ハフマン木をつくる */
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;

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]++:
}
/* (c) */
if((fp2 = fopen(output_fname,"w")) == NULL){
fprintf(stderr,"%s: can't opn file\n", output_fname);
exit(1);
}
for(i=0;i<SIZE;i++){
fprintf(fp2,"%d ", mozi_count[i]);
}
bit_count=0;
while((i=fgetc(fp1))!=EOF){
for(hcode_count[i]-1;loop>=0;loop++){
put_bit(Hcode[search_code][loop]);
bit_count++;
}
}
for(loop=0;loop<(7-(bit_count&0xF));loop++) put_bit(0);
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 */
/*******************
関数put_bit
引数として，0，または1を渡すと，1bitづつファイルに書き込む
(ファイルポインタはグローバル変数として用意する）
実際には，8bit貯まった時点でbyte単位で出力する
*******************/
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,fpcode) == EOF){
printf("Can't write \n");
exit(1);
}
mask = 0x80;
byte = 0x00;
}
}
/*使用例(100bitを書き込む)(配列array[100]に0,1が格納されているとする）*/
/*for(i = 0;i < 100;i++)　　　　　　　　　　　 　　　　　*/
/* put_bit(array[i]); 　　　　　　　　　　　*/
/*for(i = 0;i < 7;i++) put_bitは8bit単位で書き込むので最後の　　 */
/* put_bit(0); bitを書き込むために最後の2行が必要となる。 */
/*(この例の場合は，残った4bitを書き込めばよいので，7でなく4でもできる） */