guia - ¿Cuál es la complejidad del tiempo de los algoritmos Regex promedio?

qgis manual

Question

No soy nuevo en el uso de expresiones regulares, y entiendo la teoría básica en la que se basan: máquinas de estados finitos.

Sin embargo, no soy tan bueno en el análisis algorítmico y no entiendo cómo se compara una expresión regular, por ejemplo, una búsqueda lineal básica. Lo estoy preguntando porque en la superficie parece una búsqueda lineal lineal. (Si la expresión regular es simple)

¿A dónde podría ir para obtener más información sobre la implementación de un motor de expresiones regulares?

Answer 1

Este es uno de los esquemas más populares: la coincidencia de expresión regular puede ser simple y rápida . Ejecutar una expresión regular compilada por DFA contra una cadena es de hecho O (n), pero puede requerir hasta O (2 ^ m) tiempo / espacio de construcción (donde m = tamaño de expresión regular).

Answer 2

La expresión regular clásica se puede implementar de una manera que sea rápida en la práctica, pero que tenga un mal comportamiento del peor de los casos (el DFA estándar) o de una manera que haya garantizado un comportamiento de peor caso razonable (manteniéndolo como un NFA). El DFA estándar se puede ampliar para admitir muchos caracteres y banderas que coinciden, que hacen uso del hecho de que básicamente se trata de una búsqueda de seguimiento.

Los ejemplos del enfoque estándar están en todas partes (por ejemplo, integrados en Perl). Hay un ejemplo que dice tener un buen comportamiento en el peor de los casos en http://code.google.com/p/re2/ - de hecho, es incluso mejor de lo que esperaba en el peor de los casos, por lo que es posible que hayan encontrado un truco adicional o dos .

Si está interesado en esto, o si le interesan los programas que se pueden crear para bloquear entradas patológicas sólidas, lea http://swtch.com/~rsc/regexp/regexp1.html .

Answer 3

¿Está familiarizado con el término autómatas finitos determinista / no determinista ?

Las expresiones regulares reales (cuando digo real me estoy refiriendo a las expresiones regulares que reconocen los lenguajes regulares , y no las expresiones regulares que casi todos los lenguajes de programación incluyen con referencias posteriores, etc.) se pueden convertir en DFA / NFA y ambos pueden implementarse en una forma mecánica en un lenguaje de programación (un NFA se puede convertir en un DFA)

Lo que tienes que hacer es:

1. Encuentra una forma de convertir una expresión regular en un autómata
2. Implementa el reconocimiento del autómata en el lenguaje de programación que prefieras

De esta forma, con una expresión regular, puede convertirla en un DFA y ejecutarla para ver si coincide o no con un texto específico.

Esto puede implementarse en O(n) , porque DFA no retrocede (como una Máquina de Turing ), por lo que coincide con la cadena o no. Eso es suponiendo que no tomarás en cuenta las coincidencias superpuestas, de lo contrario, tendrás que volver atrás y comenzar a emparejar nuevamente ...