オートマトンを利用した拡張正規表現照合アルゴリズムの実験的評価  [in Japanese] Experimental evaluation of automata-based Algorithms for Matching Extended Regular Expressions  [in Japanese]

拡張正規表現に向けた照合アルゴリズムとして, 与えられた拡張正規表現を正規表現に分割し, 各正規表現をNFAに変換することによって照合を行うオートマトン型のアルゴリズムが提案されている.正規表現からNFAを得るための方法はいくつか提案されてるが, 本論文は, オートマトンに基づいた拡張正規表現照合アルゴリズムをいろいろなNFAに対応可能なように修正し, それぞれのNFAによってアルゴリズムの性能がどうのように変わるかを実験的に評価した.特に, Thompsonオートマトン, Glushkovオートマトン, Followオートマトンについて実際に実装し, その性能を調べた.

This paper is concerned with the extended regular expression (ERE) matching problems. Although Yamamoto [16] presented an automata-based algorithm for solving an ERE membership problem, this algorithm can be extended to ERE matching problems. We experimentally evaluate the performance of automata-based algorithms for ERE matching problems by making use of various finite automata. In fact, we make use of Thompson automata, Glushkov automata, Follow automata and deterministic finite automata and evaluate four problems, All Substring Matching Problem, Substring Matching Problem, Existing Problem and Membership Problem.