12

私は現在、特定の入力に対して一致すると指数関数的に実行される可能性がある正規表現の問題を調査し(a*)*て(a|a)*います。一致した文字列の場合、文字列の一致を試みるのに必要な時間が 2 倍になります。これは、PCRE で使用されているような、失敗する前にツリー内のすべての可能な分岐を試行するバックトラッキング/NFA アプローチをエンジンが使用する場合にのみ当てはまります。

私の質問は、なぜ(a?)*脆弱でないのですか? バックトラッキングに関する私の理解に基づいて、文字列「aaaab」で何が起こるべきかは、基本的に(a|a)*. 標準の Thomspson NFA 構造を使用して NFA を構築する場合、確実に発生する各イプシロン遷移に対して、エンジンはそれらを取り続け、2 つの a の場合と同じ方法でバックトラックする必要がありますか? 例 (いくつかの手順を省略し、@ がイプシロンに置き換わる場所):

"aaaa" は一致するが、'b' には一致しない、失敗 (バックトラック)
"aaaa@" は一致、'b' は失敗 (バックトラック)
"aaa@a" は一致、'b' は失敗 (バックトラック)
"aaa@a@ " 一致、'b' 失敗 (バックトラック)
...
"@a@a@a@a@" 一致、'b' 失敗 (バックトラック)

イプシロンと a のすべての可能な組み合わせを試してみると、確実にルートが指数関数的に爆発的に増加しますか?

NFA からイプシロン遷移を削除することは理にかなっていますが、これには(a*)*パターンからすべての非決定論を削除する効果があると思います。ただし、これは間違いなく脆弱であるため、何が起こっているのか完全にはわかりません!

事前にどうもありがとうございました！

編集: NFA が従来のバックトラッキングでトラバースされた場合、イプシロンがまだ存在できないことが Qtax によって指摘されています。それ以外の場合(@)*は、永久に一致しようとします。では、どの NFA 実装が指数関数的になり、(a*)*そうではない可能性があるのでしょうか? これが本当に質問の核心です。(a|a)*(a?)*

4

1 に答える 1

4

OK、いくつかの調査の後、最終的にこれがNFA実装での「バリア」の使用にかかっていることがわかりました。簡単に言えば、バリアは NFA の戦略的なポイント (a* の NFA 構造の 'a' 遷移の直後のノードなど) に配置されます。彼らは、そのバリアがヒットされた前回から試合が進行している必要があります。これにより、NFA が無限数のイプシロンに一致して終了できる状況に陥ることがなくなります。

言い換えれば、あるバリアから同じバリアに一致する e ムーブのみを移動することはできません。これが発生した場合、ルートはドロップされ、前のポイントからバックトラックが発生します。これには、(a?)* が指数関数的な爆発に対して脆弱ではないという副作用もあります。2 回目は null に一致できません。

于 2012-08-28T16:58:47.003 に答える