sharp - Complejidad de la sustitución de Regex

replace c# expresiones regulares

Question

No obtuve la respuesta a esto en ningún lado. ¿Cuál es la complejidad del tiempo de ejecución de un partido y sustitución 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

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

Answer 2

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, usando un algoritmo estándar. Una vez que se ha construido, ejecutar 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 en una coincidencia encontrada en la cadena debe ser un tiempo constante.

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

Answer 3

Para profundizar en la respuesta de la empresa, 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 Knuth-Morris-Pratt ).

Answer 4

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

Answer 5

Depende de lo que defina por regex. Si permite operadores de concatenación, alternativa y Kleene-star, el tiempo puede ser O(m*n+m) , donde m es el tamaño de una expresión regular n es la longitud de la cadena. Lo haces construyendo un NFA (que es lineal en m ) y luego simulándolo manteniendo el conjunto de estados en los que estás y actualizando eso (en O(m) ) para cada letra de entrada.

Cosas que dificultan el análisis regex:

• paréntesis y referencias: la captura sigue siendo correcta con el algoritmo antes mencionado, aunque aumentaría la complejidad, por lo que podría no ser viable. Las referencias retrospectivas aumentan el poder de reconocimiento de la expresión regular, y su dificultad es buena
• mirada positiva hacia adelante: es simplemente otro nombre para la intersección, que aumenta la complejidad del algoritmo mencionado anteriormente a O(m^2+n)
• mirada negativa: un desastre para construir el autómata ( O(2^m) , posiblemente PSPACE-completo). Pero todavía debería ser posible abordar con el algoritmo dinámico en algo como O(n^2*m)

Tenga en cuenta que con una implementación concreta, las cosas podrían mejorar o empeorar. Como regla general, las características simples deben ser lo suficientemente rápidas, y las expresiones genéricas no ambiguas (por ejemplo, no como a*a* ) son mejores.

Answer 6

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

Para mayor claridad, asuma la definición estándar para 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, la alternancia y el cierre de Kleene, junto con la unidad y las constantes cero (que aparecen por razones de teoría de grupo). En general, es una buena idea no sobrecargar este término a pesar de la práctica diaria en los lenguajes de scripting 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 |) time y O (| r |) espacio, 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 de tiempo y espacio O (| r | | t | / log | t |) mediante el uso de listados de nodos autómatas y el paradigma Cuatro rusos. Este paradigma parece tener el nombre de cuatro tipos rusos que escribieron un documento 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 coincidencia para las expresiones regulares con referencias hacia atrás adicionales es NP-completo, que fue probado por Aho

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

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

Para hacer coincidir las expresiones regulares con backreferences deterministically podríamos emplear backtracking (no a diferencia del motor Perl regex) para hacer un seguimiento de las posibles subwords del texto de entrada t que se pueden asignar a las variables en r. Solo hay subwords O (| t | ^ 2) que se pueden asignar a cualquier variable en r. Si hay n variables en r, entonces hay O (| t | ^ 2n) asignaciones posibles. Una vez que se ha solucionado la asignación de subcadenas a variables, el problema se reduce a la coincidencia de expresiones regulares simples. Por lo tanto, la complejidad del caso más desfavorable para emparejar expresiones regulares con referencias hacia atrás es O (| t | ^ 2n).

Sin embargo, tenga en cuenta que las expresiones regulares con referencias posteriores aún no contienen expresiones regulares completas.

Tomemos, por ejemplo, el símbolo de "no me importa" aparte de otros operadores. Existen varios algoritmos polinomiales que determinan 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

define 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 "no me importa" de longitud variable que no está contenido en cualquiera 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 la complejidad del problema de coincidencia para las expresiones regulares con referencias retrospectivas, "no me importa" y otras características interesantes de las expresiones regulares prácticas.

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

Answer 7

Si buscas la coincidencia y la sustitución, eso implica la agrupación y las referencias retrospectivas.

Aquí hay un ejemplo de Perl donde la agrupación y las referencias posteriores se pueden usar para resolver un problema completo de NP: http://perl.plover.com/NPC/NPC-3SAT.html

Esto (junto con algunas otras cositas teóricas) significa que el uso de expresiones regulares para el emparejamiento y la sustitución 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 el tiempo polinomial como se describe en las otras respuestas.