文脈自由文法のチョムスキー標準形を用いた文法圧縮アルゴリズム

摘要

本稿では新しい，文法に基いた無歪み情報源符号のクラスを提案する．簡潔さのために，文脈自由文法の準チョムスキー標準形（Semi-Chomsky Normal Form，Semi-CNF）を導入する．semi-CNFはCNFを変形したものであり，本稿の中で提案する．文法圧縮符号は文脈自由文法を用いたユニバーサルデータ圧縮アルゴリズムのクラスである．提案するアルゴリズムは，与えられた系列を，その系列のみを生成する既的な文法に二段階で変換する．第一段階では，シンボルもしくは変数のペアから新しい変数への置き換えを繰り返すことで，生成規則の集合のsemi-CNFを構成する．第二段階では，他の生成規則の中で一度しか用いられていない生成規則を削除することで，Semi-CNFを既約もしくはより小さな文法に変換する．LZ78，Multilevel Pattern Matching（MPM）法，Byte Pair Encoding （BPE）法が，このクラスの符号として扱うことができるが，これらのアルゴリズムは，この二段階の手続きのうち最初のものしか用いていない．よって，提案する方法によって，統一した手続きでこれらのアルゴリズムの圧縮性能を向上させることができる．この手法には，Semi-CNFを経由する二段階アルゴリズムを用いることで，与えられた系列から文法への変換が極めて簡潔で効率的であるという利点がある．