- 1 名前：デフォルトの名無しさん [2006/04/26(水) 11:57:53 ]
- 2bit , 3bit , 5bit ずつに頻度を取る。
2bitがいい成績だったら2bitをひとかたまりにして
2ブロック、3ブロック、5ブロックで頻度をとる。
これを繰り返す。
- 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"
↑
でした。
しかもノートに答えが載ってました、はははは。(^^ゞ
…吊ってきます。
|
 |
