圧縮

[みけCAT]

ファイルを圧縮するプログラムを作ろうと思いました。
とりあえず圧縮だけ書いて実行してみたのですが、かえってファイルサイズが大きくなりました。
5KBのassyuku.cを変換すると6KB、22KBのassyuku.exeを変換すると627KBになりました。
バイナリエディタで見ると、多量のFFが出力されています。
解凍するプログラムはまだ作っていませんので、検証はしていません。
どこか間違っていたら教えてください。
お願いします。

[softya（ソフト屋)]

ざっと見ましたが、dohenkan（）関数内の処理がかなり怪しいです。
メモリリークも起こしてますし、ポインタと実体の転送を混同している箇所も見受けられます。
手始めにprintfをいれてsublist[]の内容が合っているか確認してみると良いと思います。

ちなみに、この処理にcalloc/freeは不要だと思うのとポインタで混乱しているみたいなので、ポインタを使わず組んでみてはどうでしょうか？

[みけCAT]

一応元のデータより小さいデータ（元がzipだと大きくなりましたが）
を出力し、解凍すると同じデータが出てくるものができました。
しかし、どこがメモリリークだか分りませんし、ポインタを使わない方法も判りません。
（C言語で作りたいのでnewは無しでお願いします。）
教えていただければ幸いです。
お願いします。

[softya（ソフト屋)]

まず試しにコードを書き換えてソート前後を見てみましょう。

コード:

	/*多い要素から順につなげる*/
	printf( "-------------- ソート前 \n" );
	for(i=0;i<257;i++) {
		printf( "sublist[%d]=%p ", i, sublist[i] );
		printf( "sublist[%d]->data=%d ", i, sublist[i]->data );
		printf( "sublist[%d]->kosuu=%d \n", i, sublist[i]->kosuu );
	}
	for(i=256;i>0;i--) {
		temp=mycalloc(sizeof(bunpunode));
		temp->data=-2;
		temp->kosuu=sublist[i-1]->kosuu+sublist[i]->kosuu;
		temp->next[0]=sublist[i-1];
		temp->next[1]=sublist[i];
		sublist[i-1]->prev=temp;
		sublist[i]->prev=temp;
		for(j=i-2;j>=0;j--) {
			if(sublist[j]->kosuu>=temp->kosuu)break;
			sublist[j+1]=sublist[j];
		}
		sublist[j+1]=temp;
	}
	printf( "-------------- ソート後 \n" );
	for(i=0;i<257;i++) {
		printf( "sublist[%d]=%p ", i, sublist[i] );
		printf( "sublist[%d]->data=%d ", i, sublist[i]->data );
		printf( "sublist[%d]->kosuu=%d \n", i, sublist[i]->kosuu );
	}

この様な処理をあちこちに挟んでデバックする技をprintfデバッグといいます。

どうですか、望んだ形にsublistは出来上がっていますか？
特にソート前のアドレス（確保したメモリ）が解放した覚えもないのに無くなっていませんか？
実は、この前の降順ソートも怪しいと思うのですがどうでしょうか？

このままcallocを使わないものに書き換えると確実に致命的なバグになるのでcallocの件は後回しにさせてください。

[みけCAT]

ログを吐いてみました。
しかし、大変申し訳ありませんが、自分には読めません。
解析方法を教えていただければありがたいです。
ログを吐くようにしたassyuku.cとログを添付します。

[みけCAT]

修正しました。
変換表も出力するようにしてみました。

[softya（ソフト屋)]

私もアルゴリズムを説明してもらっていないのでコメントを当てにして答えてますが、ソート時に添字0のdata=-1の要素が後ろの方にソートされるのは意図通りなのでしょうか？
それも一番後ろではなく、最後のほう（データ次第）の位置に移動します。

それと
/*多い要素から順につなげる*/
に一番問題ありますので、こちらの後にもprintfしてみてください。
ここでメモリリークを起こしています。
ポインタ値が/*多い要素から順につなげる*/前にあったポインタ値が処理後でなくなっています。これは何故なのか確認してみてください。

[みけCAT]

ソート時に添字0のdata=-1の要素が後ろの方にソートされるのは意図通りなのでしょうか？
それも一番後ろではなく、最後のほう（データ次第）の位置に移動します。

-1は終了コードであり、終了コードは最後に一つだけ付けるので、
他の一つしかないデータと同じ位置にあれば仕様です。

/*多い要素から順につなげる*/
に一番問題ありますので、こちらの後にもprintfしてみてください。

今のプログラムで出力は付けてあるはずです。

