圧縮アルゴリズム考えたんですが

>>351
1bitデータの圧縮おながいします

>>359
1bit 1キャラクタだけなら既存の方法で相当小さくできるぞ。
もちろんPCで扱うからそのデータを表現するには1-数byteになるだろうがな。
圧縮と符号化の関係をちゃんとりかいすることだ

テキストの圧縮率が良くて(少なくともzip以上)、実装が簡単で
展開が速い圧縮法ってある？

>>361
GCAの最初の実装の（現バージョンは違う）
BlockSorting→MTF→RLE→RangeCoder
がいいかな｡
概念の理解や実用化にはちょっと苦労するかも知れんけど｡

ttp://www.geocities.co.jp/SiliconValley-Oakland/1680/zsaru.html

>>362
やっぱりそれか。
というかちょうどそこ読んでたところ。
まだRangeCoderが理解できてない…

展開は遅いけど、最近ppm系が気になる・・・。
ppmz [ttp://www.cbloom.com/src/ppmz.html] が凄げだそうですが、
結構読むのは大変そう。

会社で圧縮アルゴリズム考えてて、上司にこれ使っていいっすか！ときいたら
「おまえがすべての圧縮の特許を調べてそれがどれにも抵触してないことを証明できれば、いいよ」
と言われた

素晴らしい上司だな。

>>365
うっかり使用すると、会社がつぶれかねん。

特許フリーをうたっているアルゴリズムを使用するか、
国内で特許問題が解決済みの製品（富士通のﾀﾞﾒツールとか）を使うかしれ。

誰かJava(*.java，*.class)ファイルに特化した圧縮アルゴリズム考えて

>>368
jarだな。

javaが動作する環境なら（JRE,JDKがあるなら）、圧縮・展開できるすぐれもの！
それだけでなく、なんと圧縮した状態でもclassファイルを実行できる。

>>369 釣られると、それって結局ZIP圧縮な（ｒｙ

RangeCoderに入る前に文字の出現頻度から
おおよその圧縮率を求める方法ってないのかな？
いちいち通して確認してたらとんでもなく時間かかるし…
今のところ
A[1]^2 + ... + A[n]^2 //Aは各要素の出現回数
これが大きいほど圧縮率が良くなると考えてるんだけど。
これが分かれば配列内の数値の比較だけで済むから
MTFとRLEの最良の組み合わせを考える時間が減るんだな。

>>371
単純に
　foreach(要素の数だけ)
　　合計 += 各要素のビット数 * 各要素の出現回数
ってやるんじゃダメなん？

ビット数は必要な精度を満たすなら不動小数点数でも固定小数点数でも良いと思うけど。

>>371
Cマガ2002年７月号より

i = 0〜255とする
p[i] → iの出現確率のとき

エントロピー(もとの1バイトを何ビットに縮められるか)の限界は
(p[i] + log2(1 / p[i])) の合計

※C99以前では log2(x) = log(x) / log(2.0) で代用

>>373
> (p[i] + log2(1 / p[i])) の合計
p[i] * log2(1 / p[i]) じゃなくて？

あと log2(1 / p[i]) は圧縮限界の値なのでサイズに余裕持たせとくとか、
ちゃんと RangeCoder の実装にあった式使うとかしないとオーバーフローする可能性あるよ。

>>374
まぁ、誤差はせいぜい数バイトper1M文字。
rangecoderや算術符号で吐き出すバッファ分＋誤差数バイトとっとけばおｋ。

>>371
rangecoder通しても通さなくとも、実はほとんど時間はかわらない罠。
確率を算出するまでが、全体の9割方。
しかも、mathライブラリでlogを求めると、結局同じくらいの時間がかかる。

みんなレスありが�d

>>372
foreachって知らなかったんだけどPerlなの？
各要素のビット数ってのは8なら3で256なら8ってことかな？

>>373
やっぱりそういう式があるんだね。
log使うのか。

>>374
*,+どっちが正しいのかな？

>>375
うーん、そうか、というかそうだよね。
時間はたいして変わらないよね。

でも展開速度考えてRLEを挟まないオプションを入れようかと
考えてたんだ。
で、MTF -> RCの場合は
例えば出現回数100,20,5,3,1(要素5,MTF後を想定)みたいなのがあった時に
100 -> 99, 20 -> 21
みたいな変化をしたら確実に圧縮率が下がるのは分かるんだけど、
100 -> 99, 20 -> 25, 5 -> 1
みたいな変化をした場合には逆に上がるかもしれないじゃない。
(漏れの2乗和計算によると後者のほうが圧縮率高い)
こういう場合は3要素だけの比較で済むわけで。

いや、まだ全然実装してなくて全部思考実験の段階なんだけどさ。
実際コーディング始めたらどうでも良くなりそうな気もするけど。

夢物語，それとも大発明？　「100分の1以下」の圧縮技術
http://www.itmedia.co.jp/news/0202/21/e_zeosync.html

1/100でも映画をフロッピーには無理だろ・・・
1/40のMPEG2でさえあのでかさだ

>>377
これ、もう1年前の話か。

げ、違う。2年前か。

そのままじゃなく既存のもしくは別のlossy方式と組み合わせてってことだろうに

いや劣化なしにってあるから違うだろ。

劣化が無いのはZeroSyncの妄想圧縮アルゴリズムの話であって、
それの応用については一切言及されてないと思うんだけど？

>そういう技術があれば，映画をまるまる一本，ダイヤルアップモデムを使って簡単に転送できるし

映画に付いてはこれしか語られてないんだから。

しかしMPEG1でも1GB強
そこから100分の1しても10MB、、フロッピーはどうしても無理が・・

>>384
（・３・） そこで夢の次々次世代スーパーフロッピーですYO

モデムもメディアも進化したってことだな
しかし、>>377のリンク先の会社のリンク、みごとに何も無いな・・・

>>383
あれは全部妄想でしょ。
応用って何？

>>387
「そういう技術があれば」から続く話だろ
妄想技術と、それがあると仮定した場合の話
妄想だから応用がないとでも言いたいの？

全てのデジタルデータが1/100になるならもう一回かければさらに小さくなるのかね・・・

ほぼって書いてある。
しかし、いまさらこんな古い記事を議論して何がやりたいんだ、おまいら？

>>388
それが実現可能な技術なら応用も有りだけど。
不可能な技術に応用はないだろ。

>>391
意味が無いといえばそらそうだが、
もしもの話をしているのはあの記事なんで
苦情ならそっちへ頼むよ

>>392
引っ張り出してきた >>377 はお咎め無しですか？

>>376
ごめん、*の方が正しかった｡すまそ。

圧縮アルゴリズムは，考えはじめるとキリがないんだよな……

どんなデータも
・利用するジェネレータの種類
・そのジェネレータへ与える値
・そのジェネレータが生成したデータを適用する位置
・ゞ 適用する長さ
・ジェネレータが適用できなかったノイズの値と位置
という 5 つのデータに変換できないだろうか？
つまり，元データを生成する命令群 (Midi みたいな感じ) になる．

・ジェネレータが適用できなかったノイズの値
・その位置
6つだった

>>395
あー、元データのバイナリ列を生成する有限状態機械表現によって
元データを表す(ことが圧縮になっている)って方法の一種かな。

どっかの学会誌で読んだことがあったような。
うーん、実用性とかまでは憶えてないな、すまん。

>>362
GCAって今はどうなってんの？

>>398
後継のDGCA Ver.1.00が先日公開されますた