可逆圧縮で1/100に

masamic 曰く、 "ZDNetの「100分の1以下を実現するデータ圧縮の新技術」によると、米国の企業と数学者グループが、情報の欠損なしに圧縮・展開する技術理論を発表した模様だ。 単調な（アニメなど）の絵や情報の欠落が発生するJPEG圧縮であれば、数十分の１まで圧縮することが可能であるが、今回の理論ではランダムなデータ列を１００分の１に圧縮し、完全に再現することができるらしい。 本当にできるのだろうか？"

これだけの圧縮率 (しかも可逆) が実現されればすごいが、 気になるのはパテントの問題。 無料でとは言わないが、安価に使えるようにして欲しいところだ。

現在の情報理論の常識から言えば

[Vorspiel (2391)]

完全にランダムな乱数列を100%確実に可逆圧縮する方法は絶対にありえない(圧縮量が1/100どころかたった1bitであっても!)と記憶しているんですが，私の理解が間違ってるのか，それとも理論に穴があったのか．
しばらくは眉にツバをつけて見てたほうがいいかも．理論もまだ公開されてないわけだし．

Re:現在の情報理論の常識から言えば

[zeissmania (3689)]

完全にランダムならば、その中に情報は含まれないはずです。情報を含んだデータ列には必ず規則性が存在します。

Re:現在の情報理論の常識から言えば

[nsawa (497)]

元記事のニュアンスから推測するに、「ランダムなデータを1/100に」というのは言葉のアヤで、
「ネットワーク上でやりとりされるデータをランダムに抽出したところ、平均1/100の圧縮率」
で可逆圧縮できる方法を編み出したのではないかな、と思います。
もしそうだとすれば、それはそれで素晴らしいことです。

Re:現在の情報理論の常識から言えば

[Anonymous Coward]

フェルプス君やジェームズ・ボンド君に教えて上げてください。

「君が命懸けで入手しようとしている某国スパイの乱数表だが、 そんなものには元々情報は1bitも含まれていないんだ。 上司に白紙の報告書を出せば仕事は終わりさ」

特にボンド君は、残りの上映時間をすべて美女と楽しめることに大喜びするでしょう。

Re:現在の情報理論の常識から言えば

[Ryo.F (3896)]

ウソですね＞情報を含んだデータ列には必ず規則性が存在。

ていうか、もう少し詳しく説明してもらわないと、
何を言いたいのか理解できません。

Re:現在の情報理論の常識から言えば

[zeissmania (3689)]

＞何を言いたいのか理解できません
圧縮が可能なデータ列なら「完全なランダム」ということはあり得ないということです。だから圧縮された元データは
「一見ランダムに見えるだけで、厳密には完全なランダムなデータではなかった」
ということだろう、ということです。

Re:現在の情報理論の常識から言えば

[Ryo.F (3896)]

私が否定したのは、
        情報を含んだデータ列には必ず規則性が存在
です。
        圧縮可能なら完全にランダムではない
なんてことを否定してはいません。

Re:現在の情報理論の常識から言えば

[zeissmania (3689)]

はあ？じゃあその否定の根拠は？
＞圧縮可能なら完全にランダムではない
ことを肯定することと
＞情報を含んだデータ列には必ず規則性が存在
を否定することは矛盾してませんか？
完全にランダムな状態で情報が含まれるというのはどういうものがあるんでしょうか？

Re:現在の情報理論の常識から言えば

[Ryo.F (3896)]

冷静に考えてくれねぇかなぁ。

> ＞圧縮可能なら完全にランダムではない
> ことを肯定することと
> ＞情報を含んだデータ列には必ず規則性が存在
> を否定することは矛盾してませんか？

しません。例えば、コイントスの結果を伝える場合を考えます。情報は、出た面が表なら 1、裏なら 0 というように符号化し、一回目から順に並べるとします。
コインに偏りが無ければ、このビット列はランダムですが、コイントスの結果と言う情報は正しく伝えています。

「情報」

[Vorspiel (2391)]

> 完全にランダムならば、その中に情報は含まれないはずです。

それじゃ，あるファイルをgzip(でもcompressでも何でもいいですが)で可逆圧縮したとして，ヘッダ以外の「ランダムな」(=サイズがその情報量にほぼ等しい)部分には情報はないんですか? そんなことはないでしょう．

Re:「情報」

[zeissmania (3689)]

＞ヘッダ以外の「ランダムな」(=サイズがその情報量にほぼ等しい)部分
それは「完全なランダム」ではないです。
完全なランダムにしてしまうと復元はできません。復元するための規則性が必ず残ります。

Re:「情報」

