- 1 名前：デフォルトの名無しさん [2006/04/26(水) 11:57:53 ]
- 2bit , 3bit , 5bit ずつに頻度を取る。
2bitがいい成績だったら2bitをひとかたまりにして
2ブロック、3ブロック、5ブロックで頻度をとる。
これを繰り返す。
- 449 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 05:11:54 ]
- >>447
ハフマンよりレンジコーダーのほうが速くね？
- 450 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 06:33:23 ]
- >>449
いや、ハフマンの方が2,3倍速い。
Athlon64 X2 2.0GHzのマシンでRam Disk上で計測した場合、
ハフマン 60-80MB/s
レンジ 20-30MB/s
こんな感じ。
どっちもcで書いて結構チューニングしてる。
ファイルのi/oも含んでるから、
圧縮率の分だけ気持ちレンジコーダの方が有利かな。
LZとかなしで純粋に1byteずつ符号化した場合ね。
あ、上の数字は復号だよ。
符号化も同じようなもんだけど。
- 451 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 09:39:05 ]
- 上からモノ言ってる奴って他のスレでもそうだが、
自分から答えを教えるってことしないよな。
他人の非難は出来るけど、その実、自分で答えを
導き出せない、レベルの低い奴なのだろうか？
まぁ、2ch見てる程度の人間だから仕方がないかも。
他人の非難しかしない奴より、なんでもいいから、
自分の意見を述べる奴の方がましってのは、
どこにあっても同じだと思う。
- 452 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 09:56:47 ]
- まあ、なんだ、落ち着けよ。
こんな過疎スレで誰に言ってるのかよく分からんが。
- 453 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 10:05:33 ]
- コピペだ反応すんな
- 454 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 12:25:59 ]
- >>451
どこを縦読み?
- 455 名前：デフォルトの名無しさん [2007/02/04(日) 14:05:56 ]
- >>450
ハフマンのが速いって怪しいな。もしかして静的ハフマンか？
動的なら木の操作が入る分、ハフマンの方が不利だろ。
SSE2を使って最適化したレンジコーダがハフマンに劣ることってありえない。
一度チューニングしたそのコードを書いてみ。
- 456 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 02:09:26 ]
- 0圧縮
- 457 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 05:23:19 ]
- >>455
怪しいと言われても実測値だからねぇ。
もしかしなくても静的ハフマンだよ。
動的ハフマンなんて普通使わないでしょ。
木も使わないよ。
SSEは使ったことないから比較出来ないです。ごめん。
アセンブラあまり使えないし。
ただレンジコーダはSIMD化出来る部分が少ないはずなんだよね。
1bitにつき必ず一回は整数の乗算か除算が必要だしね。
ハフマンはシフトと表引きだけで済むからずっと速いはずなんだけど。
気になるなら実験してみて下さいな。
>450で出した数字より遅いなら最適化が十分でないですよ。
ただのハフマンならzip(deflate)やcab(lzx)と同じ位の速度がでるはず。
- 458 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 10:26:28 ]
- >>457
実測値が怪しいんじゃなくて、君の最適化が怪しいって事。
実測値でしか語らず、理論値で説明できないのは、どうして速いかという検証が君ができていないってことだ。
静的ハフマンならテーブル引き＋ストリーム出力でほぼ最速になるのは当たり前。
で、レンジコーダの方だが、こっちも静的でいいなら、少ない乗算でできる。テーブル引きとそうかわらん。
SSE2なら乗算平均1clock以下で演算できるから、ほとんど変わらない。
1bitにつきというが、一体どんなレンジコードなんだ？そんな馬鹿なことは普通はしない。
PPMとかのソース見たことないんじゃないの？
静的では若干ハフマンが有利な程度でほとんど変わらんし、
動的ではレンジコーダの方が圧倒的に上。
- 459 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 13:52:03 ]
- >>458
458さんのレンジコーダはそんなに速いの？
とりあえずハフマンは静的でレンジコーダは動的でいいよね？
最初からそのつもりで書いてたんだけど。
動的ハフマンとか静的レンジコーダってあまり見ないし。
正直SSE2はよく分からんのだけど(もうSSE4まで出てるんだっけ？)、
例えばアルファベットサイズが256ならシンボル確定するのに
8bit分の8回バイナリサーチするよね？
ここの部分が一番時間がかかってるはずなんだけど、
ここってそんなに速く出来るの？
いきなりPPMとか言われたりして、
どうも話がかみ合ってない感じなんだけど、
実験用のバイナリどこかに上げようか？
- 460 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:03:56 ]
- >>459
＞とりあえずハフマンは静的でレンジコーダは動的でいいよね？
ダメだろ。条件をどちらかに揃えないで比較するのはおかしい。
- 461 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:07:42 ]
- >>459
＞いきなりPPMとか言われたりして、
最強の圧縮アルゴリズムを語るこのスレなら、知っていて当然の基礎知識。
＞実験用のバイナリどこかに上げようか？
バイナリじゃなくて、問題箇所のソースを上げてくれ。
- 462 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:14:12 ]
- >>459
エンコードするのに、バイナリサーチする馬鹿は普通いない。
それとも「圧縮」の話から、「展開」の話に摩り替えてるの？
- 463 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:20:29 ]
- >>462
悪い俺が馬鹿だった。アンカーたどったら元は伸張の話みたいだ。orz
- 464 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:22:15 ]
- >>460
おかしいといっても実際動的ハフマンとか静的レンジコーダって殆ど使われてないし。
それにハフマンも動的と静的じゃ殆ど別のアルゴリズムと言って良いくらい違いがあるんだけど。
自分が言ってたのは一般的に使われてる静的ハフマンと動的レンジコーダなんだよ。
事実上この2つ以外を使うことってないと思うんだけど。
動的か静的かで条件を揃えるのって実用上無意味な比較なんじゃないのかな。
>>461
いやPPMは知ってるけどハフマンとかレンジコーダの話をしてていきなり
>PPMとかのソース見たことないんじゃないの？
とか言われても困っちゃうんだけど。
ソースは上げられません。ごめん。
>>462
自分が書いたのは
>>447,450,457,459で
>>442からの流れでデコードの話をしてるんだよ。
別に摩り替えてないと思うんだけど。
なんでそんなに攻撃的なのか分かりません。
もう少し落ち着いて話をしませんか？
- 465 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:50:31 ]
- >>464
＞おかしいといっても実際動的ハフマンとか静的レンジコーダって殆ど使われてないし。
動的ハフマンがあまり使われないのは、速度の劣化に対する圧縮率の向上があまりないから。
レンジコードだと動的にしても、あまり速度が遅くならず、圧縮率の向上が見られるから、動的で使うことが多いだけ。
＞自分が言ってたのは一般的に使われてる静的ハフマンと動的レンジコーダなんだよ。
でも速度比較するなら、どっちも静的にすればいい。その程度のこともできないの？
理解せずにレンジコーダをつかっているとしか思えん。
＞ソースは上げられません。ごめん。
なぜ？ビルドできなくてもいいし、部分的にでも上げる事が出来ない理由があるの？
- 466 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:52:53 ]
- >>464
＞事実上この2つ以外を使うことってないと思うんだけど。
そんなのアプリの用途の問題であって、アルゴリズムの比較とは何の関係もない。
実際、静的算術圧縮を使う事だって普通にある。
＞動的か静的かで条件を揃えるのって実用上無意味な比較なんじゃないのかな。
無意味じゃないよ。条件そろえないほうが無意味。
- 467 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:56:18 ]
- >>464
＞>PPMとかのソース見たことないんじゃないの？
＞とか言われても困っちゃうんだけど。
PPMのレンジコーダのコードは優秀。
- 468 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 15:00:54 ]
- なんか妙に絡まれてるけどなんでだろう？
やっぱり話がかみ合ってないんだよなぁ。
ソース上げろと言われてもその前にあなたが出してくださいよ、
という話になってしまうし。
私がヘボグラマーでレンジコーダの方が速いということで終了しましょう。
バイナリのアップは止めておきます。
- 469 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 15:03:31 ]
- >>467
どのPPM？
Dmitry Shkarin？
- 470 名前：お呼びじゃない? mailto:sage [2007/02/05(月) 15:07:12 ]
- PPMと聞くと、画像ファイルフォーマットか濃度かカントリーミュージックしか思い浮かばない漏れが来ましたよ。
- 471 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 15:08:15 ]
- >>465
アルゴリズムの実行効率の優劣を論じてるんじゃなくて、
＞ハフマン符号化よりも伸張のスピードが速いもの。
＞圧縮時のスピードは問いません。
＞伸張が早ければそれでよいです。
って話じゃなかったっけ。
>>45が勘違いしてエンコードの話始めてから話が変になったが。
- 472 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 15:58:28 ]
- >>468
＞なんか妙に絡まれてるけどなんでだろう？
静的と動的という、機能的に違うもので無意味な比較をしているから。
圧縮率無視すれば、ハフマンより速いレンジコーダだって書ける。
- 473 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:04:17 ]
- >>472
そんなに違わなくね？
圧縮展開って意味なら大差ないような。
ストリームに対応出来るかどうかとか？
- 474 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:11:49 ]
- >>473
全然違う。
静的なら頻度表が必要。動的なら不要。
出現確率の変化に動的なら対処できるが、静的では不可能。
- 475 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:17:25 ]
- >>474
ブロックに分割したらダメなのか？
- 476 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:18:23 ]
- >>474
それって単に多少の圧縮率の話ですよね。
それで「全然違う」かどうかは入力の性質次第かと思うが。
「機能的に違う」「全然違う」と言えるような差異としては
＞ストリームに対応出来るかどうかとか？
の方が適切なんじゃない？
- 477 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:21:05 ]
- まぁ、ストリームっても大概バッファリングするんだから
そんなに違いがあるとも思えないけどな。
- 478 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:32:25 ]
- >>476
静的も動的も、ストリームに対応するかしないかはどっちも一緒。
どっちもたいていブロックに分割した上で、対応する。
- 479 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:33:37 ]
- つまり動的か静的かはあまり意味がないってことか。
- 480 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:37:22 ]
- >>479
違うよ。
動的か静的かは、確率変動に対応できるかどうかという違いがある。
静的は展開が速いが無駄なデータが多くなるし、圧縮時は無駄なリードが発生する。
- 481 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:44:28 ]
- >>480
それって結局圧縮率の問題じゃね？
出現確率の変化の仕方次第じゃ動的な方が圧縮率悪かったりするよ？
それに動的だと出現しないシンボルが無駄になるんだよな。
エスケープ使うとますます遅くなるしな。
- 482 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 17:03:35 ]
- >>481
圧縮率無視するなら、そもそも圧縮なんかしないでいいだろ。
圧縮率が上がればその分読み込みも速くなるから無視は出来ないと思うが。
動的が圧縮率悪くなるわけではない。実装がタコだとそうなるけど。
理論値では動的のほうが必ず上になる。出現しないシンボルは、静的のテーブルの分で相殺できる。
静的に適したデータなら、動的が無駄に遅くなるという点は同意だが。
- 483 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 17:26:15 ]
- >>482
>圧縮率無視するなら、そもそも圧縮なんかしないでいいだろ。
べつにそんな事言ってないぞ。
ていうか圧縮率の問題は比較する上で静的動的と本質的に関係なくね？
>動的が圧縮率悪くなるわけではない。実装がタコだとそうなるけど。
いんや実装の問題じゃないよ。
どんな実装をしても変化を捉えられないケースは必ずある。
>理論値では動的のほうが必ず上になる。
逆じゃね？
動的だと任意の位置のシンボルの出現確率はそれまでの文脈から決定されるわけだから、
どのシンボルも常に確からしい確率を与えられるとは限らないでしょ。
静的だと区間における出現確率をあらかじめ調査するから、
その区間に限っては任意のシンボルは必ず確からしい確率が与えられるはず。
頻度表の分動的より悪くなることが多いと思うけど。
>出現しないシンボルは、静的のテーブルの分で相殺できる。
出来るとは限らないでしょ。
テーブルのサイズは決まってないわけだし。
作り方次第じゃ数バイトで済んだりするよ。
- 484 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 17:36:19 ]
- >>483
＞ていうか圧縮率の問題は比較する上で静的動的と本質的に関係なくね？
関係あるよ。これは確率論だから。
＞どんな実装をしても変化を捉えられないケースは必ずある。
その場合は静的と同じに出来る。動的の下限が静的なんだが。
＞動的だと任意の位置のシンボルの出現確率はそれまでの文脈から決定されるわけだから、
＞どのシンボルも常に確からしい確率を与えられるとは限らないでしょ。
＞静的だと区間における出現確率をあらかじめ調査するから、
ここまでは正解。
＞その区間に限っては任意のシンボルは必ず確からしい確率が与えられるはず。
ここが間違い。
例えば、区間内に「AAAA...AAAABBBB....BBBB」というデータが与えられた場合、
静的だとA、Bの確率が0.5になる。
シャッフルしたらエントロピーが上がり、情報量が下がることはわかると思うが、
静的では圧縮率に変化が起こらないことから、そういった要素を無視しているのはわかるよな？
＞作り方次第じゃ数バイトで済んだりするよ。
数バイトで済む場合、動的のほうの無駄も、同程度以下で済ますことが出来る。
情報量の計算すればわかることだが。
- 485 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 17:56:05 ]
- >>484
>ここが間違い。
>例えば、区間内に「AAAA...AAAABBBB....BBBB」というデータが与えられた場合、
>静的だとA、Bの確率が0.5になる。
ん？その区間の確率は理論上A,Bともに0.5で正しいはずだけど。
「ABABABAB...ABABABAB」も「AAAAAAAA...BBBBBBBB」も同じだよ？
どのシンボルも(AとBしかないけど)この区間においては確からしい確率が与えられてるでしょ。
極端な話「AAAAAAAAAAA」だけのデータは静的だと確率が1になるよね？ある意味ランレングス。
動的だと1/2, 2/3, 3/4, 4/5...n-1/nとなっていく訳だ。
で、極端な話0.9999999999になることはあっても決して1にはならない。
理論的には静的な方が良くなるのは分かるよね？
動的符号化は常に被符号語が未知であるが故に確からしい確率を与えることが出来ない。
>シャッフルしたらエントロピーが上がり、情報量が下がることはわかると思うが、
???
エントロピーが上がって、情報量が上がるの間違いだよね？
文脈次第では？
- 486 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:10:00 ]
- >>485
＞ん？その区間の確率は理論上A,Bともに0.5で正しいはずだけど。
「ABABABAB...ABABABAB」も「AAAAAAAA...BBBBBBBB」も同じだよ？
静的の場合はそうだが、動的の場合は違う。
動的の場合、前者は、ABともにほぼ0.5にでき、後者は、静的よりも効果的に圧縮できる。
＞動的だと1/2, 2/3, 3/4, 4/5...n-1/nとなっていく訳だ。
とは限らない。もちろんその手の変化があるという意味では正解だが、
その変化の仕方はタコなアルゴリズム。
＞で、極端な話0.9999999999になることはあっても決して1にはならない。
そうだよ。静的の場合その情報を頻度テーブルに書き込むわけだが、
動的の場合は、その差が動的な符号中に拡散するだけのこと。
＞理論的には静的な方が良くなるのは分かるよね？
理論的には、良くならない。
高圧縮のアルゴリズムはすべて動的になっていることからもわかるはずだが。
どうしても分からないなら、2値のモデルで検証してみることだ。
区間内に出現確率の変化がある場合、動的のほうが必ず良くなるから。
そして変化が無い場合でも、動的でも静的と同レベルに抑える方法があることがわかる。
＞エントロピーが上がって、情報量が上がるの間違いだよね？
エントロピーが上がる＝情報量が下がるだよ。
シャッフルしたら情報量が下がるのがわからん？
- 487 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:15:11 ]
- 「AAAB」
静的
A:3/4
A:3/4
A:3/4
B:1/4
-> 27/256 = 0.10546875
動的
A:1/2
A:2/3
A:3/4
B:1/5
-> 6/120 = 0.05000000
- 488 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:18:07 ]
- >>487
頻度テーブルの情報量を加えてごらん。
- 489 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:23:20 ]
- >>とは限らない。もちろんその手の変化があるという意味では正解だが、
>>その変化の仕方はタコなアルゴリズム。
どんな入力に対しても対応できる方法は存在しないよ。
>>高圧縮のアルゴリズムはすべて動的になっていることからもわかるはずだが。
残念。
それらは一般的な情報源に対して高圧縮率なだけ。
例えばPAQやPPM*よりLZが倍近く高圧縮になるケースが実在する。
- 490 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:25:19 ]
- >>489
＞それらは一般的な情報源に対して高圧縮率なだけ。
＞例えばPAQやPPM*よりLZが倍近く高圧縮になるケースが実在する。
だから、それは特殊な場合だろ。平均的には論理的に動的のほうが上というのがわからんの？
- 491 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:27:02 ]
- >>488
1bitでイイ？
- 492 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:29:06 ]
- >>491
どうやって表現するんだ？AAAAとAAABとAABBとABBBとBBBBが区別できないといけないだろ。
- 493 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:33:53 ]
- 以下の条件を満たすオープンソースの圧縮、伸張アルゴリズムはありませんか？
WEB上で公開されているものであれば良いです。
■条件
LZSS法、ハフマン符号化以外
（すでに所有しているため）
ハフマン符号化よりも伸張のスピードが速いもの。
圧縮時のスピードは問いません。
伸張が早ければそれでよいです。
- 494 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:33:58 ]
- だからよ、テーブルは任意サイズでもいいわけよ。
てことは少なくとも頻度表を除けば平均的な
区間圧縮率は静的な方が上なんだよ。
で、これにテーブルをどうするかって位の差なんだよなこれがさ。
最初から辞書として持っててもいいわけだ。
実際PAQとかDurilcaとかはテーブル持ってんだよね。
- 495 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:42:03 ]
- >>494
＞だからよ、テーブルは任意サイズでもいいわけよ。
誰もそれを否定していないが？
情報量から限界があるから、無駄をなくすことができるだけで、下限は情報量によって決る。
＞てことは少なくとも頻度表を除けば平均的な
＞区間圧縮率は静的な方が上なんだよ。
必要な頻度表を除けばというのはインチキだな。
最悪時の動的のロスもその程度だから、必要な頻度表を含めば動的も静的もほとんど変わらない。
しかし、区間中に確率の差がある場合、動的の方が理論的には良くなる。
＞最初から辞書として持っててもいいわけだ。
持っててもいいが、持っていなくてもいい。
- 496 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:49:29 ]
- >>493
ランレングス
- 497 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:03:14 ]
- だからさ頻度表は任意だから加えたらどっちが上かは
その時点で決められないんだよな。
>最悪時の動的のロスもその程度だから、必要な頻度表を含めば動的も静的もほとんど変わらない。
なら動的の方が良いとは限らないのでは？
>しかし、区間中に確率の差がある場合、動的の方が理論的には良くなる。
なぜ？
入力に対してどんなに対応を切り替えようが
動的である限り常に最悪のパターンは存在する。
どんなBitのパターンであっても同じだよ？
つまりどんな入力に対しても頻度表を除けば常に静的な方が圧縮率は上。
動的符号化は常に被符号語が未知であるが故に確からしい確率を与えることが出来ない。
最適な確率・符号長を与えられない時点で平均的には必ず静的より悪くなる。
その上でこれに加える頻度表は任意でいい訳よ。
どんな形で頻度表が作られるかは不明。サイズも不明。
だから動的が理論的に必ず良いというのはおかしいのさ。
そもそも頻度表が加わるから大きくなると言ってるけど
どんな形で頻度表を持たせるかは言及してないでしょ。
- 498 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:08:53 ]
- >>497
＞つまりどんな入力に対しても頻度表を除けば常に静的な方が圧縮率は上。
馬鹿。
- 499 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:11:32 ]
- >>498
馬鹿はないだろ馬鹿は。
でも間違ってないだろ？
- 500 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:13:40 ]
- いやでもこれが間違っているとなると
シャノンの情報理論も間違ってることになるんじゃ？
- 501 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:15:21 ]
- >>497
＞動的符号化は常に被符号語が未知であるが故に確からしい確率を与えることが出来ない。
＞最適な確率・符号長を与えられない時点で平均的には必ず静的より悪くなる。
間違い。
静的は全体で確率を求めるため、局所的な確率を効率よく求めることが出来ない。
最適な確率・符号長を与えられない時点で平均的には必ず動的より悪くなる。
静的なアルゴリズムを選択する場合でも、
ブロックにわけることで、擬似的に動的っぽい効果は得られるが。
- 502 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:19:43 ]
- 局所的な確率はどうやって求めんのよ？
どんな入力に対しても最適にする事は出来ないんだよ？
実装の問題とかじゃなくてさ。
- 503 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:21:46 ]
- >>502
＞局所的な確率はどうやって求めんのよ？
ベイズ推定
- 504 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:22:42 ]
- AAAB,AABA,ABAA,BAAA
これを動的符号化で期待値求めてみてよ。
- 505 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:26:07 ]
- >>504
A=aが1000個の固まり
B=bが1000個の固まり
に展開して、aとbで符号化してみたらどう？
- 506 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:28:11 ]
- 分かんないかなあ、次の文字が未知である以上
何やったって既知である静的符号化より区間平均が悪くなるのに。
特殊な情報源に強くする事は出来ても全般は無理よ。
- 507 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:37:17 ]
- >>505
母数を大きく取るのね。
500/1000
501/1001
502/1002
500/1003
0.062499813247569977380545675660332
大きくとるほどに変化に強くなる。
- 508 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:54:14 ]
- ああそうだ、動的の方が良くなるパターンに言及してなかったよ。
動的な符号化ってのはさ大体の場合、頻度の累計値が決まってんのよ。
で、一定期間(1bit毎でも)で頻度表を更新するんだけど、
これのおかげで静的で言うところの区間が可変になるんだな。
だからシンボルが連続したりすると圧縮率が良くなるんだ。
で、シンボルがランダムだと悪くなったりするんだ。
テキストとか所謂圧縮しやすい情報源だと偏りがあるから良く効くんだよ。
で、ランダムだと全然ダメだったりするんだ。
で、あらゆる全てのビットパターン(未知の情報源)をトータルすると
結局、静的符号化が上回るんだよ。
- 509 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 23:05:45 ]
- >>508
＞で、あらゆる全てのビットパターン(未知の情報源)をトータルすると
やっぱりお前は馬鹿だな。
全ビットのパターンをトータルするなら圧縮しない方が一番いい。そんなこともわからないのかよ…。
- 510 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 23:12:32 ]
- >>509
理論値を語ってるんじゃなかったんか。
- 511 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 23:14:22 ]
- >>506
じゃあ、君の考えだとPPM法を静的にした方が圧縮率が上がるということ？
そんなことやる奴なんていないと思うが。
- 512 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 23:15:54 ]
- >>510
全パターンなら、理論値だろうと実測値だろうと一緒だろ。圧縮しないのが最強だ。
- 513 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 23:26:12 ]
- >>511
頻度表を除けば理論上はそうなるよ。
まあ当たり前なんだけどさ。
頻度表をどうするかはまた別の話。
durilcaとかは自前でテキスト用に辞書をもってたりする。
実用上はもちろん頻度表は動的に作ることになるだろうけどね。
>>512
理論的に必ず動的が上だって言うからそれは違うだろって話をしてたんだよ。
究極的には圧縮しないのが最強なのは全くもってその通り。
可逆圧縮はただの変換なんだから、
どんなアルゴリズムを用いたとしても、
入力サイズ+圧縮したかしないかの1bitが最小の期待値になる。
n通りのビットパターンはn通りのビットパターンでしか表現できない。
- 514 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 23:47:50 ]
- 理論的に語るなら得意な情報源のみ取り出して上だというのは
おかしいだろという話なんだよ。
実際存在しうるデータってのはランダムの方が圧倒的に多いんだよ。
>>511
abcabcabcab
ときてabの次に何が来るか考えたら分かるよ。
cが来るだろうなと思って実際にcがきたとしても、
動的符号化はc以外の文字にも常に確率を割り当てなきゃならない。
既知であれば必ず最適な符号長が割り当てられる。
- 515 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:17:03 ]
- >>514
＞実際存在しうるデータってのはランダムの方が圧倒的に多いんだよ。
馬鹿だなー。実在するデータは、ランダムの方が少ないから、圧縮アルゴリズムが有効なんだよ。
- 516 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:19:38 ]
- >>513
何度も言うが、頻度表除いたらダメだろ。情報が頻度表に移動しているだけなんだから。
根本的に情報理論がわかってないんとちゃう？
- 517 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:30:46 ]
- >>514
＞動的符号化はc以外の文字にも常に確率を割り当てなきゃならない。
＞既知であれば必ず最適な符号長が割り当てられる。
それが違うんだな。既知であるためには、先行して情報が与えられている必要がある。
その情報の量と、動的の場合に確率を割り当てる量というのは、実は同じ。
しかし静的の場合、局所確率に適応できないため、原理的に最適な符号を割り当てることが出来ない。
圧縮率がシャッフルさせても変化しないというのは、
文字の前後との相関性の情報量を利用できていないということに他ならない。
圧縮というのは、出現の偏りによって圧縮するのであって、単なる出現確率だけよりも、
時系列情報（既出文字との相関性）の偏りを利用できた方が、一般的に圧縮率は向上する。
- 518 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:32:21 ]
- >>515
有効じゃないなんて誰も言ってないだろ。
理論的に話してるんだから考えうるデータは全部考慮しなきゃならんだろ。
>>516
>何度も言うが、頻度表除いたらダメだろ。情報が頻度表に移動しているだけなんだから。
それはそう。
だが動的にすれば常に理論上圧縮率が良くなるのは違うだろ？
頻度表をどう持たせてどう使うかはまた別の話。
そもそも動的にしたことで偏った情報源で圧縮率が良くなるのを
理論値だなんて言うからおかしくなるんだよ。
- 519 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:36:57 ]
- 局所的な確率が良くなっているのはワーストケースとの
トレードオフなんだよ。
圧縮率が良くなった時だけ見てるからそうなるんだよ。
よーく考えてみてよ。
理論上の話なんだから。
- 520 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:37:18 ]
- >>518
＞だが動的にすれば常に理論上圧縮率が良くなるのは違うだろ？
理論上、実際に使うデータでは平均的に圧縮率が向上する。
なお、現実と一致しないような理論は理論ではなく空論。
＞頻度表をどう持たせてどう使うかはまた別の話。
動的だってそれ専用の表に符号を追い出すことは出来る。
そんなもの切り離して考える方がどうかしている。
＞そもそも動的にしたことで偏った情報源で圧縮率が良くなるのを
動的にしたことで偏るんじゃなくて、偏りが抽出できるだけ。
始めから偏ったデータを使っているから圧縮アルゴリズムに意味が出てくるの。
- 521 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:38:22 ]
- >>519
理論上というのは、ランダムとか全パターンのことじゃないぞ。
根本的に何か勘違いしていると思われ。
- 522 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:42:58 ]
- >>520
なぁ、おかしくないか？
ワーストケースを考慮しないのが理論的なのか？
圧縮しやすいデータを対象にして話すのは結構だけど、
だったら理論て言葉はなしにするべきだろ。
実際tar化されたファイルとかで圧縮・非圧縮のが混ざってたりして
動的が不利になるケースとかもあるんだよ？
- 523 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:44:15 ]
- 最適な予測で符号を求める方法も、あらかじめ符号をもつのも、情報量的には実は同じ。
- 524 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:44:55 ]
- >>521
じゃあ理論上てのはどんなのだよ。
人それぞれ対象が違ったらそれこそ話が合わないじゃないか。
- 525 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:48:35 ]
- >>523
究極的にはそれはその通り。
だが符号表を除けば除いた残りの部分は必ず動的より良くなる。
当たり前すぎる。
動的が常に理論的に上ってのは間違い。
- 526 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:49:13 ]
- >>522
圧縮しやすいではなく、圧縮可能なデータ。いろいろな偏りが含まれていることが前提になる。
程度の差は様々でいいが、出現確率に差があり、相関性にも差があるのが、現実のデータ。
そういう差がないなら、それはただの乱数列であって、圧縮アルゴリズムを適用する対象外だ。
乱数であることを検出したら、圧縮しないで転送すればいいだけ。
動的でも静的でもいいが、不利になったりするのは、実装上の問題であって、情報の理論的な問題ではない。
- 527 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:49:53 ]
- 本来持っている情報量を下回る圧縮は出来ないってことだね。
- 528 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:51:21 ]
- >>525
＞だが符号表を除けば除いた残りの部分は必ず動的より良くなる。
除けばなんて話はしていない。合わせたら動的の方が良くなる。
静的で頻度表に全部符号を置けば、良くなるどころか０ビットに圧縮可能だが、そんなものは圧縮とは言わない。アホ過ぎる。
- 529 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:52:28 ]
- >>527
そういうこと。その中で、動的は時系列情報を利用できる。
- 530 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:54:03 ]
- >>526
>圧縮しやすいではなく、圧縮可能なデータ。いろいろな偏りが含まれていることが前提になる。
圧縮可能かどうかはアルゴリズム次第なんだって。
そんな前提条件があるなら先に言ってくれよ。
>そういう差がないなら、それはただの乱数列であって、圧縮アルゴリズムを適用する対象外だ。
じゃあ理論値て言葉はなしにしてくれよ。
- 531 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:55:44 ]
- >>529
時系列情報て、それは結局ワーストケースとのトレードオフなんだって。
- 532 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:56:20 ]
- >>530
理論値は理論値。確率や相関性を分散とかを適当に設定すればいいのであって。
全パターンというのは、そもそも圧縮を考える上で無意味なこと。
- 533 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:58:10 ]
- >>531
そんなことを言うなら、頻度表もワーストケースとのトレードオフだ。バカバカしい。
- 534 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:58:52 ]
- >>532
理論値てのは普通全部含めるだろ？
いい加減理論値って言葉はやめなよ。
特定の場合のみなら理論とはかけ離れてる。
- 535 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:01:29 ]
- >>533
バカバカしい、って理論の話じゃなかった訳？
あなたの理論は特定のアルゴリズムで圧縮できる
特定のファイルにのみ適用されるの？
- 536 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:06:48 ]
- >>534
＞理論値てのは普通全部含めるだろ？
含めないよ。偏りがないなら圧縮できないで終了だから。
n次相関がどれだけとか、分散がどれだけとか、偏りがあることが前提になる。
- 537 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:11:08 ]
- >>535
特定のアルゴリズムというわけではないよ。
現実のデータというのは、高次相関性があるわけ。
どんなアルゴリズムもその相関性を利用して圧縮を行う。
全次元で相関性が0なら、完全な乱数列であり、圧縮理論の対象外になる。
多かれ少なかれ、相関性があることが前提になる。
そして、その相関性を高次まで多く利用できるアルゴリズムが圧縮率が上がるということなの。
- 538 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:13:09 ]
- やっぱり根っこのところで考え方が違い過ぎて議論になってないね。
とりあえず前提条件も話さずに特定の場合のみ取り出して
「理論上は…」ってのだけは止めるべきだと思うよ。
- 539 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:18:31 ]
- >>538
理論上は静的の方が冗長な情報が含まれるから劣るんだよ。
シャッフルしたときとの差の情報が使われていないからね。
ただ、現実には理論値が出せないことがあるから、静的な方がいいこともあるだけ。
「情報量」で考えられないやつにはわからないかもしれんが。
- 540 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:20:18 ]
- >>537
無限にアルゴリズムが存在する中では高次相関とかは無意味なんだって。
完全な乱数列かどうかなんて判定は出来ないんだから。
全次元の判定なんて不可能でしょ。
というか理論と言う時点で全ての情報源は等価である事が前提だと思うんだけど。
- 541 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:29:29 ]
- >>540
＞全次元の判定なんて不可能でしょ。
だから、どれだけの次元を利用できるかということになる。
静的なら最低の相関性だけしか使わないが、
それ以上の相関性を利用できれば理論上、圧縮率が上がるのは当たり前なんだよ。
＞というか理論と言う時点で全ての情報源は等価である事が前提だと思うんだけど。
そんなんだったら、確率論も、情報理論もいらんがな。
これらは何らかの偏りがあることでしか意味がないから。
- 542 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:32:05 ]
- 一応断っておくがあなたの主張については
後だしの前提条件を踏まえる限りは概ね正しいと思うよ。
ただし議論するときは前提条件はきちんと提示するべきだね。
- 543 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:37:52 ]
- >>542
全パターンなんて基地外じみた条件こそ後出しだろ。
まともな情報理論で語るなら、そんなわかりきったことを持ち出して議論を無意味にしたりはしないのが普通。
- 544 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 11:42:47 ]
- 結局のとこ全パターン厨って何が言いたいの？
- 545 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 12:39:19 ]
- もう終わりにしろよ。
- 546 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 16:58:04 ]
- どうして情報源の設定をしないのだろうか。
エルゴード情報源くらいを仮定してみては？
- 547 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 23:20:22 ]
- >>541
理想論の放棄＝客観的なアルゴリズム比較の放棄
と同等だわな。
- 548 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 23:23:28 ]
- >>546
同意。
現代の圧縮アルゴリズム論は、もう情報源の設定が必須だな。
なんでも使える汎用アルゴリズムなんて、曖昧で議論も検証も不毛になりがち。
- 549 名前：デフォルトの名無しさん mailto:sage [2007/02/07(水) 08:42:10 ]
- Lempel-Zivについて。
"IM■ULM■UM■ULM■UND■UM■ULM■HERUM"をLempel-Zivで圧縮したらどんな風になるんでしょう？
↓ここでは最初に全部のアルファベット読み込んでるけど
ttp://en.wikipedia.org/wiki/LZW
上の例では無駄が多くなっちゃうよね？だから、動的に読むことにした。
自分で辞書とコードを作ってみたんで合ってるかどうか確認してやってください。
0 I
1 IM
2 M
3 M■
4 ■
5 ■U
6 U
7 UL
8 L
9 LM
10 M■U
11 ■UM
12 UM
13 M■UL
14 ■UL
15 ULM
16 LM■
17 M■UN
- 550 名前：デフォルトの名無しさん mailto:sage [2007/02/07(水) 08:43:09 ]
- 18 ■UN
19 UN
20 N
21 ND
22 D
23 D■
24 ■UM■
25 M■ULM
26 ■ULM
27 ULM■
28 LM■H
29 M■H
30 ■H
31 H
32 HE
33 E
34 ER
35 R
36 RU
- 551 名前：デフォルトの名無しさん mailto:sage [2007/02/07(水) 08:44:06 ]
- 原文字＝Lempel-Zivコード
I=0
M=2
■=4
U=6
L=8
M■=3
U=6
M■U=10
LM=9
■U=5
N=20
D=21
■UM=11
■UL=14
M■=3
H=31
E=33
R=35
UM=12
…どうでしょう？
- 552 名前：デフォルトの名無しさん mailto:sage [2007/02/07(水) 09:00:01 ]
- ja.wikipedia.org/wiki/LZ78
- 553 名前：デフォルトの名無しさん mailto:sage [2007/02/07(水) 09:15:44 ]
- >>552
ア、ナルほど。
1のIMや3のM■はもっと後にコード化されるみたいですね。
もう一度やってみます。
- 554 名前：デフォルトの名無しさん mailto:sage [2007/02/07(水) 09:36:59 ]
- 再挑戦です。今度こそ、どうでしょうか？
0 I
1 M
2 ■
3 U
4 L
5 M■
6 ■U
7 UM
8 M■U
9 UL
10 LM
11 M■UN
12 N
13 D
14 ■UM
15 M■UL
16 LM■
17 ■H
18 H
19 E
20 R
- 555 名前：デフォルトの名無しさん mailto:sage [2007/02/07(水) 09:37:45 ]
- 原文字＝コード
I=0
M=1
■=2
U=3
L=4
M=1
■=2
U=3
M■=5
U=3
L=4
M■U=8
N=12
D=13
■U=6
M■U=8
LM=10
■=2
H=18
E=19
R=20
UM=7
…合ってますか？
- 556 名前：549 mailto:sage [2007/02/07(水) 11:28:47 ]
- "IM■ULM■UM■ULM■UND■UM■ULM■HERUM"
ではなくて
"IN■ULM■UM■ULM■UND■UM■ULM■HERUM"
↑
でした。
しかもノートに答えが載ってました、はははは。(^^ゞ
…吊ってきます。
|
 |
