圧縮
圧縮
ファイルを圧縮するプログラムを作ろうと思いました。
とりあえず圧縮だけ書いて実行してみたのですが、かえってファイルサイズが大きくなりました。
5KBのassyuku.cを変換すると6KB、22KBのassyuku.exeを変換すると627KBになりました。
バイナリエディタで見ると、多量のFFが出力されています。
解凍するプログラムはまだ作っていませんので、検証はしていません。
どこか間違っていたら教えてください。
お願いします。
とりあえず圧縮だけ書いて実行してみたのですが、かえってファイルサイズが大きくなりました。
5KBのassyuku.cを変換すると6KB、22KBのassyuku.exeを変換すると627KBになりました。
バイナリエディタで見ると、多量のFFが出力されています。
解凍するプログラムはまだ作っていませんので、検証はしていません。
どこか間違っていたら教えてください。
お願いします。
- 添付ファイル
-
- assyuku.zip
- 問題のプログラムです。
- (12.38 KiB) ダウンロード数: 116 回
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
- softya(ソフト屋)
- 副管理人
- 記事: 11677
- 登録日時: 13年前
- 住所: 東海地方
- 連絡を取る:
Re: 圧縮
ざっと見ましたが、dohenkan()関数内の処理がかなり怪しいです。
メモリリークも起こしてますし、ポインタと実体の転送を混同している箇所も見受けられます。
手始めにprintfをいれてsublist[]の内容が合っているか確認してみると良いと思います。
ちなみに、この処理にcalloc/freeは不要だと思うのとポインタで混乱しているみたいなので、ポインタを使わず組んでみてはどうでしょうか?
メモリリークも起こしてますし、ポインタと実体の転送を混同している箇所も見受けられます。
手始めにprintfをいれてsublist[]の内容が合っているか確認してみると良いと思います。
ちなみに、この処理にcalloc/freeは不要だと思うのとポインタで混乱しているみたいなので、ポインタを使わず組んでみてはどうでしょうか?
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。
Re: 圧縮
一応元のデータより小さいデータ(元がzipだと大きくなりましたが)
を出力し、解凍すると同じデータが出てくるものができました。
しかし、どこがメモリリークだか分りませんし、ポインタを使わない方法も判りません。
(C言語で作りたいのでnewは無しでお願いします。)
教えていただければ幸いです。
お願いします。
を出力し、解凍すると同じデータが出てくるものができました。
しかし、どこがメモリリークだか分りませんし、ポインタを使わない方法も判りません。
(C言語で作りたいのでnewは無しでお願いします。)
教えていただければ幸いです。
お願いします。
- 添付ファイル
-
- assyuku2.zip
- 圧縮プログラムです。
- (13.77 KiB) ダウンロード数: 104 回
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
- softya(ソフト屋)
- 副管理人
- 記事: 11677
- 登録日時: 13年前
- 住所: 東海地方
- 連絡を取る:
Re: 圧縮
まず試しにコードを書き換えてソート前後を見てみましょう。
この様な処理をあちこちに挟んでデバックする技をprintfデバッグといいます。
どうですか、望んだ形にsublistは出来上がっていますか?
特にソート前のアドレス(確保したメモリ)が解放した覚えもないのに無くなっていませんか?
実は、この前の降順ソートも怪しいと思うのですがどうでしょうか?
このままcallocを使わないものに書き換えると確実に致命的なバグになるのでcallocの件は後回しにさせてください。
/*多い要素から順につなげる*/
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 );
}
どうですか、望んだ形にsublistは出来上がっていますか?
特にソート前のアドレス(確保したメモリ)が解放した覚えもないのに無くなっていませんか?
実は、この前の降順ソートも怪しいと思うのですがどうでしょうか?
このままcallocを使わないものに書き換えると確実に致命的なバグになるのでcallocの件は後回しにさせてください。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。
- softya(ソフト屋)
- 副管理人
- 記事: 11677
- 登録日時: 13年前
- 住所: 東海地方
- 連絡を取る:
Re: 圧縮
私もアルゴリズムを説明してもらっていないのでコメントを当てにして答えてますが、ソート時に添字0のdata=-1の要素が後ろの方にソートされるのは意図通りなのでしょうか?
それも一番後ろではなく、最後のほう(データ次第)の位置に移動します。
それと
/*多い要素から順につなげる*/
に一番問題ありますので、こちらの後にもprintfしてみてください。
ここでメモリリークを起こしています。
ポインタ値が/*多い要素から順につなげる*/前にあったポインタ値が処理後でなくなっています。これは何故なのか確認してみてください。
それも一番後ろではなく、最後のほう(データ次第)の位置に移動します。
それと
/*多い要素から順につなげる*/
に一番問題ありますので、こちらの後にもprintfしてみてください。
ここでメモリリークを起こしています。
ポインタ値が/*多い要素から順につなげる*/前にあったポインタ値が処理後でなくなっています。これは何故なのか確認してみてください。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。
Re: 圧縮
-1は終了コードであり、終了コードは最後に一つだけ付けるので、softya(ソフト屋) さんが書きました:ソート時に添字0のdata=-1の要素が後ろの方にソートされるのは意図通りなのでしょうか?
それも一番後ろではなく、最後のほう(データ次第)の位置に移動します。
他の一つしかないデータと同じ位置にあれば仕様です。
今のプログラムで出力は付けてあるはずです。softya(ソフト屋) さんが書きました:/*多い要素から順につなげる*/
に一番問題ありますので、こちらの後にもprintfしてみてください。
Perlで検証してみましたが、消えたアドレスはなさそうです。softya(ソフト屋) さんが書きました:ここでメモリリークを起こしています。
ポインタ値が/*多い要素から順につなげる*/前にあったポインタ値が処理後でなくなっています。これは何故なのか確認してみてください。
#!/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
- 登録日時: 13年前
- 住所: 東海地方
- 連絡を取る:
Re: 圧縮
失礼しました。こう言うデータ構造なのですね。
ツリー構造や圧縮アルゴリズム(圧縮後のデータ構造)のコメントが全く無いので解読に時間が掛り過ぎるので説明してもらって良いでしょうか?
今のところ分かったのは、/*多い要素から順につなげる*/でやっている処理は変換ツリーを作成することでtempは実際にtempではなく実体として必要なnodeであることとnext[0]とnext[1]が実際はleftとrightと言うツリー構造であることです。prevもupとかの表現にしてもらうと分かりやすかったです。ずっと特殊なリスト構造だと勘違いしてました。
ツリー構造や圧縮アルゴリズム(圧縮後のデータ構造)のコメントが全く無いので解読に時間が掛り過ぎるので説明してもらって良いでしょうか?
今のところ分かったのは、/*多い要素から順につなげる*/でやっている処理は変換ツリーを作成することでtempは実際にtempではなく実体として必要なnodeであることとnext[0]とnext[1]が実際はleftとrightと言うツリー構造であることです。prevもupとかの表現にしてもらうと分かりやすかったです。ずっと特殊なリスト構造だと勘違いしてました。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。
Re: 圧縮
とりあえず簡単な解説pdfを作ってみました。softya(ソフト屋) さんが書きました:ツリー構造や圧縮アルゴリズム(圧縮後のデータ構造)のコメントが全く無いので解読に時間が掛り過ぎるので説明してもらって良いでしょうか?
dohenkan関数以外は超適当なので、わかりにくかったら言ってください。
あと、/*多い要素から順につなげる*/というのは/*少ない要素から順につなげる*/の間違いでした。
すみません。
なんかの本に載っていたアルゴリズムをうろ覚えで実装したものです。ぽこ さんが書きました:これはハフマン符号化ですか?
アルゴリズムの名前は忘れました。
- 添付ファイル
-
- kaisetu.pdf
- 解説pdfです。
- (97.72 KiB) ダウンロード数: 110 回
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
- softya(ソフト屋)
- 副管理人
- 記事: 11677
- 登録日時: 13年前
- 住所: 東海地方
- 連絡を取る:
Re: 圧縮
説明を読む限りはハフマン符号だと思いますが、まだ何処に問題あるかは見つけてません。
と言うかハフマン符号は扱うの始めてだったり^^;
変換表までは、うまく出来ている気もするのですがここで間違えていると致命的なので机上チェックをしてみてください。
3つぐらいの要素なら机上で簡単にチェックできると思います。
こちらでも調べてみますのでお願いします。
と言うかハフマン符号は扱うの始めてだったり^^;
変換表までは、うまく出来ている気もするのですがここで間違えていると致命的なので机上チェックをしてみてください。
3つぐらいの要素なら机上で簡単にチェックできると思います。
こちらでも調べてみますのでお願いします。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。
- softya(ソフト屋)
- 副管理人
- 記事: 11677
- 登録日時: 13年前
- 住所: 東海地方
- 連絡を取る:
Re: 圧縮
みけCATさんが問題がないと思われるのなら、こちらも調べるのをやめます。
と言う事でよろしいですね?
と言う事でよろしいですね?
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。
- softya(ソフト屋)
- 副管理人
- 記事: 11677
- 登録日時: 13年前
- 住所: 東海地方
- 連絡を取る:
Re: 圧縮
今頃ですがバイナリエディタで眺めていたとき圧縮後のデータの法則性に、どうも違和感があったので改めてさっき見てみたら原因が分かりました。
ビットが逆順に並んでいますが意図通りですか?
c|=buf[j]<<j;
ではなく
c|=buf[j]<<(7-j);
じゃないでしょうか?
もし意図通りで狙ってビット関係を混乱させているなら申し訳ない。
私としては喉のつっかえが取れた感じですっきりしました。
ビットが逆順に並んでいますが意図通りですか?
c|=buf[j]<<j;
ではなく
c|=buf[j]<<(7-j);
じゃないでしょうか?
もし意図通りで狙ってビット関係を混乱させているなら申し訳ない。
私としては喉のつっかえが取れた感じですっきりしました。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。