[Ryo.F (3896)]

またウソですね＞完全なランダムにしてしまうと復元はできません。復元するための規則性が必ず残ります。

大体、ランダムってどういう意味で使ってますか？

ごめんなさい

[zeissmania (3689)]

エントロピーの最大と０を勘違いしてました。
完全にランダムな状態（全ての要素の出現率が均一）で情報量（エントロピー）が最大になるので、それ以上の圧縮は不可能。
でした m(_ _)m

Re:現在の情報理論の常識から言えば

[Vorspiel (2391)]

同じですというか言葉のアヤですというか馬から落馬というか．
「完全な乱数列」というのが正しい日本語だと思いますが，ちと分かりにくいかと思ってこう書きました．失礼．

ノーベル賞

[Silphire (7255)]

ZDNetより

この研究が『常温核融合』の二の舞となる か，ノーベル賞につながる研究となるかはどちらとも言えない」としている。

ノーベル賞は取れないでしょう。ノーベル数学賞は無いですから。取るとしたら、フィールズ賞かチューリング賞だと思います。

Re:ノーベル賞

[maezoh (4657)]

平和賞があるさっ ;-)
これでみんながハッピーになれればね。

Re:ノーベル賞

[Ryo.F (3896)]

経済学賞もあります。

Re:ノーベル賞

[hmr (4234)]

いまだってすでに・・・

正式名称

[white (2295)]

Novel e-Museumの経済学賞 [nobel.se]のところを見ればわかりますが、
正式名称は

"Bank of Sweden Prize in Economic Sciences in Memory of Alfred Nobel"
  --「アルフレッド・ノーベル記念スウェーデン銀行経済学賞」

なんだそうです。

ブロードバンド＆大容量化

[wish (6421)]

ストレージはテラバイト
通信はギガビット
そんな時代になれば　ムヨー　とか言われるのだろうなぁ

Re:ブロードバンド＆大容量化

[zeissmania (3689)]

そんな時代には扱うデータ量もそれに比例して増加するので、圧縮技術は永遠に必要とされると思われます。

Re:ブロードバンド＆大容量化

[nasb (3002)]

「HDは常に80%以上埋まっている」の法則ですね。

# 100GBのHDDを買ってきても、次の週には空きはわずか…

Re:ブロードバンド＆大容量化

[seldon (5637)]

