著者

中川 みなみ 南出 靖彦

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.9, no.3, pp.28, 2016-06-06

---

正規表現マッチングは文字列を操作するウェブプログラムなど,様々な場面で用いられており,その実装の多くはバックトラックに基づいている.そのため,正規表現マッチングにかかる時間が文字列の長さに関して線形でないことがあり,最悪の場合指数関数時間となる.本発表では正規表現マッチングの時間計算量を判定する手法を提案する.対象の正規表現から先読み付き木トランスデューサを構成する.その先読み付き木トランスデューサから準同型写像や有限遷移系を構成し,それらを用いた遷移過程の中に反復補題が成り立つ遷移過程が存在しているか調べることで計算量を判定することができる.この判定には,AhoとUllmanによる木トランスデューサの増加率の判定法を先読み付き木トランスデューサに拡張したものを利用する.先行研究では,EngelfrietとManethのマクロ木トランスデューサの増加率の判定法を用い,正規表現マッチングの計算時間が入力文字列に対して線形であるかどうかを判定する手法が提案された.本発表で提案する手法は,時間計算量が線形であるかどうかの判定だけでなくO(n2),O(n3),...になることも判定できる.この提案手法をOCamlによって実装し,既存のPHPプログラムで使用されている正規表現を対象に実験を行った.実験の結果,393個中入力文字列の長さに対して338個が線形,44個が2乗,6個が3乗の計算量であると判定された.