以下の問題に回答できる方,いらっしゃいましたらソースファイルと実行結果を送ってください。
 ファァイル(記号列)を読み込んで,ハフマン符号によりファイルを圧縮するプログラム(C言語)を作成する(プログラムは,圧縮を行うものと,解凍を行うものの2つ作る)。また,いくつか適当なファイルに対して,圧縮を行い圧縮率を測定する。
(1)圧縮プログラムについて
 圧縮のステップ
 (a)入力ファイルを読み込み各記号の出現頻度をカウントする。
 (b)得られた出現頻度を使って各符号のハフマン符号を生成する。
 (c)各符号の出現頻度を出力ファイルに書き出す。
 (d)もう一度入力ファイルを読み込みながら各符号をハフマン符号で置き換え    て出力ファイルに出力する。圧縮ファイルの形式は次のようになる。

  0x00の  0x01の … 0xffの 先頭文字の 2文字目の … 終端文字の
  出現頻度 出現頻度 出現頻度 符号語   符号語    符号語
   (c)で書きこむ部分      (d)で書きこむ部分

(2)解凍プログラムについて
 解凍のステップ
 (a)各符号の出現頻度を圧縮ファイルから読み込む。
 (b)得られた出現頻度を使って各符号のハフマン符号を生成する。
 (c)圧縮ファイルの符号語を読み込みながら各符号のハフマン符号と比較しも    し一致したらその記号を解凍ファイルに出力する。
 (d)(c)をファイルの終わりもしくは出現頻度をすべて足し合わせた記号数分処   理するまで繰り返す。
 関数について
 関数get_bit
 ファイルから1bit読み込んで戻り値として返す。
 (ファイルポインタはグローバル変数で用意する)

 関数put_bit
 引数として0,または1を渡すと1bitずつファイルに書き込む。
 (ファイルポインタはグローバル変数で用意する)

このQ&Aに関連する最新のQ&A

A 回答 (7件)

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



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

取り合えず、現状のソースを張って置きます。
/* 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){ /* ←ここで、戻れなくなるまで探し続ける(親を訪ねて3千里。) *//* Quenista Offset加算 */
if(code[code[search_code].parent].left==search_code){ Hcode[i][hcode_count[i]]=0; } /* ここで、左に分岐しているのか調べ、左なら0 *//* Quenista Offset加算 */
else{ Hcode[i][hcode_count[i]]=1; } /* 右なら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 */
    • good
    • 0
この回答へのお礼

返事が遅れてしまって大変申しわけありませんでした。
おかげさまでなんとか提出期限には間に合いました。なにせこのレポートを提出しないと期末試験を受けられなかったものですから。
本当に長い間お世話になりました。ありがとうございました。

お礼日時:2002/02/22 00:50

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


ごめんなさい。

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){ /* ←ここで、戻れなくなるまで探し続ける(親を訪ねて3千里。) */
if(code[code[parent_code].parent].left==parent_code){ Hcode[i][hcode_count[i]]=0; } /* ここで、左に分岐しているのか調べ、左なら0 */
else{ Hcode[i][hcode_count[i]]=1; } /* 右なら1を保存 */
parent_code=code[parent_code].parent; /* 一つ上に戻る */
hcode_count[i]++; /* ビット数を、数えて置く */
}
}

と言う感じだと思います。
少し気になったのは、この辺の動きを理解されているか解らないので、出来るだけ説明の1つのコードの部分に絞って記述した見てたのです。
search_codeについては、検索コードを明示的に書いただけです。
parent_codeいついては、code[].parentの型
つまりint型で定義すれば良いですね。

hcode_countについては、各コードのビット数をカウントして置く場所ですので、コードの数。つまり256個の箱が有れば良い事に成ります。
又、このソースからは、ビット数が256を越える事は無いのでchar型でも良いのですが、数値を入れるのでint型で取る方が良いと思います。
つまり、
int hcode_count[256];
で良いですね。
後、初期化は最初はビット数は0としたいので、
memset((char *)&hcode_count[0],0,sizeof(hcode_count));
として初期化して置いてやれば良いと思います。

絵には描き難いのですが...。

親―子―孫A
 \ \
  子 孫B
  |\
  孫 孫C
  D

と言う感じで分岐木が出来ているのを、孫から親に辿って行く作業を行っています。
それを孫から戻る時に孫は子の左右のどちらに居るかを、コードとして拾っています。
又、子から親に戻る時も親のどちら側に居るかを辿って居ます

