表題番号：2011B-312 日付：2012/03/27
研究課題クラウド環境における確率モデルに基づく無歪み高圧縮符号化に関する研究
研究者所属（当時） 資格 氏名
（代表者） メディアネットワークセンター 助教 須子　統太
研究成果概要
膨大な量のディジタルデータが流通する現代において，データ圧縮（情報源符号化）技術は，ネットワーク社会を支える重要な基盤技術のひとつとなっている．現在，主に使われているデータ圧縮技術は80 年代にZiv らによって提案されたLempel-Ziv 法(LZ 法)を基礎においている．具体的には，gzip などの圧縮ツールに用いられている手法である．LZ 法が提案されて以来，LZ法をベースにした改良法の研究が数多くされてきたものの，90 年代後半になると一定の成果を得たことで大きな進展はなくなった．また情報ネットワークの高速化に伴い，アルゴリズムの改善によるメリットが薄れてきたため，圧縮技術に関する研究は1 度は収束を迎えたかのように見えた．しかし近年，ネットワークの高速化が頭打ちになりつつある中，クラウドコンピューティングの発達やディジタルコンテンツの大容量化により，ネットワークトラヒックやサーバの記憶容量は増加の一途を辿っている．そのため，データ圧縮技術のさらなる発展が求められるようになり，今後のネットワーク社会における重要な課題のひとつであると考えられる．
データ圧縮アルゴリズムは，圧縮対象となるデータの出現構造に対し，陽に確率モデルを仮定するアルゴリズムと，陽には仮定しないアルゴリズムに分類することができる．前者にはCTW法やベイズ符号など，後者にはLZ 法やその改良法などが含まれる．圧縮アルゴリズムの性能評価は，データのサイズを伸ばしていった時に，圧縮後のファイルのサイズが，圧縮の理論限界であるエントロピーへ収束するのか，また収束する場合にはどれくらいの速さで収束するのか，によって評価される．確率モデルを陽に仮定するアルゴリズムは，エントロピーの収束速度が非常に速い代わりに，仮定した確率モデルに対してしかエントロピーへの収束を保証できない．それに対し，LZ 法などの確率モデルを陽に仮定しないアルゴリズムは，非常に広いモデルのクラスに対してエントロピーへの収束が保証できる代わりに，その収束速度は非常に遅く，有限時点での圧縮性能は必ずしも高くない．現在主流として用いられている圧縮技術のほとんどは，LZ 法をベースとした確率モデルを陽に仮定しないアルゴリズムを用いているため，汎用性は高いものの個々のファイルに対しての圧縮性能は必ずしも高いとは言えず，圧縮率の改善の余地はまだまだあると考えられる．その一方，ベイズ符号などの確率モデルを仮定するアルゴリズムに関する研究は，限られた確率モデルに対する研究しか行われておらず，実用的なデータ構造に対する研究が不十分であるため実用化には至っていない．
そこで本研究では，高圧縮率である確率モデルを仮定した圧縮アルゴリズムを，実用的なデータ構造に対して適用することを目的として研究を行った．特に従来テキストデータに対して，非常に高い圧縮率を持ち，理論的最適性の保証することのできるベイズ符号を他のデータ構造に対し拡張し適用を行った．その結果，アルゴリズムを実装する際，ベイズ符号が仮定する確率モデルと，真の確率構造がことなる場合においても，ベイズ符号は一定の圧縮性能を持つ事を理論的に示すことができた．