最頻N-gramを考慮した文法生成法に基づくデータ圧縮法

摘要

近年,Sequiturアルゴリズムや最頻digram統合法等のデータ系列の文法を用いたデータ圧縮法の研究が盛んに行われている。 文法を用いた圧縮法では,データ系列を直接符号化するのではなく,データ系列を生成するような文法を構成し,それを符号化する。 中村らによる最頻digram統合法では,データ系列を全て読み込み,連続する2記号であるdigramの出現頻度を求め,最頻digramをルールとする文法生成を行っている。 これに対して,神田らは,この文法の符号化に算術符号を適用することを前提とし,算術符号の理想符号長を計算しながら符号長の観点から最適な文法を生成する手法を提案している。 本研究では,神田らの手法と同様に算術符号の理想符号長を計算しながら文法生成を行うが,digramだけでなくより長く連続するN記号であるN-gramを考慮して文法生成を行う手法を提案する。 またカルガリーデータに対して本手法を適用し,シミュレーションに。 よる評価によって,その有効性を示す。更に系列長nのデータに対し提案手法の計算量及びメモリ量が神田らの手法と同様O（n）であることを示す。