La construcción de una expresión regular Compositor

Question

que estaba leyendo la idea del proyecto de Java described here:

El usuario da ejemplos de lo que quiere y no quiere igualar. El programa intenta deducir una expresión regular que se ajuste a los ejemplos. Luego genera ejemplos que encajarían y no encajarían. El usuario corrige los ejemplos erróneos y compone una nueva expresión regular. Iterativamente, obtienes una expresión regular lo suficientemente cerca de lo que necesitas.

Esto me parece una idea realmente interesante. ¿Alguien tiene una idea de cómo hacer esto? Mi primera idea fue algo así como un algoritmo genético, pero me encantaría recibir alguna opinión de ustedes.

Answer 1

Puede intentar utilizar un algoritmo inferir básico que se haya utilizado en otras aplicaciones. He implementado una muy básica basada en la construcción de una máquina de estado. Sin embargo, solo representa muestras positivas. El código fuente está en http://github.com/mvaled/inferdtd

Debe estar interesado en el AutomataInferrer.py que es muy simple.

Answer 2

RegexBuilder parece que tiene muchas de las funciones que está buscando.

Answer 3

En realidad, esto comienza a parecerse más y más a una aplicación de compilación. De hecho, si mal no recuerdo, el compilador de Aho Dragon usa un ejemplo de expresiones regulares para compilar un compilador de DFA. Ese es el lugar para comenzar. Este podría ser un proyecto de compilación realmente genial.

Si eso es demasiado, puede acercarse a ella como una optimización en varias pasadas para refinarlo más y más, pero será todo de predefinidos Algo Al principio:

primer paso: ¿Quieres que coincida con el gato, las capturas latas Resultado:/gato | capturas | latas/

Segundo paso: Busque condiciones de partida similares: Resultado:/Ca (t | tches | ans)/

Segundo paso: Busque condiciones Ending similares: Resultado:/Ca (t | tch | an) s */

Tercer paso: Busque más opciones como repeticiones y condiciones negativas

Answer 4

El programa intenta deducir una expresión regular que se ajuste a los ejemplos

no creo que es una pregunta útil preguntar . Tienes que saber semánticamente lo que necesitas representar para deducir algo. Cuando escribes una expresión regular, tienes un propósito: aceptar URL, aceptar correos electrónicos, extraer tokens del código, etc. Volvería a definir la pregunta como tal: dada una base de conocimiento y una semántica para la expresión regular, calcule la expresión regular más pequeña. Esto da un paso más, porque tienes un lenguaje natural que intenta explicar una expresión general y todos sabemos cómo se vuelve ambiguo. Tienes que tener alguna explicación semántica. Sin eso, lo mejor que puedes hacer para obtener ejemplos es calcular expresiones regulares que cubren todas las cadenas de la lista de buenas.

Algoritmo para la cobertura:

Llenar Ok Lista
Llenar No OK Lista
Compruebe si hay repeticiones
Compruebe si hay contradicciones (la misma cadena no puede ser tanto en la lista)
Crear determinista autómatas finitos (DFA) de Ok List donde las cadenas de la lista son estados finales
Simplifique el DFA eliminando estados repetitivos. ([1] 4.4)
Convierta DFA a la expresión regular. ([1] 3.2.2)
Prueba lista bien y no bien la lista

[1] Introduction to Automata Theory, Language, and Computation. J. Hopcroft, R. Motwani, J.D. Ullman, 2nd Edition, Pearson Education.

P. S.

Tengo un poco de experiencia con la programación genética y creo que es realmente sobrecarga para su problema. Como la función objetivo es muy ligera, es mejor evaluarla con un solo procesador y esto puede llevar mucho tiempo. Para tener una expresión más corta, solo necesita minimizar el DFA. Pero GA posiblemente puede producir resultados interesantes.

Answer 5

Existe un algoritmo que hace exactamente esto para ejemplos positivos.

La expresión regular es equivalente a DFA (autómatas finitos deterministas). La estrategia es siempre la misma:

Mire Alergia (por la teoría) y el algoritmo MDI (para uso real) si generar un Autómata determinista es suficiente.

algoritmo de la Alergia y MDI son ambos describen a continuación: http://www.info.ucl.ac.be/~pdupont/pdupont/pdf/icml2k.pdf

Si desea generar modelos más pequeños se pueden utilizar otro algoritmo. El artículo que describe es aquí: http://www.grappa.univ-lille3.fr/~lemay/publi/TCS02.ps.gz

Su página está aquí: http://www.grappa.univ-lille3.fr/~lemay

Si desea utilizar ejemplo negativo, sugiero que utilice una regla simple (colorante) que impiden que dos estados de la DFA fusionarse

Si le preguntas a estas personas, estoy seguro de que compartirán su código fuente.

Hice el mismo tipo de algoritmo durante mi Ph.D. para autómatas probabilísticos. Eso significa que puede asociar una probabilidad a cada cadena, y he creado un programa C++ que "aprende" autómatas ponderados.

Principalmente estos trabajos algoritmo de esa manera:

a partir de ejemplos positivos: {ABB, aba, ABBB}

crear la DFA más simple que acepte exactamente todos estos ejemplos:

-> x -- a --> (y) -- b --> (z) 
      \ 
      b --> t -- b --> (v) 

x cativas tiene que declarar y leyendo la letra 'a' por ejemplo. Los estados son x, y, z, t y v. (Z) significa que es un estado finito.

entonces estados "de combinación" de la DFA:. (Aquí por ejemplo el resultado después de la fusión de los estados y y t

   _ 
      /\ 
      v | a,b  (<- this is a loop :-)) 
x -- a -> (y,t) _/ 

el nuevo estado (y, t) es un estado terminal de la obtención mediante la fusión de Y y t. Y puede leer la letra a y b de la misma. Ahora el DFA puede aceptar: a (a | b) * y es fácil construir la expresión regular del DFA.

Qué estados fusionar es una elección que hace la diferencia principal entre los algoritmos.

Answer 6

Tal vez Estoy un poco tarde, pero hay una manera de resolver este problema mediante la Programación Genética.

programación genética (GP) es una técnica de aprendizaje automático evolutivo en el que el candidato una solución candidata para un problema dado se represeted como un árbol de sintaxis abstracta.

Varios estudios han sido publicados sobre el uso médico de cabecera con el fin de encontrar una expresión regular que coincide con un determinado conjunto de ejemplos. Puede encontrar los artículos y los detalles here

Una aplicación web que hace esto se aloja en regex.inginf.units.it. El código fuente detrás de la aplicación se ha hecho público en github