Javascript regex: Hier finden Sie alle URLs Optimierung

Diese Frage ist ein Follow-up für den folgenden Beitrag: Javascript regex: Find all URLs outside <a> tags - Nested Tags Javascript regex: Hier finden Sie alle URLs Optimierung

Ich entdeckte, dass der Code:

\b((https?|ftps?):\/\/[^"<\s]+)(?![^<>]*>|[^"]*?<\/a)

extrem ineffizient ist im Vergleich zu separat Ausführung für http und ftp Teil wie folgt aus:

\b(https?:\/\/[^"<\s]+)(?![^<>]*>|[^"]*?<\/a)

und

\b(ftps?:\/\/[^"<\s]+)(?![^<>]*>|[^"]*?<\/a)

Hier sind einige Beispiele an regex101.com:

1. Methode - 6395 steps
2. Methode - 3393 steps + 863 steps

jedoch in einer meiner HTML-Seite diese Codes vergleicht als Schritte vs. 7258 + 795 st Eps, das ist ziemlich verrückt.

Soweit ich gesehen habe, reduziert die Verwendung von (x|y) Muster die Ausführungslänge, aber hier wahrscheinlich aus einem seltsamen Grund ist es anders.

Jede Hilfe wäre willkommen.

Quelle

2016-03-12 Klaidonis

Was ist das letzte Glied in Ihren Beispieldaten? Es ist mit '' gemeint. Sie können jedoch den Lookahead nach einem festen Teil Ihrer Regex setzen, um Schritte zu reduzieren. Probieren Sie ['\ b (?: Htt | ft) ps?: \/\/(?! [^ <>] *> | [^"] *? <\/A) [^ "<\ s] +' ] (https://regex101.com/r/tZ1yY2/1). Der bessere Weg wäre, [diesen Trick] (http://www.rexegg.com/regex-best-trick.html#thetrick) zu verwenden, um das zu erreichen, was du nicht willst, aber erfasse, was du brauchst: [' | <[^>] +> | \ b ((?: Htt | ft) ps?: \/\/[^ "<\ S] +)'] (https://regex101.com/r/tZ1yY2/2) , Javascript regex unterstützt Atomic Groups nicht –

Wenn Sie suchen, finden Sie alle Links in Dokument als Lösung ist dies. es ein Array

document.anchors

Quelle

2016-03-12 09:23:41

Wie der vorherige Beitrag erklärt - Ich möchte alle URLs finden, die außerhalb der Anker sind() Tags – Klaidonis

Es scheint, dass Sie ein Opfer von catastrophic backtracking sind.

Diese Regex funktioniert der Trick in nur 3492 Schritte:

\b(?>(https?|ftps?):\/\/[^"<\s]+)(?![^<>]*>|[^"]*?<\/a)

Alles, was ich getan haben wird, die erste Gruppe eine atomic group, wodurch der Motor alle Rückzieher Optionen zu verwerfen, sobald sie es abgestimmt ist.

Das ist in Ihrem Fall richtig: Sie können es sich jetzt als zwei Teile vorstellen, "finden Sie eine URL" dann "Verwenden Sie den negativen Lookahead, um zu entscheiden, ob wir es behalten wollen". Ihre ursprüngliche Regex würde, wenn der Lookahead fehlgeschlagen ist, mit dem Zurückverfolgen des url-passenden Ausdrucks fortfahren. Der [^"<\s]+ Block würde einige Symbole ergeben, dann würde es den Lookahead wieder versuchen, dann ein paar weitere Symbole ergeben und es erneut versuchen, und so weiter ...

Der Grund der Hinzufügung des https?|ftps? Teils machte es so viel schlimmer Dies bietet eine zusätzliche Quelle für Backtracking (das Verlieren der optionalen s), so dass das spätere Backtracking wieder von vorn beginnt.

Sie wissen, dass regex101.com eine "Regex Debugger" -Option auf der Symbolleiste auf der linken Seite hat? Wenn Sie das verwenden, erklärt es , wie Ihre Regex übereinstimmt, so können Sie (wie ich gerade) herausfinden, wo das verrückte Backtracking ist.

Bonus edit: Eine weiter verbesserte eine, die nur 3185 Schritte:

\b(?>ht|f)tps?:\/\/(?>[^"<\s]+)(?![^<>]+>|[^"]*?<\/a)

Quelle

2016-03-12 10:19:09

Vielen Dank! Ich war mir der katastrophalen Rückverfolgung, die ich auch mit der gefunden Hilfe des Debuggers, aber konnte es nicht lösen – Klaidonis

Der Trick ist, herauszufinden, welche Teile Ihrer Regex überleben können, atomic so zu werden.Ihr Beispiel ist ein einfaches, aber viele Regexes erfordern viel Rückverfolgung, um richtig zu arbeiten. Manchmal ist es möglich die Regex ein wenig zu rejigieren, um diesen Trick besser zu machen. –

Javascript regex: Hier finden Sie alle URLs Optimierung

Antwort

Verwandte Themen