¿Cómo funcionan realmente las expresiones regulares?

Digamos que tiene un documento con un ensayo escrito. Desea analizar este ensayo para seleccionar solo ciertas palabras. Guay.

¿Está usando una expresión regular más rápido que analizar el archivo línea por línea y palabra por palabra buscando una coincidencia? Si es así, ¿cómo funciona? ¿Cómo puedes ir más rápido que mirar cada palabra?

¿Como funciona?

Echa un vistazo a la teoría de autómatas

En resumen, cada expresión regular tiene un autómata finito equivalente y puede compilarse y optimizarse para un autómata finito. Los algoritmos involucrados se pueden encontrar en muchos libros de compilación. Estos algoritmos son utilizados por programas unix como awk y grep.

Sin embargo, la mayoría de los lenguajes de programación modernos (Perl, Python, Ruby, Java (y lenguajes basados ​​en JVM), C #) no utilizan este enfoque. Utilizan un enfoque de retroceso recursivo, que compila una expresión regular en un árbol o una secuencia de construcciones que representan varios subconjuntos de la expresión regular. La mayoría de las sintaxis modernas de "expresión regular" ofrecen referencias de retroceso que están fuera del grupo de lenguajes regulares (no tienen representación en autómatas finitos), que son trivialmente implementables en el enfoque de retroceso recursivo.

La optimización generalmente produce una máquina de estado más eficiente. Por ejemplo: considere aaaab | aaaac | aaaad, un programador normal puede obtener la implementación de búsqueda simple pero menos eficiente (comparando tres cadenas por separado) en diez minutos; pero al darse cuenta de que es equivalente a aaaa [bcd], se puede hacer una mejor búsqueda al buscar las primeras cuatro 'a' y luego probar el quinto carácter contra [b, c, d]. El proceso de optimización fue uno de mis trabajos de compilación en casa hace muchos años, así que supongo que también está en la mayoría de los motores modernos de expresión regular.

Por otro lado, las máquinas de estado tienen alguna ventaja cuando aceptan cadenas porque usan más espacio en comparación con una "implementación trivial". Considere un programa para eliminar las comillas en cadenas SQL, es decir: 1) comienza y termina con comillas simples; 2) las comillas simples se escapan por dos comillas simples consecutivas. Entonces: la entrada ['a' ''] debería producir la salida [a ']. Con una máquina de estados, las comillas simples consecutivas son manejadas por dos estados. Estos dos estados tienen el propósito de recordar el historial de entrada de modo que cada carácter de entrada se procese exactamente una sola vez, como se ilustra a continuación:

...
S1->'->S2
S1->*->S1, output *, * can be any other character 
S2->'->S1, output '
S2->*->END, end the current string

Entonces, en mi opinión, la expresión regular puede ser más lenta en algunos casos triviales, pero generalmente más rápida que un algoritmo de búsqueda diseñado manualmente, dado el hecho de que la optimización no puede ser realizada de manera confiable por humanos.

(Incluso en casos triviales como buscar una cadena, un motor inteligente puede reconocer la ruta única en el mapa de estado y reducir esa parte a una simple comparación de cadena y evitar la administración de estados).

Un motor particular de un marco / biblioteca puede ser lento porque el motor hace muchas otras cosas que un programador generalmente no necesita. Ejemplo: la clase Regex en .NET crea un grupo de objetos que incluyen Match, Grupos y Capturas.

Las expresiones regulares solo se ven rápido porque tienes computadoras rápidas.

En la década de 1980, cuando 1 MIPS era una computadora rápida, las expresiones regulares eran un área bastante grande de preocupación, preocupación e investigación porque eran lentas, feas y computacionales. El desarrollo inteligente de algoritmos siguió y ayudó, pero a todos los efectos prácticos en estos días se está viendo el milagro de las máquinas rápidas que se están desmoronando.

¿Por qué crees que son más rápidos que buscar el documento?

Hay algunos trucos que puedes hacer, por ejemplo. si está buscando una palabra de 10 letras que comience con A y termine con B, entonces si encuentra una A y el carácter 9 posiciones más adelante no es B, puede omitir algunas. ver algoritmo Knuth – Morris – Pratt

¿Qué hace que una expresión regular sea rápida?

En realidad, no lo son. No mucho. Es solo que no son lo suficientemente lentos para que la mayoría de nosotros nos demos cuenta. En los viejos tiempos lentos, era mucho más notable.

Tampoco son la herramienta adecuada para cada trabajo: el martillo .

Las RegEx son comparativamente más rápidas que el código que podría escribir, porque la mayoría de las bibliotecas son el resultado de que muchos desarrolladores pasan muchos años optimizándolas para obtener el último rendimiento posible. Es difícil para un solo individuo duplicar eso en su propio código de búsqueda.

Tu premisa básica es incorrecta.

Las expresiones regulares no siempre son más rápidas que una simple búsqueda. Todo depende del contexto. Depende de la complejidad de la expresión, la longitud del documento que se busca y una gran cantidad de factores.

Lo que sucede es que la expresión regular se compilará en un analizador simple (que lleva tiempo). Por lo tanto, si el documento es pequeño, este tiempo adicional superará cualquier ventaja. Además, si la expresión es simple, entonces la expresión regular no le dará ninguna ventaja.

Si la expresión es compleja y el documento es lo suficientemente grande, puede obtener algún beneficio. Si esto es lo suficientemente significativo como para considerar que las expresiones regulares son más rápidas dependerá en gran medida del esfuerzo que desee poner en la búsqueda (también las expresiones regulares pueden tener algunas optimizaciones que una biblioteca podría proporcionar que no habría pensado en usted).

Lo que estoy tratando de decir es que no hay una respuesta generalizada y general. Si tenía una expresión específica (y un tamaño de documento conocido), entonces podría decir derivar una respuesta sí / no de si la expresión será más rápida que una simple búsqueda (y por qué).

La verdadera ventaja de las expresiones regulares es que una vez que comprende cómo escribirlas, la capacidad de expresar una búsqueda compleja de manera concisa. Debido a que es una forma generalizada, puede crear herramientas que permitan búsquedas de una manera útil en el caso general; Por lo general, es al menos tan rápido como una simple búsqueda (en documentos de tamaño mínimo; en documentos más pequeños que esto no importaría, ya que incluso si es más lento, sigue siendo lo suficientemente rápido).

Es plausible que en algunos lenguajes de alto nivel (quizás javascript), el uso de una biblioteca de expresiones regulares implementada en un lenguaje de bajo nivel (quizás C) sea más rápido que escribir lógica de analizador sintáctico en el lenguaje de alto nivel.

Plausible: no tengo idea de si este es realmente el caso.