トップページ⇒tech
992コメント329KB

【2ch】圧縮アルゴリズム【オリジナル】

■ このスレッドは過去ログ倉庫に格納されています
0001１NGNG
おい、おまえら圧縮ソフト作ってみませんか？
中途半端に圧縮されて拡張子が.2ch
0478デフォルトの名無しさんNGNG
>>477
BW変換なんてそんなに難しい方じゃないと思う。
suffix-arrayの構築による手法が何種類もあるから、それを使えばいいし。
力任せでも何とかなる。suffix-treeだっていい。

しかし、PPMを実装するためには、せめて8次〜20次の文脈を扱いたいから、
どうしてもsuffix-treeの知識が必要だし、
suffix-treeだけでは素のPPMすら実装は難しい。
0479ナナシサソNGNG
圧縮のアルゴリズムって基本的に偏りを利用してると思うんだが、
偏りがあまりないデータだと圧縮率が悪くなるよな。
意図的に偏りを作り出すことって出来ますか？
もちろん可逆でbit数の増加が無視できる程度で。
0480デフォルトの名無しさんNGNG
>>479
ブロックソートやMTFは考えとしてはそれに近い。
というより、文脈が。
もっといえば、情報源を高度に推定していくことに近い。
0481デフォルトの名無しさんNGNG
>>479 モデル化しる
0482ナナシサソNGNG
>>480
情報源を高度に推定って具体的にどうやればいいんでしょうか？
回帰分析みたいな感じですか？
0483デフォルトの名無しさんNGNG
>>482
MDLとかAIC規準ではなかろうか
0484デフォルトの名無しさんNGNG
>>482 データマイニングしる
0485デフォルトの名無しさんNGNG
最近だと、PPMTなんてものもあるらしい。
でもユニバーサルではないよなぁ？
http://citeseer.nj.nec.com/teahan01combining.html
0486ナナシサソNGNG
>>483
算術符号とか動的ハフマンのようなものですか？
0487デフォルトの名無しさんNGNG
言葉だけ中途半端に知ってる厨房の集まりだなここは。
0488デフォルトの名無しさんNGNG
>>487
こんばんは、厨房その１です。
恥ずかしながら、仰るとおりです。
0489デフォルトの名無しさんNGNG
>>478
suffix-tree と パトリシアトライの区別がつかないんだけど…
0490デフォルトの名無しさんNGNG
>>489
同じです。
派閥(?)によって呼び方が違うだけのようです。
0491デフォルトの名無しさんNGNG
>>490
さんきゅ
0492零細ﾘｰﾏｿ ◆eXL7Vooglk NGNG
やばい、、すごい圧縮アルゴリズム開発しちまった・・・。
今HDDにあるファイルで手当たり次第テストしてるが、MAXでも元サイズの12％にしかならない。
（しかもlzhやzip,jpgなどのファイルでも！）
ちょっと怖くなってきた。。
（当然可逆圧縮。）

詳しくはいえないので簡単に言うと複素数平面を使用した圧縮。（＋Zオーダー）
辞書とかは持たずにほぼ数式のみで成り立ってる。

こんなんになるとは夢にも思わんかった・・。
0493デフォルトの名無しさんNGNG
祭の予感？
0494デフォルトの名無しさんNGNG
>>492
そのネタは1年ほど前に見たことがあるような…
0495デフォルトの名無しさんNGNG
>>492
ソースあげれ.もしくはバイナリ.
0496零細ﾘｰﾏｿ ◆eXL7Vooglk NGNG
今は特許考えてるんで、ソース・バイナリともにあげるのはちょっと無理。
（バイナリ解析されると怖いんで）


改善点はスピード。
これが今のところかなり遅い。（同種系の３〜５倍くらい遅い）
0497デフォルトの名無しさんNGNG
じゃあ圧縮データサンプル出せ
特許つったって公開されるんだから
ソース出したって変わらんと思うがな。
0498デフォルトの名無しさんNGNG
>>492
中途半端なネタは最悪。

お前の頭で理解できるようなアルゴリズムか、
このスレの誰も理解できないような複雑なアルゴリズムを出せ。
0499デフォルトの名無しさんNGNG
>>498

複雑なアルゴリズムは圧縮にはむかないとおもわれ。
0500デフォルトの名無しさんNGNG
>>492

このサイトでもう少し圧縮について基本的なことを勉強したほうがいいですよ。
ttp://www.ingnet.or.jp/~kojif/mu/comp/
0501デフォルトの名無しさんNGNG
偏りがあまりないデータ ＝ 疑似乱数
な罠
0502 ◆SIA81xrZRg NGNG
age
0503デフォルトの名無しさんNGNG
>>492

