長さ制限のある極小禁止語を用いた動的な反辞書データ圧縮法

摘要

反辞書は，入力系列に現れない極小系列（極小禁止語）の集まりのことで，これを算術符号の確率モデルとして用いたデータ圧縮法が提案されている．この静的手法では，復号側に送る反辞書コストの削減のために，長さ制限のある極小禁止語の集まりを反辞書として利用し，よい圧縮率を与えることが知られている．しかしながら，反辞書コストを抑えるために，2値アルファベットしか扱えない問題点がある．本稿では，圧縮率の改善を目的として，多値アルファベットを扱える動的な反辞書データ圧縮法を改良し，長さ制限のある極小禁止語の集まりを用いた線形計算量で動作する動的手法を提案する．計算機実験の結果，無記憶およびマルコフ情報源に対してエントロピーレートに近い圧縮率が得られた．また，Calgary corpusのファイルに対しても，従来手法より圧縮率が改善し，平均圧縮率でbzip2と同じ圧縮率が得られた．