拡張正規表現照合のためのビット並列アルゴリズム

スポンサーリンク

概要

論文の詳細を見る
本論文では、拡張正規表現の照合問題に対するアルゴリズムを設計する。拡張正規表現の照合問題とは、長さmの拡張正規表現rと長さnの記号列xが与えられたとき、xの部分記号列でrと一致するすべてのものを見つける問題である.すなわち、集合F={(i,j) I a_i,…a_j⋴L(r)}を見つけるアルゴリズムについて考える。拡張正規表現とは、正規表現に共通集合演算と補集合演算を加えたもので、パターン照合問題においては柔軟なパターンの記述が可能である。我々は、この問題に対し、O((mn^2+ex(r)n^3)/W)時間かつO((mn+⋴x(r)n^2)/W領域で動作するビット並列パターンマッチングアルゴリズムを与える.ここで、ex(r)はrに出現する共通集合演算および補集合演算の数、Wは計算機のワード長である。さらに本論文では、提案したアルゴリズムを実際に実装し、その評価も行なう。
社団法人電子情報通信学会の論文
2003-01-17

著者

関連論文

もっと見る

スポンサーリンク