¿Cuál es la complejidad de la expresión regular?

¿Cuál es la complejidad con respecto a la longitud de cadena que lleva a realizar una comparación de expresiones regulares en una cadena?¿Cuál es la complejidad de la expresión regular?

Fuente

2010-12-07 Ahmad Farid

La complejidad depende más de la naturaleza de la expresión regular que de la longitud de la cadena. – LukeH

@LukeH Alternativamente, depende del lenguaje de programación utilizado. Por ejemplo, Python Regex nunca puede exceder el poder de la computadora de un DFA, pero Perl Regex puede estar completo. – BlackVegetable

posible duplicado de [Complexity of Regex substitution] (http://stackoverflow.com/questions/21669/complexity-of-regex-substitution) – Kevin

La respuesta depende de qué es exactamente lo que quiere decir con "expresiones regulares". Las expresiones regulares clásicas pueden ser compiled en Deterministic Finite Automata que pueden coincidir con una cadena de longitud N en O(N) vez. Ciertas extensiones del lenguaje de expresiones regulares cambian eso para peor.

Puede encontrar el siguiente documento de interés: Regular Expression Matching Can Be Simple And Fast.

Fuente

2010-12-07 15:54:25 NPE

Me encanta ese artículo. – tchrist

Supongo que no sería posible obtener los datos de prueba utilizados para ese artículo. Mi lugar de trabajo usa perl regex todo el tiempo. Si fueran tan lentos, nuestro hardware fallaría por completo. – DeepDeadpool

ilimitado: puede crear una expresión regular que nunca termina en una cadena de entrada vacía.

Fuente

2010-12-07 15:42:23

Solo por curiosidad, ¿podría dar un ejemplo, Alex? –

see man perlre - "'foo' = ~ m {(o?) *} X;". Perl tiene un código especial para detectar la recursión infinita en este caso y estallar. –

Si usa normal (TCS: sin referencia, concatenación, alternancia, estrella de Kleene) expresiones regulares y expresiones regulares ya está compilada, entonces es O (n).

Fuente

2010-12-07 15:46:40 royas

Si está buscando límites asintóticos ajustados en RegEx (sin respeto a la expresión en sí), entonces no hay uno. Como señala Alex, puedes crear una expresión regular que sea O (1) o una expresión regular que sea Omega (infinito). Como un algoritmo puramente matemático, un motor de expresión regular sería demasiado complicado para realizar cualquier tipo de análisis asintótico formal (aparte del hecho de que dicho análisis sería básicamente inútil).

La tasa de crecimiento de una expresión particular (ya que, en realidad, constituye un algoritmo, de todos modos) sería mucho más significativa, aunque no necesariamente más fácil de analizar.

Fuente

2010-12-07 15:47:02

Eso está considerando extensiones de expresiones regulares formales. Se puede demostrar que las expresiones regulares que involucran construcciones usuales (sin patrones de anticipación/retroceso por ejemplo) siempre terminan en cualquier entrada, en un tiempo O (longitud de la cadena de entrada). –

@clement Incluso la mayoría de las extensiones no empujan el RE más allá de un DFA. Por ejemplo, Python Regex siempre puede ser modelado por un DFA. Sin embargo, tan pronto como comienzas a trabajar con Perl regex (¿y creo que Javascript?) Se convierte en un animal diferente que es equivalente a una MT en su lugar. – BlackVegetable

¿Cuál es la complejidad de la expresión regular?

Respuesta

Cuestiones relacionadas