Powolne działanie Regexa

Question

Poniższy kod zawiera wyrażenie regularne przeznaczone do wyodrębniania literału C#, ale wydajność dopasowywania do wyrażenia regularnego dla ciągów wejściowych składających się z więcej niż kilku znaków jest fatalna.

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"); 
    } 
} 

Potrafię przekształcić wyrażenie regularne w inną formę, ale czy każdy może podać wyjaśnienie, dlaczego wydajność jest tak zła?

Answer 1

używasz do catastrophic backtracking:

Załóżmy uprościć regex nieco (bez uciekły cudzysłowie i bez drugiego opcjonalnego grupy, ponieważ, podobnie jak w swoim komentarzu, że to bez znaczenia dla badanych ciągów):

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

([^\\"]*) dopasowuje dowolny ciąg oprócz cudzysłowów lub odwrotnych ukośników. Ten ponownie jest zamknięty w opcjonalnej grupie, która może być powtarzana dowolną liczbę razy.

teraz na ciąg "ABC silnik regex musi wypróbować następujące permutacje:

• ", 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
• etc.
• ", A, B, C
• ", A, B, C, <empty string>
• ", A, B, <empty string>, C
• itd. Itd., Z których

każde następnie kończy się niepowodzeniem, ponieważ nie ma kontynuacji ng ".

Ponadto, testujesz tylko podłańcuchy, zamiast zmuszać wyrażenie regularne do dopasowania do całego ciągu znaków. Zwykle chcesz używać ciągów wiernych dla wyrażeń regularnych, aby zmniejszyć liczbę potrzebnych ciasnych ukośników. Jak o tym:

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

Spróbuj

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

będzie to "inteligentnie" ignoruj ​​parzystą liczbę \. To dlatego " zamyka ciąg, \" nie, \\" robi (bo pierwsza backslash ucieka drugi), \\\" nie ...

.*? jest leniwy kwantyfikator. Możesz nawet użyć kwantyfikatora standardowego .*. Powiem, że być może powinieneś zakotwiczyć swoje wyrażenie regularne za pomocą ^ i $.

Używam Zamień ponieważ uchodzące cudzysłowy dał mi bóle głowy :-)

dodam, że z tekstu 4k jest to chwilowa na moim komputerze, zarówno w meczu i nie pasują do siebie.

Jako alternatywę:

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

Objaśnienie:

(?>) disables backtracking 

^ begin of the string 

wtedy masz przemienne konstrukt (0 lub więcej razy, *):

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

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

$ end of the string 

To też jest bardzo szybko i jest to dość łatwe do odczytania.

Answer 3

EDIT

Proszę bardzo: "\"([^\\\\\"]|\\\\.)*\""

Aby wyjaśnić, po C# uciekł ciąg masz ten regex: "([^\\"]|\\.)*"

Znaczenie:

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

Przez nie zagnieżdżając twojego * nie dostaniesz expone ntial lub nieskończona pętla, i natychmiast dla mnie wraca.

Answer 4

Myślę, że @Tim Pietzcker dał najlepsze wyjaśnienie dotyczące wycofywania.

Poprzez różne odniesienia wokół (wliczone własne) są to szybkie sposoby:

Metoda 1, rozwijając

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

metody 2 naprzemienne

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

Metoda 1, może przewyższyć 2 przez znaczne marże.

informacji

myślę, że naprawdę trudno wyjaśnić katastrofalny Backtracking. Nawet rozpoznanie tego jest czasem trudne, chyba że jest to bardzo oczywiste. Następnie, w aplikacjach krytycznych czasowo, czasami warto wykonać pewne testy porównawcze.

W tym temacie chciałbym dodać nowe podejścia do skryptu wzorcowego perl (5.10 engined), aby zobaczyć, jak to działa. Każdy silnik jest trochę inny. Jeśli ci zależy, oto przykład.

Próby Regexa w funkcji czasu z użyciem silnie cytowanych i unikniętych ciągów znaków
iterowane 100 000 razy.

(?x-ism:" ((?: \\?.)*?) ")
kod trwało: 14.7031 sek wallclock (14,58 usr + 0.00 sys = 14,58 CPU)

(?x-ism:" (.*? (?<!\\) (?:\\{2})*) ")
kod miały: 12.8435 wallclock sek (12,75 usr + 0.00 sys = 12,75 CPU)

(?x-ism:" ((?: [^\\"] | \\.)*) ")
kod wzięli: 10.3123 sek wallclock (10.27 usr + 0.00 sys = 10,27 CPU)

(?x-ism: " ((?: [^"\\]+ | (?:\\.)+)*) ") kod trwało: 8.39063 wallclock sek (8.39 usr + 0.00 sys = 8,39 CPU)

(?x-ism: " ((?: [^"\\]+ | \\.)*) ")
kod trwało: 8.7498 sekund wallclock (8,75 usr + 0.00 sys = 8,75 CPU)

(?x-ism: " ((?: \\. | [^"\\]+)*) ")
kod trwało: 8.5623 wallclock sek (8,44 usr + 0,00 = 8,44 sys CPU)

(?x-ism: " ([^"\\]* (?: \\. [^"\\]*)*) ")
kod trwało: 7.79661 sekund wallclock usr (7,80 + 0,00 = 7,80 sys CPU)

(?x-ism: (?> " ((?: [^"\\] | \\.)* ")))
kod wzięli: 10.5156 sek wallclock (10,52 usr + 0.00 sys = 10,52 CPU)

Answer 5

Oto co chciałbym używać:

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

@sln jest poprawna o unrolled- Podejście pętlowe jest najszybsze, ale chciałbym udoskonalić je nieco, wykluczając przekazywanie linii, które nie są dozwolone w staromodnych ciągach literowych.Część \\. jest w porządku, ale [^"\\] należy zmienić na [^\n"\\]. Ponadto, jeśli mówimy o wymianie ciągów literowych , nie możemy zakotwiczyć regex za pomocą \A i \Z.

Użyłem RegexBuddy do porównania wydajności Twojego wyrażenia regularnego, regexu Tima bez kotwicy i tego. Umieściłem kursor przed otwarciem środki w każdym z ciągów próbek i używane „Debug tutaj”, a oto wyniki:

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 

podłączając że w kodzie jako dosłownego łańcucha, co można uzyskać:

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

EDIT: Nawiasem mówiąc, ja nie mówię, że moszczu wykorzystanie tego regex, ponieważ jest szybszy; inne rozwiązania są prawie na pewno wystarczająco szybkie. Ale jeśli potrzebujesz maksymalnej wydajności (przy jednoczesnym użyciu wyrażenia regularnego), jest to prawdopodobnie sposób na osiągnięcie tego. To, co sprawia, że ​​jest tak szybki, to to, że regex zawsze porusza się do przodu: bez odsyłania wstecznego, bez patrzenia, i co najważniejsze, bez cofania.