遅い正規表現のパフォーマンス

Question

以下のコードには、C＃文字列リテラルを抽出するために設計された正規表現が含まれていますが、数文字以上の入力文字列の正規表現マッチングの実行は大変です。

class Program 
{ 
    private static void StringMatch(string s) 
    { 
     // regex: quote, zero-or-more-(zero-or-more-non-backslash-quote, optional-backslash-anychar), quote 
     Match m = Regex.Match(s, "\"(([^\\\\\"]*)(\\\\.)?)*\""); 
     if (m.Success) 
      Trace.WriteLine(m.Value); 
     else 
      Trace.WriteLine("no match"); 
    } 

    public static void Main() 
    { 
     // this first string is unterminated (so the match fails), but it returns instantly 
     StringMatch("\"OK"); 

     // this string is terminated (the match succeeds) 
     StringMatch("\"This is a longer terminated string - it matches and returns instantly\""); 

     // this string is unterminated (so the match will fail), but it never returns 
     StringMatch("\"This is another unterminated string and takes FOREVER to match"); 
    } 
} 

正規表現を別の形式にリファクタリングすることはできますが、その理由は誰でも説明できますか？

Answer 1

あなたは（あなたのコメントのように、それがテストした文字列に対して無関係だ、ので、エスケープ引用符と二オプションのグループなし）のビット正規表現を単純化してみましょうcatastrophic backtracking:

に実行している：

"(([^\\"]*))*" 

([^\\"]*)は、引用符またはバックスラッシュを除くすべての文字列と一致します。このは、任意の回数繰り返すことができるオプションのグループで囲まれています。

今すぐ文字列"ABCのために、正規表現エンジンは、次の順列しようとする必要があります。

• "を、ABC
• "、ABC、<empty string>
• "、AB、C
• "、 AB,C、<empty string>
• "、AB、<empty string>、C
• "、AB、<empty string>、C、<empty string>
• "、<empty string>、AB、C
• "、<empty string>、AB、C、<empty string>
• "、<empty string>、AB、<empty string>、C、<empty string>
• "、<empty string>、AB、<empty string>、C
• "、A、BC
• "、A、BC、<empty string>
• "、A、<empty string> 、BC
• "、<empty string>、A、BC
• など
"
• 、A、B、C
"
• 、A、B、C、<empty string>
"
• 、A、B、<empty string>、C
• 等など

その各々のフォロイがないので失敗するng "。

また、正規表現を文字列全体と一致させる代わりに、部分文字列をテストするだけです。そして、通常は正規表現に逐語文字列を使用して、必要なバックスラッシュの数を減らしたいとします。どのようにこの件について：

foundMatch = Regex.IsMatch(subjectString, 
    @"\A  # Start of the string 
    ""  # Match a quote 
    (?:  # Either match... 
    \\.  # an escaped character 
    |  # or 
    [^\\""] # any character except backslash or quote 
    )*  # any number of times 
    ""  # Match a quote 
    \Z  # End of the string", 
    RegexOptions.IgnorePatternWhitespace); 

Answer 2

は、 "インテリジェント" \の偶数を無視します

Match m = Regex.Match(s, @"'.*?(?<=[^\\](\\\\)*)'".Replace("'", "\"")); 

これを試してみてください。この"は、文字列を閉じているため、\"は、（最初​​のバックスラッシュは、二番目のをエスケープするため）\\"はない、\\\"は...

.*?は怠惰な数量詞ではありませんしません。あなたは、標準.*量子を使用することもできます。おそらく、正規表現を^と$とアンカーする必要があります。

私はエスケープ二重引用符は、私はそれが試合にと一致していないの両方、私のコンピュータ上で瞬時に4kのテキストとそのを追加します:-)

頭痛ましたので交換してください使用しています。

Match m = Regex.Match(s, @"^'(?>([^'\\]|\\.)*)'$".Replace("'", "\"")); 

説明：別の方法として

(?>) disables backtracking 

^ begin of the string 

、あなたは交互構築物（0回以上、*）を持っている：

[^'\\] any non-quote and non backslash 

\\. or a backslash followed by another character (that is escaped) 

$ end of the string 

これはあまりにもあります非常に速く、読むのがとても簡単です。 "\"([^\\\\\"]|\\\\.)*\""

説明するために、C＃は、あなたがこの正規表現を取得した文字列エスケープした後： "([^\\"]|\\.)*"

意味：によって

