データ圧縮の究極

■ ２ちゃんねるは、ここのサーバを使ってるです。。。

　.jp ドメインお持ちのお客様大歓迎。maido3.jp
　.fm 取得代行します。(US) maido3.fm
　.ca 取得代行します。(US) maido3.ca
　.com .net .org 取得代行します。(US) maido3.com
　.cc .to .tv 取得代行はじめました。NEW

月々1,000円からの BinboServer.com

２ちゃんねるも使っている Big-Server.com

>> ２ちゃんねる、サーバ監視所

■掲示板に戻る■ ■過去ログ倉庫めにゅーに戻る■

1 名前： 名無しさん＠１周年 投稿日： 2000/11/05(日) 23:37: デジタルデータはニ進数で表した一個の数値とみることができるからある数式を
再帰的に計算してその数値にまで肥大させるようにする。
必要になる情報といえば数個の数式、停止段数の情報、素数分のずれ補填といったところ
現行のＰＣでどこらへんのファイルサイズまで扱えそうかな
2 名前： 名無しさん＠１周年 投稿日： 2000/11/06(月) 11:05: .
3 名前： 名無し人間 投稿日： 2000/11/06(月) 15:04: どういう形に持っていこうとも、結局はビットで０と１の並びになる。
並びの次のビットが予測できるうちは圧縮できるのだけど、
予測できなくなったところで、いくら再帰しても圧縮がかけられなくなる。

エントロピーがどうこういう証明がたしかあったはず。
4 名前： 名無しさん＠１周年 投稿日： 2000/11/06(月) 17:46: 　それだとマンデルやジュリア集合が大きなサイズの画像データに
なってるのを説明できないんじゃ……
5 名前： 名無しさん＠１周年 投稿日： 2000/11/06(月) 20:51: データを究極的に圧縮すると、それは乱数と区別つかなくなる。
っていう話をどっかで読んだな。ジョン・キャスティの本だっけか。
6 名前： 名無しさん＠１周年 投稿日： 2000/11/07(火) 00:06: 意味論を導入した圧縮の理論てどんなのがあるの？　ないか？
7 名前： 名無しさん＠１周年 投稿日： 2000/11/07(火) 08:40: なんかブリタニア百科事典を宇宙人が持って帰る方法って
たとえ話が在ったような
8 名前： 名無し人間 投稿日： 2000/11/07(火) 18:28: >>4
それはたまたま一方向の特定の値にでかくなる関数の話なのでは？
任意の画像だと逆方向に数値化できないのではないかと思うんだけど。

って、こういう調子で１の望んだ展開になってるんですかね？（笑）
9 名前： 名無しさん＠１周年 投稿日： 2000/11/07(火) 19:28: むかし「どんなプログラムでも9バイト(かそこら)に圧縮する」
ってインチキプログラムがあったな。ファイルを隠し属性に
して退避させるだけってやつ。その理論がふるっていて
「いままでに作られたプログラムは 10^9 より少ないから、
1つのプログラムに1つの数を割り当てれば、世界じゅうの
すべてのプログラムは 9バイトで表現できる」とかいうの。
あれにだまされるやつはいるのかしらん。
10 名前： 名無しさん＠１周年 投稿日： 2000/11/07(火) 20:59: LYEEなんぞをを使ってる連中はだまされそうだ >>9

ところで、「究極のコンパイラ」の話は知ってますか？　どんなプログ
ラムもこれ以上小さくできないくらいに最適化してしまうコンパイラが
あったとしましょう。あるプログラムをこのコンパイラにかけたところ、

0: jmp 0

