Complessità della sostituzione di Regex

Question

Non ho trovato la risposta da nessuna parte.Qual è la complessità di runtime di una corrispondenza e sostituzione di Regex?

Modificare:Lavoro in Python.Ma mi piacerebbe conoscere in generale i linguaggi/gli strumenti più popolari (Java, perl, sed).

Answer 1

Da un punto di vista puramente teorico:

L'implementazione che conosco sarebbe quella di costruire un automa finito deterministico per riconoscere la regex.Questo viene fatto in O(2^m), dove m è la dimensione della regex, utilizzando un algoritmo standard.Una volta costruito questo, il passaggio di una stringa attraverso di esso è lineare nella lunghezza della stringa: O(n), dove n è la lunghezza della stringa.Una sostituzione su una corrispondenza trovata nella stringa dovrebbe essere costante.

Quindi nel complesso, suppongo O(2^m + n).

Answer 2

Altre informazioni teoriche di possibile interesse.

Per chiarezza, presupponiamo la definizione standard di un'espressione regolare

http://en.wikipedia.org/wiki/Regular_lingual

dalla teoria del linguaggio formale.Praticamente, ciò significa che l'unico materiale da costruzione sono i simboli dell'alfabeto, gli operatori di concatenazione, alternamento e chiusura di Kleene, insieme all'unità e alle costanti zero (che appaiono per motivi teorici di gruppo).Generalmente è una buona idea non sovraccaricare questo termine nonostante la pratica quotidiana nelle lingue di scripting che porta a ambiguità.

C'è una costruzione NFA che risolve il problema corrispondente per un'espressione regolare r e un testo di input t in o (| r | | t |) tempo e O (| r |), dove |-| è la funzione di lunghezza.Questo algoritmo è stato ulteriormente migliorato da Myers

http://doi.acm.org/10.1145/128749.128755

alla complessità temporale e spaziale O(|r| |t| / log |t|) utilizzando elenchi di nodi di automi e il paradigma dei Quattro Russi.Questo paradigma sembra prendere il nome da quattro ragazzi russi che hanno scritto un documento rivoluzionario che non è online.Tuttavia, il paradigma è illustrato in queste note di lezione di biologia computazionale

http://lyle.smu.edu/~saad/courses/cse8354/lectures/lecture5.pdf

Trovo divertente nominare un paradigma per il numero e la nazionalità degli autori invece dei loro cognomi.

Il problema corrispondente per le espressioni regolari con backreferenze aggiunte è NP-completo, che è stato dimostrato da AHO

http://portal.acm.org/citation.cfm?id=114877

mediante una riduzione dal problema della copertura dei vertici che è un classico problema NP-completo.

Per abbinare le espressioni regolari con backreferenze determinalmente, potremmo impiegare il backtracking (non diversamente dal motore perl regex) per tenere traccia delle possibili sotto -parole del testo di input che possono essere assegnate alle variabili in r.Ci sono solo o (| t |^2) sotto -parole che possono essere assegnate a una variabile in r.Se ci sono n variabili in r, allora ci sono O (| t |^2n) possibili incarichi.Una volta risolta un'assegnazione di sottostringi alle variabili, il problema si riduce alla semplice corrispondenza dell'espressione regolare.Pertanto, la complessità del caso peggiore per abbinare espressioni regolari con backreferenze è O (| T |^2n).

Nota, tuttavia, le espressioni regolari con backreferenze non sono ancora regexen.

Prendi, ad esempio, il simbolo "Non preoccuparti" a parte qualsiasi altro operatore.Esistono diversi algoritmi polinomiali che decidono se una serie di motivi corrisponde a un testo di input.Ad esempio, Kucherov e Rusinowitch

http://dx.doi.org/10.1007/3-540-60044-2_46

definire un modello come una parola w_1@w_2@...@w_n dove ogni w_i è una parola (non un'espressione regolare) e "@" è un simbolo "non importa" di lunghezza variabile non contenuto in nessuno dei w_i.Derivano un algoritmo O ((| t | + | p |) log | p |) per abbinare un set di motivi p contro un testo di input t, dove | t | è la lunghezza del testo e | p | è la lunghezza di tutte le parole in P.

Sarebbe interessante sapere come si combinano queste misure di complessità e qual è la misura di complessità del problema di abbinamento per le espressioni regolari con backreferenze, "non si preoccupano" e altre caratteristiche interessanti delle espressioni regolari pratiche.

Ahimè, non ho detto una parola su Python...:)

Answer 3

Dipende da cosa definisci con regex.Se si consentono gli operatori di concatenazione, alternativi e Kleene-star, il tempo può effettivamente essere O(m*n+m), Dove m è la dimensione di una regex e n è la lunghezza della stringa.Lo fai costruendo un NFA (che è lineare in m), quindi simulandolo mantenendo l'insieme di stati in cui ti trovi e aggiornandolo (in O(m)) per ogni lettera di input.

Cose che rendono difficile l'analisi delle espressioni regolari:

• parentesi e riferimenti all'indietro:l'acquisizione è ancora OK con l'algoritmo di cui sopra, anche se aumenterebbe la complessità, quindi potrebbe essere irrealizzabile.I backreference aumentano il potere di riconoscimento della regex e la sua difficoltà è buona
• sguardo positivo:è solo un altro nome per intersezione, che aumenta la complessità del suddetto algoritmo a O(m^2+n)
• sguardo al futuro negativo:un disastro per la costruzione dell'automa (O(2^m), possibilmente PSPACE-completo).Ma dovrebbe essere ancora possibile affrontare l'algoritmo dinamico in qualcosa di simile O(n^2*m)

Tieni presente che con un'implementazione concreta, le cose potrebbero migliorare o peggiorare.Come regola generale, le funzionalità semplici dovrebbero essere sufficientemente veloci e inequivocabili (ad es.non come a*a*) le espressioni regolari sono migliori.

Answer 4

Per approfondire la risposta di Prise, per la costruzione dell'automa, O(2^m) è il caso peggiore, anche se dipende in realtà dalla forma dell'espressione regolare (per un'espressione molto semplice che corrisponde a una parola, è in O( m), utilizzando ad esempio il Algoritmo di Knuth-Morris-Pratt).

Answer 5

Dipende dall'implementazione.Quale lingua/biblioteca/classe?Potrebbe esserci il caso migliore, ma sarebbe molto specifico per il numero di funzionalità nell'implementazione.

Answer 6

Puoi scambiare spazio con velocità costruendo un automa finito non deterministico invece di un DFA.Questo può essere attraversato in tempo lineare.Naturalmente, nel peggiore dei casi potrebbe essere necessario uno spazio di O(2^m).Mi aspetterei che ne valesse la pena.

Answer 7

Se stai cercando l'abbinamento e la sostituzione, ciò implica raggruppamento e riferimenti all'indietro.

Ecco un esempio in Perl in cui il raggruppamento e i riferimenti all'indietro possono essere utilizzati per risolvere un problema NP completo: http://perl.plover.com/NPC/NPC-3SAT.html

Questo (insieme ad alcune altre curiosità teoriche) significa che l'uso delle espressioni regolari per la corrispondenza e la sostituzione è NP-completo.

Nota che questo è diverso dalla definizione formale di un'espressione regolare - che non ha la nozione di raggruppamento - e corrisponde in tempo polinomiale come descritto dalle altre risposte.