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

で、みんなＣマガ読んだ？？

漏れ頭悪いのかサパーリ。誰か解説キボン。

yz2の記事のアルゴリズム解説以外の部分と
ひんろーださんのページと
編集後記のやっさんのページだけ立ち読みした。

Ｃマガは高すぎる、半額でいいぐらいだ

今から書店いってCマガ立ち読みしてくる。

458じゃないけど、立ち読みしてきた。
圧縮に関しては何も得ることが無かった。
yz2はソースプログラムも読んだことあるし、直接解説を聞いたこともあるから。

yzよりGCAの作者をぶん殴りたい

>>460
なぜ？ fjで暴れているから？

>460-461
SYNさんって、なんで嫌われるのかな。

yzより圧縮率高いじゃん。ブロックソートだから当然と言えば当然だけど。

まあ、議論はもうこのくらいでいいよ、
ＧＣＡやｙｚ２を超えるアーカイバをサクッと作ってみろや。
おまいらの腕ならそれが可能なんだろ？

>>463
PPMをベースにすれば、はじめから超えている

ＧＣＡって既出の理論でソートを少し最適化しただけで
後出のくせに圧縮率もたいしたことないし、処理遅いのに
なんでこんなにありがたがられてるんだか理解できないな。

嫌われてるっていうのは、良くしらないけど
そういうところにあるんじゃない？

>>465
割れ物でよく使われてるから。

解凍すべき物がそこにないなら、誰も使わんでしょ。

>>465
圧縮率が大したことあるから。

作者が嫌われるってのと
作ったソフトの性能にはあんまし関係は無いのでは？
坊主憎けりゃ袈裟まで憎いっての以外には。

>>465
いまどき微々たる圧縮率の差を競うのは時代遅れだよな
50%も圧縮率が優れていればﾏﾝｾｰなんだが
実際は平均より数%程度で激ノロで偉そうにしてれば
叩かれて当然だろう..

>>469
50% っても zip で 100 -> 97 ぐらいのやつが 100 -> 94
ぐらいになってもあんまうれしくないね。
あと zip で 100 -> 24 ぐらいのやつが 100 -> 12
ぐらいでも面倒くさいから zip でいーじゃんとか思う。

圧縮が効かないデータでは立場がさらに苦しいな > GCA

>GCA
たいていCabのLZX最高圧縮の方が縮むんであって使ってない

>>472
そりゃあ、向いてないファイルに使ってるからでない？
ＧＣＡは主にテキスト、あるいはアニメ画像なんかに向いてるのだが。

最近はCBTに抜かれてます＞GCA

おまいらXPointer使って圧縮して見れ

>>474
というか、テキストなら7z・RARのPPMdが最強かと。

>>465
たしかにガイシュツの理論だが実装が難しいんだよ、BWTは。
圧縮率はｶﾅｰﾘ高いほうだよ、圧縮比率比較しているサイト行ってみな。
嫌われているのは処理が遅いからだろう。

>>477
BW変換なんてそんなに難しい方じゃないと思う。
suffix-arrayの構築による手法が何種類もあるから、それを使えばいいし。
力任せでも何とかなる。suffix-treeだっていい。

しかし、PPMを実装するためには、せめて8次〜20次の文脈を扱いたいから、
どうしてもsuffix-treeの知識が必要だし、
suffix-treeだけでは素のPPMすら実装は難しい。

圧縮のアルゴリズムって基本的に偏りを利用してると思うんだが、
偏りがあまりないデータだと圧縮率が悪くなるよな。
意図的に偏りを作り出すことって出来ますか？
もちろん可逆でbit数の増加が無視できる程度で。

>>479
ブロックソートやMTFは考えとしてはそれに近い。
というより、文脈が。
もっといえば、情報源を高度に推定していくことに近い。

>>479 モデル化しる

>>480
情報源を高度に推定って具体的にどうやればいいんでしょうか？
回帰分析みたいな感じですか？

>>482
MDLとかAIC規準ではなかろうか

>>482 データマイニングしる

最近だと、PPMTなんてものもあるらしい。
でもユニバーサルではないよなぁ？
http://citeseer.nj.nec.com/teahan01combining.html

>>483
算術符号とか動的ハフマンのようなものですか？

言葉だけ中途半端に知ってる厨房の集まりだなここは。

