ユニバーサルデータ圧縮の理論解析および高精細画像符号化への応用に関する研究

本研究においては,これまで理論的に解析が進んでおり,また実用的にも広く用いられているZiv-Lempelデータ圧縮法と,1990年代後半から提案されている,ソートを用いたデータ圧縮法を組み合わせた,新しいデータ圧縮方式を提案し,その理論的な性能および高精細画像の圧縮における実用的な性能について検証を行なってきた.本年度は,1990年代後半から提案されている,ソートを用いたデータ圧縮法に関する理論解析を行なった.ソート法のうち,1994年にBurrowsとWheelerによって提案されたブロックソート法は,サンプルファイルを圧縮した時の圧縮率を,これまで広く使われているLempel-Ziv法を用いたgzipと比較すると,多くのファイルで1割程度高性能である.この理由によってブロックソート法は昨今注目されており,bzipやbzip2などのプログラムが作成されるなど実用化が進んでいる.ところが,その理論的な解析は全く進んでおらず,実用的な圧縮性能と理論解析とのギャップはまだまだ大きいと言わざるを得ない.そこで本年度の研究においては,ブロックソート法の一部として用いられているMove-To-Front法について,シンボル拡大を用いない場合にこの符号化アルゴリズムを用いて情報源のエントロピーレートで漸近的に符号化可能な情報源のクラスに関する研究を行なった.その結果,定常無記憶情報源およびエルゴード的な定常マルコフ情報源においては,1シンボル単位での定常分布が一様な場合にしかMove-To-Front法で漸近的にエントロピーレートで符号化できない事が明らかになった.これより,ブロックソート法でシンボル拡大無しに漸近的に情報源のエントロピーレートを達成できる十分条件の一つが明らかになった.

本研究においては,これまで理論的に解析が進んでおり,また実用的にも広く用いられているZiv-Lempelデータ圧縮法と,1990年代後半から提案されている,ソートを用いたデータ圧縮法を組み合わせた,新しいデータ圧縮方式を提案し,その理論的な性能および高精細画像の圧縮における実用的な性能について検証を行なってきた.本年度は,1990年代後半から提案されている,ソートを用いたデータ圧縮法に関する理論解析を行なった.ソート法のうち,1994年にBurrowsとWheelerによって提案されたブロックソート法は,サンプルファイルを圧縮した時の圧縮率を,これまで広く使われているLempel-Ziv法を用いたgzipと比較すると,多くのファイルで1割程度高性能である.この理由によってブロックソート法は昨今注目されており,bzipやbzip2などのプログラムが作成されるなど実用化が進んでいる.ところが,その理論的な解析は全く進んでおらず,実用的な圧縮性能と理論解析とのギャップはまだまだ大きいと言わざるを得ない.そこで本年度の研究においては,ブロックソート法の一部として用いられているMove-To-Front法について,シンボル拡大を用いない場合にこの符号化アルゴリズムを用いて情報源のエントロピーレートで漸近的に符号化可能な情報源のクラスに関する研究を行なった.その結果,定常無記憶情報源およびエルゴード的な定常マルコフ情報源においては,1シンボル単位での定常分布が一様な場合にしかMove-To-Front法で漸近的にエントロピーレートで符号化できない事が明らかになった.これより,ブロックソート法でシンボル拡大無しに漸近的に情報源のエントロピーレートを達成できる十分条件の一つが明らかになった.