圧縮文字列に対する省メモリなパターンマッチアルゴリズム

概要

論文の詳細を見る
本論文では,テキストとパターンがいずれも直線的プログラム(Straight-Line Program:SLP)を用いて圧縮されているとき,それらに対しパターンマッチを行う確率的アルゴリズムを提案する.我々はまずSchmidt-Schaussらの確率的等価性判定法を拡張することにより,関数FirstMismatchを新しい方法で確率的に実現する.FirstMismatchとは,テキストの非終端記号とパターンの非終端記号を与えられた位置から照合したときの最初の相違位置を返す関数である.FirstMismatchの新しい実現法をMiyazakiらのパターンマッチ手法と組み合わせることで,計算時間O(n(n log N+m log M)log M),計算領域O(n log N+m log M)でのパターンマッチを実現する.ここでn,mはテキストとパターンを表すSLPのサイズであり,N,Mはテキストとパターンの文字列長である.Jezらに提案されたアルゴリズムと比較すると,計算時間は劣るが計算領域が小さいため,使用できる領域が限られている場合に有効な手法である.
2012-10-24