espressione regolare va in loop infinito

Question

sto parsing (specie) i nomi del modulo:

Parus Ater 
H. sapiens 
T. rex 
Tyr. rex 

che hanno normalmente due termini (binomio), ma a volte hanno 3 o più.

Troglodytes troglodytes troglodytes 
E. rubecula sensu stricto 

ho scritto

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)* 

che ha lavorato la maggior parte del tempo, ma di tanto in tanto è andato in un ciclo infinito. C'è voluto del tempo per rintracciare che era in corrispondenza regex e poi ho capito che era un errore di battitura e ho dovuto scrivere

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s+[a-z]+)* 

che svolge correttamente.

Le mie domande sono:

• Perché questo ciclo accada?
• c'è un modo per verificare errori di espressioni regolari simili prima di eseguire il programma? Altrimenti potrebbe essere difficile intercettarli prima che il prgram sia distribuito e causare problemi.

[Nota: Non ho bisogno di un'espressione più generale per le specie - non v'è una specifica formale 100 + linea di espressioni regolari per i nomi di specie - questo era solo un primo filtro].

NOTA: Il problema è sorto perché, anche se la maggior parte dei nomi sono stati estratti con precisione in 2 o occasionalmente 3/4 termini (come lo erano in corsivo) ci sono stati un paio di falsi positivi (come "Homo sapiens lives in big cities like London") e la partita non riesce a "L". ]

NOTA: nel debug di questo ho trovato che la regex si completava spesso ma era molto lenta (ad esempio su stringhe di destinazione più corte). È prezioso che ho trovato questo bug attraverso un caso patologico. Ho imparato una lezione importante!

Answer 1

Per rispondere alla prima parte della domanda, è necessario leggere catastrophic backtracking. In sostanza, ciò che sta accadendo è che ci sono troppi modi per abbinare la tua espressione regolare alla tua stringa, e il parser viene continuamente rintracciato per cercare di farlo funzionare.

Nel tuo caso, era probabilmente la ripetizione annidata: (\s*[a-z]+)* Che probabilmente ha causato alcuni loop molto molto strani. Come ha puntualmente fatto notare Qtax, è difficile dirlo senza ulteriori informazioni.

La seconda parte della tua domanda è, purtroppo, impossibile da rispondere. È fondamentalmente lo Halting problem. Poiché le espressioni regolari sono essenzialmente di una macchina a stati finiti il ​​cui input è una stringa, non è possibile creare una soluzione generale che preveda quali espressioni regolari torneranno indietro in modo catastrofico e quali no.

Per quanto riguarda alcuni suggerimenti per rendere più veloci le espressioni regolari? È una grande lattina di vermi. Ho passato un sacco di tempo a studiare le espressioni regolari per conto mio, e qualche tempo ottimizzandoli, ed ecco cosa ho trovato aiuta in generale:

1. Compilare le espressioni regolari al di fuori dei vostri loop, se il vostro supporto per il linguaggio esso.
2. Se possibile, aggiungi anchors quando sai che sono utili.Soprattutto lo ^ per l'inizio della stringa. Vedi anche: Word Boundaries
3. Evita la ripetizione annidata come la peste. Se devi averlo (cosa che farai), fai del tuo meglio per fornire suggerimenti al motore per cortocircuitare qualsiasi backtracking non intenzionale.
4. Approfitta dei costrutti di sapori per velocizzare le cose. Sono parziale a Non-Capturing groups e possessive quantifiers. Non appaiono in ogni sapore, ma quando lo fanno, dovresti usarli. Controlla anche Atomic Groups
5. Trovo sempre che sia vero: Più lunga è la tua espressione regolare, più problemi avrai rendendolo efficiente. Le espressioni regolari sono uno strumento grande e potente, sono come un martello super intelligente. Don't fall into the trap of seeing everything as a nail. A volte la funzione di stringa che stai cercando è proprio sotto il tuo naso.

Spero che questo ti aiuti. In bocca al lupo.

Answer 2

Per la prima regex:

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)* 

Il backtracking catastrofica accade a causa (\s*[a-z]+)* come evidenziato nel commento. Tuttavia, è valido solo se si sta convalidando la stringa con String.matches(), poiché questo è l'unico caso in cui il rilevamento di un carattere non valido fa sì che il motore provi a tornare indietro, anziché restituire una corrispondenza (ciclo Matcher).

Cerchiamo di abbinare una stringa non valida contro (\s*[a-z]+)*:

inputstringinputstring; 

(Repetition 1) 
\s*=(empty) 
[a-z]+=inputstringinputstring 
FAILED 

Backtrack [a-z]+=inputstringinputstrin 
(Repetition 2) 
\s*=(empty) 
[a-z]+=g 
FAILED 

(End repetition 2 since all choices are exhausted) 
Backtrack [a-z]+=inputstringinputstri 
(Repetition 2) 
\s*=(empty) 
[a-z]+=ng 
FAILED 

Backtrack [a-z]+=n 
(Repetition 3) 
\s*(empty) 
[a-z]+=g 
FAILED 

(End repetition 3 since all choices are exhausted) 
(End repetition 2 since all choices are exhausted) 
Backtrack [a-z]+=inputstringinputstr 

A questo punto, si dovrebbe avere notato il problema. Cerchiamo di definire T(n) come la quantità di lavoro per controllare una stringa di lunghezza n non corrisponde al modello. Dal metodo di backtracking, sappiamo T(n) = Sum [i = 0..(n-1)] T(i). Da ciò possiamo ricavare T(n + 1) = 2T(n), il che significa che il processo di backtracking è esponenziale in termini di complessità temporale!

Modifica *-+evita completamente il problema, dal momento che un caso di ripetizione può iniziare solo al confine tra uno spazio e di un carattere dell'alfabeto inglese. Al contrario, la prima regex consente a un'istanza di ripetizione di iniziare tra due caratteri alfabetici.

Per dimostrarlo, (\s+[a-z]+\s*)* ti darà un inferno di backtracking quando la stringa di input non valida contiene molte parole che sono separate da più spazi consecutivi, poiché consente di avviare più posizioni per un'istanza di ripetizione. Ciò segue la formula b^d dove b è il numero massimo di spazi consecutivi (meno 1) e d è il numero di sequenze di spazi. È meno grave della prima regex che hai (richiede almeno un alfabeto Englsh e un carattere di spazio per ripetizione, al contrario di un alfabeto inglese per ripetizione nella tua prima espressione regolare), ma è ancora un problema.