ﾀﾜﾗ
0504デフォルトの名無しさんNGNG
>>497
ソース公開すると(下手したらバイナリ公開も)特許は取れなくなるかと。
0505デフォルトの名無しさんNGNG
とりあえず、特許申請するまえに
伊藤家の食卓にハガキだしとけ
0506デフォルトの名無しさんNGNG
>>504
ですね。
学会発表なら特許取得もできるので、すぐさま
情報処理学会、電子情報通信学会、情報理論とその応用学会、IEEE、ACM
のどれかに投稿しる！
レターの形でもいいから。
0507デフォルトの名無しさんNGNG
その方法での圧縮は算術演算以上にならないことがすでに証明されています。
従って、単なるネタ。
0508デフォルトの名無しさんNGNG
×算術演算
○算術圧縮
0509デフォルトの名無しさんNGNG
全てのデータに対して圧縮率が高い圧縮方法は難しいが、
特定のデータに対してなら劇的に圧縮率を上げることができると思う。

たとえば、実行ファイルなら実行ファイルの特徴があり、
その構造を整理することで大幅な圧縮が可能だろう。
つまり、圧縮・解答ソフト自身がMFCやglibなどを持っていて、
それを辞書として使えば、そのライブラリを使って作られた
ファイルは圧縮データにライブラリを含まなくても良くなる。
また、ループや関数呼び出しなどの制御構造を解析すれば、jmp文と
目的アドレスデータを大幅に削除できる。

また、画像や音楽の圧縮もJPEGやMPEGよりフラクタル理論を使った方が
圧縮率が高くなることが知られている。
0510デフォルトの名無しさんNGNG
>>509
データの種別に応じて圧縮法をチューニングするのは、
あるいは専用の圧縮法を使うのは、ツールとしては確かに有効です。
しかし、圧縮理論で最も重視される性質の一つである、
ユニバーサル性を失うことになるため、拒絶する人は多いかもしれません。

>フラクタル理論を使った方が
これは現在のところ、どちらとも言えない状態です。
というのも、たとえば画像データは有限画素値で有限画素数であるため、
フラクタル変換した場合の情報の相似がいまいちだからです。
そのため、計算機上のデータに対してはフラクタル圧縮はそこそこにしかなりません。

