以下の問題に回答できる方,いらっしゃいましたらソースファイルと実行結果を送ってください。
 ファァイル(記号列)を読み込んで,ハフマン符号によりファイルを圧縮するプログラム(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コード変換(漢字)のサンプルプログラム

始めまして!
困っています、御力添えをお願いします。
UNIX(SouOS5.8)でのコード変換(SJIS→EUC、EUC→SJIS)のコーディング(サンプルソース:C言語)をどなたか教えて頂けないでしょうか?
お願いします。

Aベストアンサー

下記URL参照。

参考URL:http://www-cms.phys.s.u-tokyo.ac.jp/~naoki/CIPINTRO/CCGI/kanjicod.html

Qハフマン符号化プログラミング

 学校の課題でVisualStudioで実現できるハフマン符号化プログラム(3次拡大)を作成せよ。という課題が出題されました。
 しかし私は今まで入門程度のプログラミングしかやったことがなく、。指定されたファイルの文字数を調べる程度の事しかできない程度のプログラミングの知識なのでさっぱりです。

 指定されたtxtファイルを読み込んで、文字数を数えて、文字の種類を調べて、各文字の発生確率を調べて、各文字を3次拡大行列にし、ツリー構造のアルゴリズムを作成し、各値を2進数に変換して、2進数に変換したものをtxtファイルにして保存するということは何となくわかるのですが、それを実現する知識がありません。

 プログラミングの知識をお持ちの方のご協力をお願いいたします。

Aベストアンサー

「ハフマン符号化プログラム(3次拡大)を作成せよ。」

これだと、問題に不備があるとおもう。
入力情報源の符号はビット?バイト?その他?

一文字だとすると、文字コードによっては長さが変動するから、固定長の文字コードじゃないと無理だと思う。

例えば、
扱う文字が限定されているとか、
ファイルで使う文字コードが決まってるとか
なにか他に限定する条件が必要。


この課題を素直に解釈すると、
ファイルの bit ストリームを、3bit ずつ区切るか、
ファイルの byte ストリームを、3byte ずつ区切るか
して「一つの符号」とする。

1) 出現回数をカウントして
2) 二分木を構築する。
3) 構築した二分木から bit 列 → 「一つの符号」の対応テーブルをファイルに出力。
4) 作成した二分木をつかって、入力の「一つの符号」を順番に bit 列に変換しながら、ファイルに出力して、入力の「一つの符号」がなくなるまで繰り返す。

おしまい。


あと、必要な知識は、

二分木
http://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9C%A8

連結リストは、二分木の前提知識
http://ja.wikipedia.org/wiki/%E9%80%A3%E7%B5%90%E3%83%AA%E3%82%B9%E3%83%88

ハフマン符号化の為の、
- 「一つの符号」
- 出現回数
- 左右の子の接点の合計
をノードの属性として含めて、構造体かクラスにする。
クラスにするなら、二分木の操作をクラス関数に含める。

構造体
http://ja.wikipedia.org/wiki/%E6%A7%8B%E9%80%A0%E4%BD%93

クラス
http://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%A9%E3%82%B9_%28%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%29

ノードのソート
http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88

「ハフマン符号化プログラム(3次拡大)を作成せよ。」

これだと、問題に不備があるとおもう。
入力情報源の符号はビット?バイト?その他?

一文字だとすると、文字コードによっては長さが変動するから、固定長の文字コードじゃないと無理だと思う。

例えば、
扱う文字が限定されているとか、
ファイルで使う文字コードが決まってるとか
なにか他に限定する条件が必要。


この課題を素直に解釈すると、
ファイルの bit ストリームを、3bit ずつ区切るか、
ファイルの byte ストリームを、3byte ずつ区切るか...続きを読む

Qブログ等で公開されているサンプルコードの著作権について

個人の方などが、ブログ等で公開されているサンプルコードについてですが、

あるプログラムの解説サイトで見つけた、サンプルコードと、
同じコードで解説しているサイトを2つ発見したので、こういうのって、法律的に、どういう扱いなのだろうかという疑問です。

Aベストアンサー

プログラミング言語や規約つまりプロトコルは対象外だけど、ソースは保護対象なんだってば。
当たり前だよ。プログラミング言語使って生み出された創作物なんだもん。
この辺、IT系資格の参考書でもたまに間違いを見かけるからわかりにくいんだろうね。

