6

メールアドレスを検証するために、次の正規表現があります。

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

基本的な電子メールで実行すると、美しく機能します。

/^[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');

しかし、長い文字列で実行するとChromeがクラッシュします。

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

私はそれが約40文字で始まることに気づきました

非常に集中的なこの正規表現についてはどうですか？

4

4 に答える 4

7

では、ここで何が起こっているか見てみましょう。ありがたいことに、正規表現を適用するとどうなるかまで、問題はすでに単純化されています

(d+)*@

文字列に

ddddd

が欠落しているため、明らかに一致できません@。しかし、正規表現エンジンがこれをすぐに理解できないのはなぜでしょうか?

本質(d+)*的には、次の一致によって満たすことができます (各グループはスペースで区切られています)。

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

したがって、文字列を分割せずに文字列を照合する方法は 1 つ、文字列を 2 つの文字列に分割する方法は 4 つ、文字列を 3 つに分割する方法は 6 つ、文字列を 4 つに分割する方法は 4 つ、文字列を 5 つの文字列に分割する方法は 1 つです。 . これらのすべての組み合わせは、最終的に次の@.

なぜもっと早くそれを理解しないのですか？まあ、一部の正規表現エンジンは、おそらくこのような単純化された例でそれを行うことができます. ラリー・ウォールがそれをカバーしていると思います。しかし、実際の正規表現はもう少し複雑なので、事前に把握するのははるかに難しいと思います. さらに、このすべての組み合わせ試行が起こらないようにする簡単な方法があります。しかし、私は後でそれに戻ります。

私は、これらのちっぽけな 5 よりも長い文字列に対して、そのような組み合わせがいくつあるのか疑問に思っていましたd。

長さのあるひもを取りましょうm(さまざまな位置で切り離すことができますm-1)。としましょうn = m-1。次に、次のように組み合わせの数を計算できます。

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

最初と最後の項目は常に 1 ですが、その間の項目は非常に大きくなる可能性があります。小さな Python プログラムを書きましょう:

>>> 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、うまくいくようです。もっと大きなものを試してみましょう:

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

ねえ、ここにパターンがあります: ways_to_split(n)is equal to 2**(n-1). 証明については、Mathematics SEを参照してください。ともかく。正規表現にはO(2^n)複雑さがあります。さて、これで時間がかかる理由がわかりました...

ありがたいことに、多くの正規表現エンジンはこれに対する保護を提供します: 所有量指定子またはアトミック キャプチャ グループ。

(d++)*

また

(?>d+)*

どちらも、d+他の組み合わせを試すために一致したものが再び放棄されないようにします。良いニュースですね。

JavaScript を使用している場合はそうではありません。これらの機能のいずれもサポートしていません。

したがって、次のようにバックトラッキングの影響を受けないように正規表現を書き直す必要があります。

それ以外の

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

使用する

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

または、いずれにせよ、正規表現を使用して電子メール アドレスを検証しようとするのはやめてください。

于 2012-10-09T22:00:27.650 に答える
2

正規表現で電子メールを検証しないでください。これは20年ほど前から常識だったと思います。複雑すぎます。ほぼ完全な検証の例はここにあります http://www.ex-parrot.com/~pdw/Mail-RFC822-Address.htmlでさえ、標準を完全に実装していません。同じことを行う関数を書くのははるかに簡単です。電子メールの一部を個別に検証できる場合、それは簡単になります。さらに、あなたの場合と同様に、関数はこれをはるかに高速に実行します。

于 2012-10-09T17:59:08.210 に答える
2

問題の根本はここにあります：

[_.-]?

最初の[A-Za-z0-9]+(+ちなみに、を省略した) 使用する英数字が不足し、次の文字が区切り文字 ( [_.-]) のいずれでもない場合、一致の試行はすぐに失敗するはずです。

正規表現で何が起こるかというと、最初[A-Za-z0-9]+の文字がバックオフを開始し、一致したばかりの文字を 1 つずつ放棄し、2 番目[A-Za-z0-9]+(*ループ内) が代わりにそれらの文字を一致させようとすることです。それはそれが試さなければならない多くの組み合わせです（ティムの論文の答えが説明するように☺）、そしてそれはすべて完全に無意味です.

これを見てください：

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

この正規表現は*、区切り文字の 1 つが実際に検出されない限り、ループに入りません。内の部分式は*オプションである場合がありますが、それが一致するものは何でも、、、またはで始まる必要があります。同様に、正規表現がローカル部分の一致に成功し、次の文字が ではない場合、すぐに救済され、バックトラッキングの別の発作が発生します。_.-@

RegexBuddy によると、あなたの正規表現は一致するのに 57 ステップかかりますがdave@the-taylors.org、私の場合は 17 ステップです。そして、あなたが他の文字列に固執する場所で、私のものは 5 つのステップで一致の失敗を報告します。

教訓は、実際にはオプションではないものに?or数量詞を使用しないことです。*

免責事項:電子メール アドレスを照合するために、この正規表現やその他の正規表現を使用することを推奨するものではありません。質問の正規表現の何が問題なのかを説明しているだけです。

于 2012-10-10T04:18:03.560 に答える
2

文字列の長さではなく、正規表現に関連していると思います。メールの検証に次の正規表現を使用しましたが、Chrome ではクラッシュしませんでした..

/^(([^<>()[\]\\.,;:\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');
于 2012-10-09T16:05:06.247 に答える