ここでメモリリークを起こしています。
ポインタ値が/*多い要素から順につなげる*/前にあったポインタ値が処理後でなくなっています。これは何故なのか確認してみてください。

Perlで検証してみましたが、消えたアドレスはなさそうです。

コード:

#!/usr/local/bin/perl

open(IN,"< log.txt") or die("input file open error");

$a=<IN>;
open(OUT,"> row1.txt");
@row1=();
while(<IN>) {
	if($_ =~ /^ソ\/){last;}
	$_ =~ s/^sublist\[[0-9]+\]=([0-9a-zA-Z]+)/push(@row1,$1);print OUT $1 . "\n";/e;
}
close(OUT);
open(OUT,"> row2.txt");
@row2=();
while(<IN>) {
	if($_ =~ /^変換ツリ/){last;}
	$_ =~ s/^sublist\[[0-9]+\]=([0-9a-zA-Z]+)/push(@row2,$1);print OUT $1 . "\n";/e;
}
close(OUT);
open(OUT,"> row3.txt");
@row3=();
while(<IN>) {
	if($_ =~ /^変換/){last;}
	$_ =~ s/^ *address=([0-9a-zA-Z]+)/push(@row3,$1);print OUT $1 . "\n";/e;
}
close(OUT);
close(IN);

open(OUT,"> del2.txt");
foreach $data ( @row1) {
	if(grep(/$data/,@row2)==0) {
		print OUT $data . "\n";
	}
}
close(OUT);
open(OUT,"> new2.txt");
foreach $data ( @row2) {
	if(grep(/$data/,@row1)==0) {
		print OUT $data . "\n";
	}
}
close(OUT);
open(OUT,"> del3.txt");
foreach $data ( @row2) {
	if(grep(/$data/,@row3)==0) {
		print OUT $data . "\n";
	}
}
close(OUT);
open(OUT,"> new3.txt");
foreach $data ( @row3) {
	if(grep(/$data/,@row2)==0) {
		print OUT $data . "\n";
	}
}
close(OUT);

[softya（ソフト屋)]

失礼しました。こう言うデータ構造なのですね。
ツリー構造や圧縮アルゴリズム（圧縮後のデータ構造）のコメントが全く無いので解読に時間が掛り過ぎるので説明してもらって良いでしょうか？
今のところ分かったのは、/*多い要素から順につなげる*/でやっている処理は変換ツリーを作成することでtempは実際にtempではなく実体として必要なnodeであることとnext[0]とnext[1]が実際はleftとrightと言うツリー構造であることです。prevもupとかの表現にしてもらうと分かりやすかったです。ずっと特殊なリスト構造だと勘違いしてました。

[Poco]

これはハフマン符号化ですか？

[みけCAT]

ツリー構造や圧縮アルゴリズム（圧縮後のデータ構造）のコメントが全く無いので解読に時間が掛り過ぎるので説明してもらって良いでしょうか？

とりあえず簡単な解説pdfを作ってみました。
dohenkan関数以外は超適当なので、わかりにくかったら言ってください。
あと、/*多い要素から順につなげる*/というのは/*少ない要素から順につなげる*/の間違いでした。
すみません。

これはハフマン符号化ですか？

なんかの本に載っていたアルゴリズムをうろ覚えで実装したものです。
アルゴリズムの名前は忘れました。

[softya（ソフト屋)]

説明を読む限りはハフマン符号だと思いますが、まだ何処に問題あるかは見つけてません。
と言うかハフマン符号は扱うの始めてだったり^^;
変換表までは、うまく出来ている気もするのですがここで間違えていると致命的なので机上チェックをしてみてください。
3つぐらいの要素なら机上で簡単にチェックできると思います。

こちらでも調べてみますのでお願いします。

[みけCAT]

そもそも本当に問題があると思うのですか？

[softya（ソフト屋)]

みけCATさんが問題がないと思われるのなら、こちらも調べるのをやめます。
と言う事でよろしいですね？

[みけCAT]

それでいいです。
ということで、解決にさせていただきます。
ありがとうございました。

[softya（ソフト屋)]

今頃ですがバイナリエディタで眺めていたとき圧縮後のデータの法則性に、どうも違和感があったので改めてさっき見てみたら原因が分かりました。
ビットが逆順に並んでいますが意図通りですか？
c|=buf[j]<<j;
ではなく
c|=buf[j]<<(7-j);
じゃないでしょうか？

もし意図通りで狙ってビット関係を混乱させているなら申し訳ない。
私としては喉のつっかえが取れた感じですっきりしました。