情報処理学会 第79回全国大会講演要旨

コンピュータで処理する入力データの認識は,リアルタイムな状況において高速であるほど良い.認識方法の一つとしてflexが挙げられ,正規表現の規則に従い,入力データを決定性有限オートマトンで認識するソースを生成するツールである.本論は決定性有限オートマトン上の遷移を高速に照合する手法を提案する.遷移を実装する手法としてダブル配列があり,木の一種であるトライを高速に探索するが,決定性有限オートマトンを認識できない.そこで,複数の親節点を定義できるように拡張したダブル配列をflexにおける遷移関数に実装して,正規表現の照合性能を評価する.