Backtracking are loc atunci când un model de expresie regulată conține cuantificatorii variabile sau modificări de proiectare. și regulate ale motorului de expresie revine la starea salvată anterior pentru a continua căutarea unui meci. Backtracking Puterea expresiilor regulate. Datorită lui, expresia poate fi puternică și flexibilă, dar, de asemenea, coincide cu modele complexe. Pe de altă parte, aceste caracteristici sunt scumpe. De multe ori, este backtracking reduce semnificativ performanța motorului de expresie regulată. Din fericire, dezvoltatorul poate controla funcționarea motorului de expresie regulată și modul în care utilizează backtracking. Această secțiune descrie modul în care backtracking, și modul în care acestea pot fi controlate.
În general, atunci când se utilizează AFN-mașină (non-determinist automate finite), cum ar fi un cadru procesor NET expresii regulate, responsabile pentru crearea de funcționare eficientă și rapidă a expresiilor regulate este pe dezvoltator.
Această secțiune cuprinde următoarele subpuncte.
În cazul în care un model de expresie regulată nu conține cuantificatori sau modificări variabile ale structurilor, motorul de expresie regulată se execută în timp liniar. Acest lucru înseamnă că, atunci când motorul de expresie regulată găsește o potrivire cu primul șir de intrare șablon de text element de limbaj, acesta compară următorul șablon element de limbaj cu următoarele simboluri, sau un grup de caractere din șirul de intrare. Acest lucru continuă până la căutarea unui meci nu se încheie cu succes sau fără succes. În ambele cazuri, motorul expresie regulată avansează prin prelucrarea unui caracter din șirul de intrare.
Exemplul următor ilustrează.
O expresie regulată e \ w \ b caută următoarea linie: două apariții ale lui «e» scrisoarea, apoi simbolul cuvântului, apoi cuvântul de delimitare.
În ciuda faptului că aceasta conține o Cuantificator expresie regulată. este procesat într-un mod liniar. Motorul expresie regulată nu efectuează backtracking, deoarece cuantificatorul nu este un cuantificator variabile; indică o anumită, mai degrabă decât un număr variabil de apariții ale expresiei precedente. Ca urmare, expresia regulată caută un meci cu șablonul din șirul de intrare, așa cum se arată în tabelul de mai jos.
Poziția în șablon
În cazul în care un regulate cuantificatorii modelul de expresie nu sunt variabile sau de a modifica desene, numărul maxim de comparații necesare pentru a căuta în șirul de intrare se potrivește cu modelul de expresie regulată, aproximativ egal cu numărul de caractere din șirul de intrare. În acest caz, motorul expresie regulată utilizează 19 comparații pentru a determina posibile potriviri în șirul de 13 cifre. Cu alte cuvinte, motorul expresie regulată funcționează aproape în timp liniar, în cazul în care nu există variabile sau cuantificatori modificări de design.
Dacă expresia regulată include variabile cuantificatorii sau schimbarea de design, evaluarea șirului de intrare nu poate fi liniară. Când utilizați AFN-mașină șablon de potrivire de elementele de limbaj ale unei expresii regulate, nu caracterele din șirul de intrare. Prin urmare, motorul expresie regulată încearcă să găsească un meci complet pentru alegerea variabilă sau subexpressions subexpression. În tranziția la următoarea subexpressions element de limbaj și de abuz se potrivește cu motorul de expresie regulată aruncă o parte sălbatice și revine la starea salvată anterior; este necesar pentru a găsi din nou în șirul de intrare se potrivește cu expresia regulată ca întreg. Procesul de revenire la o stare salvată anterior pentru a găsi un meci numit „backtracking“.
De exemplu, să considerăm un model de expresie regulată. * (Es). care coincide cu caracterele „ES“ și oricare dintre caracterul precedent. După cum se arată în exemplul următor, dacă luăm șirul de intrare „serviciile esențiale sunt furnizate de expresii regulate.“, La fel ca modelul va alinia toate în sus literele „ES“, în cuvântul „expresii“ inclusiv.
În acest caz, motorul expresie regulată utilizează un backtracking după cum urmează.
Handler găsește o potrivire a expresiei. * (Care se potrivește cu orice număr de caracter), cu întregul șir de intrare.
Apoi, handler caută un meci pentru simbolul „e“ modelul de expresie regulată. Cu toate acestea, șirul de intrare nu este mai de caractere pentru a găsi un meci.
Handler revine la locul ultimului meci de succes, „serviciile esențiale sunt furnizate de expresii regulate“, și compară caracterul „e“ cu un punct la sfârșitul propozițiilor. Nici o coincidență.
Handler continua sa vina inapoi la meciul cu succes anterior, pas cu pas înapoi un caracter, în timp ce subșir probabil potrivite devine subșir „serviciile esențiale sunt furnizate de expr regulate“. Apoi, procesorul compară simbolul „e“ modelul cu a doua litera „e“ în „expresiile“ cuvânt și găsește un meci.
Se compară apoi simbolul „S“ model cu simbolul „s“ după „e“ caracter din șirul (prima literă „s“ în „expresiile“ cuvânt). meci de succes.
Atunci când se utilizează o căutare backtracking pentru o potrivire a modelului de expresie regulată cu lungimea șir de intrare de 55 de caractere necesită 67 de operații de comparare. Interesant, în cazul în care modelul de expresie regulată include un cuantificator leneș, *? (Es). căutarea unui meci va necesita comparații suplimentare. În acest caz, este necesar să se efectueze o căutare inversă la începutul liniei în căutare de „Es“, în loc de căutare inversă de la sfârșitul liniei înainte de caracterul „r“ în „expresiile“ cuvânt expresie regulată, ceea ce ar necesita 113 comparații. De regulă, în cazul în care un model de expresie regulată, există un cuantificator variabilă sau o modificare a structurii, numărul de comparații necesare pentru a căuta în șirul de intrare se potrivește cu modelul de expresie regulată, mai mult de două ori numărul de caractere din șirul de intrare.
Numărul de comparații necesare pentru a căuta în șirul de intrare se potrivește cu modelul de expresie regulată, poate crește exponențial în cazul în care șablonul include un număr mare de modificări sau modificări de proiectare a structurilor imbricate, sau ceea ce se întâmplă variabile cuantificatorii mai des imbricate. De exemplu, modelul de expresie regulată ^ (a +) + $ ar trebui să se potrivească șirul format din unul sau mai multe caractere „o“. Exemplul prezintă două linii de intrare de aceeași lungime, dintre care numai una coincide cu modelul. System.Diagnostics Class. Cronometrul utilizat pentru determinarea timpului de execuție corespunde operațiunii de căutare.
Ca exemplu de ieșire, motorul expresie regulată pentru a stabili lipsa de coincidență cu șablonul durează de două ori mai mult timp decât găsirea unui meci. Nereușită coincidență - cel mai rău scenariu. Expresia regulată este de a utiliza o expresie regulată pentru a testa toate căile posibile de date pentru a concluziona că nu există nici un meci, iar parantezele imbricate crește foarte mult numărul de astfel de căi. Pentru a stabili că a doua linie nu coincide cu modelul, motorul de expresie regulată, efectuați următorii pași:
Se verifică dacă stocate la începutul liniei, iar apoi verifică primele cinci caractere ale șirului pentru un meci cu șablon a +. Apoi verifică dacă linia are alte grupuri de caractere „o“. Apoi, se realizează un test înainte de sfârșitul liniei. Deoarece linia de verificare conține un simbol suplimentar, nu are succes. Acest rezultat negativ necesită 9 comparații. Motorul expresie regulată păstrează, de asemenea, informații despre starea când coincidență "a" (Match 1), "aa" (coincidență 2), "aaa" (coincidență 3) și "aaaa" (Match 4).
Apoi revine la stocată anterior 4. Apoi coincidență, o prezență de simbol suplimentar „o“, care este atribuit grup capturat suplimentar. Apoi, se realizează un test înainte de sfârșitul liniei. Deoarece linia de verificare conține un simbol suplimentar, nu are succes. Acest rezultat negativ necesită patru comparații. Astfel, un total de 13 comparații efectuate.
Apoi se intoarce la salvat anterior coincidență 3. Se stabilește existența a două caractere suplimentare „a“, care sunt numiți de către un grup de capturat suplimentar. Cu toate acestea, verificarea la sfârșitul liniei nu trece. Handler se întoarce pentru a coincide cu 3 și încearcă să se potrivească cu două caractere suplimentare „o“ cu două grupuri suplimentare capturate. Verificarea pentru linia de închidere nu trece. Pentru cei de meciuri eșuate necesită 12 comparații. Astfel, un total de 25 de comparații efectuate.
Comparând șirul de intrare față de o expresie regulată continuă în acest mod până când expresia regulată nu este enumără toate combinațiile posibile de chibrituri, concluzionând că nu există nici un meci. Datorită prezenței cuantificatorilor nested această comparație este o operațiune exponențială complexitate O (2 n) unde n - numărul de caractere din șirul de intrare. Acest lucru înseamnă că, în cel mai rău caz, linia de intrare constând din 30 de caractere necesită la estimări aproximative 1073741824 comparații, și o linie de intrare de 40 de caractere - 1 099 511 627 776 comparații. Când se utilizează astfel de rânduri sau tehnici mai mari de operare expresii regulate pot fi executate pentru o lungă perioadă de timp înainte de a se stabilește că șirul de intrare nu se potrivește cu modelul de expresie regulată.
Deoarece .NET Framework 4.5, se poate seta valoarea timeout, care este egală cu valoarea cea mai lungă intervalul necesar expresia regulată pentru a căuta meciuri la prima, în timp ce acesta nu va suspenda încercări de a găsi un meci și nu va provoca o RegexMatchTimeoutException excepție. Pentru a seta timeout, introduceți valoarea în constructor Perioadă de timp Regex. Regex (String, RegexOptions, Durata de timp), de exemplu expresie regulată. În plus, fiecare metodă statică de comparație cu un șablon are o versiune supraalimentata cu parametrul Perioadă de timp. care vă permite să specificați o valoare timeout. Intervalul de timp de expirare implicit este specificat în regex. InfiniteMatchTimeout și în timp ce de așteptare pentru handler expresie regulată expiră.
Este întotdeauna recomandat să setați intervalul de expirare, în cazul în care expresia regulată utilizează backtracking.
Expresia RegexMatchTimeoutException indică faptul că motorul de expresie regulată nu a putut găsi un meci într-un interval de timeout specificat, dar nu specifică cauza de a crea o excepție. Motivul poate fi excesivă în Backtracking și valoarea intervalului de timp suficient de așteptare pentru încărcarea sistemului curent la momentul excepției. Procesarea o excepție poate fi întreruptă de o căutare ulterioară a meciurilor șirului de intrare sau de a mări intervalul de timeout și executați operația de căutare.
De exemplu, următorul cod apelează constructorul Regex. Regex (String, RegexOptions, Durata de timp) la instantieze regex obiect cu valoarea timpului de așteptare egală cu o secundă. model expresie regulată (a +) + $. care este comparat cu secvența unuia sau mai multor caractere „o“ în capătul liniei se referă la șabloanele cu utilizarea excesivă a backtracking. Dacă creați RegexMatchTimeoutException excepție. intervalul de timp de așteptare în acest exemplu este crescută la o valoare maximă egală cu trei secunde. După această încercare de a se potrivi cu modelul va fi întreruptă.