正規表現の一致はなぜそんなに遅いのですか？

デフォルトでは、問題はaパターンの二重反復です。このセクションでは、周辺a*のさまざまなことを許可します。a(·)* 返品パターンはいくらでも受け入れられます。

aこれにより、パターンを文字列に一致させるさまざまな方法を使用できます。 （Five's）などの文字列はb、、、、、...と一致する可能性があることを今は無視してください。文字列を一致させる方法は指数関数的に多いです。aaaaaa(aaaaa)(aaaa)(a)(aaa)(aa)(aaa)(a)(a)(aa)(aaa)(aa)(aa)(a)

結局のところb、バックトレースエンジンは一致する方法を試して、見つからないことにa気づき、b1つのステップに戻り、他の方法を試してみて見つかりませんでしたb...すべてを使い果たすのに時間がかかりすぎる方法を使用します。可能な処置を取ってから失敗しました。

このトピックについて私が書くことができるよりもオンラインではるかに良い記事があります。次の内容を読んでください。

• 暴走正規表現：災害的な逆追跡著者Jan Goyvaertsは、この問題とそれを防ぐいくつかの方法を説明しています。

• 正規表現のマッチングは簡単で高速です（しかし...）Russ Coxもこの問題について説明し、逆追跡を使用せずに正規表現を有限オートマトンとして実装することがこの問題の影響を受けない方法について説明します。写真もあります。

実際には、可能であれば、文字列を一致させるさまざまな方法を可能にするパターンを避けてください。ここの例は、入れ子になった繰り返しがない(a*)*cため、明らかに愚かですa*c。