例えば、孫Cから戻ると子の右側に繋がって居て、その子は親の左側に繋がっている事になり、それをこのコードで表すと、[0],[1]となります。
それを逆から読んだ物がハフマン符号になります。
(つまり、[10])
この戻った回数が、ビット数として保存して置いてます。
ビット数は、出現頻度の高いデータは短く、出現頻度の少ないデータは多くなる事になりますね。

ハフマン符号の分岐木の生成とデータ分布率の部分は、少し考えないと難しいかも知れませんが、良く理解してコードに落として行って下さいね。

もしこの辺が解りにくい場合は、絵に書く等して見ると解りやすいかも知れません。

>よろしかったらデバックしてください。
少し忙しくなって来てまして余り早く回答出来ないかも知れませんが、こちらでも確認して見ます。

それと、このプログラムコードはまだまだ改善出来る個所が多々有りそうですので、全体の動作を良く押えて見て下さいね。
    • good
    • 0

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


ここ、間違ってました。

足りない分を補うので、
for(loop=0;loop<(7-(bit_count&0xF));loop++) bit_put(0);
が正しいですね。

検証してないので、他にもバグってるかも知れません。
注意して下さいね。
    • good
    • 0

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



/* 各符号から上の要素番号をたどれなくなるまでたどりながら、自分が左側にいたら0を右側にいたら1を並べていくと、その逆順がその記号のハフマン符号となる。*/
/* これを各符号に対して行い,それぞれのハフマンコードを2次元配列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>

#defineSIZE256

/* 二分木 */
typedef struct _node {
unsigned intcount;/* 頻度 */
intparent; /* 上の要素番号 */
intleft; /* 左側を 0 */
intright; /* 右側を 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()
{
inti, 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 unsignedint mask = 0x80;
static unsignedint 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 unsignedint mask = 0x80;
static unsignedint 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でもできる) */

補足日時:2002/01/17 00:00
    • good
    • 0

>実は(a)からあまりよく理解していなかったようで・・・。


では、順に行きましょう。

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

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

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

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

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

この回答への補足

仕様書の内容をまとめると以下のようになりました。
#include<stdio.h>
#include<stdlib.h>

#defineSIZE256

/* 二分木 */
typedef struct _node {
unsigned int count; /* 頻度 */
intparent; /* 上の要素番号 */
intleft; /* 左側を 0 */
intright; /* 右側を 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を並べていくと,その逆順がその記号のハフマン */
/* 符号となる。これを各符号に対して行い,それぞれのハフマンコードを2次 */
/* 元配列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 */
日本語で書いてあるところがわかりません。

補足日時:2002/01/06 16:31
    • good
    • 0

>(c)から先はよく分かりません。


先ず、単純にファイルを舐めながら、変数に加算して行けば良いと思います。
それを最後に並べ直せば、出現頻度順に並べる事が出来ますので、それをフォーマットに沿った形で吐いてやれば、良いですね。

後は、ハフマンの分岐木を生成して、出現頻度順に割り当ててを行い、
そのルールでビットへ変換して行けば良いでしょう。

後、辞書圧縮は行わないで良いのですよね?

この回答への補足

 実は(a)からあまりよく理解していなかったようでうまく説明できません。特に(b)がよく分かっていませんでした。
辞書圧縮は行わなくて良いです。

補足日時:2001/12/19 23:50
    • good
    • 0

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


先ず、何処で詰っているか補足頂けますか?

不明個所についてなら、アドバイスが出来るかも知れません。

又、一言でハフマン圧縮と言っても、種類が有りますが、
動的ハフマンですか?
静的ハフマンですか?

この回答への補足

 静的ハフマン符号です。
 ネットで「ハフマン符号」で検索してサンプルプログラムを得たのですが,インクルードファイルが見たこともないものを使っていたのと,はっきり言って理解できなかったんです。
 ちなみに,stdio.h stdilb.h string.h math.h くらいしか使ったことがりません。
 サンプルプログラムを見て,圧縮の方は(b)のところまではなんとか理解したつもりですが,(c)から先はよく分かりません。
 解凍の方はまだ手をつけていません。たぶん,(c)から先がまた分からないと思います。

補足日時:2001/12/18 22:48
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qハフマン符号化の問題を解くプログラム

ハフマンの符号化の問題を解くプログラムをC言語(コンソールアプリケーション)で作りたいのですが
ファイルの圧縮とかをするプログラムはいろいろなサイトにあったのですが、
簡単な情報源を与えられたものを符号化するプログラムで参考にできるようなサイトは見つかりませんでした。
誰かプログラムの例を教えていただけないでしょうか?
入力する例はつぎのようなものです
S=(a1, a2, a3, a4, a5, a6/0.35, 0.15, 0.15, 0.20, 0.10, 0.05)

Aベストアンサー

木の作り方によって得られる符号は微妙に違いますのでこれは参考です。
シンボルと頻度テーブルから木を作って符号一覧を表示します。
符号化だけならleftとrightは不要です(復号化のとき使う)

#include <stdio.h>
#define N 6 /* N>=2 */
char *s[N]={"a1","a2","a3","a4","a5","a6"};
float f[2*N-1]={0.35,0.15,0.15,0.20,0.10,0.05};
int size=N, parent[2*N-1], left[2*N-1], right[2*N-1];
/* ハフマン木の作成 */
void huff(void) {
 int i,j,dat1,dat2;
 float min;
 /* 初期化 */
 for (i=0;i<2+N;i++) left[i]=right[i]=parent[i]=0;
 /* 最小頻度2個をまとめ続ける */
 while(1) {
  /* 一番小さい数を探す */
  for (i=0;i <size;i++) if (f[i]>=0) break;
  if (i==size) break; /* 頻度リストが空? */
  dat1=i; min=f[dat1];
  for (;i<size;i++) if (f[i]<min && f[i]>=0) {min=f[i]; dat1=i;}
  /* 二番目に小さい数を探す */
  for (i=0; i<size; i++) if ((f[i]>=0)&&(i!=dat1)) break;
  if (i==size) break; /* 頻度リストが1個しかない */
  dat2=i; min=f[dat2];
  for (;i<size;i++) if (f[i]<min && f[i]>=0 && i!=dat1) { min=f[i]; dat2=i; }
  /* 木に登録 */
  left[size]=dat1; right[size]=dat2;
  parent[dat1]=size; parent[dat2]= -size;
  f[size]=f[dat1]+f[dat2]; f[dat1]= -1; f[dat2]= -1;
  size ++;
 }
}
/* ハフマン符号の出力 */
void outenc(int huf) {
 if (huf== size-1) return;
 if (parent[huf]<0) {
  outenc(-parent[huf]); printf("1");
 } else {
  outenc(parent[huf]); printf("0");
 }
}
/* メインルーチン */
int main(void) {
 int i;
 huff();
 for (i=0; i<N; i++) { printf("%s ",s[i]); outenc(i); printf("\n"); }
 return 0;
}

木の作り方によって得られる符号は微妙に違いますのでこれは参考です。
シンボルと頻度テーブルから木を作って符号一覧を表示します。
符号化だけならleftとrightは不要です(復号化のとき使う)

#include <stdio.h>
#define N 6 /* N>=2 */
char *s[N]={"a1","a2","a3","a4","a5","a6"};
float f[2*N-1]={0.35,0.15,0.15,0.20,0.10,0.05};
int size=N, parent[2*N-1], left[2*N-1], right[2*N-1];
/* ハフマン木の作成 */
void huff(void) {
 int i,j,dat1,dat2;
 float min;
 /* 初期化 */
 fo...続きを読む

Qデータを圧縮したい

変数の配列を圧縮したいのですが、全く検討もつきません。
どうすればいいでしょうか?
簡単な圧縮の勉強サイトはないのでしょうか?

Aベストアンサー

まあ役に立つかどうかはわかりませんが

Run-Length圧縮の一例(ゆみみみっくす フォーマット解説:圧縮されたデータの展開のしかた)
http://ku-www.ss.titech.ac.jp/~yatsushi/yumimi.html
Windows DIBのRun-Length圧縮(BMP(DIB)フォーマット解説:圧縮について)
http://hp.vector.co.jp/authors/VA022217/tips/doc/bitmap.html

いわゆる"辞書法"による圧縮(LZ77/LZ78法)
技術評論社 Software Technologyシリーズ
C言語による最新アルゴリズム事典(ISBN4-87408-414-1)
http://www.gihyo.co.jp/books/syoseki.php/4-87408-414-1

# 最近高速化のためのindexingとかばかりで
# 「データをでっかくする方向」ばかり
# やってたからちょっと新鮮。

Qガロア体の逆元計算について

私は今、AES暗号の勉強をしているのですが、ガロア体の所でつまづいています。

ガロア理論での逆元はx∈GF(p)のとき、
GF(p)でx * y が1になる時のyがxの逆元だと思うのですが、
下記のページの上から1/6ぐらいの場所にある逆数変換テーブルを見る限り、
この方法では求められないような気がします。

このページでは16進数の53の逆元を計算しているので、10進数では83になります。
(83 * 219 - 1 )/256= 0なので、53の逆元は219かなと思ったのですが、
以下のページでは16進数のCAで、10進数では202になってしまいます。

私は、どこで間違っているのか、指摘していただけないでしょうか。

http://bw-www.ie.u-ryukyu.ac.jp/~wada/design04/spec_j.html

Aベストアンサー

ガロア体を勉強しましょう
むちゃくちゃなことをしていますぞ

GF(2^8)の元を2つかける時に
それらの元をそれぞれ十進数にして整数の掛け算をしてはいけません

aとbをかけるには
aの多項式表現を作り
bの多項式表現を作り
それら多項式を多項式として掛け算し
参考のページにのっている既約多項式でその結果を割った余りを求め
その余り多項式の係数を並べて16進表現をだすのである
a逆元をもとめるには
aに0を除く255個の元すべてを上の方法でかけてみて1(上の意味で0x01)になるものを選べばいいのです

QLPCWSTRとchar

質問なのです・・・

現在、私は[Visual Stdio.Net 2005]を使って、C++のプログラミングをしようと思いまして、今日参考書を見てやってみたのですが、

charの配列を使って、文字列を格納しそれを使おうとしたら、LPCWSTRのキャストが必要というエラーがでました。
参考書だと普通に通るらしいのですが・・・Visual Stdio.Net 2003と2005の違いなのでしょか?わかる方教えていただけませんでしょうか??

Aベストアンサー

補足です。
2005デフォルトのUNICODEを変更する方法は
プロジェクト->プロパティ->構成プロパティ->全般 の中にある
文字セットを[Unicode 文字セットを使用する]から[マルチバイト文字セットを使用する]
に変更することで可能です。

Q1文字って1バイトだったっけ?

タイトルの通りなんですが
私の記憶では1文字1バイトで漢字が2バイトだったような・・・。
アルファベットは?数字は?わかんないので教えてください。
それと、1バイト=8ビットですよね?
ちょっと興味があるので暇のある方がおられましたら詳しく教えてほしいです。

よろしくおねがいいたします。

Aベストアンサー

全角文字(英語・漢字・数字問わず):2バイト
半角文字:1バイト
では無いでしょうか?

>1バイト=8ビット
その通りです

http://www.pc-view.net/Help/manual/0082.html
などもありますので参考までに

参考URL:http://www.pc-view.net/Help/manual/0082.html

Qファイルからビット単位での読み書き

手元に1MBのファイルがあります。
PCの内部ではこのファイル0,1で表現されていますよね?
C言語でその1MBのファイルから01のデータを128ビットずつ読み込んできて処理したいのですが,何をどうやったらいいのか分かりません。
分かる方お願いします。

Aベストアンサー

#1に加えての回答です。
読み込む領域は
unsigned char ucBuffer[16];
という具合に、unsigned char の配列で定義します。そして各 ucBuffer[i] に対して各ビットに対するビット積を行い、その結果によってビット毎の処理を行います。たとえば、
int i,j;
for ( i = 0; i < 16; i++ )
{
for ( j = 7; j >=0; j-- )
{
int nBit = ( ucBuffer & ( 1 << j ) ) ? 1 : 0 ;
/******/
}
}
とし、コメント部分で nBit の値をもとに各ビットごとの処理を行えばいいのです。
#ただし、実際にはコメント部分では読み込みデータ→ビット値を格納する配列への変換のみを行い、実際の処理は上記の2重ループを抜けたところで行うべきです。

Qint型からchar型への変換

タイトル通り、int型からchar型への変換の仕方がわかりません!><
どうしたらいいのでしょうか?

Aベストアンサー

#include <stdio.h>


char buf[5];
int no;

no = 10;
sprintf(buf, "%d", no);

Qjpegの量子化テーブルはどう決まるの?

jpegについて勉強しています。
画像を8x8ブロック毎にDCTで周波数変換するところは理解できました。
その後の量子化テーブルを用いて高周波成分を圧縮するところで疑問がわきました。量子化テーブルは通常、左上の方の低周波側が小さい値で、右下の方の高周波側が大きい値になる、ということは分かります。でもこの値って一体、誰がいつどうやって決めるものなんでしょうか?
推奨値みたいなものがあるんでしょうか。それともjpeg化するアプリケーションによって異なるような自由度の高いものなんでしょうか。

Aベストアンサー

自由に決めてかまいませんが、jpeg形式を作ったjpeg(団体)の出している仕様書に例が載っています。これから派生したテーブルを使うソフトがほとんどです。
輝度:
16, 11, 10, 16, 24, 40, 51, 61,
12, 12, 14, 19, 26, 58, 60, 55,
14, 13, 16, 24, 40, 57, 69, 56,
14, 17, 22, 29, 51, 87, 80, 62,
18, 22, 37, 56, 68,109,103, 77,
24, 35, 55, 64, 81,104,113, 92,
49, 64, 78, 87,103,121,120,101,
72, 92, 95, 98,112,100,103, 99
色差:
17, 18, 24, 47, 99, 99, 99, 99,
18, 21, 26, 66, 99, 99, 99, 99,
24, 26, 56, 99, 99, 99, 99, 99,
47, 66, 99, 99, 99, 99, 99, 99,
99, 99, 99, 99, 99, 99, 99, 99,
99, 99, 99, 99, 99, 99, 99, 99,
99, 99, 99, 99, 99, 99, 99, 99,
99, 99, 99, 99, 99, 99, 99, 99
というものです。
ただし、大抵のソフトではこれらの推奨値をそのまま使うのではなく、一定の式に当てはめて変換して高画質用~低画質用のさまざまなテーブルを作ります。
よくある式は、
低画質~高画質を-1~1の数字で表したとき、

高画質側では
推奨値×(1-画質)  (ただし0になったら1)

低画質側では
255 - {(255-推奨値)×(1+画質)}

となります。これを-1~1でなく0~100のパーセンテージで表すことが一般的です。
つまり、画質設定を50%にすると上のテーブルが出るわけです。
GIMPとPixiaで50%を試してみましたところ、見事にこれが出ました。またMSペイントの出力は全ての値が丁度これの1/2(切上げ)でした。つまり上の式でいくと75%に当たります。

ただ、このテーブルは縦と横で対称でないのがどうも私は気に食わないので以前jpegエンコーダを作ったときは何かのソフトで縦横対称なテーブルを使っているものがあったのでそれを拝借しました。
で今そのソフトを探したのですが見つかりませんでした。「AzPainter」だったかな…。

自由に決めてかまいませんが、jpeg形式を作ったjpeg(団体)の出している仕様書に例が載っています。これから派生したテーブルを使うソフトがほとんどです。
輝度:
16, 11, 10, 16, 24, 40, 51, 61,
12, 12, 14, 19, 26, 58, 60, 55,
14, 13, 16, 24, 40, 57, 69, 56,
14, 17, 22, 29, 51, 87, 80, 62,
18, 22, 37, 56, 68,109,103, 77,
24, 35, 55, 64, 81,104,113, 92,
49, 64, 78, 87,103,121,120,101,
72, 92, 95, 98,112,100,103, 99
色差:
17, 18, 24, 47, 99, 99, 99, 99,
18, 21, 26, 66, 99...続きを読む

Qファイルやディレクトリの存在確認を行う方法

ファイルをオープンするのはfopenでOKですが、ファイルやディレクトリの存在確認を行う方法が知りたいです。

何か組み合わせて作るものなのでしょうか?
perlとか便利な演算子があるのですが、C/C++って器用ではないですね。
これは処理系?依存の内容ですか?

私の環境は VC6, VC2005 Windows2000です。

Aベストアンサー

int access(const char* path, int mode);
int stat(const char* path, struct stat* sb);

かな?
MSDN を引くと _access_s() を使えとか書いてあるけど。

QC言語の二分法のプログラムについて

二分法によりルート2の近似値を求めるプログラム、ってどうやって作ったらいいんですか?
ちなみに初期値は2で、収束条件は10^-5です。
収束までの回数も求めなきゃいけません(ニュートン法と比較するため。ちなみにニュートン法はできました。)

似たような質問を見つけたのですが、どれも、難しいプログラムばかりで解読ができません。
関数とかif else文とかwhile文とかfor文とか、そういう簡単なのしか習ってないので、それで作れる範囲で教えてくださる方、
いらっしゃいましたら、よろしくお願いします。

Aベストアンサー

これでどうでしょう。
if文判定、及びwhile文判定を修正しました。

#include <stdio.h>
#include <math.h>
#define f(x)(x*x-2.0)
int main(void)
{
int i=0;
double m,x1=2.0,x2=1.0,eps=1.0e-5;
do{
++i;
m=(x1+x2)/2;
if (f(m)>0)
{
x1 = m;
}
else
{
x2 = m;
}
}
while (fabs(x1-x2)>eps);
printf("%f,%d\n",m,i);
return 0;
}


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング

おすすめ情報