generador/reductor de expresión regular?

Question

Me plantearon una pregunta interesante de un colega sobre un punto de dolor operacional que tenemos actualmente, y me da curiosidad si hay algo por ahí (utilidad/biblioteca/algoritmo) que pueda ayudar a automatizar esto.

Supongamos que tiene una lista de valores literales (en nuestro caso, son URL). Lo que queremos hacer es, en base a esta lista, crear una expresión regular única que coincida con todos los elementos literales.

lo tanto, si la lista es:

http://www.example.com 
http://www.example.com/subdir 
http://foo.example.com 

La respuesta más simple es

^(http://www.example.com|http://www.example.com/subdir|http://foo.example.com)$ 

pero esto se hace grande para un montón de datos, y tenemos un límite de longitud que estamos tratando de mantenerse debajo.

Actualmente escribimos manualmente las expresiones regulares, pero esto no se escala muy bien ni es un gran uso del tiempo de nadie. ¿Existe una forma más automatizada de descomponer los datos de origen para obtener una expresión regular de longitud óptima que coincida con todos los valores de origen?

Answer 1

El algoritmo de coincidencia Aho-Corasick construye un autómata finito para hacer coincidir varias cadenas. Puede convertir el autómata a su expresión regular equivalente, pero es más sencillo usar el autómata directamente (esto es lo que hace el algoritmo)

Answer 2

Creo que tendría sentido dar un paso atrás y pensar en lo que estás haciendo, y por qué.

Para que coincida con todas esas URL, solo esas URL y ninguna otra, no necesita una expresión regular; probablemente pueda obtener un rendimiento aceptable haciendo comparaciones exactas de cadenas sobre cada elemento de su lista de URL.

Si necesita expresiones regulares, ¿cuáles son las diferencias de variable que está tratando de acomodar? Es decir. ¿Qué parte de la entrada debe coincidir textualmente, y dónde hay margen de maniobra?

Si realmente desea usar una expresión regular para que coincida con una lista fija de cadenas, quizás por motivos de rendimiento, entonces debería ser lo suficientemente simple como para escribir un método que combine todas las cadenas de entrada como alternativas, como en su ejemplo . La máquina de estado que hace la conversión de expresiones regulares detrás de escena es bastante inteligente y no se ejecutará más lentamente si las alternativas de coincidencia tienen subcadenas comunes (y posiblemente redundantes).

Answer 3

Tomando el ejemplo de las otras dos respuestas, lo único que necesita para coincidir son solo las cuerdas suministrado, probablemente sea mejor hacer una coincidencia de cadena recta (lento) o construir un FSM simple que coincida con esas cadenas (rápido).

Un regex en realidad crea un FSM y luego compara su entrada con él, por lo que si las entradas provienen de un conjunto previamente conocido, es posible y en general es más fácil hacer el FSM en vez de intentar autogenerar un regex

Aho-Corasick ya ha sido sugerido. Es rápido, pero puede ser difícil de implementar. ¿Qué hay de poner todas las cadenas en un Trie y luego consultar en su lugar (ya que está haciendo coincidir cadenas enteras, no buscando subcadenas)?

Answer 4

Si quiere comparar contra todas las cadenas de un conjunto y solo contra esas, use un trie, o compressed trie, o mejor aún un directed acyclic word graph. Este último debería ser particularmente eficiente para las URL de la OMI.

Aunque tendrías que abandonar las expresiones regulares.

Answer 5

La función de utilidad Emacs regexp-opt (source code) no hace exactamente lo que usted desea (solo funciona en cadenas fijas), pero podría ser un punto de partida útil.

Answer 6

Hoy estaba buscando eso. No lo encontré, así que creo una herramienta: kemio.com.ar/tools/lst-trie-re.php

Poner una lista en el lado derecho, enviarla y obtener la expresión regular en el lado izquierdo.

me trataron con una lista de las palabras 6Kb, y produjo una expresión regular de 4 Kb (que puse en un archivo JS) como: var re=new RegExp(/..../,"mib");

No abusar de ella, por favor.

Answer 7

Un generador automático para expresión regular está disponible here. La herramienta tiene una interfaz web y usa Genetic Programming para generar expresiones regulares de un conjunto de pocos ejemplos: puede elegir entre una sintaxis lista para motores de expresiones regulares Java o JavaScript. Ha sido desarrollado por nuestro grupo de investigación y se ha presentado en la conferencia GECCO 2012.

Answer 8

Una manera fácil de hacer esto es utilizar hachoir_regex módulo de Python:

urls = ['http://www.example.com','http://www.example.com/subdir','http://foo.example.com'] 
as_regex = [hachoir_regex.parse(url) for url in urls] 
reduce(lambda x, y: x | y, as_regex) 

crea la expresión regular simplificada

http://(www.example.com(|/subdir)|foo.example.com) 

El código primero crea un tipo simple de expresiones regulares para cada URL, entonces concatena estos con | en el paso de reducción.