regexp_replace - ¿Generador/reductor de expresiones regulares?

sql regular expression like

Question

Un colega me planteó una pregunta interesante para un punto problemático operacional que tenemos actualmente, y tengo curiosidad si hay algo por ahí (utilidad / biblioteca / algoritmo) que pueda ayudar a automatizar esto.

Digamos que tienes una lista de valores literales (en nuestro caso, son URL). Lo que queremos hacer es, basado en esta lista, crear una expresión regular única que coincida con todos esos elementos literales.

Entonces, si mi 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 una gran cantidad de datos, y tenemos un límite de longitud que estamos tratando de mantener por 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

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

Para hacer coincidir todas esas URL, solo esas URL y ninguna otra, no necesita una expresión regular; Probablemente pueda obtener un rendimiento aceptable al hacer comparaciones de cadenas exactas en cada elemento de su lista de URL.

Si necesita expresiones regulares, ¿cuáles son las diferencias de variables que está tratando de acomodar? Es decir, qué parte de la entrada debe coincidir literalmente, y dónde hay espacio de maniobra?

Si realmente desea usar una expresión regular para hacer coincidir una lista fija de cadenas, quizás por razones de rendimiento, entonces debería ser lo suficientemente simple como para escribir un método que pegue todas las cadenas de entrada como alternativas, como en su ejemplo. La máquina de estados que realiza la coincidencia de expresiones regulares entre bambalinas es bastante inteligente y no se ejecutará más lentamente si sus alternativas de coincidencia tienen subcadenas comunes (y por lo tanto posiblemente redundantes).

Answer 2

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

Answer 3

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

Pones una lista en el lado derecho, la envías y obtienes la expresión regular en el lado izquierdo.

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

No abuses de ello, por favor.

Answer 4

La función de utilidad de Emacs regexp-opt ( código fuente ) no hace exactamente lo que usted desea (solo funciona en cadenas fijas), pero puede ser un punto de partida útil.

Answer 5

Si desea comparar contra todas las cadenas en un conjunto y solo contra esas, use un trie o trie comprimido , o incluso mejor un gráfico de palabras acíclicas dirigido . Este último debe ser particularmente eficiente para las URL de la OMI.

Sin embargo, tendrías que abandonar las expresiones regulares.

Answer 6

Siguiendo el ejemplo de las otras dos respuestas, es todo lo que necesita para hacer coincidir solo con las cadenas proporcionadas, es probable que sea mejor hacer una coincidencia de cadena recta (lenta) o construir un FSM simple que coincida con esas cadenas (rápida).

En realidad, una expresión regular crea un FSM y luego compara su entrada con él, por lo que si las entradas son de un conjunto de un conjunto conocido anteriormente, es posible y a menudo más fácil hacer el FSM usted mismo en lugar de intentar generar automáticamente una expresión regular.

Aho-Corasick ya ha sido sugerido. Es rápido, pero puede ser difícil de implementar. ¿Qué tal si ponemos todas las cadenas en un trie y luego las consultamos en ese lugar (ya que está haciendo coincidir cadenas completas, no buscando subcadenas)?

Answer 7

Un generador automático para expresiones regulares está disponible aquí . La herramienta tiene una interfaz web y utiliza la programación genética para generar expresiones regulares a partir de un conjunto de pocos ejemplos: puede elegir entre una sintaxis preparada para los motores de expresiones regulares de Java o JavaScript. Fue desarrollado por nuestro grupo de investigación y presentado en la conferencia GECCO 2012 .

Answer 8

Una forma fácil de hacer esto es usar el módulo hachoir_regex 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 de expresión regular simple para cada URL, luego las concatena con | En el paso de reducir.