VF符号と算術符号の組合せ手法による圧縮性能の向上について

概要

論文の詳細を見る
本稿では,VF 符号に算術符号を組み合わせることで,検索の効率と圧縮率とを保つ方法について議論する.ここで議論する VF 符号とは,分節木と呼ばれる圧縮のための辞書木を用いて元のテキストを可変長のブロックに分割し,各ブロックに固定長の符号語を割り当てることでデータ圧縮を達成する情報源符号化方法である.VF 符号は,近年,パターン照合を高速化することのできるデータ圧縮法として見直されている.VF 符号は,符号語長が固定であるという制限から,分節木が小さいときには圧縮性能が低い.圧縮率を向上させるには分節木を大きくすればよいが,逆にパターン照合時の前処理に時間がかかり全体の検索の速度を低下させてしまう.そこで,VF 符号の出力を,展開が早い他の符号化方法で符号化することで,圧縮率と検索速度の両方を保つ方法が考えられる.本稿では,代表的な VF 符号である Tunstall 符号および VF 符号の中では優れた圧縮性能を持つ STVF 符号に Range Coder を組み合わせた圧縮方法について,その圧縮性能を実験的に評価した.その結果,符号語長が短い場合において,それぞれおよそ 18 〜 20%,7 〜 15% の圧縮率改善が見られた.
2010-07-28