平衡直線的プログラムに対するパターン照合アルゴリズム

摘要

テキストとパターンが直線的プログラムとその変種で記述された文字列の照合問題を扱う．直線的プログラムによって表される文字列の長さは，その記述長に対して指数的に長くなる可能性があるので，展開することなしに，いかに高速な照合を行うかが問題となる．直線的プログラムに対する既存の最も良い圧縮パターン照合アルゴリズムはO（n~2m~2）時間O（nm）領域で動作する．ここで，nは圧縮テキストのサイズで，mは圧縮パターンのサイズである．本論文では，平衡直線的プログラムという直線的プログラムの変種を提案し，それに対する高速な圧縮パターン照合アルゴリズムを示す．平衡直線的プログラムは直線的プログラムに比べ圧縮率では劣るが，直線的プログラムと同様に指数長の表現力をもつ．提案アルゴリズムはO（nm）時間O（nm）領域で動作する．