著者

山本 博章

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.72, pp.59-66, 2005-05-13

---

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