【2ch】圧縮アルゴリズム【オリジナル】
レス数が950を超えています。1000を超えると書き込みができなくなります。
0001１
NGNG中途半端に圧縮されて拡張子が.2ch
0942デフォルトの名無しさん
NGNG数学的に…、って意味じゃないのかねぇ。
Shannon limit (てかエントロピー？)って可逆圧縮と不可逆圧縮の絶対境界線だっけ？
0943デフォルトの名無しさん
NGNG＞Shannon limit (てかエントロピー？)って可逆圧縮と不可逆圧縮の絶対境界線だっけ？
無歪み圧縮は、Shannon限界までしか圧縮できないことが数学的に証明されていますね。
有歪み圧縮もShannonのレート定義が重要ですしね。
ま、何にしろ通信と圧縮はShannonが創生したしたわけで。
0944デフォルトの名無しさん
NGNG限界はあるけど、それを計算するアルゴリズムは存在しないってゆーよーな。
→ Shannon limit は計算できない（から議論してもしゃーない）!?
# うろ覚えスマソ
0945デフォルトの名無しさん
NGNGそれは一般情報源についてかな。
Shannon limit は定義だから。
H(P) = - p_i log p_i, p_i in P
0946デフォルトの名無しさん
NGNG2ch みたいに繰り返しの多い入力に対する圧縮の限界も評価できる
んすか？
0947デフォルトの名無しさん
NGNGあるモデルを想定して、そのモデルの下でのエントロピー達成度を調べることで評価される。
もしすべてのモデルについて評価できるならば、
全体の評価が出来るわけだが、すべてのモデルを評価できないので、
特定のモデル（LZ77, LZW, ブロックソート法, などで考えるとよい）などを使うわけだ。
どちらにしろ、>>945の式H(P)よりも小さくはならない。
0948デフォルトの名無しさん
NGNG情報源によってエントロピーが異なるから、
シャノン限界（945 も言ってるけど定義なので値は前提によって異なる） も変わる。
参考：
炉辺夜話
http://www.ne.jp/asahi/personal/kobayashi-osamu/Writings/Essays/BF.13.html
http://www.ne.jp/asahi/personal/kobayashi-osamu/Writings/Essays/BF.14.html
2ch がテンプレだけで構成されていると考えて、
特定のテンプレの出現頻度が高い、と単純化して考えれば分かりやすいと思う。
英文で特定のアルファベットの出現頻度が高いのと同様になるから。
日本語のエントロピー、歌の歌詞のシャノンエントロピー、
新聞文章のシャノンエントロピー、2ch 文章のシャノンエントロピー…
はどのように異なるかという話になる。
適当な数をサンプリングして計算すれば圧縮限界の理論値も出せるかと。
0949デフォルトの名無しさん
NGNGそ、それは理論値ではなく実測値（実験値）では・・・
理論値は数学的に証明できるものでないと。
つーか、一般情報源に対する理論値を証明できたらチューリング賞ものですね。
0950デフォルトの名無しさん
NGNG0951デフォルトの名無しさん
NGNG謝りついでに、次スレあけおめことよろ
0952デフォルトの名無しさん
NGNGできない(理論値などでない)ことがわかっている。
対象物を限定すれば、特定のものを1ビットに圧縮できる一方、
限定しなければ(あらゆるデータが一律に出現する)、
圧縮など不可能で、無意味だから。
圧縮とは、存在しそうも無い膨大な種類のデータでは大きくなるかわりに、
ごく一部のデータだけを小さくする技術。
0953デフォルトの名無しさん
NGNGん？ そんなことはないですよ。
最近は韓先生などが、一般情報源に対する漸近的圧縮限界を証明されました。
これには情報スペクトル理論が用いられています。
0954デフォルトの名無しさん
NGNGhttp://www.i.u-tokyo.ac.jp/mi/staff/yamamoto-j.html
論文を当たってみてください。
0955デフォルトの名無しさん
NGNG論文読まないとなんともいえないが、この場合「一般情報源」に特殊な偏りがあるんだろうね。
でなければ、圧縮は不可能であることは自明。
明確な偏りがある場合、対象としているデータと濃度が決まれば理論値は簡単に出る。
一つのデータを一個の巨大な整数値とみなし、その出現確率を使って
算術圧縮した時のビット数が、圧縮率の限界になる。
もちろんこれは理論値であって、実用にはならないが。
0956デフォルトの名無しさん
NGNGhttp://www.hn.is.uec.ac.jp/~han/Spectrum-preface.html
0958デフォルトの名無しさん
NGNGつうか、単に確率分布があるだけで。
それに見合った符号化（サイズの増減は確率分布による）ができるわけで。
その確率分布の特性にエルゴード性や、定常性が存在するか否かが、
一般情報源かどうかを区別しているわけですね。
0959デフォルトの名無しさん
NGNG>>957
>>958
サンキュー。予想通りだった。つーかこれ当たり前のことで、ある尺度で捉えた場合の
理論的限界は求まっても、真の限界はわかんないよ。
例えば、π１００万桁の数値を圧縮するとする。これを乱数列と見なした場合の限界は
この方法で求まるが、πを数ビットに、他のものを多少増やす圧縮方法もあるわけ。
0960デフォルトの名無しさん
NGNGえっと、それはたぶん何を語っているかの方向の違いですね。
何を目的として情報源符号化を語るかを注意しないといけないということには、同意です。
他の方（特に初学者）に注意しておいて欲しいのは、次のこと。
すべてのデータを圧縮できる符号は存在しない、は、真です。そして
一般情報源の理論的限界を達成するような符号は存在する、も、真です。
0961デフォルトの名無しさん
NGNG＞この方法で求まるが、πを数ビットに、他のものを多少増やす圧縮方法もあるわけ。
それは一般情報源の符号化ではない
0962デフォルトの名無しさん
NGNG>>961
でも、漏れ達の周りのデータって「一般情報源」から外れるものばかり
テキストも音楽も画像も単なる「一般情報源」では無い罠
0963デフォルトの名無しさん
NGNG>>962
いや、パイのデータを短くするような符号化法は、
最適な符号ではないことは確かだが、一般情報源の符号化であることに違いはないだろう。
最適な符号は、パイだったらパイのエントロピーに符号化する。
（パイのエントロピーはほぼランダムなものと同程度であるらしいから）
テキストや音楽のデータは、一般情報源からの出力と考えられる。
したがってその確率分布が圧縮しやすければ圧縮になり、
ランダムならば圧縮にならない。
0964デフォルトの名無しさん
NGNG最適な符号で無いのに、πのエントロピーに符号化するのがなんで最適な符号になるの？
それはあくまで、乱数列と見なした場合のことだよね。
そうでない方法、「π６５５３６桁」みたいに圧縮する方法もある。
0965デフォルトの名無しさん
NGNG最適な符号とは、あらゆる入力に対して、そのエントロピーまで符号化できる符号。
一方、特定の入力を短くするのは、最適でない符号。
で、パイを符号化するために「パイｎ桁」とするのは、実は「符号」ではない。
それはモデル化だな。
他にも、
この楽曲は「ｘｘ交響曲」である、というような上の方で議論のあった、
音楽データのMIDI化みたいな符号化法も、実はモデル化ということ。
で、パイ＝3.1415926535...
という数値そのものをたとえば２バイトで表現するとか、
そういった「符号」を考えるならば、最適ではない符号ということで。
0966デフォルトの名無しさん
NGNG> テキストや音楽のデータは、一般情報源からの出力と考えられる。
> したがってその確率分布が圧縮しやすければ圧縮になり、
それだけじゃないってことを言っている。例えば、
「観自在菩薩行深般若」の後、何がくるか圧縮できるでしょ？
確率分布だけで圧縮する以上の方法があるの。
音楽もそう。一定のリズム、人間が作る音楽の特性、そう言ったものを取り入れるか、
入れないかで、最適な符号なんて変わってしまうよ。
画像もウェーブレットを使った高次元の処理をすることで、1次元のデータ列とみた場合とは
結果が変わってくる。
0967デフォルトの名無しさん
NGNGえーと多分>>965を読む前に書かれたと思いますが、一応>>965の追記も兼ねて。
データ圧縮（情報源符号化）は、次の要素からなっています。
モデル化 ＋ 確率推定 ＋ 符号化
用語の使い方の問題かもしれませんが、一般に「符号化」といった場合は、
すでに確率が与えられている場合のみの操作を表します。
たとえば、符号化の族には、Huffman符号や算術符号、が入りますが、
LZ77やPPMなどは「符号化」ではありません。
またHuffman符号などで、記号の頻度を求める前処理がありますが、
それもモデル化であり、純粋にHuffman符号といった場合には、
すでに確率が与えられている必要があるわけです。
＞「観自在菩薩行深般若」の後、何がくるか圧縮できるでしょ？
＞確率分布だけで圧縮する以上の方法があるの。
したがって、続く文字列を推定するのは「モデル化」
モデル化によって得られた知識から、確率を算出するのが「確率推定」、
得られた確率をビット列に変換するのが「符号化」です。
0968デフォルトの名無しさん
NGNGモデル化を考えない符号なら、そのデータの存在確率で算術圧縮するのが
最適で、とっくに解決している。
現実のデータの圧縮を考えるのなら、モデル化は避けられないし、
乱数列と見なすのも一つのモデルに過ぎない。
で、漏れは、乱数列と見なすこと自体が最適でないと思うわけ。
乱数列と見なした場合は、そのデータの存在確率で算術圧縮すればいいと思うわけ。
0969デフォルトの名無しさん
NGNG0970デフォルトの名無しさん
NGNG0971デフォルトの名無しさん
NGNG0972デフォルトの名無しさん
NGNGモデルが異なれば、限界も異なるはず。
で、どのモデルが適当かを決める一般的なアルゴリズムは存在しない(>>944)?
モデル化できなければ、確率推定もできないし、エントロピーも計算できないし、（最適）符号化もできない(>>967).
今ある圧縮符号は、思いつきで決めたモデルに基づく最適符号にすぎないから、もっといろんなモデルを考えよう(>>964,>>966)!
…という理解でよろしいでしょうか？
0973デフォルトの名無しさん
NGNG>>972 どのモデルが適当かを決める一般的なアルゴリズムは存在しない
これって正しいんでつか?
0974デフォルトの名無しさん
NGNG0975デフォルトの名無しさん
NGNGちうよりは、情報量をつきつめていくと、単体では確率など存在しなくても、
各記号の出現確率に基づくShannon限界への漸近式が得られるという。
たとえば、LZ78法などは確率を一切、陽に用いていないにも関わらず、その冗長度は、
H(P) + O(loglog n / log n)
となるわけでつ。
0976デフォルトの名無しさん
NGNG0977デフォルトの名無しさん
NGNG0978デフォルトの名無しさん
NGNG0979デフォルトの名無しさん
NGNG0980lo;デフォルトの&lro;名無しlo;さん
NGNG0981&rlo;デフォルトの&lro;名無し&rlo;さん
NGNG0982デフォルトの名無しさん
NGNGLZ78が必ずしも得意としていない無記憶情報源（各p_iが独立）モデルで評価した場合はそうなりまつが、それではLZ78の実力は測れないでじょ?
0983デフォルトの名無しさん
NGNG0984デフォルトの名無しさん
NGNG0985デフォルトの名無しさん
NGNGttp://hirosuke.sr3.t.u-tokyo.ac.jp/pdfs/ibis2001.pdf によれば、
冗長度 O(loglog n / log n) になるのは LZ77 の有限次数マルコフ情報源に対して。
LZ78 の冗長度は O(1 / log n) らしい。
0986デフォルトの名無しさん
NGNGそのプログラム（もし載ってたら）が詳しく載ってる書籍ってご存知ないですか？
興味があるのでちょっと勉強してみたいのですが、なかなか見つからなくて・・・・
ＨＰでもいいのでもし知っていたら教えてください。
スレ違い質問すいません ＞＜
0987デフォルトの名無しさん
NGNGLZ77/LZSSの場合、符号化されたトークンは
(スライド辞書内のインデックス+文字長)を現している。
で、これが12+4ビットで、が3〜18文字長を示す場合、
18バイトまでの文字列が16ビット=2バイトで置換できる
ことになる。従ってこのケースの最高圧縮率は1/9よね?
同様にトークンのビット数を増やしていって得ることができる
圧縮率を見ていって、方程式を導き出したのが(以下略)
LZ78/LZWの場合は、あるトークンは以前に出現した別の
ふたつのトークンまたはリテラル文字を結合した文字列を意味している。
この階層化されたトークンをすべて展開すると、リテラル文字を葉に持つ
二分木構造を持っていることが解かる。この木を作るには
根(現在のトークン)の左右の子が既知でなくちゃいけないから、
以前のトークンとは現トークンの1/2の情報量(葉)を持っている。
こうして葉に至るまで分解して並べると、出現する根の数(＝圧縮結果)は
全体の葉の数(＝圧縮源)の O(1 / log n) 以下にはなりえない。(合ってる…?)
0988デフォルトの名無しさん
NGNGあったけど潰れた.
第三の脳室ってとこ.
0990デフォルトの名無しさん
NGNG0991デフォルトの名無しさん
NGNGレス数が950を超えています。1000を超えると書き込みができなくなります。