正規表現

正規表現の処理効率は、オートマトンの作り方の部分に依存して、オートマトンのマッチ処理の方はあまりバリエーションはないのかなと思って、ちょっと調べていました。
とりあえず、探索を深さ優先にするか幅優先にするかという選択はあると思うのですが、マッチ結果が変わるような気がします。
citeseerで調べていたところ、次の論文を見かけました。
http://citeseer.ist.psu.edu/navarro99fast.html
abstractを読んだ感じでは、既に読み込んでマッチに失敗した部分の文字列をスキップして検索をするという方法のようで、KMP法やBM法に似たアイデアなのかなと思いました。
後で読んでみます。