Regular Expressions
バックトラッキング

バックトラッキングの原因は何ですか？

一致を見つけるために、正規表現エンジンは文字を1つずつ消費します。部分一致が始まるとエンジンは開始位置を記憶するので、次の文字が一致しない場合に戻ることができます。

• 一致が完了すると、バックトラッキングはありません
• マッチが完了していない場合、エンジンは文字列をバックトラックします（古いテープを巻き戻したときのように）。

たとえば、文字列abc123defに対する\d{3}[az]{2}は次のようにabc123defされます。

abc123def
^ Does not match \d
abc123def
 ^ Does not match \d
abc123def
  ^ Does not match \d
abc123def
   ^ Does match \d (first one)
abc123def
    ^ Does match \d (second one)
abc123def
     ^ Does match \d (third one)
abc123def
      ^ Does match [a-z] (first one)
abc123def
       ^ Does match [a-z] (second one)
           MATCH FOUND

正規表現を同じ文字列（ abc123def ）に対して\d{2}[az]{2}しabc123def ：

abc123def
^ Does not match \d
abc123def
 ^ Does not match \d
abc123def
  ^ Does not match \d
abc123def
   ^ Does match \d (first one)
abc123def
    ^ Does match \d (second one)
abc123def
     ^ Does not match [a-z]
abc123def
    ^ BACKTRACK to catch \d{2} => (23)
abc123def
      ^ Does match [a-z] (first one)
abc123def
       ^ Does match [a-z] (second one)
           MATCH FOUND

バックトラッキングがなぜトラップになるのでしょうか？

regexエンジンはすべてのパスを探索しようとするため、バックトラックはオプションの数量子または代替構造によって引き起こされる可能性があります。正規表現a+bをaaaaaaaaaaaaaaに対して実行すると一致するものはなく、エンジンはかなり高速になります。

しかし、正規表現を(aa*)+b変更すると、組み合わせの数はかなり高速になり、ほとんどの（最適化されていない）エンジンはすべての経路を探索しようとし、一致を見つけたり、タイムアウト例外。これは壊滅的なバックトラッキングと呼ばれます。

もちろん、 (aa*)+bは初心者のエラーと思われますが、この点を説明するためにここにありますが、同じ問題ではなく複雑なパターンで終わることもあります。

壊滅的なバックトラックのより極端な場合には、正規表現で発生します(x+x+)+y （あなたはおそらく前にそれを見てきたこことここに含まれている文字列のことを把握する指数時間を必要とする）、 x Sを何もない（たとえば、 xxxxxxxxxxxxxxxxxxxx ）が一致しません。

それを避ける方法は？

可能な限り具体的に、できるだけ多くのパスを減らしてください。いくつかの正規表現マッチャーは、 Thkpson NFAに基づいているため、 awkやgrep含まれる正規表現マッチャーのようにバックトラックに脆弱ではないことに注意してください。