【2ch】圧縮アルゴリズム【オリジナル】
■ このスレッドは過去ログ倉庫に格納されています
0001１
NGNG中途半端に圧縮されて拡張子が.2ch
0703デフォルトの名無しさん
NGNGコンソールアプリなら、
gzip, bzip2 互換のインタフェースの方が使いやすい。
0704デフォルトの名無しさん
NGNG画像どころかCソースでも圧縮できない圧縮法に何の意味があんの？
0705デフォルトの名無しさん
NGNG「圧縮できない」ネタうざすぎ。
なんの工夫もなく「圧縮できない」というウソを繰り返すだけのやつは
もう飽きたってば。
>>690 や >>694 のとおりCソースもほぼ50%に圧縮できている。
以後は >>647 >>690 >>694 に対抗したコメントを捏造するくらいの
工夫をせよ。
0706デフォルトの名無しさん
NGNG圧縮できた妄想患者はすれ違いだからさっさと出て行け。
0707デフォルトの名無しさん
NGNG本人たちが圧縮できてると思ってるんなら、それでいいじゃん。
彼らはそれで圧縮して満足なんだし、圧縮できないと思えば
普通のアーカイバを使えば済むこと。
---------------終了---------------
0708デフォルトの名無しさん
NGNG0709デフォルトの名無しさん
NGNGだから工夫しろって。
せめて >>647 に一言いってみろや。
２次のMTFと同等だから圧縮できて当り前だろ？
0710デフォルトの名無しさん
NGNG0711デフォルトの名無しさん
NGNG0712デフォルトの名無しさん
NGNG彼(ら)の頭ではうpされたコードどころかword countも理解できません。
0713デフォルトの名無しさん
NGNG647に一言いってみろや。なんにも言えないんだろ（藁
0714デフォルトの名無しさん
NGNG圧縮できる/できない で埋め立てるつもりか？
0715デフォルトの名無しさん
NGNGbib: 66314, 66687, 111261
book1: 470878, 470260, 768771
book2: 361427, 360827, 610856
geo: 75105, 76935, 102400
news: 235941, 235700, 377109
obj1: 13857, 14105, 21504
obj2: 127266, 126602, 246814
paper1: 31091, 31521, 53161
paper2: 48992, 49321, 82199
paper3: 28162, 28544, 46526
paper4: 8030, 8332, 13286
paper5: 7115, 7416, 11954
paper6: 22117, 22507, 38105
pic: 159535, 159648, 513216
progc: 21760, 22223, 39611
progl: 35562, 35849, 71646
progp: 23932, 24316, 49379
trans: 49036, 49343, 93695
優劣は微妙だが誤差範囲かも
0716デフォルトの名無しさん
NGNG平均符号長が２次MTFの出力に漸近するのは明らか。
0717デフォルトの名無しさん
NGNGなかなか見事だと思う
0718デフォルトの名無しさん
NGNGただの名無しだろ？
0719デフォルトの名無しさん
NGNGもっとも>>649-654は十分なアイデアが出尽くす前に2chエンコーダ・デコーダを
名乗ってしまったわけで、それはそれで名無しではあるが「俺が2chエンコーダ・
デコーダの作者だ」と主張しているようでいかがなものかと。
0720デフォルトの名無しさん
NGNG0721デフォルトの名無しさん
NGNG>十分なアイデアが出尽くす前に2chエンコーダ・デコーダを
>名乗ってしまった
もうここらでいいんじゃない？ 中途半端なところで。
こんな駄スレに次スレは立たないだろうし。
0722デフォルトの名無しさん
NGNG>>649-654を試してみたよ。
>>649-654を圧縮してみたわけよ。
そしたら1.93KBが1.00KBになったわけよ。
で、驚きながら出コードしてみたわけよ。
そしたら511バイトになったわけよｗ
ネカマ口調で書いてみたけど、
なんかコンパイルでミスったのか？オレは。
0723デフォルトの名無しさん
NGNGま、これもひとつの2chではあるな。
>>722
main()の頭に
setmode (fileno (stdin), O_BINARY);
setmode (fileno (stdout), O_BINARY);
入れてみても駄目かい？
0724デフォルトの名無しさん
NGNG4ビット単位とか2ビット単位とか1ビット単位で
並び替えるとどーなるんでしょう？ 意味無し？
0725デフォルトの名無しさん
NGNG(1)次数に制限のない高次のモデルを使って、
(2)符号長を1bitより短くできるような符号化をするなら、
入力を短いbitで切ってもあまり関係ない。
540とSSSだとどっちも充たさないから短いbitで切ると損。
0726デフォルトの名無しさん
NGNG0727デフォルトの名無しさん
NGNGテキスト系でだいたい半分。
当初の目的のAA系だとものによって２０％くらいまで減らせるようだ。
解凍がなかなか早いのもGood
0728デフォルトの名無しさん
NGNGunsigned char buffer[BLOCK_SIZE];
は
unsigned char buffer[BLOCK_SIZE + 1];
としないとマズイのでは。
0729デフォルトの名無しさん
NGNGソートしたらさらに圧縮率が上がったけど、けっきょく文脈ソートや
ブロックソートに近づいているようで鬱
0730デフォルトの名無しさん
NGNG.DQNがおにあいだ
まずＤＱＮｋａｒａｈａｊｉｍｅｒｅ
0731デフォルトの名無しさん
NGNGIMEを全然操れてないところがDQNぽくてナイス
0732デフォルトの名無しさん
NGNG0733デフォルトの名無しさん
NGNG0734デフォルトの名無しさん
NGNG0735デフォルトの名無しさん
NGNGcompressなんかだと単純に出現順に割り当てた
符号語を出力しますが、それをさらにMTF+可変長符号で
頻度が高いものほど短くなるように符号化する。
あらかじめ決めた辞書サイズが溢れたら、MTFで
いちばん下のところ(最近使われていないところ)
を辞書から削除する。
0736デフォルトの名無しさん
NGNG辞書の捨て方はBTLZ(V.42bisに使われたやつ)に似ているが、
あれはMTF符号化をしていなかった気がする。
0737デフォルトの名無しさん
NGNGLZ78系だと基本的には辞書に登録する単語がどんどん長くなるわけだけど
そうすると新しく登録した単語ばかりが使われることになるだろうから
MTFが効かないような気もする。
最長不使用法で古い単語を捨てて辞書を小さく保つのは有効のはず。
単純なLZ78に組み込む場合はその処理に時間がかかるのがデメリットだけど
MTFに組み合わせるなら殆ど負担にはならないのが利点かな？
0738デフォルトの名無しさん
NGNGそのエントリが他のエントリから参照されているかも知れないから。
その時はどうする？ 子供も全て捨てるか、「子供のいない最も古い
やつを捨てる」か。
0739デフォルトの名無しさん
NGNGMTFは「最近出てきたものがまたすぐ出てくる」とき良く圧縮できる。
LZ78は「一度出てきたものは辞書に登録して、
なるべく同じ出力を繰り返さない」ことを狙いとしている。
0740SYN ◆8smMJ0UaoA
NGNGきちんとした符号化を考えた時、最適(とはいわないでも良好)なモデル化とはいいがたいです。
無条件に先頭に持ってくるのは少々乱暴な感じ。
出現率をきちんと管理できるのであれば、「移動させる」MTFは必要ないです。
0741SYN ◆8smMJ0UaoA
NGNGGCAは実験的作品なので糞なのは認めます。ごめんなさい。
ただ、ガイシュツの理論だけではないです。
BWT+MTF+RangeCoderで作ってみるとわかりますが、
それだけではあまり圧縮率が出せません。
0743デフォルトの名無しさん
NGNG0744SYN ◆8smMJ0UaoA
NGNG気に入らないことがあるなら私に直接言ってください。
fjの方の方でしたら、知っていると思いますが、
「ヤりたい」のなら私はそれに付き合うつもりもあります。
某TRPG関連の方でしたら、本当の事実を知らないだけです。
その場合も私に連絡をください。真実をお伝えしますから。
わざと壊した.gcaファイルを配布する人や、ウィルス入りのファイルを
配布する人もいて、本当に困るよ…。
0745デフォルトの名無しさん
NGNGまぁ公開アルゴリズムをつかいながGCAソース非公開
アーカイバプロジェクトへのGCA/APIの一部非公開
が問題だな
0746SYN ◆8smMJ0UaoA
NGNGソースを公開していないのは、仕様変更がしにくくなるからです。
そういう意味でGCAはまだ完成していません。真打はGCAではないですし…。
それにGCAみたいなしょぼいソフトのソースなど誰も見たがらないと思う。
0747SYN ◆8smMJ0UaoA
NGNG限定ソートのメリットってほとんどないです。szipで使われていますが、
完全ブロックソートでも、あれに近いぐらいの速度が出ます。
完全＝大まかにソート(限定ソート)＋αなのですが、このαの部分って
ほとんどのファイルのデータでは極小なので、差はほとんど出ないです。
0748デフォルトの名無しさん
NGNGその割にB&Wはソートの高速化に苦労していたみたいだが。
特にバイナリで0x00が大量に続くようなとき、単純なソートだと
恐ろしく遅くなるよ。
0749デフォルトの名無しさん
NGNG0750デフォルトの名無しさん
NGNGアルゴリズムがどうの言ってる暇があったら自己展開書庫のヘタレUIを改善して欲しいよ…
0751デフォルトの名無しさん
NGNGだから最初にランレングスしたり
ブロックのバイト列の終端にどの数よりも必ず大きく（小さく）なる値を割り当てて
比較長を短くしたりする、いろいろな工夫があるんだろ？
0752デフォルトの名無しさん
NGNGブロックサイズを（完全と比べて）果てしなく大きく取ることが出来るので
ある種のデータではブロックが小さい完全ソートより
良好な結果を得ることが出来ると思うんだが。
0753デフォルトの名無しさん
NGNGだから単純なソートだと遅いから高速化に苦労してたって、>>748が言ってるだろ？
0754デフォルトの名無しさん
NGNGそれならば、すでに先人が苦労した成果があるんだから
後からそれを利用するだけなら大した苦労も無いだろう。
0755デフォルトの名無しさん
NGNG話の筋を追えんやつだな（ｗ
0758デフォルトの名無しさん
NGNG80行で完全ソート書いてみて >>SYN
0759デフォルトの名無しさん
NGNG0760デフォルトの名無しさん
NGNG0761デフォルトの名無しさん
NGNGオーダーにするとその通りだけど、限定ソートなら 1(n/2)+ちょっと で出来るでしょ。
0762デフォルトの名無しさん
NGNG>>758
限定ソートほどじゃないけど、速度を気にしなければ、
普通に書いても2,30行ぐらいでいけます。
ちなみに展開の方は普通に10行ぐらいで書けます。
>>761
確かにバッファは減らせるけど、それによって確保できるブロックサイズは
精々数倍程度で、果てしなく大きくってほどじゃないと思うけど…
それにブロックサイズは無闇に大きくするとデータの揺らぎに対応できずに、
結果が悪くなることが多いです。
0763デフォルトの名無しさん
NGNG「540＋MTF＋ハフマン」
で圧縮ソフト組んだのですが。
MTFとハフマンはそこらへんから拾ってきたソース組み込んだだけだったけど。
いや、別にいいんだけどさ。
0764デフォルトの名無しさん
NGNG2〜30行ならうｐしてみろや
可変長符号だけで10行やそこらはかかると思うんだが
まさか最密充填コード？
0765デフォルトの名無しさん
NGNG0766ふﾄﾝｶ ◆wX94FutoNg
NGNGDVD-ROM片面２層の辞書を持っている、
有名な曲とか、定番の発言とか、全部入っている
そうしたらすごい圧縮できるんてじゃないでしょうか。
10MBのMP3が10KBに！、とか…
まぁそこまでは行かなくともですが、、まぁ多分、原理的に無理だから誰もしないんですよね、、失礼。
0767デフォルトの名無しさん
NGNG0768デフォルトの名無しさん
NGNGソース公開しろとまでは言わんが、
GCAのMAC版、Unix版が無いのはいかがなものか？
自分でＧＣＡがヘボイと言っているのならそれは自分でゴミを垂れ流してることになるだろ
0769デフォルトの名無しさん
NGNG0770デフォルトの名無しさん
NGNGクリスマスに、ってのが泣ける｡
･ﾟ･(ﾉД`)･ﾟ･｡
0771デフォルトの名無しさん
NGNG身内用に作ったものを勝手に使用しているようなものなのに、なんでえらそうなんですか
もともと趣味で作ったもの。MacやLinux版をわざわざ出すわけないでしょう
圧縮方法もまだしっかり確立していないのに
今のはテスト版のようなもの。圧縮方法がしっかりときまったらソース公開や他OS版も考えるでしょう
0772デフォルトの名無しさん
NGNG0773デフォルトの名無しさん
NGNG0774デフォルトの名無しさん
NGNGそれだけだ
0775デフォルトの名無しさん
NGNGブロックソート関連のWebページ逝けば３０行くらいで普通に載ってるぞ。
それに、bzip2のソースも実質そんなていど、といってみるテスト。
0776☆南幸☆
NGNG0778デフォルトの名無しさん
NGNGMTFが３〜４行、算術符号は５行くらいでかけるから、
qsort使ってよいなら、かなり短くなると思うよ。
0779デフォルトの名無しさん
NGNGもったいぶらずに早く書いてよ。
0780デフォルトの名無しさん
NGNG>>773
>>777
普通BWTは圧縮とは言わないから、符号化までは入れないでしょう。
後段の符号化をやらないで、ベタで垂れ流してもBWTであることには変わりないですし。
0781デフォルトの名無しさん
NGNGなあんだ。ホラかよ。
限定ソートが80行に対して２、３０行で書けるとかほざいときながら。
0782778!=780
NGNG完全ソートなら30行で書けますよね？
限定ソートの方が、工程が多い分だけ長くなるということで。
>>780
始めは俺もBWTだけを書くという話だと思ってたよ。
もしかして>>777>>781はBWTを知らないんじゃないかと・・・
0783デフォルトの名無しさん
NGNG半数が空行やコメントのプログラムが、７３行だった。実質３０行台。
うはっ、われながらひどいプログラムだ。
0784デフォルトの名無しさん
NGNGスマソ。それは遅れていただけで、やる気が無いわけではないです。
確かに今のUIがヘボイことは認めざるを得ません。
ただ、UIの発展をどういう方向に進ませるべきか意見を聞きたかったのです。
結果はDGCAで出せると思います。
同時ではないですが、MAC、Linuxの予定もあります。
0785デフォルトの名無しさん
NGNGいや、bzip2のソースもBurrowsとWheelerの論文も読んでるけどさ。
限定ソートの高速なソースは現に80行かそこらであるわけよ。>>649に。
んで、ＳＹＮは限定ソートのメリットなんて無いとほざいたわけよ。
たった２、３０行で書けると。
ホラ吹くんじゃねーよ（ｗ
0786デフォルトの名無しさん
NGNG30行で高速なブロックソート圧縮プログラム早くうｐして見せろや。
0787デフォルトの名無しさん
NGNG確かに>>649はそれはそれですごいが、
あれをBWTの限定ソートと呼ぶのはどうかと。
そんなことをいったら1次モデルもBWTの限定版になってしまうがな。
0788デフォルトの名無しさん
NGNGSYNの言うこといちいち真に受けるなよ（ｗ
だからコテハンなんてろくな香具師じゃないって。
0789デフォルトの名無しさん
NGNGじゃああんたのいう限定ソートって何？
0790デフォルトの名無しさん
NGNG限定ソートにメリットが無いことは、各種論文でも言われていると思うけど。
本当にブロックソート関連の論文読んだの？
0791デフォルトの名無しさん
NGNGbzip2みたいに、せめて100kバイト程度のブロックであって欲しいな。
0792デフォルトの名無しさん
NGNG2-30行のソースとやら晒して見せろや
嘘つきヤロウ
0793デフォルトの名無しさん
NGNGbzip2のブロックと、限定ソートの長さ制限は意味が違う。
0794デフォルトの名無しさん
NGNGそれだけかよ（ｗ
じゃあ#define直せば限定ソートになるのか？
0795デフォルトの名無しさん
NGNGあー、それなら私が悪かった。申し訳ない。
ソースコードが小さいというがメリットになると思っていなかったので。
ただ、速度を気にしないBWTは異様なほど小さく出来る。
選択ソートやバブルソート使ったら( ﾟДﾟ)ｺﾞﾙｧ！かもしれませんが。
しかし、ここはIDも出ないのですね。自分の発言がどれかわからなくなりそう。
0796デフォルトの名無しさん
NGNGここに載っているのにqsort使うと３０行くらいじゃないか？
0797デフォルトの名無しさん
NGNGまてまて、焦ってはいけない。
>>540から>>649が登場するまでだって、あれだけ時間がかかったのだ。
せめて１〜２日はまってやろうじゃないか。
0798デフォルトの名無しさん
NGNG本当に速度を気にしなくても良いなら、qsortつかって7行プログラミングできそう。
0799デフォルトの名無しさん
NGNGがいしゅつです。
すでにBWTは7行プログラミングされてます。
0800デフォルトの名無しさん
NGNGなんだもう7行で概出か・・・俺が間違ってたよ。
0801デフォルトの名無しさん
NGNGお前誰だよｗ
>>799
無かったぞ。それともたまたまdat落ちしているpart2にあったとでも？
都合がいいな。
0802デフォルトの名無しさん
NGNG■ このスレッドは過去ログ倉庫に格納されています