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

質問

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

回答No.3

quenista

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

先ず、ターゲット（圧縮するファイル）の分布を洗い出す為に、ファイルを一度なめると言う動作を考えます。
色々な考え方などが有りますが、取り敢えず一番単純な１バイト単位で考えてみます。
すると、ファイルから１バイトづつ読みながらカウントすれば良いですよね？
つまり２５６個の領域を取って置いて、加算して行けば良いだけです。

こんどは、この２５６個のデータをソートして、加算された順に並べます。

そして、この２５６個のデータにハフマンの分岐木を割り当てて行けば良いのです。（勿論、ビットの少ない方から。）
そして、そのヘッダー部分を出力形式に変換しながらファイル出力します。
最後にデータの先頭に戻って、各データをビット毎にファイルに出力して行けば良いのです。（シフト等を使いながら。）

逆に解凍の場合は、先にビットパターンからバイトに変換するテーブルを作成し、
１ビット毎に比較（こちらも、シフトとマスクを使って、比較を行えば良い。）を行ない、元のバイトデータに戻して行きます。

これで、詰まった所を教えて頂けますか？

補足

仕様書の内容をまとめると以下のようになりました。
#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];
int mozi_count[SIZE];

int
main()
{
int i, total = 0;
char input_fname[] = "read.txt";
char output_fname[] = "out.txt";
FILE *fp1,*fp2;
int min1, min2, freeNode, root;

/* (a) */
/* データの初期化 */
for( i = 0; i < 2*SIZE+1; i++ ) code[i].count = 0;
for( i = 0; i < SIZE+1; 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++;
}
fclose(fp1);

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

/* ハフマン木をつくる */
code[2*SIZE].count = 0x100; /* 番兵 */
for (freeNode = 256; ; 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)
in2 = i;
}

if (min2 == 2*SIZE) 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;
/* 各符号から上の要素番号をたどれなくなるまでたどりながら，自分が左側に */
/* いたら0を，右側にいたら1を並べていくと，その逆順がその記号のハフマン */
/* 符号となる。これを各符号に対して行い，それぞれのハフマンコードを２次 */
/* 元配列Hcodeに格納する。例えば，記号('A' = 65)のハフマンコードが"011"*/
/* の場合　Hcode[65][0] = 0; Hcode[65][1] = 1; Hcode[65][2] = 1; */

/* (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]);
}
fclose(fp2);
/* (d) */
/* もう一度ファイルを読み込み，その記号に対応するハフマンコードをファイ */
/* ルに書いていく。 */

/* (d)の書き込みにはput_bit関数を使って書き込むことができる。また注意点 */
/* として，put_bit関数は，8bitたまった時点でファイルに書き込みを行うの　*/
/* で，ファイルの記号をすべて処理した時に，最後に8bitたまっていない場合 */
/残りのbitに'0'を書き込む必要がある。*/
}

/* end of file */
日本語で書いてあるところがわかりません。