圧縮

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
アバター
みけCAT
記事: 6247
登録日時: 9年前
住所: 千葉県
連絡を取る:

圧縮

#1

投稿記事 by みけCAT » 9年前

ファイルを圧縮するプログラムを作ろうと思いました。
とりあえず圧縮だけ書いて実行してみたのですが、かえってファイルサイズが大きくなりました。
5KBのassyuku.cを変換すると6KB、22KBのassyuku.exeを変換すると627KBになりました。
バイナリエディタで見ると、多量のFFが出力されています。
解凍するプログラムはまだ作っていませんので、検証はしていません。
どこか間違っていたら教えてください。
お願いします。
添付ファイル
assyuku.zip
問題のプログラムです。
(12.38 KiB) ダウンロード数: 36 回
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
softya(ソフト屋)
副管理人
記事: 11677
登録日時: 9年前
住所: 東海地方
連絡を取る:

Re: 圧縮

#2

投稿記事 by softya(ソフト屋) » 9年前

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

ちなみに、この処理にcalloc/freeは不要だと思うのとポインタで混乱しているみたいなので、ポインタを使わず組んでみてはどうでしょうか?
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。

アバター
みけCAT
記事: 6247
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: 圧縮

#3

投稿記事 by みけCAT » 9年前

一応元のデータより小さいデータ(元がzipだと大きくなりましたが)
を出力し、解凍すると同じデータが出てくるものができました。
しかし、どこがメモリリークだか分りませんし、ポインタを使わない方法も判りません。
(C言語で作りたいのでnewは無しでお願いします。)
教えていただければ幸いです。
お願いします。
添付ファイル
assyuku2.zip
圧縮プログラムです。
(13.77 KiB) ダウンロード数: 21 回
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
softya(ソフト屋)
副管理人
記事: 11677
登録日時: 9年前
住所: 東海地方
連絡を取る:

Re: 圧縮

#4

投稿記事 by softya(ソフト屋) » 9年前

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

コード:

	/*多い要素から順につなげる*/
	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の件は後回しにさせてください。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。

アバター
みけCAT
記事: 6247
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: 圧縮

#5

投稿記事 by みけCAT » 9年前

ログを吐いてみました。
しかし、大変申し訳ありませんが、自分には読めません。
解析方法を教えていただければありがたいです。
ログを吐くようにしたassyuku.cとログを添付します。
添付ファイル
log.txt
ログファイルです。
(117.6 KiB) ダウンロード数: 26 回
assyuku.c
プログラムです。
(8.39 KiB) ダウンロード数: 16 回
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6247
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: 圧縮

#6

投稿記事 by みけCAT » 9年前

修正しました。
変換表も出力するようにしてみました。
添付ファイル
log.txt
ログです。
(122.37 KiB) ダウンロード数: 23 回
assyuku.c
プログラムです。
(8.72 KiB) ダウンロード数: 22 回
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
softya(ソフト屋)
副管理人
記事: 11677
登録日時: 9年前
住所: 東海地方
連絡を取る:

Re: 圧縮

#7

投稿記事 by softya(ソフト屋) » 9年前

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

それと
/*多い要素から順につなげる*/
に一番問題ありますので、こちらの後にもprintfしてみてください。
ここでメモリリークを起こしています。
ポインタ値が/*多い要素から順につなげる*/前にあったポインタ値が処理後でなくなっています。これは何故なのか確認してみてください。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。

アバター
みけCAT
記事: 6247
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: 圧縮

#8

投稿記事 by みけCAT » 9年前

softya(ソフト屋) さんが書きました:ソート時に添字0のdata=-1の要素が後ろの方にソートされるのは意図通りなのでしょうか?
それも一番後ろではなく、最後のほう(データ次第)の位置に移動します。
-1は終了コードであり、終了コードは最後に一つだけ付けるので、
他の一つしかないデータと同じ位置にあれば仕様です。
softya(ソフト屋) さんが書きました:/*多い要素から順につなげる*/
に一番問題ありますので、こちらの後にもprintfしてみてください。
今のプログラムで出力は付けてあるはずです。
softya(ソフト屋) さんが書きました:ここでメモリリークを起こしています。
ポインタ値が/*多い要素から順につなげる*/前にあったポインタ値が処理後でなくなっています。これは何故なのか確認してみてください。
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);
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
softya(ソフト屋)
副管理人
記事: 11677
登録日時: 9年前
住所: 東海地方
連絡を取る:

Re: 圧縮

#9

投稿記事 by softya(ソフト屋) » 9年前

失礼しました。こう言うデータ構造なのですね。
ツリー構造や圧縮アルゴリズム(圧縮後のデータ構造)のコメントが全く無いので解読に時間が掛り過ぎるので説明してもらって良いでしょうか?
今のところ分かったのは、/*多い要素から順につなげる*/でやっている処理は変換ツリーを作成することでtempは実際にtempではなく実体として必要なnodeであることとnext[0]とnext[1]が実際はleftとrightと言うツリー構造であることです。prevもupとかの表現にしてもらうと分かりやすかったです。ずっと特殊なリスト構造だと勘違いしてました。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。

Poco
記事: 161
登録日時: 9年前

Re: 圧縮

#10

投稿記事 by Poco » 9年前

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

アバター
みけCAT
記事: 6247
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: 圧縮

#11

投稿記事 by みけCAT » 9年前

softya(ソフト屋) さんが書きました:ツリー構造や圧縮アルゴリズム(圧縮後のデータ構造)のコメントが全く無いので解読に時間が掛り過ぎるので説明してもらって良いでしょうか?
とりあえず簡単な解説pdfを作ってみました。
dohenkan関数以外は超適当なので、わかりにくかったら言ってください。
あと、/*多い要素から順につなげる*/というのは/*少ない要素から順につなげる*/の間違いでした。
すみません。
ぽこ さんが書きました:これはハフマン符号化ですか?
なんかの本に載っていたアルゴリズムをうろ覚えで実装したものです。
アルゴリズムの名前は忘れました。
添付ファイル
kaisetu.pdf
解説pdfです。
(97.72 KiB) ダウンロード数: 27 回
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
softya(ソフト屋)
副管理人
記事: 11677
登録日時: 9年前
住所: 東海地方
連絡を取る:

Re: 圧縮

#12

投稿記事 by softya(ソフト屋) » 9年前

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

こちらでも調べてみますのでお願いします。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。

アバター
みけCAT
記事: 6247
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: 圧縮

#13

投稿記事 by みけCAT » 9年前

そもそも本当に問題があると思うのですか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
softya(ソフト屋)
副管理人
記事: 11677
登録日時: 9年前
住所: 東海地方
連絡を取る:

Re: 圧縮

#14

投稿記事 by softya(ソフト屋) » 9年前

みけCATさんが問題がないと思われるのなら、こちらも調べるのをやめます。
と言う事でよろしいですね?
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。

アバター
みけCAT
記事: 6247
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: 圧縮

#15

投稿記事 by みけCAT » 9年前

それでいいです。
ということで、解決にさせていただきます。
ありがとうございました。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
softya(ソフト屋)
副管理人
記事: 11677
登録日時: 9年前
住所: 東海地方
連絡を取る:

Re: 圧縮

#16

投稿記事 by softya(ソフト屋) » 9年前

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

もし意図通りで狙ってビット関係を混乱させているなら申し訳ない。
私としては喉のつっかえが取れた感じですっきりしました。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。

閉鎖

“C言語何でも質問掲示板” へ戻る