情報圧縮理論

概要

マルチメディア社会において、情報を効率良く符号化することによって通信コストを節約する情報圧縮技術は不可欠である。また情報圧縮は、「事物を簡潔に表現する」という本来の意味から、学習や推論などの研究をはじめ他の様々な分野に応用されている技術でもある。このような情報圧縮技術に関して、その限界を知る問題やこれを実現するアルゴリズムの構成などに関する理論的研究を行なってきた。主な成果は以下の通り。

歪みを許した時の複雑度の理論と歪みを許す情報圧縮アルゴリズム

声や画像などの情報は本来連続的なもので、これをデジタル回線で歪みなく伝送することは不可能である。そこで、元の情報とこれを符号化・復号化した後の情報との間に生じる歪みをある程度許容した情報圧縮を考えることが現実的となる。今までに無歪み圧縮アルゴリズムが数多く発見されているので、これを歪みを許す圧縮に利用できないかという問題について考えた。まず、理論的に最適な無歪み圧縮アルゴリズムの持つ共通の性質に注目して系列の複雑度の概念を定義した。次にこれに基づいて歪みを許した時の複雑度の概念を定義し、その基本的な性質に関する定理を証明した[1][3]。歪みを許す圧縮アルゴリズムは複雑度を最小化するような歪みを与えた後に無歪み圧縮を行なうことによって構成される(図1参照)。従来は圧縮レートの最小性を保証するために特定の複雑度と無歪み圧縮器が必要であった。本手法では、ある条件を満たす任意の複雑度と無歪み圧縮器を用いて最小の圧縮レートを持つ歪みを許す圧縮アルゴリズムを構成できる(表1参照)。

Fig 1: Our construction of a semifaithful data compression algorithm
Table 1: Complexities and faithful data compression which can be used to construct a semifaithful data compression algorithm
Old method Our method

Complexities
(faithful data compression) Kolmogorov complexity (program length) Any
(clarifying condition)

Lempel-Ziv code (incremental parsing)

共通の情報を伴う情報圧縮アルゴリズム

何らかの手段で共通の情報が送り手と受け手の間にあらかじめ伝送されている状況で、共通の情報と相関のある新たな情報を効率良く符号化する問題を考える。これは「共通の情報を伴う情報圧縮」と呼ばれる。共通の情報を伴う情報圧縮の圧縮レートの理論的な限界値は知られているが、その具体的な構成は無歪み圧縮の場合でさえも知られていなかった。本研究ではまず最小の圧縮レートを持つ無歪み圧縮アルゴリズムの具体的な構成を与え、次に歪みを許した時の複雑度の理論を共通の情報を伴う場合に拡張することによって最小の圧縮レートを持つ歪みを許す圧縮アルゴリズムを構成した[2][3]。

(連絡先：　村松純; Email: pure@cslab.kecl.ntt.co.jp)

[1] Muramatsu, J. and Kanaya, F.: Distortion-complexity and rate-distortion function, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E77-A, No.8, pp. 1224-1229 (1994).

[2] Muramatsu, J. and Kanaya, F.: Universal data compression with common side information, Proc. of the 1997 IEEE International Symposium on Information Theory, p. 183 (1997).

[3] Muramatsu, J.: Universal data compression algorithms for stationary ergodic sources based on the complexity of sequences, 学位論文, 名古屋大学 (1998).

[Top of this page] [BACK]