"    #start with a quote 
(
    [^\\"]  #match a non backslash or quote 
    |   #or 
    \\.   #backslash something 
)     
*    #And repeat 
"    #end with a quote 

をあなたが行く

Answer 3

EDITここ

あなたの巣を入れないで*あなたは葬儀を得ないntialまたは無限ループ、それは私のために即座に戻ります。

Answer 4

@Tim Pietzckerがバックトラックについての最も良い説明をしたと思います。周りの様々なベンチマークを通じ

（私自身含まれている）、これらは速い方法があります。、

方法1方法1

" [^"\\]* (?: \\. [^"\\]*)* " 

方法2、交代

" (?: \\. | [^"\\]+)* " 

をアンロール、アウトパフォームすることができます2に大幅なマージンを与える。

情報

私は壊滅的なバックトラックを説明するために、その本当に難しいと思います。たとえそれが時間的に非常に明白でない限り、それを認識することさえ困難です。次に、タイムクリティカルなアプリケーションでは、いくつかのベンチマークを行うことが有益な場合があります。

この引用の主題では、ベンチマークテンプレートのperl（5.10 engined）スクリプトに新しいアプローチを追加して、それがどのように機能するかを確認したいと思います。各エンジンは少し異なります。あなたが気にしているなら、ここにサンプルがあります。

大まかに引用されエスケープされた文字列を使用した正規表現のサンプル対正規表現のサンプル
それぞれ100,000回反復されました。

(?x-ism:" ((?: \\?.)*?) ")
コードがかかった：14.7031ウォールクロック秒（14.58 USR + 0.00 SYS = 14.58 CPU）コードがかかっ

(?x-ism:" (.*? (?<!\\) (?:\\{2})*) ")
：12.8435ウォールクロック秒（12.75 USR + 0.00 SYS = 12.75 CPU）

を

(?x-ism:" ((?: [^\\"] | \\.)*) ")
コードがかかった：10.3123ウォールクロック秒（10.27 USR + 0.00 SYS = 10.27 CPU）

(?x-ism: " ((?: [^"\\]+ | (?:\\.)+)*) ")
コードがかかった：8.39063ウォールクロック秒を（8.39 USR + 0.00 SYS = 8.39 CPU）コードがかかっ

(?x-ism: " ((?: [^"\\]+ | \\.)*) ")
：8.7498ウォールクロック秒（8.75 USR + 0.00 SYS = 8.75 CPU）

(?x-ism: " ((?: \\. | [^"\\]+)*) ")
コードがかかった：8.5623ウォールクロック秒を（8.44 USR + 0.00 SYS = 8.44 CPU）コードがかかっ

(?x-ism: " ([^"\\]* (?: \\. [^"\\]*)*) ")
：7.79661ウォールクロック秒（7.80 USR + 0.00 SYS = 7.80 CPU）

(?x-ism: (?> " ((?: [^"\\] | \\.)* ")))
コードが取った：10.5156壁時計秒（10.52 USR + 0.00 SYS = 10.52 CPU）

Answer 5

をここで私が使用するものです。

"[^\n"\\]*(?:\\.[^\n"\\]*)*" 

@slnはunrolled-に関する正しいですループアプローチは最も速いですが、昔ながらの文字列リテラルでは許可されていない改行を除外することでもう少し洗練されていきます。\\.部分は問題ありませんが、[^"\\]を[^\n"\\]に変更する必要があります。また、の文字列リテラルをとすると、\Aと\Zという正規表現をアンカーできません。

私はRegexBuddyを使用して、正規表現、Timの正規表現、アンカーなしの正規表現のパフォーマンスを比較しました。私はあなたのサンプル文字列と使用「ここでのデバッグ」の各開口部の引用の前にカーソルを置き、これらは結果である：

逐語的文字列として、あなたのコードにそれを差し込む

original regex  : "(([^\\"\n]*)(\\.)?)*" 

"OK     : failed in 101 steps 

"This is a longer... : matched in 12 steps 

"This is another... : gave up after 1,000,000 steps 



Tim's regex   : "(?:\\.|[^\\"\n])*" 

"OK     : failed in 17 steps 

"This is a longer... : matched in 211 steps 

"This is another... : failed in 253 steps 


unrolled loop   : "[^\\"\n]*(?:\\.[^\\"\n]*)*" 

"OK     : failed in 5 steps 

"This is a longer... : matched in 5 steps 

"This is another... : failed in 5 steps 

、あなたが得るでしょう：

Match m = Regex.Match(s, @"""[^\n""\\]*(?:\\.[^\n""\\]*)*"""); 

EDIT：ところで、私はそれが高速ですので、あなたががこの正規表現を使用しなければならないとは言いませんよ。他のソリューションはほぼ確実に十分に速いです。しかし、最大のパフォーマンスが必要な場合（まだ正規表現を使用している間）、これはおそらくそれを達成する方法です。それを非常に速くすることは、正規表現が常に前進することです。逆参照も見逃しもなく、最も重要なのは、バックトラッキングもありません。