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

摘要

In the grammar based code proposed by Kieffer and Yang, a context-free grammar which only produces the input sequence is constructed, and the obtained grammar is encoded into a binary sequence. Lin et al. proposed a grammar based code by using the most frequent substring. Their proposed code is based on the reduction of the string which appears most frequently in the sequence. Lin et al. also proved that their code is a universal code whose average length converges to the entropy rate of the source as the length of the input sequence tends to infinity. However, it is not clear whether the grammar transformation proposed by Lin et al. can be executed in practical computational complexity. In this paper, we propose a new grammar based code by using the most frequent substring. We prove that the proposed code is a universal code, and that the proposed grammar transformation can be executed in O(n~2) for the length of the input sequence n.%KiefferとYmg によって提案された文法に基づく符号では、入力された系列だけを生成する文脈自由文法を作成した後、得られた文法を二元系列に変換する。林らは系列中に最頻出する部分列、すなわち最多一致部分列の簡約化を行う文法に基づく符号を提案し、擢案符号のユニバーサル性、すなわち提案符号の平均符号長が、入力系列長が長くなるにつれて情報源のエントロピーレートに漸近することを示した。しかしながら、林らの文法変換法が実用的な計算量で実行できるのかについては明らかではなかった。本論文では、最多一致部分列による文法に基づく符号を新たに提案し、提案符号がユニ′ミーサル符号であり、長されの入力系列に対し文法変換が0（n~22）の計算量で実行できることを示す。