Katastrophales Backtracking
Katastrophales Backtracking ist ein Phänomen bei regulären Ausdrücken, bei dem die Engine eine übermäßige Zeit benötigt, um bestimmte Muster auszuwerten, was zu erheblichen Leistungseinbußen führt. Dieses Problem kann auftreten, wenn die reguläre-Ausdruck-Engine wiederholt versucht, Teile des Strings auf verschiedene Weise zu matchen, insbesondere bei komplexen Mustern mit verschachtelten Quantifizierern.
Was verursacht katastrophales Backtracking?
Katastrophales Backtracking tritt typischerweise auf, wenn verschachtelte Quantifizierer in regulären Ausdrücken verwendet werden. Diese Quantifizierer ermöglichen es, Teile des Musters auf mehrere Arten zu matchen, wodurch die Engine übermäßig zurückverfolgt (backtracked). Hier ist ein Beispiel:
Wenn dies auf Ihrem Computer nicht lange dauert, können Sie ein weiteres a-Zeichen zum str hinzufügen. Warum dauert dies also so lange? Lassen Sie es uns analysieren. Das Muster /^(a+)+$/ besteht aus:
^, das die Position am Anfang des Strings assertiert (gibt an).(a+), das ein oder mehrerea-Zeichen matcht.+, das die Wiederholung der vorherigen Gruppe(a+)ein- oder mehrmals erlaubt.$, das die Position am Ende des Strings assertiert (gibt an).
Der Matching-Prozess läuft nun wie folgt ab:
- Initiales Match: Die Engine beginnt am Anfang des Strings (
^). - Erster Gruppen-Match: Die Engine matcht das erste
a+und verbraucht allea-Zeichen (aaa...). - Äußerer Quantifizierer: Der äußere
+erlaubt es der Engine, die(a+)-Gruppe zu wiederholen.
Wenn die Engine das Ausrufezeichen (!) erreicht, kann es nicht mit dem Muster gematcht werden, wodurch das Match fehlschlägt. An diesem Punkt beginnt das Backtracking:
- Backtracking-Versuch: Die Engine backtracked, um die gematchten
a-Zeichen wiederholt zwischen dem innerena+und dem äußeren+-Quantifizierer aufzuteilen. Sie bewertet jede Aufteilung neu, um zu prüfen, ob eine andere Partition das Muster bis zum Ende des Strings matchen kann. - Exponentielles Wachstum: Dieser Backtracking-Prozess kann exponentiell wachsen, da die Engine jeden möglichen Weg versucht, den String der
a-Zeichen in verschiedene Gruppen aufzuteilen, die potenziell(a+)+matchen könnten.
Bei einem String aus n a-Zeichen kann die Anzahl der Möglichkeiten, diese für (a+)+ in Gruppen aufzuteilen, erheblich sein, was die Auswertungszeit dramatisch erhöht.
Erkennen von Mustern, die anfällig für katastrophales Backtracking sind
Muster, die besonders anfällig für katastrophales Backtracking sind, umfassen oft:
- Verschachtelte Quantifizierer (z. B.
(a+)+) - Überlappende Zeichengruppen (z. B.
([a-zA-Z0-9_]+)+) - Mehrdeutige Submuster, die auf viele Arten gematcht werden können
Strategien zur Vermeidung von katastrophalem Backtracking
Um katastrophales Backtracking zu verhindern, sollten Sie folgende Strategien in Betracht ziehen:
1. Verschachtelte Quantifizierer umstrukturieren
Nicht-gierige Quantifizierer verhindern katastrophales Backtracking in verschachtelten Mustern nicht. Stattdessen sollte die Regex umstrukturiert werden, um verschachtelte Quantifizierer zu eliminieren oder begrenzte Quantifizierer zu verwenden.
2. Optimieren Sie Ihre regulären Ausdrücke
Vereinfachen Sie Ihre regulären Ausdrücke, um unnötige Komplexität und Verschachtelung zu vermeiden. Stellen Sie sicher, dass jeder Teil des Musters so spezifisch wie möglich ist.
Praktische Beispiele und Lösungen
Beispiel 1: Matchen verschachtelter HTML-Tags
Ein häufiger Anwendungsfall für Regex ist das Matchen verschachtelter HTML-Tags, was bei unsachgemäßer Handhabung leicht zu katastrophalem Backtracking führen kann. Hinweis: Reguläre Ausdrücke sind im Allgemeinen nicht geeignet, um beliebige oder tief verschachtelte HTML-Strukturen zu parsen; verwenden Sie für komplexe Dokumente einen richtigen HTML-Parser.
Problematisches Muster
Verbessertes Muster
Beispiel 2: Matchen wiederholter Muster
Problematisches Muster
Verbessertes Muster
Fazit
Katastrophales Backtracking kann die Leistung Ihrer JavaScript-Anwendungen bei der Verwendung regulärer Ausdrücke erheblich beeinträchtigen. Durch das Verständnis der Ursachen und die Implementierung von Strategien wie dem Umstrukturieren von Mustern, dem Vermeiden verschachtelter Quantifizierer und der Verwendung begrenzter Quantifizierer können Sie diese Leistungsprobleme verhindern. Testen Sie Ihre regulären Ausdrücke immer mit verschiedenen Eingabelängen und -komplexitäten, um sicherzustellen, dass sie effizient arbeiten.
Praxis
What are the common causes of catastrophic backtracking in regular expressions?