しかし、フラクタル発見の効率はよいため、
・画素の類似性を計測するためにフラクタルを使う（文脈として使う）
・線形走査法（ヒルベルト走査など）に組み合わせて、１次元上でのフラクタル圧縮を行う
などの研究が行われているようです。
0511デフォルトの名無しさんNGNG
>>492
寒いですよ。ネタバレバレ。頭が悪いこともバレてます。
もっと圧縮の勉強をしてから書いてください。
0512デフォルトの名無しさんNGNG
492はもともとものすごく冗長なデータしか持ってなかったのかも知れないよ
0513デフォルトの名無しさんNGNG
>>500
おまえばかだな。
0514デフォルトの名無しさんNGNG
>>512
lzhやzipが、さらに圧縮できていることを考えると、
ファイル名が
00000000000000000000000000000000000000000.txt
のようなものだったと思われる。
0515デフォルトの名無しさんNGNG
>>514
新圧縮ｷﾀ━━━━━━（ﾟ∀ﾟ）━━━━━━ !!
0KByteのファイルを作り、ファイル内容をBASE64でエンコードして名前に設定
完璧!!
0516デフォルトの名無しさんNGNG
492に釣られている香具師がいっぱいだな(w
0517デフォルトの名無しさんNGNG
>>515
圧縮カコイイ！
0518デフォルトの名無しさんNGNG
T-RangeCorder
ttp://homepage2.nifty.com/rohizuka/ka/pa_003_a.htm
0519デフォルトの名無しさんNGNG
>>518
ぐはっ、これでひっかかったの4回目です。宇都田。
0520デフォルトの名無しさんNGNG
>>518
一生、呪ってやる。
0521デフォルトの名無しさんNGNG
凄まじい圧縮といえばテキストでしょ。
１つの文字を１，２バイトまで圧縮できるんだから。
究極のモデル化だね。
解凍するために必要なデータは膨大だけどね（フォントデータ）。
但し、ない文字は使えない、または外字を入れると
サイズが膨大になるという欠点も持っている。

さらに圧縮かけると最強。
実はテキストって凄いのですよ。
0522デフォルトの名無しさんNGNG
電波ｷﾀ─wwﾍ√ﾚvv~(ﾟ∀ﾟ)─wwﾍ√ﾚvv~─ !!!
0523デフォルトの名無しさんNGNG
>>521
おまい、それ静的辞書法っていうってこと知ってます？
0524デフォルトの名無しさんNGNG
>>523
するとUnicodeはごく僅かに劣化する非可逆圧縮でつかね？
0525アフォNGNG
あのさ、>>521
640x400の時代にね。
画面を8bitx8bitで区切る。
同じ図形に同じ番号ふる。
最大で4096パターン。
頻繁に出現する番号に小さいのを当てる。
・図形個数出力。
・図形データ出力。
・マップ出力。
・ハフマンライブラリを経由してファイル出力。
2画面目では変化のある部分だけについて上の
パターンを適用する。
って動いた時、これは静的辞書法？動的辞書法？
0526デフォルトの名無しさんNGNG
>>525
ﾈﾀにﾏｼﾞﾚｽ(ﾌﾟ
0527アフォNGNG
>>525だって十分ﾈﾀだよぉ
0528デフォルトの名無しさんNGNG
メタファイルでいいじゃん　
0529デフォルトの名無しさんNGNG
圧縮前
sample.txt
Rｼﾅd儁eｷ｡h"; I J喨

↓

圧縮後
Uu+9vO++hQVk5YSBZe+9txnvvaFoBSI7IAIgSSAgICDCgAEBSgHllqg=.txt
sample
0530デフォルトの名無しさんNGNG
＞言葉だけ中途半端に知ってる厨房の集まりだなここは。

ちがいます。保健体育だけ中途半端に知ってる厨房の集まりです。ここは。
0531デフォルトの名無しさんNGNG
たとえば、
ああああああああ
というのがあったら
8あ
と圧縮する
0532デフォルトの名無しさんNGNG
>>531
ランレングスがどうかしましたか？

その方式だと

Boooooooooooooooom!

位だと思われ。圧縮できるのは。
まぁ、辞書の話になるんだろうな。
0533デフォルトの名無しさんNGNG
うへうへうへへへへへ
↓
3うへ4へ

こうなっていくのか。辞書か。そうか。
0534デフォルトの名無しさんNGNG
>>532
RLEって辞書必要だったのか…
0535デフォルトの名無しさんNGNG
>>534
いや、いろいろ突き詰めていくとそっちの方向に向かうなってこと。
0536デフォルトの名無しさんNGNG
>>535
で、結局 LZ77 か LZ78 の類似品になるわけですね…
0537デフォルトの名無しさんNGNG
10バイトのデータがあるとする。
そこから、2バイトのCRC値を得る。

そのCRC値を元に、それが得られるようなデータを複数求め、
元のデータがその何番目に当たるかを求める。
もし、256番目以前であれば、元のデータは、CRC値と番号の合計3バイトで表す
ことができる。

256を超えた場合、9バイトで試してみる。それでもダメな場合、8バイトで試してみる。
どうしてもダメな場合、ダメであったことを表す1ビットのフラグをつけ、
元のデータをそのまま保存する。
0538デフォルトの名無しさんNGNG
>>537
時間がやたらとかかるよーな…

あとさぁ 00 00 00 00 00 00 00 00 00 00 から
そのCRC値になるまでインクリメントして256個だけ、
っつー事であれば 圧縮できるのは
00 00 00 00 00 00 00 00 ?? ?? みたいな並びばっかにならんか？
0539デフォルトの名無しさんNGNG
インクリメントする必要もないし、0から始める必要もない。
他の圧縮方法で圧縮できそうなデータは故意に飛ばせば良い。
0540 NGNG
ある文脈の次に出現する記号を、
入力データの先頭から順番に出力していく
という感じのモデルって既にあるでしょうか。
性能はイマイチ。

例えば、記号を{ a, b, c }の３種類として
入力データを{ abcacacabca }とする。

まず、a の次に出現する記号を順番に出力すると

bccb

となる。b, c についても同様に出力すると

bccb cc aaaa

となる。以上。

説明の為に多少簡略化してあり、
この出力だけでは当然復元できません。
（このやり方なら入力データの頭と尻の記号が必要になる）

速度・メモリを無視すれば、オーダーを増やしていっても復元可能です。
（aaの次の記号を出力、baの次の記号を出力・・・）
0541デフォルトの名無しさんNGNG
>>540
データ量が減ってない気がするんですが。
0542デフォルトの名無しさんNGNG
>>541
モデルだからな。
0543540NGNG
>>541
その後、適当に符号化します。
540の出力結果はブロックソート法を甘くした感じになります。
0544デフォルトの名無しさんNGNG
>>543
また、アルファベットのみの場合には妙に効果があるってヤツ？
0545540NGNG
>>544
そうですね。性能は悪いですけど．．．
0546デフォルトの名無しさんNGNG
>>540-543

漏れの少ない脳みそを検索した結果だな……(・∀・)ｲｲ！。行けると思う。

マジで。
0547デフォルトの名無しさんNGNG
ttp://210.153.114.238/img-box/img20021025185801.zip

>>540 を実装してみた。符号化してないのでサイズ増えるけどｗ
復元の為の付加情報は符号化のときに一緒に折り込むのがいいかな？
0548デフォルトの名無しさんNGNG
>>547
>符号化してないのでサイズ増えるけどｗ

その処理を通す前と通した後のデータをそれぞれLZHか何かで適当に圧縮してみそ。
それで圧縮率が変わるようならモデルとしては優秀なんじゃない。
なるべく大きなデータがいいね。当然jpegやmp3はダメだぞ。
0549デフォルトの名無しさんNGNG
age
0550540NGNG
>>547
コンパイルしてないけど、
入力データの最初と最後に記号a を付加して、
それごとエンコードすれば、復元の為の付加情報は必要なくなると思う。
どっちがいいのか分からないけど。

...aaa abcacacabca a
0551デフォルトの名無しさんNGNG
>>550 それはダメ。復号できない。
0552540NGNG
>>551

＜エンコード＞
入力：a abcacacabca a

aの次：abccba
bの次：cc
cの次：aaaa

出力：abccbaccaaaa


＜デコード＞
入力：abccbaccaaaa

aの数：6個、bの数：2個、cの数：4個より、

abccba cc aaaa

とわかり、aから始まるので、順にたどれば、

aabcacacabcaa

となり、先頭と最後を取り除けば、

出力：abcacacabca


ダメかな…。
0553デフォルトの名無しさんNGNG
>>552
よーわからんが 最後の a って付加する必要ある？
055457NGNG
>>552
いいんじゃない？
その方法なら先頭にa(実際の実装なら'\0'か？)を付けるだけで良いと思う。
あと、その方法、なんかBlockSortingの復号みたいだな

#自分でも>>540を実装してみたけど逆に圧縮率落ちた。鬱。
0555540NGNG
> よーわからんが 最後の a って付加する必要ある？
たぶんない。
デコードの際、各記号の数を数えるときに都合がよかったのかな。

>>554
大量の文脈を使えばある程度効果はあると思うけど、
力不足で実装できませんでした。
0556デフォルトの名無しさんNGNG
>入力：abccbaccaaaa
>aの数：6個、bの数：2個、cの数：4個より、

なぜ「cの数：4個」とわかるのか？と小一時間問い詰めたい。
0557デフォルトの名無しさんNGNG
>>556
cという文字の前に来ている文字が４個、また最初の文字はaなので、cは４個
じゃないのかなぁ・・・
0558デフォルトの名無しさんNGNG
結局突き詰めていくと、
逆転文字列をブロックソートした状態になるんじゃないか？
0559540NGNG
>>556
「aの数：6個、bの数：2個、cの数：4個より」
というのは、デコード時の入力データ「abccbaccaaaa」
の各記号の個数を数えただけです。

エンコード時、最初と最後にaを付け加えることにより、
上のように単純に数えることができると考えたんだと思いますが、
余計だったかもしれません。
理屈は>>557の通り。


> 逆転文字列をブロックソートした状態になるんじゃないか？
ですね。
出力結果がブロックソート法より良くなることは無いです。
0560デフォルトの名無しさんNGNG
みんな既存の考え方にとらわれすぎ！

新しい発想でかんがえようよ！

定石やあるゴリ図無なんてｸｿ倉枝よ！
0561デフォルトの名無しさんNGNG
もう全部算術圧縮でいいよ。
0562デフォルトの名無しさんNGNG
>>561
符号化はもうほとんど算術符号になってるよ。
一部の分野でGolomb符号などが使われているくらい。

今問題にしているのはモデル化の話。
0563デフォルトの名無しさんNGNG
>>561
算術符号は特許問題がやっかいなので使わぬが吉。
RangeCoderにしとけ。
0564デフォルトの名無しさんNGNG
>>563
RangeCoderも白っぽいけど灰色という罠
0565デフォルトの名無しさんNGNG
ソースを書こうよ
0566これでええやんけNGNG

// 希望の圧縮率にできる限り近い圧縮をおこなっちゃうよっ
bool compresser(void *soce　//圧縮対象メモリ
　,int soce_size　　　//圧縮対象メモリサイズ
　,void *dest　　　　//展開先メモリ
　,int dest_size　　 //展開先メモリサイズ
　,int compress_rate)　//希望の圧縮率
{
　　if( compress_rate<1 || 99<compress_rate ){
　　　　printf("1〜99 の間で指定しろや！");
　　　　return false;
　　}

　　for(int i=0,w=0; i<soce_size; i++){
　　　　if( (rand()%100) > compress_rate )　　continue;

　　　　if( dest_size>=w ){
　　　　　　ptinrf("展開先ちゃんと確保しろや！");
　　　　　　retunr false;
　　　　}
　　　　dest[w++] = soce[i];
　　}

　　print("%d％に圧縮しますた[ハート]",w*100/soce_size);
　　return true;
}
0567デフォルトの名無しさんNGNG
確かに非可逆圧縮だな。
0568デフォルトの名無しさんNGNG
圧縮率間違ってないか？
99を指定すると無圧縮に…
0569デフォルトの名無しさんNGNG
File file = new File(filename);
file.open();String content = file.readAll();file.close();
file.rename(Base64.encode(content));
file.open();file.write(filename);file.close();
0570デフォルトの名無しさんNGNG
　　　　　　∧＿∧　 　 　　∧＿∧
　　　　　_（　´∀｀）　　　　（´∀｀　）
　 三(⌒), 　　　ノ⊃　　　 （　>>1 .） 　 糞スレは　　
　　　 ￣/　/)　 ）　　　　　 |　|　　|
　　　 . 〈＿）＼_）　 　　　 （__（_＿_）
　　　　　　　　　∧＿∧　　.∧＿∧
　　　　　　　　 （　　´∀）　（´∀｀　）
　　　　　 　≡≡三 三ニ⌒)　>>1 .） 　　 立てるなって
　　　　　　　　/　 /)　 ） ￣.|　|　　|
　　　　　 　　〈＿_）＿_）　 （__（_＿_）
　　　　　　　　 　 ∧＿∧　 ,__ ∧＿∧
　　　　　　　　　 （　　　 ´）ノ　）:;:;)∀｀）
　　　　　　　　　 /　　　￣,ノ''　>>1 .　） 　　言ってるだろうが
　　　　　　　　 Ｃ　　　/~　/　/ 　 /
　　　　　　　　 / 　 /　〉 （__（＿_./
　　　　　　　 　＼__）＼）
　　　　　　　　　　　　　　　　　　　　　 ヽ ｌ /／
　　　　　　　　　　　　∧＿∧(⌒) ―― ☆ ―――
　　　　　　　　　　　 （　　　　） /|ｌ　　／/ | ヽ 　　ヴォケがーー！
　　　　　　　　　　　（/　 　　 ノｌ|ｌｌ ／　/　|　 ヽ
　　　　　　　　　　　 （Ｏ　　ノ 彡''　 　/　 .|
　　　　　　　　　　　　/　 ./ 〉
　　　　　　　　　　　　＼__）_）
0571566NGNG
>>568
おお、そだな。 0-99の乱数発生だな。
rand関数 滅多につかわんので、まちがえちまった。 % 演算把握の問題って向きもあるが。

