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