IT2010-11 アルファベットが未知の木情報源に対する効率的ベイズ符号化アルゴリズム(フレッシュマンセッション,一般)

スポンサーリンク

概要

論文の詳細を見る
一般的なユニバーサル符号では,情報源アルファベット中の全記号が正の出現確率を持つという仮定のもとで符号化法が構成されている.しかし実際の情報源系列では,すべての記号が出現するとは限らない.そこで,先行研究においてアルファベット中の出現記号数を未知とした符号アルゴリズムがいくつか提案されている.ベイズ最適性を保証するベイズ符号においても,アルファベットが未知の場合の符号化法が提案されているが,計算量が膨大であり,また定常無記憶情報源を仮定しているという制約があった.本研究では,従来の研究で示されたアルゴリズムと等価な符号を効率的に計算するアルゴリズムを提案し,さらに,次数未知の木情報源を対象にしたベイズ符号に拡張したアルゴリズムを定式化する.また,平均計算量が漸近的に収束をすることに注目し,計算量の理論的評価として漸近計算量を示す.平均計算量が実際に収束することを確認し,従来手法と提案手法の計算量の評価を行う.
2010-07-15

著者

関連論文

もっと見る

スポンサーリンク