最多一致部分列に基づくユニバーサル情報源符号化法の実用的なアルゴリズム

摘要

KiefferとYangによって提案された文法に基づく符号では、入力された系列だけを生成する文脈自由文法を作成した後、得られた文法を二元系列に変換する。林らは系列中に最頻出する部分列、すなわち最多一致部分列の簡約化を行う文法に基づく符号を提案し、提案符号のユニバーサル性、すなわち提案符号の平均符号長が、入力系列長が長くなるにつれで情報源のエントロピーレートに漸近することを示した。しかしながら、林らの文法変換法が実用的な計算量で実行できるのかについては明らかではなかった。本論文では、最多一致部分列による文法に基づく符号を新たに提案し、提案符号がユニバーサル符号であり、長さnの入力系列に対し文法変換がO（n~2）の計算量で実行できることを示す。