私は法学部卒の現役エンジニアです。
ソースコードが著作物なのは断言します。

Q大量のファイルを読み込み、その各ファイルの中の最大値と最小値の出力の仕方

各ファイルの名前はinput_0.txtからinput_4.txtまであるとします。これらのファイルには(1)ナンバー(2)身長(3)体重がスペースをはさんで入力されています。
例:input_0.txt
1 172.3 65.3
2 164.3 54.6
3 176.4 55.4
4 170.2 70.4
5 167.4 63.8

この例では3番目の176.4が最大値として認識し2番目の164.3を最小値として出力させたいのですが、うまくいきません。プログラムを以下のように作りました。どこがいけないでしょうか?ご教授の方よろしくお願いします。

FILE *fpr,*fpw;
int no[N],i,j,max_j,min_j;
char fname[30];
float height[N],weight[N],max=0,min=0;

for(i=0;i<4;i++)//file題名用ループ
{
sprintf(fname,"input_%d.txt",i);

if((fpr=fopen(fname,"r"))==NULL)
{puts("file open error!!");return 0;}

for(j=0;j<5;j++){//ファイル内容用ループ
while((fscanf(fpr,"%d%f%f",&no[j],&height[j],&weight[j]))!=EOF)


if(height[j]>max){
max=height[j];max_j=j;
printf("number=%d__height=%.2f__weight=%.2f\n",no[max_j],max,weight[max_j]);
}
if(height[j]<min){
min=height[j];min_j=j;}
printf("number=%d__height=%.2f__weight=%.2f\n",no[min_j],min,weight[min_j]);

fclose(fpr);

各ファイルの名前はinput_0.txtからinput_4.txtまであるとします。これらのファイルには(1)ナンバー(2)身長(3)体重がスペースをはさんで入力されています。
例:input_0.txt
1 172.3 65.3
2 164.3 54.6
3 176.4 55.4
4 170.2 70.4
5 167.4 63.8

この例では3番目の176.4が最大値として認識し2番目の164.3を最小値として出力させたいのですが、うまくいきません。プログラムを以下のように作りました。どこがいけないでしょうか?ご教授の方よろしくお願いします。

FILE *fpr,*fpw;
int no[N],i,j,ma...続きを読む

Aベストアンサー

うまくいかないとは、具体的にどういう結果になってしまうのかを
書いてくだされば原因を特定しやすいのですが……。

ざっと見て思ったのは以下のとおり。これで直ればよいのですが……。
○2つめのファイルを読み込むとき、たとえば一つ目のファイルの
 最大値が max に代入されたままです。
 ループの最初でmaxやその他の変数に初期値を代入しましょう。
○if(height[j]>max) と if(height[j]<min) の閉じ括弧の位置が違う。
○最大値や最小値を発見するたびに表示してしまっているので
 ファイル内容用ループのあとにprintfを移動する。
○fscanf(fpr,"%d %f %f",&no[j],&height[j],&weight[j])
 と、第二引数に半角スペースを空ける。

Q数学演算のサンプルコード集のあるサイトを探しています(VB6)

VB6で数学演算のソースコードのサンプル集を探しています。

例えば今回は3次元のベクトルをX,Y,Z軸周りに任意の角度だけ回転する行列をプログラムしたいので、アフィン変換のサンプルなんかないかと探しています。いいサイトがあれば教えていただけませんでしょうか。

よろしくお願いします。

Aベストアンサー

まったくの素人なので、
参考になるかはわかりませんが、
検索したらこんなのがありました。

参考URL:http://files.codes-sources.com/fichier.aspx?id=37873&f=mdlMath.bas

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...続きを読む

QHead First PHPサンプルコード文字化け

よろしくです。
下記のphpの本を参考にプログラムを勉強しているのですが、
サンプルコード(完成品)の日本語部分(DBがソースの日本語部分全て)がすべて文字化けしてしまいます。
この本は文字化け対策を強みにした本なのですが、実際のサンプルコードがこんな状態なので非常に困っています。
例えば、表示サイトページ内に3時間というデータが表示される予定だとすると、3??(ハテナマーク)のように表示されます。
ちなみに文字化け後、ブラウザ、DB、phpの文字コード設定はutf8統一であることは確認しました。apacheの文字コードはわかりません。
テスト環境は、自宅のローカルサーバーと、某レンタルサーバーの2つでどちらでも文字化けです。

この本を試した方、もしくはちゃっちゃっと下記サイトからサンプルをとって試していただける方、どうかレスをお願いします。
著書内ではこれでどうだというくらい日本語対策をうたっているのに、全サンプルがNGとは、あまりに不思議な現象で、とても困っています。
どうかよろしくお願いします。

『Head First PHP & MySQL――頭とからだで覚えるWebアプリケーション開発の基本』
Lynn Beighley, Michael Morrison 著、佐藤 嘉一 訳
2010年03月 発行
672ページ
ISBN978-4-87311-444-6

http://www.oreilly.co.jp/books/9784873114446/
関連ファイル ー サンプルコード
に本の中で使われている全てのサンプルが入っています。

よろしくです。
下記のphpの本を参考にプログラムを勉強しているのですが、
サンプルコード(完成品)の日本語部分(DBがソースの日本語部分全て)がすべて文字化けしてしまいます。
この本は文字化け対策を強みにした本なのですが、実際のサンプルコードがこんな状態なので非常に困っています。
例えば、表示サイトページ内に3時間というデータが表示される予定だとすると、3??(ハテナマーク)のように表示されます。
ちなみに文字化け後、ブラウザ、DB、phpの文字コード設定はutf8統一であることは確認しま...続きを読む

Aベストアンサー

表示させるだけじゃねーじゃん。

確かにデフォルトだと文字化けした。
でも文字化け回避できた。

--------------------------------
// Connect to the database
$dbc = mysqli_connect(DB_HOST, DB_USER, DB_PASSWORD, DB_NAME);
mysqli_set_charset($dbc, "utf8");// ←追加

Q1,1,2,3,5,8,13の合計

初心者ですみませんが、1,1,2,3,5,8,13の合計を出すプログラミングがどうしてもわかりません。どなたかご教示頂けましたら助かります。
宜しくお願いいたします。

Aベストアンサー

#include <stdio.h>

int main(void)
{
   printf("%d\n", 1+1+2+3+5+8+13);
}

Qホームページや書籍などのサンプルコードは動かないものばかりでしょうか?

ホームページや書籍などのサンプルコードを試して動かしてみても、動かないサンプルコードばかりだと思いますが、同じことを考えている人はいらっしゃいますか?

何か…ホームページや書籍などのサンプルコードが動かないということは、そのサンプルコード自体の問題というよりは作者の問題と思いますが…。なぜなら、1件のホームページや1冊の書籍で、このサンプルコードが動かなければ別のサンプルコードが動かない可能性が高いです。逆にこのサンプルコードがちゃんと動くということは、他のサンプルコードも動く可能性が高い。経験談で感じた限りです。

要するには作者の解説力次第になりますと思いますが、どうでしょうか?どんな簡単な言語でも解説力がなければ取っ付きにくく、どんな難しい言語でも解説力があれば取っ付きやすいものでしょうか?

何か解決法とかありますでしょうか?ご回答をお願いします。

Aベストアンサー

ちょっと抽象的かも、です。

>ホームページや書籍などのサンプルコードが動かないということは、そのサンプルコード自体の問題というよりは作者の問題と思いますが…。

それは「あり得ます」。
ただし、その前に自分の環境をチェックした方がいいでしょう。
ヴァージョン違い、なんてのは他のお方が仰ってる通りなんですが、他にも原因は色々と考えられると思います。
基本的に、一概にプログラミング言語と言っても、

1.提供元が一つしか無いもの
2.公式規格が制定されているもの

の2種類があります。
例えばC#なんかはMicrosoftしか提供元が無い言語がありますし、最近流行りのスクリプト言語系(Python、Ruby等)も提供元が一つしかありません。こう言う場合はヴァージョン違いだと動かない可能性がありますね。他のお方が仰っているように、使用してる言語のヴァージョンをチェックした方がいいでしょう。
じゃあ、2番なら安心か、と言うとそう言う事もないのです。
例えばC言語なんかは公式規格があったりしますが、かと言って、通常は「公式規格に則って」作っただけの言語なんてのも無くって、大体その提供側独特の「拡張ライブラリ」が入ってたりするんです。
つまり、A社が提供した「拡張ライブラリ」を利用したプログラムを「B社製の」一応公式規格に則った言語で書いても動かない場合があるんです。「拡張ライブラリ」自体は独特なんで、B社が同じモノを付けている、とは限りません。そう言う場合があるんですね。
まあ、そう言う事が(しばしば)生じるんで、何らかのサイト/参考書を利用してプログラムの勉強をする場合は、なるたけその筆者と「同じ環境を」備えるようにした方がいいです。作成者自身も「全部の環境を」試せるワケではない、と言う事を最初に納得しておくべきだと思います。

>要するには作者の解説力次第になりますと思いますが、どうでしょうか?
>どんな簡単な言語でも解説力がなければ取っ付きにくく、どんな難しい言語でも解説力があれば取っ付きやすいものでしょうか?

一理あるとは思います。
が、同時に「言語の性質」ってのはありますね。解説力があってもそれを埋める事は難しいでしょう。

これ言って良いのか悪いのか分かりませんが、原則、書籍を購入して勉強する場合は「定番で」「評価の高い」書籍を選んだ方が、万能では無いですけど「失敗する確率は低い」とは思います。やっぱ校正とかそのテのノウハウを蓄積してる「実績ある」出版社の本を選んだ方がいいですね。
敢えて言いますが、最近「ネットで発表」→「書籍化」と言うのが流行りになっていますが、ホームページを作れても書籍が作れるのか、と言うとこれはまた別の話なんですね。
新興のネット関係での出版社なんかがプログラミング言語の本をサイトの作者の持ち込みで「安く」出版してるケースが見られますが、単なるブログ系の本だったらいざ知らず、このテの技術系の本の場合、「校正を全く行わない」「誤字脱字が多い」「索引でデタラメで役に立たない」状態で出版していて、「安い」だけで買うと、結局役に立たないんで痛い目見ます(敢えて会社名は伏せておきますがそう言う実例があるのです)。
ですから、サイトで勉強するなら構いませんが、書籍を買って勉強する場合は、少々値段が高くでも「定番商品」の方が結果安上がりです。書評に関しては大体のトコamazonで見れますし(もっともamazonは否定的な意見は載せたがらない方針ですが)、何種類か評判が良い書籍をメモっておいて本屋で現物を見た後購入した方が良いでしょう。または、評判書籍を取りあえず図書館で借りて読んでみる、とか。
出版社もすべて同じなワケではなく、「一回刷っちゃったらあとは絶版でイイや」程度で考えて粗製本作ってるケースも確かに存在するんで、そこまで行くと、確かに仰る通りかもな、とは思います。

ちょっと抽象的かも、です。

>ホームページや書籍などのサンプルコードが動かないということは、そのサンプルコード自体の問題というよりは作者の問題と思いますが…。

それは「あり得ます」。
ただし、その前に自分の環境をチェックした方がいいでしょう。
ヴァージョン違い、なんてのは他のお方が仰ってる通りなんですが、他にも原因は色々と考えられると思います。
基本的に、一概にプログラミング言語と言っても、

1.提供元が一つしか無いもの
2.公式規格が制定されているもの

の2種類があり...続きを読む

Qファイルから Carray に読み込みたい

1
2
3
4
5
xxxxxx


のように、数字を記録したファイル(語尾はxxxxxxの目印あり)を
Carray<int, int> に読み込ませるには、どういう関数を、どう使えばいいのでしょうか。

ちなみに MFC のダイアログベースで作成しています。

初心者で、マイクロソフトのヘルプを見てもサッパリわからず、
困っています、助けてください。

Aベストアンサー

要素を追加するにはAddを使います。
CArray< int , int > test;
test.Add(1);
test.Add(2);
test.Add(3);
test.Add(4);
test.Add(5);

逆に取り出すにはGetAtを使います。
for( int i = 0 ; i < test.GetSize() ; i++ ){
int tmp = test.GetAt(i);
}

あとCArrayを使うにはAfxtempl.hをincludeする必要がありますね。


人気Q&Aランキング

おすすめ情報