というたった一行のアセンブリコードが出力されました。つまりこのプ
ログラムは「停止しない」ことがわかったわけです。うーむ。:-)
11 名前： 名無しさん＠１周年 投稿日： 2000/11/07(火) 21:45: >>9
それって NIFTY の FGAL のジョークソフトコーナーにあったような気がする。
12 名前： 名無しさん＠１周年 投稿日： 2000/11/07(火) 22:49: ６が言ってるのはどういうことかな。
13 名前： 名無しさん＠１周年 投稿日： 2000/11/07(火) 23:19: 単語の出現頻度や文法規則を考慮した、英文テキストの圧縮技法が
あったけど、もっとセマンティカルな情報をいれてもっと圧縮しよう
ってことなんでしょうかね。

画像処理のことはよく知らないけど、例えば人の顔の表情の変化の情
報をうまいこと特徴抽出して、テレビ電話なんかに必要な帯域を減ら
そうという研究はありますね。
14 名前： 名無しさん＠１周年 投稿日： 2000/11/08(水) 19:31: >6
たとえばjpegは意味論を持ってるといえなくもないと思うけど、
そういう話じゃないの? そんなこといったらハフマン符号
だって意味論を含んでいるとも言えるし、圧縮てのは結局
なんらかの意味論を持ってないとダメなんじゃないだろうか。
問題はその意味論が高水準か低水準かってことじゃないかな。
人間なんぞはめちゃくちゃ高水準の意味論を使って
何百ページもの物語を「圧縮」できるわけだし。
15 名前： 名無しさん＠１周年 投稿日： 2000/11/08(水) 23:04: あ、すいません、６です。１３が書いてるようなのでいいんですけど、
もっと極端な例を書いてみますと、

例１）
（圧縮前）１３本の赤白の横縞と紺地に白色の☆を５０個配列したものを
重ねあわせた画像　→　（圧縮後）「星条旗」（6バイト）

例２）
（圧縮前）「314159265・・・・・・・・・」（10^8バイト）　→　（圧縮後）「π一億桁」（8バイト）

こんな感じです。上の二例はすごく単純すぎる特殊例だけど、こういう
要素を取り入れることによって圧縮率を上げることができるという話です。
で、個人的には、こんなの理論化できないだろうと思ってるのですが、
だれか真面目にやってたら面白いなと思って、６で尋ねてみたわけです。

いかが？
16 名前：６投稿日： 2000/11/09(木) 01:25: １４で書かれてることも、おっしゃる通りだと思います。
で、その、人間レベルの高水準の意味論を利用するというわけで、
結局、「情報量」って突き詰めれば何なのかということです。
Shannonがすごくきれいな理論を構築した代償に、捨象したものです。
17 名前： 名無しさん＠１周年 投稿日： 2000/11/09(木) 05:51: >15
それは情報を圧縮しているのではなくて、
情報に対するポインタを作っているだけでは？
18 名前： 名無しさん＠１周年 投稿日： 2000/11/09(木) 12:50: >>15
流れからはずれるのは承知であえて書くと、もっとマトモな例をあげてほしい。

１．例１は、赤白紺の色情報、画像のサイズ、ストライプや星のサイズ等が
無くなっているので、非可逆なんですけど？
２．例２は、文字コードや文字列であること等が無くなっているので、
非可逆なんですけど？
３．両方の例は圧縮されているという情報が無くなっているのですか？

