Ich habe die folgende RegExp, um eine E-Mail-Adresse zu validieren:

^[A-Za-z0-9](([_\.\-]?[a-zA-Z0-9]+)*)@([A-Za-z0-9]+)(([\.\-]?[a-zA-Z0-9]+)*)\.([A-Za-z]{2,})$

Das Ausführen in einer einfachen E-Mail funktioniert hervorragend:

/^[A-Za-z0-9](([_\.\-]?[a-zA-Z0-9]+)*)@([A-Za-z0-9]+)(([\.\-]?[a-zA-Z0-9]+)*)\.([A-Za-z]{2,})$/.test('dave@the-taylors.org');

Wenn Sie es jedoch auf einer langen Zeichenfolge ausführen, stürzt Chrome ab:

/^[A-Za-z0-9](([_\.\-]?[a-zA-Z0-9]+)*)@([A-Za-z0-9]+)(([\.\-]?[a-zA-Z0-9]+)*)\.([A-Za-z]{2,})$/.test('dddddddddddddddddddddddddddddddddddddddd');

Ich habe bemerkt, dass es bei ungefähr 40 Zeichen beginnt

Was ist an diesem RegExp so intensiv?

6
Dave Taylor 9 Okt. 2012 im 19:53

3 Antworten

Beste Antwort

OK, mal sehen, was hier passiert. Zum Glück haben Sie das Problem bereits dahingehend vereinfacht, was passiert, wenn Sie den regulären Ausdruck anwenden

(d+)*@

Zum String

ddddd

Was eindeutig nicht übereinstimmen kann, weil das @ fehlt. Aber was hält die Regex-Engine davon ab, dies schnell herauszufinden?

Nun, (d+)* kann im Wesentlichen durch die folgenden Übereinstimmungen erfüllt werden (jede Gruppe durch Leerzeichen getrennt):

ddddd
dddd d
ddd dd
dd ddd
d dddd
ddd d d
dd d dd
d d ddd
dd dd d
d dd dd
d ddd d
d d d dd
d d dd d
d dd d d
dd d d d
d d d d d

Sie haben also eine Möglichkeit, die Zeichenfolge abzugleichen, ohne die Zeichenfolge aufzubrechen, vier Möglichkeiten, sie in zwei Zeichenfolgen aufzuteilen, sechs Möglichkeiten, sie in drei aufzuteilen, vier Möglichkeiten, sie in vier aufzuteilen, und eine Möglichkeit, sie in fünf Zeichenfolgen aufzuteilen . Alle diese Kombinationen müssen von der Regex-Engine überprüft werden, bevor sie eine Nichtübereinstimmung erklären kann, wenn sie schließlich mit dem folgenden @ konfrontiert werden muss.

Warum findet es das nicht früher heraus? Nun, einige Regex-Engines können dies wahrscheinlich mit einem so vereinfachten Beispiel tun. Ich wette, Larry Wall hat das abgedeckt. Aber Ihre tatsächliche Regex ist etwas komplexer, daher wäre es wahrscheinlich viel schwieriger, dies vorher herauszufinden. Außerdem gibt es eine einfache Möglichkeit, um sicherzustellen, dass all diese Kombinationsversuche nicht stattfinden. Aber darauf komme ich später zurück.

Ich hatte mich gefragt, wie viele solcher Kombinationen es für eine längere Zeichenfolge geben würde als diese mickrigen fünf d s:

Nehmen wir eine Zeichenfolge mit der Länge m (die an verschiedenen Positionen in m-1 auseinandergeschnitten werden kann). Sagen wir n = m-1. Dann können Sie die Anzahl der Kombinationen wie folgt berechnen:

1 + (n!/(1! * (n-1)!)) + (n!/(2! * (n-2)!)) + ... + (n!/(n! * (n-n)!))

Der erste und der letzte Gegenstand sind immer 1, aber die dazwischen liegenden Gegenstände können ziemlich groß werden. Schreiben wir ein kleines Python-Programm:

>>> from math import factorial as f
>>> def comb(n,x):
...    return f(n) // (f(x) * f(n-x))
...
>>> def ways_to_split(len):
...    return 1 + sum(comb(len-1,x) for x in range(1,len))
...
>>> ways_to_split(5)
16

OK, scheint zu funktionieren. Versuchen wir etwas Größeres:

>>> ways_to_split(10)
512
>>> ways_to_split(40)
549755813888
>>> ways_to_split(100)
633825300114114700748351602688

Hey, hier gibt es ein Muster: ways_to_split(n) ist gleich 2**(n-1). Einen Beweis finden Sie unter Mathematics SE. Wie auch immer. Ihr regulärer Ausdruck ist O(2^n) komplex. Nun sehen Sie, warum das eine Weile dauern könnte ...

Zum Glück bieten viele Regex-Engines Schutz davor: Possessive Quantifizierer oder atomare Erfassungsgruppen.

(d++)*

Oder

(?>d+)*

Beide stellen sicher, dass das, was d+ übereinstimmt, nicht erneut aufgegeben wird, um andere Kombinationen auszuprobieren. Gute Nachrichten, richtig?

Nicht, wenn Sie JavaScript verwenden. Keine dieser Funktionen wird unterstützt.

Daher müssen Sie entweder Ihre Regex neu schreiben, um nicht für das Zurückverfolgen wie folgt anfällig zu sein:

Anstatt von

(([_\.\-]?[a-zA-Z0-9]+)*)

Verwenden

[a-zA-Z0-9]+([_.-][a-zA-Z0-9]+)*

Oder hören Sie auf, einen regulären Ausdruck zu verwenden, um eine E-Mail-Adresse zu überprüfen, die ohnehin nie zuverlässig funktioniert.

7
Community 13 Apr. 2017 im 12:19

Überprüfen Sie E-Mails nicht mit regulären Ausdrücken. Ich denke, das war seit ungefähr zwanzig Jahren allgemein bekannt. Es ist zu komplex. Ein Beispiel für eine größtenteils vollständige Validierung finden Sie hier http: //www.ex- parrot.com/~pdw/Mail-RFC822-Address.html und selbst das implementiert den Standard nicht vollständig. Es ist viel einfacher, eine Funktion zu schreiben, die dasselbe tut. Wenn Sie Teile der E-Mail separat validieren können, wird dies trivial. Außerdem würde die Funktion, wie in Ihrem Fall, dies viel schneller tun.

2
user797257user797257 9 Okt. 2012 im 17:59

Ich denke, es hängt mit Ihrer Regex zusammen, nicht mit der Länge der Zeichenfolge. Ich habe den folgenden regulären Ausdruck für die E-Mail-Validierung verwendet und er ist in Chrome nicht abgestürzt.

/^(([^<>()[\]\\.,;:\s@\"]+(\.[^<>()[\]\\.,;:\s@\"]+)*)|(\".+\"))@((\[[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\])|(([a-zA-Z\-0-9]+\.)+[a-zA-Z]{2,}))$/.test('dddddddddddddddddddddddddddddddddddddddd');
2
scusyxx 9 Okt. 2012 im 16:05