効率よいVF符号のためのMDL原理に基づく分節木の訓練手法

概要

論文の詳細を見る
本稿では,VF 符号における辞書データ構造を訓練することで VF 符号の性能を向上させる方法について論じる.ここで議論する VF 符号とは,分節木と呼ばれる木構造を用いて入力テキストを可変長のブロックに分割し,各ブロックに固定長の符号語を割り当てることでテキスト圧縮を達成する情報源符号化方法である.VF 符号の圧縮率は分節木によって決定されるが,入力テキストに対して最適な分節木を構築することは NP 困難であることが知られている.そのため,最適に近い分節木を構築するために,入力テキストを繰り返し走査しつつ分節木を訓練させるという手法が提案されている.しかしながら,既存の手法では,符号化の際に事前に符号語長をパラメータとして与える必要があった.符号語長を長くすればテキストの分割数は減少するが,逆に分節木を保存するコストが増大し最終的なデータ圧縮率を低下させうる.本稿では,MDL 原理に基づく指標を示し,それによって分節木に登録する文字列を貪欲に決定していく訓練アルゴリズムを提案する.このアルゴリズムは,訓練する過程において符号語長を自動的に調節する.
2011-07-26