分節木と共有文字列で表現される符号上での効率良い圧縮照合アルゴリズム(アルゴリズム理論,情報検索,<特集>情報爆発論文)

概要

論文の詳細を見る
本論文では,VF符号で圧縮されたテキスト上でのパターン照合アルゴリズムについて論じる.ここで扱うVF符号とは,テキストを分節木によって可変長の部分文字列に分割し,固定長の符号語を割り当てる形式の符号化手法である.圧縮照合問題の形式的枠組みであるCollage systemを用いれば,VF符号上でKMP型の汎用的なアルゴリズムを組織的に導出でき,O(m^2+D)時間・領域の前処理の後, O(n+R)時間で圧縮テキストを走査できる.ここで, m, n, R, Dはそれぞれ,パターン長,テキスト長,パターンの出現回数,圧縮辞書のサイズである.しかし,この圧縮辞書のサイズは,各符号語に対する文字列の長さの総和に等しい.そこで,分節木上で共有される文字列の構造を利用し,より効率良く前処理を行うアルゴリズムを提案する.提案アルゴリズムは,大きさ|T|の分節木T上の各ラベル文字列が,長さ|S|である文字列Sの一部分として表現されている場合,O(m^2+|S|+|T|)時間・領域で前処理を行うことができる.ここで, |S|+|T|はもとのDよりも非常に小さいものである.本結果は,Collage system上で示されており,同種の構造の圧縮法であればVF符号に限らず適用できる.
2010-06-01