私はそれから学んだこの記事バックトラッキングを実装する正規表現エンジンの場合、場合によってはripgrep非常に遅くなる可能性がありますが、その理由はよくわかりません。次のPythonコードスニペット（リンクされた記事の例）が非常に遅い理由を簡単に説明できますか？
>>> import re
>>> re.search('(a*)*c', 'a' * 30)
答え1
デフォルトでは、問題は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。