Universal Lossless Source Coding Based on Sequential Grammar Transforms

摘要

文法に基づく符号はKiefferとYangによって提案された幅広いユニバーサル符号のクラスである．一般に文法に基づく符号は入力列を全て得た後でなければ対応する符号列を得ることができないという欠点を有していた．本研究では，まず入力列を読みながら，入力列の語頭について文法を作成できる逐次的な文法変換法を導入する．次に逐次的な文法変換法に対応した逐次的に符号化ならびに復号化可能な文法の2進列への変換手法を提案する．一方，既約文法と呼ばれる文法を作成する文法変換法のクラスを用いたとき，文法に基づく符号がユニバーサル符号となることが知られて，いる．しかしながら，逐次的な文法変換法によって得られる文法は既約ではない．そこで，逐次的な文法変換法でも作成可能な準既約文法という文法のクラスを導入し，準既約文法を作成する文法変換法を用いたとき，提案する符号化アルゴリズムが定常エルゴード情報源に対してユニバーサル符号となることを示している．%The grammar-based code proposed by Kieffer and Yang is a large class of universal codes. Usually, the grammar-based codes can not encode a data string into a binary string before reading all the data string. In this paper, we introduce sequential grammar transforms which can construct grammars for some prefixes of the data string. To efficiently encode these grammars sequentially, we also propose sequential grammar encoding and decod­ing algorithms. Combined with the irreducible grammar transform, our encoding algorithm provides the universal code. However, the sequential grammar transforms can not be irreducible. To overcome this problem, we propose a new class of grammar transforms called quasi-irreducible, and show that quasi-irreducible grammar transforms together with the proposed algorithm provide a universal code for a class of stationary and ergodic sources.