>　if( ((rand()%100)+1) > compress_rate )　　continue;

こんな感じでかんべんしてくれ。
0572デフォルトの名無しさんNGNG
540のは面白いと思う。1次の文脈だけ利用するんだね。

BlockSortingみたいにMoveToFrontにして前の出力との
位置の差を算術符号かstart-step-stop符号で符号化す
れば圧縮できるだろう。

たぶん、素の(0次の)MTFよりは良くて、BlockSortよりは
悪い、実に中途半端な圧縮率が得られてスレの主旨に
ぴったりでは。速度も中間になる(BSよりはだいぶ速い)
はず。
0573デフォルトの名無しさんNGNG
そんなんで圧縮できるわけねーだろ。
0574デフォルトの名無しさんNGNG
>>573
圧縮は当然できるだろ。
0次のMTFと比べてどうかはわからんが。
0575デフォルトの名無しさんNGNG
できるわけねーだろ。
なんでできると思うんだ？
0576540NGNG
>>572
1次に限らずとも可能ですよ。
おっしゃるとおり、2次程度の540 → MTF → 算術でそれなりに縮みます。

大量の文脈を使用する場合、>>547のソースでいう code_count の
扱いが問題になると思います。
0577デフォルトの名無しさんNGNG
>>576
いや、これ次数を高くしたらつまんないと思う。
普通のPPMコーダとかの、高次混合モデルを
作るやつの方が良くなっちゃう。

単にバッファを1MBくらいに大きくしてみれば？
■ このスレッドは過去ログ倉庫に格納されています