冷凍庫の方は結構埋まったりします。
ウチでは「冷凍庫がいっぱいだから今日は冷凍食品買うのは止めとこう」とかいう会話が...
頼むから冷蔵庫の空き領域は埋めなくてはならないという強迫観念を何とかしてくれぇ＞配偶者(^^;

ところで圧縮/展開にかかる時間は?

[shiba (273)]

本当に1/100になるか疑問だが,圧縮や展開にかかる時間は,
どの程度なんだろうか?

100MBを1MBに圧縮するのに P4-2GHz でも1年かかったら
実用性がしばらくないと思うが...

嘘だっ

[dai75 (557)]

と一瞬思ったけど

　ZeoSyncは数学用語を使って，自社の技術を以下のように説明している。「自然発生パターンを意図的に作り出して，エントロピーライクなランダムシーケンスを形成するもの」

カオスとかその辺でしょうか。
与えられたデータに適合する、「自然発生パターン」を発見する方法を見つけた、と。

…それならありうるかもしれない。
でも計算量かかりそうですね。
実用に耐えるためには P4 10GHz くらい必要だったりして。

--
-- wanna be the biggest dreamer

Re:嘘だっ

[ikemo (901)]

Steve Smale氏の研究業績 [berkeley.edu]にはカオスという言葉が
何度か出て来ているようなので、その可能性はありそうですね。

最後の2つの論文がなんか怪しい…。誰か読んでみません？(^^;)

無限圧縮

[okome (1916)]

きっと、1/100に圧縮したデータもさらに1/100に圧縮できるに違いない。
そんなのできるわけない。

--
okome

Re:無限圧縮

[Silphire (7255)]

ええ。C.E.Shannonの"Mathematical Theory of Communication" (Bell System Tech. J., Vol. 27 /1948)によって、エントロピーを越える圧縮をかけると元に戻せなくなることが証明されていますから。

試験に出るＸ１

[gesaku (7381)]

っていう連載（Ｏｈ！ＭＺ誌）を思い出した。
　確かその中の質問コーナーに、
「ダンプリストのチェックサム情報だけで
元のデータを復元することはできないでしょうか？」
などというものがあって、その答えのなかで、
「もし２５６バイトのダンプのチェックサムデータ
３２バイトだけで元のデータが復元できるならば、
それを繰り返すことによって数十ＫＢのデータが
たった３２バイトだけで復元できることになってしまう。」
とかなんとか書いてあったような。

　１０年前にこの技術があれば、あのブ厚いI/Oの
ダンプリストをちまちまと入力することも無かっただろうに。

Re:試験に出るＸ１

[Anonymous Cowboy (6205)]

当時雑誌に載っていたダンプリストのほとんどはバイナリファイルが素で掲載されていましたから、ちょっとした圧縮をほどこしたものを掲載するだけでもだいぶ違ったと思います。

#PCマガジン派

にわかには信じられませんね

[Ryo.F (3896)]

仮に、任意文字列を元の文字列より常に短くする
符号化が存在するとすれば、その圧縮率がたとえ数百分の一といわず、
ほんの 1/2 だったとしても、任意の文字列を 1bit で
表せることになってしまいますね。
同じ圧縮を繰り返しかけていけば、
最後には 1bit になってしまうでしょうから。

ということは、1bit、つまり零か壱かの弐状態で、
任意の文字列を表すことができることになりますが、
それは絶対に無理だということが直観的にわかるでしょう。

もちろん、文字列をビット列や画像に置き換えたところで
全く同じことが言えます。

ということで、元の情報の特性を全く利用しない圧縮は
ありえないわけで、もう少し詳しい情報が無いと
なんとも判定できませんね。

Re:にわかには信じられませんね

[tomatsu (2545)]

0x20～0x7e。特に、0x61～0x7aに偏った任意文字列なのでは？

Re:にわかには信じられませんね

[Ryo.F (3896)]

はぁ... なんでこんなに AC は人の話を読まないんだろう...
任意の文字列を常に短くできる圧縮なんか存在しない、
ということを説明している文章なんだが、この AC には解らんのだろうな。

もしや

[Anonymous Cowboy (6205)]

THcomp [nurs.or.jp]?

Re:もしや

[wintermute (732)]

うわ、なつかしい。でも定期的に話題に上るねえ。
まさに「世界中のファイルのバリエーションなんざ2^64程度
に違いない」ってのが出発点だと聞いたような。

Re:もしや

[densuke (113)]

私は丹羽さんの「どんなファイルも1バイトに圧縮するアーカイバ｣というネタを思い出しました。

なんの雑誌だったかなぁ。あの人の話は好きでした。

--
-- やさいはけんこうにいちば〜ん！

もしかしてアレ?

[nekopon (1483)]

あの、定期的に出てくる、『世界中のすべてのファイルはだいたい8バイトくらいまで圧縮できる』ってゆーネタ?

# あれをまじめに実装するには、とんでもなく広い帯域とデカいディスクが必要な気がするのだが。

悔しい。

[kamira (6480)]

「自然発生パターンを意図的に作り出して，
    エントロピーライクなランダムシーケンスを形成するもの」

言葉尻だけ捕らえようとするとかなり難解ですね。
自然発生パターンっていうのは、規則性の認められるパターン？
エントロピーライク・・・

http://dictionary.goo.ne.jp/cgi-bin/dict_search.cgi?MT=%A5%A8%A5%F3%A5%C8%A5%ED%A5%D4%A1%BC&sw=2

言葉の意味すら理解できないですが、
その特許の名前が「BinaryAccelerator」はいかがなものか。
理解できず悔しいので謝辞を一つ、ば。

「今回の発表は、ランダムシーケンス解析法によるデータ形成過程、
　その極微細構造制御及び復元・符号化を介した情報論理解析理論に
    多大な貢献が認められる」
(注：言葉はすべて適当です)

翻訳チップ利用かな？

[Seth (1176)]

　既に、 「数億パターンを数百千パターンに対応させた、 　翻訳チップを利用して圧縮。 　そして、同じその翻訳チップを使用して、 　解凍する」 って、 「かの有名なＳＦネタ（核爆）」 では無いですかね（笑） 　ただ、命題として、 「翻訳チップに存在するだけの、 　その数億→←数百万パターンで、 　『すべての情報を圧縮、解凍可能か？」 　という、 　そのパターンを発見できるか？？ 　そもそも、 　『その時空連続体に、 　　そのパターン、 　　”神（々）が天地創造に用いた技” 　　を、人類が発見出来るか!？？？」 って奴ですネ（謎） 　この辺の、 「ＳＦネタ、多いですからね（笑）」

--
"castigat ridendo mores" "Saxum volutum non obducitur musco"

実は先日、

[memex (4261)]

大きめの画像を貼り付けた一太郎ファイルを作ってセーブしたところ、
約16MBになりましたが、こいつをWinZipで「フツー」に圧縮したら
156kB、つまり102%もの圧縮率となってブッたまげました。

これはWinZipがエラいんでもなんでもなく、単に一太郎が画像ファイル
を無駄に大きなサイズでセーブしてしまうのが原因のようです。

それにしても、結果だけ見るとちょっとビックリしてしまいますね。

今回の話で圧縮すると、圧縮率は一体いくらになるのやら．．．？

--
Eureka !

Re:実は先日、

[elmirage (6555)]

圧縮率といえば思い出す。
初代Lunatic Dawnのセーブデータ。

--
だが、いいこともあるぞ、外の天気は上々なんだ

Re:実は先日、

[Rosh (170)]

見事に笑わせてもらいましたが、あれはどちらかっつーとクラスタを食い荒らしてただけのような。(^^;

--
勝つて言はず、敗れて語らず、
謙譲を崇ぶ者は君子也、怨怒を起す者は小人也。

Re:実はその昔、

[Ryo.F (3896)]

古いバージョンのMS PowerPointで作ったファイルを
LHA で圧縮したら、元のサイズの 2%(すなわち 1/50)に
なったことならありました。

ところで、圧縮率 102% って何？

Re:実はその昔、

[memex (4261)]

>ところで、圧縮率 102% って何？

あわててちょいと間違えてしまいました、はは。

要は100分の一以下のサイズになったということでご理解ください。

では

--
Eureka !

立証に何年も？

[nasb (3002)]

同社の圧縮方式は理論上は実現可能なものだが，確実な立証にはまだ何年もかかるとしている

可逆圧縮だったら、エンコードしてデコードしたものを元ファイルと
比べるだけでOKな気がしますが、何を言いたいんでしょうね？

ひょっとして、この方式が適用できる確率を気にしているのかな。
ジャンルを限定しても1%とかだったら、実用になりませんものね。

Re:立証に何年も？

[Silphire (7255)]

理論上は出来ても、実装出来るようなコンピュータが無いということではないでしょうか。
例えば、メモリを100TB使用するとか、計算量が膨大すぎるとか。
BlockSortingも、論文通りに実装するとデータ量の２乗のメモリが必要だというのをどこかで見た記憶があります。

Re:立証に何年も？

[yellow tadpole (7084)]

同社の圧縮方式は理論上は実現可能なものだが，
                確実な立証にはまだ何年もかかるとしている

> 可逆圧縮だったら、エンコードしてデコードしたものを
> 元ファイルと比べるだけでOKな気がしますが、何を言いた
> いんでしょうね？

元記事に「今回の理論ではランダムなデータ列を１００分の１に圧縮し、完全に再現することができるらしい」
と書いてあるので、「ある特定のランダムなデータ列」は圧縮できるけれど、それ以外のデータ列だと自信ないな、ってなところでしょか。（ははは

--
〜◍

推測

[L.star (163)]

勝手に推測ですが、あらゆるビットシーケンスを発生させることの出来るようなジェネレーターでないでしょうか？つまり「世の中のデータを高々８バイトで実現してしまう」の親を作ってしまう何か。そして、データ全体より圧倒的に少ないヒントで再現を試みることができると。あまりにもとっぴな想像ですが。

たとえば、そこそこのデータのCRC16とMD5を作成し、データ長とともに転送します。それを受け取った側ではbrute forceでデータを復元するような感じです。一応断っておきますが、あくまで例なのでこの方法で出来るとは私も思いませんし、大体出来たとしても気が遠くなるような速度です。これの非常に数学的で効率的な方法を編み出したと。

Shanonの定理に抜け道が見つかると言うのは考えづらいですが、これで事前にあらゆるデータプールが存在していると言うことになっていると、実際には最初に無限大のデータを転送していることになりますから、Shanonの定理に反しているとはいえないと思います。

P2Pと組み合わせて

[oltio (3848)]

1. どっかに同じ内容を含んだファイルが落ちてないか探す。
2. そのファイルのURI、開始番地と長さを返す。

これでよいに違いない(よくあるネタですが)。当然、 1番目の処理ですでに破綻してますが。

あるいは、

1. オリジナルの作者のメールアドレスを返す。
2. 展開時に、作者に「もう一度送れ」とメールを投げる。

この圧縮方式はよく採用されています(泣)。
#こないだ送っただろー!!探す手間も惜しいのか?!

Re:P2Pと組み合わせて

[minz (3213)]

10年程前のディスクパックから、現在のウィンチェスタにコピーすれば、1/100000程の可逆的圧縮が可能... by 低レ研(当社容積比)

--
みんつ