アルファベットが未知の木情報源に対する効率的ベイズ符号化アルゴリズム

摘要

一般的なユニバーサル符号では，情報源アルファベット中の全記号が正の出現確率を持つという仮定のもとで符号化法が構成されている．しかし実際の情報源系列では，すべての記号が出現するとは限らない．そこで，先行研究においてアルファベット中の出現記号数を未知とした符号アルゴリズムがいくつか提案されている．ベイズ最適性を保証するベイズ符号においても，アルファベットが未知の場合の符号化法が提案されているが，計算量が膨大であり，また定常無記憶情報源を仮定しているという制約があった．本研究では，従来の研究で示されたアルゴリズムと等価な符号を効率的に計算するアルゴリズムを提案し，さらに，次数未知の木情報源を対象にしたベイズ符号に拡張したアルゴリズムを定式化する．また，平均計算量が漸近的に収束をすることに注目し，計算量の理論的評価として漸近計算量を示す．平均計算量が実際に収束することを確認し，従来手法と提案手法の計算量の評価を行う．%In general universal coding, it is supposed that every symbol in alphabet appears. However, some symbols may not apper in data sequence in practice. Then source coding algorithms for sources with unknown alphabet have been propsed. On the other hand, it is difficult to use the Bayes cording algorithm for a source with unknown alphabet in practice, because the algorithm has huge computational complexity. In this paper, we propse an algorithm that has the identical compression performance and less complexity as the conventional method. Additionally we formularize an extended algorithm for tree sources. Furthermore we show that the average computational complexity converges asymptotically. Finally we show the simulation experiment for asymptotic performances of conventional and propsed methods.