双対型positionオートマトンを用いたコンパクトなDFA表現

スポンサーリンク

概要

論文の詳細を見る
正規表現のための照合アルゴリズムは,正規表現を決定性有限オートマトン(DFA)に変換すれば,検索は高速に行うことができる.しかし,最悪の場合は,DFAのサイズが元の正規表現の長さの指数的になってしまう.長さmの正規表現に対し,一般にDFAのサイズは(m+1)2^<2m+1>|Σ|ビット必要とする.NavarroとRaffinotは,positionオートマトンを利用して,(m^^〜+1)2^<m^^〜>(=(m^^〜+1)Π_<a∈Σ>2^<m_a>)ビットでDFAを表現する方法を示した.ここで,m^^〜=Σ_<a∈Σ>m_a,m_aは与えられた正規表現に出現するアルファベット記号aの数である.本論文は,双対型positionオートマトンというモデルを導入し,(m^^〜+1)(Σ_<a∈Σ>2^<m_a>)ビットのみを使ったDFAの表現方法を示す.このDFA表現を使うと,通常のDFAと同様に,高速に正規表現の照合を行うことができる.
2011-12-09

著者

関連論文

もっと見る

スポンサーリンク