計算論的情報源モデルと圧縮アルゴリズム

スポンサーリンク

概要

論文の詳細を見る
情報源符号化における無歪み圧縮の手法として,形式文法を用いた圧縮法の研究が行われている.文法に基づく符号化法は,サンプルデータから計算機モデルを推定する問題とも考えることができる.これまでの研究では,情報源系列から符号化される文法は文脈自由文法を用いていたが,これが最適というわけではない.文法のクラスを変更することにより,冗長度が0に収束する速度や,符号化・復号化の計算量をより適切なものにする可能性があるためである.そのため,情報源クラスに応じた文法のクラスを考える必要がある.本稿では,情報源系列の発生過程も計算機モデルとする計算論的な情報源を考え,その性質と形式文法の階層構造がどのような影響を与えるのか明らかにする.また,情報源が既知の場合における符号化アルゴリズムを示し,このときの計算量を明らかにする.最後にこれらの情報源におけるユニバーサル符号を示す.
2002-09-17

著者

関連論文

もっと見る

スポンサーリンク