パスワードを忘れた? アカウント作成
2008 story

可逆圧縮で1/100に 140

ストーリー by yasu
小さくなるのは良いことだ 部門より

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

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

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • 完全にランダムな乱数列を100%確実に可逆圧縮する方法は絶対にありえない(圧縮量が1/100どころかたった1bitであっても!)と記憶しているんですが,私の理解が間違ってるのか,それとも理論に穴があったのか.
    しばらくは眉にツバをつけて見てたほうがいいかも.理論もまだ公開されてないわけだし.
    • by zeissmania (3689) on 2002年01月10日 18時33分 (#53001)
      完全にランダムならば、その中に情報は含まれないはずです。情報を含んだデータ列には必ず規則性が存在します。
      親コメント
      • by nsawa (497) on 2002年01月10日 18時51分 (#53012)
        元記事のニュアンスから推測するに、「ランダムなデータを1/100に」というのは言葉のアヤで、
        「ネットワーク上でやりとりされるデータをランダムに抽出したところ、平均1/100の圧縮率」
        で可逆圧縮できる方法を編み出したのではないかな、と思います。
        もしそうだとすれば、それはそれで素晴らしいことです。
        親コメント
      • by Anonymous Coward on 2002年01月10日 20時08分 (#53063)

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

        「君が命懸けで入手しようとしている某国スパイの乱数表だが、 そんなものには元々情報は1bitも含まれていないんだ。 上司に白紙の報告書を出せば仕事は終わりさ」
        特にボンド君は、残りの上映時間をすべて美女と楽しめることに大喜びするでしょう。

        親コメント
      • ウソですね>情報を含んだデータ列には必ず規則性が存在。

        ていうか、もう少し詳しく説明してもらわないと、
        何を言いたいのか理解できません。
        親コメント
        • >何を言いたいのか理解できません
          圧縮が可能なデータ列なら「完全なランダム」ということはあり得ないということです。だから圧縮された元データは
          「一見ランダムに見えるだけで、厳密には完全なランダムなデータではなかった」
          ということだろう、ということです。
          親コメント
          • 私が否定したのは、
                    情報を含んだデータ列には必ず規則性が存在
            です。
                    圧縮可能なら完全にランダムではない
            なんてことを否定してはいません。
            親コメント
            • はあ?じゃあその否定の根拠は?
              >圧縮可能なら完全にランダムではない
              ことを肯定することと
              >情報を含んだデータ列には必ず規則性が存在
              を否定することは矛盾してませんか?
              完全にランダムな状態で情報が含まれるというのはどういうものがあるんでしょうか?
              親コメント
              • 冷静に考えてくれねぇかなぁ。

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

                しません。例えば、コイントスの結果を伝える場合を考えます。情報は、出た面が表なら 1、裏なら 0 というように符号化し、一回目から順に並べるとします。
                コインに偏りが無ければ、このビット列はランダムですが、コイントスの結果と言う情報は正しく伝えています。
                親コメント
      • by Vorspiel (2391) on 2002年01月10日 18時51分 (#53013) ホームページ
        > 完全にランダムならば、その中に情報は含まれないはずです。

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

        親コメント
        • by zeissmania (3689) on 2002年01月10日 19時06分 (#53029)
          >ヘッダ以外の「ランダムな」(=サイズがその情報量にほぼ等しい)部分
          それは「完全なランダム」ではないです。
          完全なランダムにしてしまうと復元はできません。復元するための規則性が必ず残ります。
          親コメント
          • by Ryo.F (3896) on 2002年01月10日 19時16分 (#53037) 日記
            またウソですね>完全なランダムにしてしまうと復元はできません。復元するための規則性が必ず残ります。

            大体、ランダムってどういう意味で使ってますか?
            親コメント
      • by zeissmania (3689) on 2002年01月10日 20時03分 (#53062)
        エントロピーの最大と0を勘違いしてました。
        完全にランダムな状態(全ての要素の出現率が均一)で情報量(エントロピー)が最大になるので、それ以上の圧縮は不可能。
        でした m(_ _)m
        親コメント
  • ノーベル賞 (スコア:3, 参考になる)

    by Silphire (7255) <silphire@gmail.com> on 2002年01月10日 17時56分 (#52983) ホームページ 日記
    ZDNetより
    この研究が『常温核融合』の二の舞となる か,ノーベル賞につながる研究となるかはどちらとも言えない」としている。
    ノーベル賞は取れないでしょう。ノーベル数学賞は無いですから。取るとしたら、フィールズ賞かチューリング賞だと思います。
  • ストレージはテラバイト
    通信はギガビット
    そんな時代になれば ムヨー とか言われるのだろうなぁ
  • 本当に1/100になるか疑問だが,圧縮や展開にかかる時間は,
    どの程度なんだろうか?

    100MBを1MBに圧縮するのに P4-2GHz でも1年かかったら
    実用性がしばらくないと思うが...
  • by dai75 (557) on 2002年01月10日 18時06分 (#52988) 日記
    と一瞬思ったけど


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


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

    …それならありうるかもしれない。
    でも計算量かかりそうですね。
    実用に耐えるためには P4 10GHz くらい必要だったりして。
    --
    -- wanna be the biggest dreamer
  • きっと、1/100に圧縮したデータもさらに1/100に圧縮できるに違いない。
    そんなのできるわけない。
    --
    okome
  • by gesaku (7381) on 2002年01月10日 18時25分 (#52995)
    っていう連載(Oh!MZ誌)を思い出した。
     確かその中の質問コーナーに、
    「ダンプリストのチェックサム情報だけで
    元のデータを復元することはできないでしょうか?」
    などというものがあって、その答えのなかで、
    「もし256バイトのダンプのチェックサムデータ
    32バイトだけで元のデータが復元できるならば、
    それを繰り返すことによって数十KBのデータが
    たった32バイトだけで復元できることになってしまう。」
    とかなんとか書いてあったような。

     10年前にこの技術があれば、あのブ厚いI/Oの
    ダンプリストをちまちまと入力することも無かっただろうに。
    • by Anonymous Cowboy (6205) on 2002年01月10日 19時50分 (#53056)
      当時雑誌に載っていたダンプリストのほとんどはバイナリファイルが素で掲載されていましたから、ちょっとした圧縮をほどこしたものを掲載するだけでもだいぶ違ったと思います。

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

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

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

    ということで、元の情報の特性を全く利用しない圧縮は
    ありえないわけで、もう少し詳しい情報が無いと
    なんとも判定できませんね。
  • by Anonymous Cowboy (6205) on 2002年01月10日 18時32分 (#53000)
    THcomp [nurs.or.jp]?
    • by wintermute (732) on 2002年01月10日 18時56分 (#53018) ホームページ 日記
      うわ、なつかしい。でも定期的に話題に上るねえ。
      まさに「世界中のファイルのバリエーションなんざ2^64程度
      に違いない」ってのが出発点だと聞いたような。
      親コメント
    • by densuke (113) on 2002年01月10日 21時39分 (#53094) 日記
      私は丹羽さんの「どんなファイルも1バイトに圧縮するアーカイバ」というネタを思い出しました。

      なんの雑誌だったかなぁ。あの人の話は好きでした。
      --
      -- やさいはけんこうにいちば〜ん!
      親コメント
  • by nekopon (1483) on 2002年01月10日 18時33分 (#53002) 日記

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

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

  • by kamira (6480) on 2002年01月10日 18時49分 (#53009) ホームページ
    「自然発生パターンを意図的に作り出して,
        エントロピーライクなランダムシーケンスを形成するもの」

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

    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」はいかがなものか。
    理解できず悔しいので謝辞を一つ、ば。

    「今回の発表は、ランダムシーケンス解析法によるデータ形成過程、
     その極微細構造制御及び復元・符号化を介した情報論理解析理論に
        多大な貢献が認められる」
    (注:言葉はすべて適当です)
  • by Seth (1176) on 2002年01月10日 19時06分 (#53027) 日記
     既に、 「数億パターンを数百千パターンに対応させた、  翻訳チップを利用して圧縮。  そして、同じその翻訳チップを使用して、  解凍する」 って、 「かの有名なSFネタ(核爆)」 では無いですかね(笑)  ただ、命題として、 「翻訳チップに存在するだけの、  その数億→←数百万パターンで、  『すべての情報を圧縮、解凍可能か?」  という、  そのパターンを発見できるか??  そもそも、  『その時空連続体に、   そのパターン、   ”神(々)が天地創造に用いた技”   を、人類が発見出来るか!???」 って奴ですネ(謎)  この辺の、 「SFネタ、多いですからね(笑)」
    --
    ------------------------------ "castigat ridendo mores"
  • by memex (4261) on 2002年01月10日 19時06分 (#53028) ホームページ
    大きめの画像を貼り付けた一太郎ファイルを作ってセーブしたところ、
    約16MBになりましたが、こいつをWinZipで「フツー」に圧縮したら
    156kB、つまり102%もの圧縮率となってブッたまげました。

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

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

    今回の話で圧縮すると、圧縮率は一体いくらになるのやら...?
    --
    Eureka !
  • by nasb (3002) on 2002年01月10日 19時34分 (#53044) 日記
    同社の圧縮方式は理論上は実現可能なものだが,確実な立証にはまだ何年もかかるとしている

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

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

    • 理論上は出来ても、実装出来るようなコンピュータが無いということではないでしょうか。
      例えば、メモリを100TB使用するとか、計算量が膨大すぎるとか。
      BlockSortingも、論文通りに実装するとデータ量の2乗のメモリが必要だというのをどこかで見た記憶があります。
      親コメント
    • 同社の圧縮方式は理論上は実現可能なものだが,
                      確実な立証にはまだ何年もかかるとしている

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

      元記事に「今回の理論ではランダムなデータ列を100分の1に圧縮し、完全に再現することができるらしい」
      と書いてあるので、「ある特定のランダムなデータ列」は圧縮できるけれど、それ以外のデータ列だと自信ないな、ってなところでしょか。(ははは
      --
      〜◍
      親コメント
  • by L.star (163) on 2002年01月10日 21時51分 (#53099) ホームページ
    勝手に推測ですが、あらゆるビットシーケンスを発生させることの出来るようなジェネレーターでないでしょうか?つまり「世の中のデータを高々8バイトで実現してしまう」の親を作ってしまう何か。そして、データ全体より圧倒的に少ないヒントで再現を試みることができると。あまりにもとっぴな想像ですが。

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

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

  • by oltio (3848) on 2002年01月10日 22時55分 (#53128) 日記
    1. どっかに同じ内容を含んだファイルが落ちてないか探す。
    2. そのファイルのURI、開始番地と長さを返す。

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

    あるいは、

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

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

typodupeerror

目玉の数さえ十分あれば、どんなバグも深刻ではない -- Eric Raymond

読み込み中...