Regular Expressions
Rückverfolgung

Wodurch wird Backtracking verursacht?

Um eine Übereinstimmung zu finden, verbraucht die Regex-Engine Zeichen nacheinander. Wenn eine teilweise Übereinstimmung beginnt, merkt sich der Motor die Startposition, so dass er zurückgehen kann, falls die folgenden Zeichen die Übereinstimmung nicht vollenden.

• Wenn die Übereinstimmung abgeschlossen ist, erfolgt keine Rückverfolgung
• Wenn die Übereinstimmung nicht vollständig ist, führt die Engine die Zeichenfolge zurück (wie beim Zurückspulen eines alten Bandes), um eine vollständige Übereinstimmung zu finden.

Zum Beispiel: \d{3}[az]{2} gegen die Zeichenfolge abc123def wird wie abc123def durchsucht:

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

Ändern wir nun den Regex in \d{2}[az]{2} für dieselbe Zeichenfolge ( 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

Warum kann Backtracking eine Falle sein?

Backtracking kann durch optionale Quantifizierer oder Alternativkonstrukte verursacht werden, da die Regex-Engine versucht, jeden Pfad zu erkunden. Wenn Sie den Regex a+b gegen aaaaaaaaaaaaaa gibt es keine Übereinstimmung und die Engine wird es ziemlich schnell finden.

Wenn Sie den Regex jedoch in (aa*)+b ändern, wird die Anzahl der Kombinationen ziemlich schnell ansteigen. Die meisten (nicht optimierten) Engines versuchen alle Pfade zu erkunden und benötigen eine Ewigkeit, um eine Übereinstimmung zu finden oder eine zu werfen Timeout-Ausnahme. Dies wird als katastrophales Backtracking bezeichnet .

Natürlich scheint (aa*)+b ein Neuling-Fehler zu sein, aber es ist hier, um den Punkt zu veranschaulichen, und manchmal werden Sie mit demselben Problem enden, aber mit komplizierteren Mustern.

Ein extremer Fall von katastrophalem Backtracking tritt mit dem Regex (x+x+)+y (Sie haben es wahrscheinlich hier und hier gesehen ), der exponentielle Zeit benötigt, um herauszufinden, dass eine Zeichenfolge, die x s enthält, und nichts anderes (z xxxxxxxxxxxxxxxxxxxx ) passen nicht zusammen.

Wie vermeide ich es?

Seien Sie so genau wie möglich und reduzieren Sie die möglichen Pfade so weit wie möglich. Beachten Sie, dass einige Regex-Matcher nicht anfällig für Backtracking sind, z. B. diejenigen, die in awk oder grep da sie auf Thompson NFA basieren.