Come funzionano effettivamente le espressioni regolari?

How does it work?

Dai un'occhiata alla teoria degli automi

In breve, ogni espressione regolare ha un automa finito equivalente e può essere compilata e ottimizzata per un automa finito. Gli algoritmi coinvolti possono essere trovati in molti libri del compilatore. Questi algoritmi sono usati dai programmi unix come awk e grep.

Tuttavia, la maggior parte dei linguaggi di programmazione moderni (Perl, Python, Ruby, Java (e linguaggi basati su JVM), C #) non utilizzano questo approccio. Usano un approccio di backtracking ricorsivo, che compila un'espressione regolare in un albero o una sequenza di costrutti che rappresentano vari sotto-pezzi dell'espressione regolare. Le sintassi più moderne di "espressione regolare" offrono backreferenze che sono al di fuori del gruppo di linguaggi regolari (non hanno rappresentazione in automi finiti), che sono banalmente implementabili nell'approccio ricorsivo di backtracking.

L'ottimizzazione di solito produce una macchina a stati più efficiente. Ad esempio: considerare aaaab | aaaac | aaaad, un normale programmatore può ottenere un'implementazione di ricerca semplice ma meno efficiente (confrontando tre stringhe separatamente) in soli dieci minuti; ma rendendosi conto che è equivalente aaaa [bcd], una ricerca migliore può essere eseguita cercando i primi quattro "a" e poi testando il quinto personaggio contro [b, c, d]. Il processo di ottimizzazione è stato uno dei miei lavori di compilatore a casa molti anni fa quindi presumo che sia anche nella maggior parte dei moderni motori di espressioni regolari.

D'altra parte, le macchine a stati hanno qualche vantaggio quando accettano le stringhe perché usano più spazio rispetto a una "implementazione banale". Si consideri un programma per annullare la citazione su stringhe SQL, ovvero: 1) inizia e termina con virgolette singole; 2) le virgolette singole sono sfuggite da due citazioni singole consecutive. Quindi: input ['a' ''] dovrebbe produrre output [a ']. Con una macchina a stati, le virgolette singole consecutive vengono gestite da due stati. Questi due stati hanno lo scopo di ricordare la cronologia di input in modo tale che ogni carattere di input venga elaborato esattamente una sola volta, come illustrato di seguito:

...
S1->'->S2
S1->*->S1, output *, * can be any other character 
S2->'->S1, output '
S2->*->END, end the current string

Quindi, a mio parere, l'espressione regolare potrebbe essere più lenta in alcuni casi banali, ma di solito più veloce di un algoritmo di ricerca manuale, dato che l'ottimizzazione non può essere eseguita in modo affidabile da umani.

(Anche in casi banali come cercare una stringa, un motore intelligente può riconoscere il singolo percorso nella mappa di stato e ridurre quella parte a un semplice confronto tra stringhe ed evitare di gestire gli stati.)

Un motore particolare da un framework / libreria può essere lento perché il motore fa un sacco di altre cose di cui un programmatore di solito non ha bisogno. Esempio: la classe Regex in .NET crea un sacco di oggetti inclusi Match, Groups e Capture.

Le espressioni regolari sembrano veloci perché hai computer veloci.

Negli anni '80, quando 1 MIPS era un computer veloce, le espressioni regolari erano una zona abbastanza grande di preoccupazione, preoccupazione e ricerca perché erano lente, brutte e ad alta intensità di calcolo. Lo sviluppo intelligente dell'algoritmo ha seguito e aiutato - ma per tutti gli scopi pratici in questi giorni stai vedendo il miracolo di macchine veloci che tappezzano le fessure.

Perché pensi che siano più veloci rispetto alla ricerca del documento?

Ci sono alcuni trucchi che puoi fare, ad es. se stai cercando una parola di 10 lettere che inizia con A e termina con B, allora se trovi un A e il personaggio 9 posizioni più avanti non è B, puoi saltarne un po '. vedi l'algoritmo di Knuth-Morris-Pratt

I regEx sono relativamente più veloci per il codice che potresti scrivere perché la maggior parte delle librerie è il risultato di molti sviluppatori che impiegano molti anni ad ottimizzarli per eliminare ogni possibile risultato. È difficile per un singolo individuo duplicarlo nel proprio codice di ricerca.

Cosa rende veloce un'espressione regolare?

In realtà, non lo sono. Non molto. È solo che non sono abbastanza lenti da avvertire la maggior parte di noi. Tornando ai 'vecchi tempi lenti, era molto più evidente.

Sono anche non il diritto strumento per ogni lavoro - il martello .

La tua premessa di base è sbagliata.

Le espressioni regolari non sono sempre più veloci di una semplice ricerca. Tutto dipende dal contesto. Dipende dalla complessità dell'espressione, dalla lunghezza del documento ricercato e da un'intera serie di fattori.

Quello che succede è che l'espressione regolare verrà compilata in un parser semplice (che richiede tempo). Pertanto, se il documento è piccolo, questo tempo extra supererà qualsiasi vantaggio. Inoltre, se l'espressione è semplice, l'espressione regolare non ti darà alcun vantaggio.

Se l'espressione è complessa e il documento abbastanza grande, puoi ottenere qualche beneficio. Se questo è abbastanza significativo da considerare che le espressioni regolari siano più veloci dipenderà molto dal livello di impegno che si vuole mettere nella ricerca (anche le espressioni regolari potrebbero avere alcune ottimizzazioni che una libreria potrebbe fornire che non avresti pensato a te stesso).

Quello che sto cercando di dire è che non esiste una risposta generalizzata e globale. Se avessi un'espressione specifica (e una dimensione nota del documento), allora potresti dire di ottenere una risposta sì / no se l'espressione sarà più veloce di una semplice ricerca (e perché).

Il vero vantaggio delle espressioni regolari è che una volta capito come scriverle, la capacità di esprimere una ricerca complessa in modo conciso. Poiché si tratta di un modulo generalizzato, è quindi possibile creare strumenti che consentono ricerche in un modo che è utile nel caso generale; di solito è veloce almeno quanto una semplice ricerca (su documenti di dimensioni minime, su documenti più piccoli di questo non importa in quanto anche se è più lento, è comunque abbastanza veloce).

È plausibile che in alcuni linguaggi di alto livello (forse javascript), l'uso di una libreria regex implementata in un linguaggio di basso livello (forse C) sia più veloce della scrittura della logica del parser nel linguaggio di alto livello.

Plausibile - Non ho idea se questo sia mai effettivamente il caso.