適応的アルファベット分解を用いた無ひずみデータ圧縮

摘要

適応的アルファベット分解という概念を提案し，それを用いた無ひずみデータ圧縮のモデルを提案する．提案モデルに類似する従来法としてPPMがよく知られている．PPM型のデータ圧縮法では，次に出現する記号を予測する際に，次数の異なる文脈を扱うモデルを用いる．一方，本論文の提案法では，予測される記号を可変次数に基づくモデルと同一のままで，それらをいくつかの等価なサブアルファベットに分割し，出現記号の予測に利用する．具体的には，次数の変化ではなく，これらのサブアルファベットの逐次的な参照によって次の記号を符号化する．ここで，記号がどのサブアルファベットに含まれるかを示すために，PPM法のエスケープ機能を用いる．ただし，そのためのエスケープ確率は，適応的アルファベット分解から独自に導出した推定値を利用している．提案モデルを実装し，圧縮実験を行った結果，PPM~*やブロックソート法よりもほとんどの場合において良い圧縮性能を得ることを確認した．