効率よいVF符号とその上での高速なパターン照合の実現に関する研究

点击翻译按钮获取中文摘要

本研究の目的は, 圧縮率が高く, 圧縮処理や圧縮パターン照合が高速に行えるデータ圧縮の方法を開発することである. 平成25年度は, 高性能なVF符号の開発と, その理論的および実験的な性能評価を行った. 具体的には, 次の(1)と(2)の研究を行った.(1)Re-Pairを用いたVF符号の消費メモリ量を削減するために, 入力テキストを数十MBから数百MBのブロックに分割して, それぞれについてRe-Pairを使用して圧縮するVF符号を開発した. また, この場合, 各ブロックに対応する辞書に重複する変換規則が存在すると考えられる. これに対して, 本研究では, 隣接する2ブロック間で, 前のブロックの変換規則の中で, 後ろのブロックにおいても頻出であるものを共有することで, 辞書を格納する領域を削減する手法を提案した. また, この手法を実装して, 実験的な評価を行った. その結果, Re-Use法と比較して, 圧縮速度を低下させることなく, 圧縮率を改善することができた.(2)VF符号で圧縮されたデータに元のテキストと同じ長さのビット列に対する簡潔索引構造を埋め込むことで, この対応付けを高速に行う手法を提案した. このビット列は, 符号語に対応する文字列の最後の文字の位置だけが1となっている. なお, このビット列に対する簡潔索引構造を埋め込むことで, 位置関係の対応付けが高速に行えるようになっている. また, 実験の結果, 同様の機能を持つ可変長符号であるFOLCAよりも10倍以上高速に位置関係の対応付けができることが明らかになった.