>>487
こんばんは、厨房その１です。
恥ずかしながら、仰るとおりです。

>>478
suffix-tree と パトリシアトライの区別がつかないんだけど…

>>489
同じです。
派閥(?)によって呼び方が違うだけのようです。

>>490
さんきゅ

やばい、、すごい圧縮アルゴリズム開発しちまった・・・。
今HDDにあるファイルで手当たり次第テストしてるが、MAXでも元サイズの12％にしかならない。
（しかもlzhやzip,jpgなどのファイルでも！）
ちょっと怖くなってきた。。
（当然可逆圧縮。）

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

こんなんになるとは夢にも思わんかった・・。

祭の予感？

>>492
そのネタは1年ほど前に見たことがあるような…

>>492
ソースあげれ.もしくはバイナリ.

今は特許考えてるんで、ソース・バイナリともにあげるのはちょっと無理。
（バイナリ解析されると怖いんで）


改善点はスピード。
これが今のところかなり遅い。（同種系の３〜５倍くらい遅い）

じゃあ圧縮データサンプル出せ
特許つったって公開されるんだから
ソース出したって変わらんと思うがな。

>>492
中途半端なネタは最悪。

お前の頭で理解できるようなアルゴリズムか、
このスレの誰も理解できないような複雑なアルゴリズムを出せ。

>>498

複雑なアルゴリズムは圧縮にはむかないとおもわれ。

>>492

このサイトでもう少し圧縮について基本的なことを勉強したほうがいいですよ。
ttp://www.ingnet.or.jp/~kojif/mu/comp/

偏りがあまりないデータ ＝ 疑似乱数
な罠

age

>>492

ﾀﾜﾗ

>>497
ソース公開すると(下手したらバイナリ公開も)特許は取れなくなるかと。

とりあえず、特許申請するまえに
伊藤家の食卓にハガキだしとけ

>>504
ですね。
学会発表なら特許取得もできるので、すぐさま
情報処理学会、電子情報通信学会、情報理論とその応用学会、IEEE、ACM
のどれかに投稿しる！
レターの形でもいいから。

その方法での圧縮は算術演算以上にならないことがすでに証明されています。
従って、単なるネタ。

×算術演算
○算術圧縮

全てのデータに対して圧縮率が高い圧縮方法は難しいが、
特定のデータに対してなら劇的に圧縮率を上げることができると思う。

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

また、画像や音楽の圧縮もJPEGやMPEGよりフラクタル理論を使った方が
圧縮率が高くなることが知られている。

>>509
データの種別に応じて圧縮法をチューニングするのは、
あるいは専用の圧縮法を使うのは、ツールとしては確かに有効です。
しかし、圧縮理論で最も重視される性質の一つである、
ユニバーサル性を失うことになるため、拒絶する人は多いかもしれません。

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

しかし、フラクタル発見の効率はよいため、
・画素の類似性を計測するためにフラクタルを使う（文脈として使う）
・線形走査法（ヒルベルト走査など）に組み合わせて、１次元上でのフラクタル圧縮を行う
などの研究が行われているようです。

>>492
寒いですよ。ネタバレバレ。頭が悪いこともバレてます。
もっと圧縮の勉強をしてから書いてください。

492はもともとものすごく冗長なデータしか持ってなかったのかも知れないよ

>>500
おまえばかだな。

>>512
lzhやzipが、さらに圧縮できていることを考えると、
ファイル名が
00000000000000000000000000000000000000000.txt
のようなものだったと思われる。

>>514
新圧縮ｷﾀ━━━━━━（ﾟ∀ﾟ）━━━━━━ !!
0KByteのファイルを作り、ファイル内容をBASE64でエンコードして名前に設定
完璧!!

