Complejidad de la sustitución de expresiones regulares

Question

No obtuve la respuesta a esto en ninguna parte.¿Cuál es la complejidad del tiempo de ejecución de una coincidencia y sustitución de Regex?

Editar:Trabajo en Python.Pero me gustaría saber en general acerca de los lenguajes/herramientas más populares (java, perl, sed).

Answer 1

Desde una postura puramente teórica:

La implementación con la que estoy familiarizado sería construir un autómata finito determinista para reconocer la expresión regular.Esto se hace en O(2^m), siendo m el tamaño de la expresión regular, utilizando un algoritmo estándar.Una vez construido esto, pasar una cadena a través de él es lineal en la longitud de la cadena: O (n), siendo n la longitud de la cadena.Un reemplazo de una coincidencia encontrada en la cadena debe ser de tiempo constante.

Entonces, en general, supongo O (2 ^ m + n).

Answer 2

Otra información teórica de posible interés.

Para mayor claridad, asuma la definición estándar de una expresión regular.

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

de la teoría del lenguaje formal.Prácticamente, esto significa que el único material de construcción son los símbolos del alfabeto, los operadores de concatenación, alternancia y cierre de Kleene, junto con la unidad y cero constantes (que aparecen por razones teóricas del grupo).En general, es una buena idea no sobrecargar este término a pesar de la práctica cotidiana en los idiomas de secuencias de comandos, lo que conduce a ambigüedades.

Hay una construcción de NFA que resuelve el problema de coincidencia para una expresión regular r y un texto de entrada t en o (| r | | t |) tiempo y espacio o (| r |), donde |-| es la función de longitud.Este algoritmo fue mejorado aún más por Myers.

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

a la complejidad temporal y espacial O(|r| |t| / log |t|) mediante el uso de listados de nodos autómatas y el paradigma de los cuatro rusos.Este paradigma parece llevarse a cabo de cuatro chicos rusos que escribieron un periódico innovador que no está en línea.Sin embargo, el paradigma se ilustra en estas notas de conferencia de biología computacional

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

Me parece gracioso nombrar un paradigma por el número y la nacionalidad de los autores en lugar de sus apellidos.

El problema de correspondencia para expresiones regulares con backreferencias adicionales es NP-COMPLETE, que fue probado por Aho

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

por una reducción del problema de cobertura de vértices, que es un problema clásico NP-completo.

Para que coincidan con las expresiones regulares con backreferencias de forma determinista, podríamos emplear retroceso (no muy diferente del motor Perl Regex) para realizar un seguimiento de las posibles subvenciones del texto de entrada t que se puede asignar a las variables en r.Solo hay subfrenciones o (| t |^2) que pueden asignarse a cualquier variable en r.Si hay n variables en r, entonces hay o (| t |^2n) posibles tareas.Una vez que se soluciona una asignación de subcadenas a variables, el problema se reduce a la coincidencia de expresión regular simple.Por lo tanto, la peor complejidad de los casos para hacer coincidir las expresiones regulares con backreferencias es o (| t |^2n).

Sin embargo, tenga en cuenta que las expresiones regulares con backreferencias aún no son reglas con todas las funciones.

Tomemos, por ejemplo, el símbolo de "no me importa" aparte de cualquier otro operador.Hay varios algoritmos polinomiales que deciden si un conjunto de patrones coincide con un texto de entrada.Por ejemplo, Kucherov y Rusinowitch.

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

defina un patrón como una palabra w_1@w_2@...@w_n donde cada w_i es una palabra (no una expresión regular) y "@" es un símbolo de longitud variable "no me importa" que no está contenido en ninguno de w_i.Derivan un algoritmo O ((| t | + | p |) log | p |) para hacer coincidir un conjunto de patrones p con un texto de entrada t, donde | t | es la longitud del texto, y | p | es la longitud de todas las palabras en P.

Sería interesante saber cómo se combinan estas medidas de complejidad y cuál es la medida de complejidad del problema coincidente para expresiones regulares con backreferencias "no me importa" y otras características interesantes de expresiones regulares prácticas.

Por desgracia, no he dicho una palabra sobre Python...:)

Answer 3

Depende de lo que definas por expresión regular.Si permite operadores de concatenación, alternativa y Kleene-star, el tiempo puede ser realmente O(m*n+m), dónde m es el tamaño de una expresión regular y n es la longitud de la cuerda.Lo haces construyendo un NFA (que es lineal en m), y luego simularlo manteniendo el conjunto de estados en los que se encuentra y actualizándolo (en O(m)) por cada letra de entrada.

Cosas que dificultan el análisis de expresiones regulares:

• paréntesis y referencias anteriores:la captura todavía está bien con el algoritmo antes mencionado, aunque aumentaría la complejidad, por lo que podría ser inviable.Las referencias retrospectivas aumentan el poder de reconocimiento de la expresión regular y su dificultad está bien
• visión positiva hacia el futuro:es solo otro nombre para intersección, lo que eleva la complejidad del algoritmo antes mencionado a O(m^2+n)
• anticipación negativa:un desastre para la construcción del autómata (O(2^m), posiblemente PSPACE-completo).Pero aún debería ser posible abordarlo con el algoritmo dinámico en algo como O(n^2*m)

Tenga en cuenta que con una implementación concreta, las cosas pueden mejorar o empeorar.Como regla general, las funciones simples deben ser lo suficientemente rápidas e inequívocas (p. ej.diferente a a*a*) las expresiones regulares son mejores.

Answer 4

Para profundizar en la respuesta de theprise, para la construcción del autómata, O(2^m) es el peor caso, aunque realmente depende de la forma de la expresión regular (para una muy simple que coincida con una palabra, está en O( m), utilizando por ejemplo el Algoritmo de Knuth-Morris-Pratt).

Answer 5

Depende de la implementación.¿Qué idioma/biblioteca/clase?Puede haber un mejor caso, pero sería muy específico de la cantidad de funciones en la implementación.

Answer 6

Puede intercambiar espacio por velocidad construyendo un autómata finito no determinista en lugar de un DFA.Esto se puede recorrer en tiempo lineal.Por supuesto, en el peor de los casos esto podría necesitar O(2^m) de espacio.Espero que la compensación valga la pena.

Answer 7

Si lo que busca es hacer coincidir y sustituir, eso implica agrupación y referencias retrospectivas.

Aquí hay un ejemplo de Perl donde se pueden usar agrupaciones y referencias inversas para resolver un problema NP completo: http://perl.plover.com/NPC/NPC-3SAT.html

Esto (junto con algunos otros datos teóricos) significa que el uso de expresiones regulares para hacer coincidir y sustituir es NP completo.

Tenga en cuenta que esto es diferente de la definición formal de una expresión regular, que no tiene la noción de agrupación, y coincide en tiempo polinomial como se describe en las otras respuestas.