No obtuve la respuesta a esto en ninguna parte. ¿Cuál es la complejidad del tiempo de ejecución de un partido y sustitución Regex?Complejidad de la 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).
Desde una postura puramente teórico:
La aplicación Conozco sería construir un determinista Autómata Finito de 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.
Así que, en general, supongo que O (2^m + n).
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.
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), usando por ejemplo el Knuth-Morris-Pratt algorithm).
Puede intercambiar espacio por velocidad mediante la construcción de 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.
Depende de lo que defina por regex. Si permite operadores de concatenación, alternativa y Kleene-star, el tiempo puede ser realmente O(m*n+m), donde m tiene el tamaño de una expresión regular y n es la longitud de la cadena. Lo hace construyendo un NFA (que es lineal en m) y luego simulándolo manteniendo el conjunto de estados en los que se encuentra y actualizando eso (en O(m)) para cada letra de entrada.
cosas que hacen difícil el análisis de expresiones regulares:
O(m^2+n)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 regulares no ambiguas (por ejemplo, no como a*a*) son mejores.
Otra información teórica de posible interés.
Para mayor claridad, asumen 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 símbolos del alfabeto, operadores de concatenación, la alternancia y cierre Kleene, junto con la unidad y cero constantes (que aparecen para razones de grupos teórico). En general, es una buena idea no sobrecargar este término a pesar de la práctica diaria en lenguajes de scripting que conduce a ambigüedades.
Hay una construcción NFA que resuelve el problema de la concordancia de un habitual expresión r y un texto de entrada t en O (| r | | t |) tiempo y O (| r |) el espacio, donde | - | es la función de longitud. Este algoritmo se ha mejorado aún más por Myers
http://doi.acm.org/10.1145/128749.128755
al tiempo y el espacio complejidad O (| r | | t |/log | t |) mediante el uso de listados de nodo autómata y el paradigma cuatro rusos. Este paradigma parece tener el nombre de cuatro tipos rusos que escribieron un documento innovador que no es en línea. Sin embargo, el paradigma se ilustra en ellas la biología computacional notas de clase
http://lyle.smu.edu/~saad/courses/cse8354/lectures/lecture5.pdf
me resulta hilarante para nombrar un paradigma por el número y la nacionalidad de los autores en lugar de sus apellidos.
El problema a juego para expresiones regulares con backreferences añadido es NP-completo, el cual fue probado por Aho
http://portal.acm.org/citation.cfm?id=114877
por una reducción del problema de vértice de la cubierta que es un clásico problema NP-completo .
para que coincida con las expresiones regulares con referencias hacia atrás de forma determinista podríamos retroceso empleo (no muy diferente del motor de expresiones regulares de Perl) para realizar un seguimiento de los posibles palabras parciales 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 peor caso para emparejar expresiones regulares con referencias hacia atrás es O (| t |^2n).
Obsérvese, sin embargo, las expresiones regulares con referencias hacia atrás son todavía no regexen con todas las funciones.
Tomemos, por ejemplo, el "no me importa" símbolo aparte de cualquier otro operadores. Hay 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
definir 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 una longitud variable el símbolo "no me importa" no está incluido en ninguno de los 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 la complejidad y lo es la medida de la complejidad del problema de la concordancia de expresiones regulares con referencias hacia atrás, "no importa" y otras características interesantes de las expresiones regulares prácticas .
Por desgracia, no he dicho una palabra sobre Python ... :)
Si lo que busca a juego y sustitución, que implica la agrupación y referencias hacia atrás.
Aquí está un ejemplo Perl donde agrupación y referencias hacia atrás se pueden utilizar para resolver un NP completo problema: http://perl.plover.com/NPC/NPC-3SAT.html
Este (junto con algunos otros tidbits teóricos) significa que el uso de expresiones regulares para hacer coincidir y sustitución es NP -completar.
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.
Me temo que no entiendo lo que quiere decir con "resolver un problema NP-completo". Debido a su integridad de NP, no existe un algoritmo eficiente (tiempo de polinomio) para computar instancias de 3-CNF-SAT. Uno necesitaría tal algoritmo para * resolver * el problema. El hecho de que uno pueda codificar 3-CNF-SAT con expresiones regulares todavía no significa que la expresión regular resuelva 3-CNF-SAT porque no hay un algoritmo de tiempo polinomial para calcular expresiones regulares. –
No mencioné inicialmente el tiempo de polinomios, pensé que mi respuesta implicaba que la correspondencia y la sustitución de expresiones regulares estaba en NP, aunque desde el punto de vista reflexivo no estaba tan claro a partir de cómo lo escribí. He limpiado mi respuesta un poco, espero que aclare un poco las cosas. Gracias por la respuesta. – Dave
¿La complejidad sigue siendo lineal cuando se considera el rastreo de retroceso según lo necesiten algunos cuantificadores? – Joey
Estoy interesado en una prueba para "Esto se hace en O (2^m), siendo m el tamaño de la expresión regular, usando un algoritmo estándar". Como se te ocurrió? –
¿Hay una serie de armónicos para el número de operaciones en la situación extrema? –