492に釣られている香具師がいっぱいだな(w

>>515
圧縮カコイイ！

T-RangeCorder
ttp://homepage2.nifty.com/rohizuka/ka/pa_003_a.htm

>>518
ぐはっ、これでひっかかったの4回目です。宇都田。

>>518
一生、呪ってやる。

凄まじい圧縮といえばテキストでしょ。
１つの文字を１，２バイトまで圧縮できるんだから。
究極のモデル化だね。
解凍するために必要なデータは膨大だけどね（フォントデータ）。
但し、ない文字は使えない、または外字を入れると
サイズが膨大になるという欠点も持っている。

さらに圧縮かけると最強。
実はテキストって凄いのですよ。

電波ｷﾀ─wwﾍ√ﾚvv~(ﾟ∀ﾟ)─wwﾍ√ﾚvv~─ !!!

>>521
おまい、それ静的辞書法っていうってこと知ってます？

>>523
するとUnicodeはごく僅かに劣化する非可逆圧縮でつかね？

あのさ、>>521
640x400の時代にね。
画面を8bitx8bitで区切る。
同じ図形に同じ番号ふる。
最大で4096パターン。
頻繁に出現する番号に小さいのを当てる。
・図形個数出力。
・図形データ出力。
・マップ出力。
・ハフマンライブラリを経由してファイル出力。
2画面目では変化のある部分だけについて上の
パターンを適用する。
って動いた時、これは静的辞書法？動的辞書法？

>>525
ﾈﾀにﾏｼﾞﾚｽ(ﾌﾟ

>>525だって十分ﾈﾀだよぉ

メタファイルでいいじゃん　

圧縮前
sample.txt
Rｼﾅd儁eｷ｡h"; I �J喨

↓

圧縮後
Uu+9vO++hQVk5YSBZe+9txnvvaFoBSI7IAIgSSAgICDCgAEBSgHllqg=.txt
sample

＞言葉だけ中途半端に知ってる厨房の集まりだなここは。

ちがいます。保健体育だけ中途半端に知ってる厨房の集まりです。ここは。

たとえば、
ああああああああ
というのがあったら
8あ
と圧縮する

>>531
ランレングスがどうかしましたか？

その方式だと

Boooooooooooooooom!

位だと思われ。圧縮できるのは。
まぁ、辞書の話になるんだろうな。

うへうへうへへへへへ
↓
3うへ4へ

こうなっていくのか。辞書か。そうか。

>>532
RLEって辞書必要だったのか…

>>534
いや、いろいろ突き詰めていくとそっちの方向に向かうなってこと。

>>535
で、結局 LZ77 か LZ78 の類似品になるわけですね…

10バイトのデータがあるとする。
そこから、2バイトのCRC値を得る。

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

256を超えた場合、9バイトで試してみる。それでもダメな場合、8バイトで試してみる。
どうしてもダメな場合、ダメであったことを表す1ビットのフラグをつけ、
元のデータをそのまま保存する。

>>537
時間がやたらとかかるよーな…

あとさぁ 00 00 00 00 00 00 00 00 00 00 から
そのCRC値になるまでインクリメントして256個だけ、
っつー事であれば 圧縮できるのは
00 00 00 00 00 00 00 00 ?? ?? みたいな並びばっかにならんか？

インクリメントする必要もないし、0から始める必要もない。
他の圧縮方法で圧縮できそうなデータは故意に飛ばせば良い。

ある文脈の次に出現する記号を、
入力データの先頭から順番に出力していく
という感じのモデルって既にあるでしょうか。
性能はイマイチ。

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

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

bccb

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

bccb cc aaaa

となる。以上。

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

速度・メモリを無視すれば、オーダーを増やしていっても復元可能です。
（aaの次の記号を出力、baの次の記号を出力・・・）

>>540
データ量が減ってない気がするんですが。

>>541
モデルだからな。

>>541
その後、適当に符号化します。
540の出力結果はブロックソート法を甘くした感じになります。

>>543
また、アルファベットのみの場合には妙に効果があるってヤツ？

>>544
そうですね。性能は悪いですけど．．．

>>540-543

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

マジで。

ttp://210.153.114.238/img-box/img20021025185801.zip

>>540 を実装してみた。符号化してないのでサイズ増えるけどｗ
復元の為の付加情報は符号化のときに一緒に折り込むのがいいかな？

>>547
>符号化してないのでサイズ増えるけどｗ

その処理を通す前と通した後のデータをそれぞれLZHか何かで適当に圧縮してみそ。
それで圧縮率が変わるようならモデルとしては優秀なんじゃない。
なるべく大きなデータがいいね。当然jpegやmp3はダメだぞ。

age

>>547
コンパイルしてないけど、
入力データの最初と最後に記号a を付加して、
それごとエンコードすれば、復元の為の付加情報は必要なくなると思う。
どっちがいいのか分からないけど。

...aaa abcacacabca a

>>550 それはダメ。復号できない。

>>551

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

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

出力：abccbaccaaaa


＜デコード＞
入力：abccbaccaaaa

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

abccba cc aaaa

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

aabcacacabcaa

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

出力：abcacacabca


ダメかな…。

>>552
よーわからんが 最後の a って付加する必要ある？

>>552
いいんじゃない？
その方法なら先頭にa(実際の実装なら'\0'か？)を付けるだけで良いと思う。
あと、その方法、なんかBlockSortingの復号みたいだな

#自分でも>>540を実装してみたけど逆に圧縮率落ちた。鬱。

> よーわからんが 最後の a って付加する必要ある？
たぶんない。
デコードの際、各記号の数を数えるときに都合がよかったのかな。

>>554
大量の文脈を使えばある程度効果はあると思うけど、
力不足で実装できませんでした。

>入力：abccbaccaaaa
>aの数：6個、bの数：2個、cの数：4個より、

なぜ「cの数：4個」とわかるのか？と小一時間問い詰めたい。

>>556
cという文字の前に来ている文字が４個、また最初の文字はaなので、cは４個
じゃないのかなぁ・・・

結局突き詰めていくと、
逆転文字列をブロックソートした状態になるんじゃないか？

>>556
「aの数：6個、bの数：2個、cの数：4個より」
というのは、デコード時の入力データ「abccbaccaaaa」
の各記号の個数を数えただけです。

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


> 逆転文字列をブロックソートした状態になるんじゃないか？
ですね。
出力結果がブロックソート法より良くなることは無いです。

みんな既存の考え方にとらわれすぎ！

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

定石やあるゴリ図無なんてｸｿ倉枝よ！

もう全部算術圧縮でいいよ。

>>561
符号化はもうほとんど算術符号になってるよ。
一部の分野でGolomb符号などが使われているくらい。

今問題にしているのはモデル化の話。

>>561
算術符号は特許問題がやっかいなので使わぬが吉。
RangeCoderにしとけ。

>>563
RangeCoderも白っぽいけど灰色という罠

ソースを書こうよ

// 希望の圧縮率にできる限り近い圧縮をおこなっちゃうよっ
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;
}

確かに非可逆圧縮だな。

圧縮率間違ってないか？
99を指定すると無圧縮に…

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();

　　　　　　∧＿∧　 　 　　∧＿∧
　　　　　_（　´∀｀）　　　　（´∀｀　）
　 三(⌒), 　　　ノ⊃　　　 （　>>1 .） 　 糞スレは　　
　　　 ￣/　/)　 ）　　　　　 |　|　　|
　　　 . 〈＿）＼_）　 　　　 （__（_＿_）
　　　　　　　　　∧＿∧　　.∧＿∧
　　　　　　　　 （　　´∀）　（´∀｀　）
　　　　　 　≡≡三 三ニ⌒)　>>1 .） 　　 立てるなって
　　　　　　　　/　 /)　 ） ￣.|　|　　|
　　　　　 　　〈＿_）＿_）　 （__（_＿_）
　　　　　　　　 　 ∧＿∧　 ,__ ∧＿∧
　　　　　　　　　 （　　　 ´）ノ　）:;:;)∀｀）
　　　　　　　　　 /　　　￣,ノ''　>>1 .　） 　　言ってるだろうが
　　　　　　　　 Ｃ　　　/~　/　/ 　 /
　　　　　　　　 / 　 /　〉 （__（＿_./
　　　　　　　 　＼__）＼）
　　　　　　　　　　　　　　　　　　　　　 ヽ ｌ /／
　　　　　　　　　　　　∧＿∧(⌒) ―― ☆ ―――
　　　　　　　　　　　 （　　　　） /|ｌ　　／/ | ヽ 　　ヴォケがーー！
　　　　　　　　　　　（/　 　　 ノｌ|ｌｌ ／　/　|　 ヽ
　　　　　　　　　　　 （Ｏ　　ノ 彡''　 　/　 .|
　　　　　　　　　　　　/　 ./ 〉
　　　　　　　　　　　　＼__）_）

>>568
おお、そだな。 0-99の乱数発生だな。
rand関数 滅多につかわんので、まちがえちまった。 % 演算把握の問題って向きもあるが。

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

こんな感じでかんべんしてくれ。