情報を捨てていいのなら、いくらでも圧縮できると思うよ
19 名前： 名無しさん＠１周年 投稿日： 2000/11/09(木) 14:23: 15が書いているのは圧縮というより「解釈」って感じだな。
ここまでのことをやらせるにゃ、ありとあらゆる一般知識を
計算機に教えこまねばいけんぞ。今のところは(つうか、とーぶん)ムリそうだな。
そんなのより、もうちょっと目的を絞った非可逆圧縮の話をしたほうがおもしろいと思うよ。
物語の圧縮とか楽曲の圧縮はだれかが手をつけてそうだな。水戸黄門のシナリオなんか毎回パターン同じだから、かなり圧縮率高いんじゃない(藁
20 名前： >19 投稿日： 2000/11/09(木) 14:33: ゴルゴ１３はやたら圧縮率高そうだな。わら
21 名前： 名無しさん＠１周年 投稿日： 2000/11/09(木) 14:38: というか、１５はコーディングです。
22 名前：６投稿日： 2000/11/09(木) 14:45: >18
えー、そういうレスはあるかなと思いましたが、そこは本質じゃないんで…
可逆にするために、色情報、サイズ情報、「文字列であること」等必要な情
報をつけ加えてもＯＫです。

>17
「圧縮」の定義の問題になってきますね。
従来の圧縮も、冗長性を利用した決め事を前提としていて、その決め事は
予め了解しあうことによって伝達不要であるという意味で同じ。
23 名前： 名無しさん＠１周年 投稿日： 2000/11/09(木) 17:10: ↑
ならば解凍、あるいは復号化の際に参照すべき辞書のサイズも考えなくちゃね。
データ本体とは別に予め配布されているなら別だけどね。
24 名前： 名無しさん＠１周年 投稿日： 2000/11/09(木) 18:48: 例１）
（圧縮前）１３本の赤白の横縞と紺地に白色の☆を５０個配列したものを重ねあわせた画像
（圧縮後）赤白の横線数本に☆が数個だったかなぁ。後は書いてみてからバランスよく数をあわせよう。

例２）
（圧縮前）「314159265・・・・・・・・・」（10^8バイト）
（圧縮後）とりあえず３．１４１５９ぐらいだけど、精度が気になるならこれは使わずに、他から正確なデータをとってこよう。

人間の場合こんな感じじゃないのかなぁ。
可逆圧縮は無理だけど、データの正確さがそれぞれのデータに含まれており、
精度にあわせたデータのポインターを持っているって感じ。
で、参照先が本だったり語呂合わせ的な記憶だったりするのでは？

まぁ、正確さが求められるコンピュータには役に立たない圧縮だな。
25 名前： 名無しさん＠１周年 投稿日： 2000/11/09(木) 20:42: 円周率は、それを任意の桁まで求めるプログラムによって
完全に表現できるじゃん？
これこそ、究極の圧縮。
26 名前： >25 投稿日： 2000/11/09(木) 20:56: 確かに圧縮率は飛び抜けて良いが、復元速度が鬼のように遅ぞ。
27 名前： 名無しさん＠１周年 投稿日： 2000/11/09(木) 21:14: えーと、たしか情報の複雑さを、
「そのビット列を生成し停止するようなチューリングマシンの
最小状態数」で定義するってのがあっただろう。
(復元プログラムも入れると)それ以上の圧縮は不可能って状態に
なる。それが究極的に圧縮した情報じゃないかな。
28 名前： 名無しさん＠１周年 投稿日： 2000/11/10(金) 01:27: >>25
具体的にどうやるの？
不勉強ですまんです。
29 名前： 名無しさん＠１周年 投稿日： 2000/11/10(金) 01:29: pentiumってπをあつかう演算をもってなかったっけ？
30 名前： 名無しさん＠１周年 投稿日： 2000/11/10(金) 04:40: 情報エントロピーと熱エントロピーの関係について解説者求む
http://cheese.2ch.net/test/read.cgi?bbs=sci&key=972917510
31 名前： 名無しさん＠１周年 投稿日： 2000/11/10(金) 20:38: 円周率は、級数展開（数列の無限和）で表すことができます。
コンピュータでは無限は扱えないので、
和の計算を有限個の項で打ち切ったり、各項を有限の桁数で評価することになります。
しかし、円周率の真の値との誤差を評価できれば、コンピュータで計算した結果は
ある桁までは正しいと考えることができます。この誤差は、より多くの項を計算したり、
より多くの桁数まで評価することによって、いくらでも小さくできる性質のものです。
すなわち、理論的には誤差はいくらでも小さくできます。

「誤差をいくらでも小さくできるだけでは、真の値などわからないではないか」
という意見もあるかもしれません。しかし、実数とは所詮そういうモノです。。
32 名前： デデキント 投稿日： 2000/11/10(金) 20:58: 神の造りたもうた自然数をバカにしてる奴は逝って良し!
33 名前： 名無しさん＠１周年 投稿日： 2000/11/10(金) 21:10: >>28
1-(1/3)+(1/5)-(1/7)+(1/9)-... でもπ/4になるよ。
めちゃくちゃ収束遅いけど。もっと速いのが知りたければ
「ラマヌジャン」「円周率」かなんかで検索エンジンしな。
34 名前： 名無しさん＠１周年 投稿日： 2000/11/11(土) 20:15: 自然数を作ったのは人間だろ。宗教板にでも逝ってな。
35 名前： 名無しさん＠１周年 投稿日： 2000/11/13(月) 18:10: >31,33
初めて知りました、ありがとです。もっとよく調べてみます。

とりあえずageとくね。
36 名前： つーか 投稿日： 2000/11/13(月) 18:33: 33のテーラー展開なんて高校生でも知ってるぞ。>35
37 名前： 名無しさん＠１周年 投稿日： 2000/11/13(月) 23:26: >36
そうか？記憶になかったけど忘れてただけか？
まぁ、知らなかったとしても、今知ったからそれでいいや。
38 名前： 名無しさん＠１周年 投稿日： 2000/11/14(火) 00:08: 究極の可逆圧縮理論はやはりマルコフ符号化になるんでしょうか。
39 名前： 名無しさん＠１周年 投稿日： 2000/11/14(火) 14:15: このπの例って算術圧縮の特殊ケースに過ぎないとなぜ気付かないの？
40 名前： >39 投稿日： 2000/11/16(木) 19:39: リファレンスデータとしてπの値を使うんじゃないの？
41 名前： 名無しさん＠１周年 投稿日： 2000/11/27(月) 22:24: 遅延評価を使えば無限のデータを完全に表現しつつ、必要なだけ（有限）取り出せます。
42 名前： 名無しさん＠１周年 投稿日： 2001/03/18(日) 20:03: age
43 名前： 名無しさん＠１周年 投稿日： 2001/03/18(日) 22:56: >>39
まんま算術圧縮ですね。
ところで、ローリング圧縮って誰か
知ってますか？以前どこかのＨＰにあって絶賛して
たんだけど、行方が分からなくなって。
ぜひ知りたいです。つかいてー。
44 名前： 名無しさん＠１周年 投稿日： 2001/03/24(土) 03:39: >>1
フラクタル圧縮に似てますね
45 名前： 名無しさん＠１周年 投稿日： 2001/03/24(土) 07:41: >>6
もっと単純に考えればいいんじゃない?
ある情報を圧縮する側をA、その圧縮データから元の情報を得る側をBとし、
圧縮データのやりとりをAからBへの通信と考える。
んで、>>15の例1の場合について考えると、
Bはすでに通信(圧縮データのやりとり)前に「星条旗とは１３本の赤白の横縞と
紺地に白色の☆を５０個配列したものを重ねあわせた画像である」
ということを知っている(先験情報として持っている)わけだから、
通信前後のBの情報量の変化は「元の画像は星条旗である」って
評価できることになる。
だから、情報量の変化(=先験情報と圧縮したい情報との差分)を
どう評価するかって問題はあるにせよ、従来の情報量に関する理論と
なんら変わることはない。

あと、ついでに言えば、非可逆性を認める圧縮(有歪み圧縮)ってのも
通信路符号化の双対な問題であることがよく知られているから、
これも結局シャノン理論の単なる延長でしかない。
人間(でなくてもいいのだが)の先験情報をどう評価するかとか、
人間にとって違和感のない有歪み圧縮とはどういうものかってのが
わかりにくいからシャノン理論との関連が見えにくくなってるだけでしょ。
46 名前： 6 投稿日： 2001/03/24(土) 09:43: >>45
うん、俺も、Shannonの通信理論の上にのってるってことは、全然同意。
ただ、もし、そこから一歩踏み出した領域で理論化できたら面白いのに
な、と思ったんだ。

>だから、情報量の変化(=先験情報と圧縮したい情報との差分)を
>どう評価するかって問題はあるにせよ、
結局、その部分をエレガントに説明できるかどうかです。聞きたかったのは。
47 名前： 提供：名無しさん 投稿日： 2001/03/24(土) 17:25: コロモゴロフ複雑度(Kolmgorov Complexity)を勉強するといいよ。
48 名前： 名無しさん＠１周年 投稿日： 2001/04/03(火) 15:18: あ・げ
49 名前： 名無しさん＠東京地裁 投稿日： 2001/04/03(火) 20:49: bzip2マンセー
50 名前： いつも上手く行ってる圧縮方法（文系） 投稿日： 2001/04/03(火) 23:53: 私のデータ圧縮の方法↓。

１）テキストFileなら斜め読みして口伝で伝える。
　　　[例]「鏡の中から女神が出てきて主人公に惚れてくれるの。」

２）画像ファイルなら、じっと眺めた印象を伝える。
　　　[例]「額にチクワの輪切りが貼り付いてる感じのヤツ。」

日常業務で大抵うまくいってるョ。
51 名前： 名無しさん 投稿日： 2001/04/07(土) 16:31: 量子情報的圧縮。すべての情報が同一の大きさで表現できるさ。
52 名前：投稿日： 2001/04/07(土) 20:13: >>25
プログラム実行環境っていう外部記憶に頼っているだろ。
小説のタイトル教えているのと同じ。

情報理論で「記憶のない通信路」って概念勉強しよう。> 分からない人
53 名前： 名無しさん＠１周年 投稿日： 2001/04/09(月) 04:33: ↑
>プログラム実行環境っていう外部記憶に頼っているだろ。
>小説のタイトル教えているのと同じ。
意味不明
54 名前： 名無しさん＠１周年 投稿日： 2001/04/09(月) 10:42: >>51
量子情報的圧縮って何ですか
>>52
意味不明

>>25
可算無限個の手続きで記述できる無理数は実数全体に比して圧倒的に少ないので
一般的な記号列の圧縮はできないと思うけど、情報源の「その生成アルゴリズム
への」圧縮って、どこまで研究が進んでるのかなあ？
55 名前： 名無しさん＠１周年 投稿日： 2001/04/21(土) 00:51: 量子情報圧縮って　もしや全ての情報が１ｑｂｉｔで表せるとか（ｗ
圧縮は出来てもデコードはどうやってするんだ？
56 名前： 名無しさん＠１周年 投稿日： 2001/04/21(土) 04:58: ベクトル量子化を使った圧縮とは違うの？
57 名前： 名無しさん＠１周年 投稿日： 2001/04/23(月) 01:57: ベクトル量子化って何？
AD変換？
58 名前： 名無しさん＠１周年 投稿日： 2001/04/23(月) 05:08: ＞５７
画像符号化の本を参照されたし。
ＡＤ変換じゃないよ。
59 名前： 名無しさん＠１周年 投稿日： 2001/04/23(月) 12:49: >>55
たまたまうまく復号化できた世界線以外は熱死かなにかで
壊れてしまうような仕組を考えればよいのでは？
ちょっと大げさすぎるかな。
60 名前： 非決定性名無しさん 投稿日： 2001/06/11(月) 12:03: 学術ａｇｅ
61 名前： 非決定性名無しさん 投稿日： 2001/06/11(月) 17:32: 単なる思いつきですが、カオス圧縮ってのはどうでしょう？

有限長の数列を一意に表現できる＝ファイルを表すこと

と考えると、表現できる式のパラメータと、数列の列の数がわかれば
ファイルを復元できるかなと。

とーぜん圧縮展開時間は鬼のようにかかりますよ（ｗ

２ちゃんねるは、ここのサーバを使ってるです。。。