¿Es posible que una computadora "aprenda" una expresión regular mediante ejemplos proporcionados por el usuario?

¿Es posible que una computadora "aprenda" una expresión regular mediante ejemplos proporcionados por el usuario?

Para aclarar:

• Yo no quiero aprender expresiones regulares.
• Quiero crear un programa que "aprenda" una expresión regular a partir de ejemplos proporcionados de forma interactiva por un usuario, tal vez seleccionando partes de un texto o seleccionando marcadores de inicio o fin.

¿Es posible? ¿Hay algoritmos, palabras clave, etc. que pueda buscar en Google?

EDITAR : Gracias por las respuestas, pero no me interesan las herramientas que brindan esta función. Estoy buscando información teórica, como artículos, tutoriales, código fuente, nombres de algoritmos, para poder crear algo por mí mismo.

El libro Introducción a la teoría del aprendizaje computacional contiene un algoritmo para aprender un autómata finito. Como todo lenguaje regular es equivalente a un autómata finito, es posible aprender algunas expresiones regulares mediante un programa. Kearns y Valiant muestran algunos casos en los que no es posible aprender un autómata finito. Un problema relacionado es el aprendizaje de modelos de Markov ocultos , que son autómatas probabilísticos que pueden describir una secuencia de caracteres. Tenga en cuenta que la mayoría de las "expresiones regulares" modernas que se utilizan en los lenguajes de programación son en realidad más fuertes que los lenguajes regulares y, por lo tanto, a veces son más difíciles de aprender.

Sí, es posible, podemos generar expresiones regulares a partir de ejemplos (texto -> extracciones deseadas). Esta es una herramienta en línea que funciona y hace el trabajo: http://regex.inginf.units.it/

La herramienta en línea Regex Generator ++ genera una expresión regular a partir de los ejemplos proporcionados utilizando un algoritmo de búsqueda GP. El algoritmo GP está impulsado por una aptitud multiobjetivo que conduce a un mayor rendimiento y una estructura de solución más simple (Occam's Razor). Esta herramienta es una aplicación demostrativa del Machine Lerning Lab, Trieste Univeristy (Università degli studi di Trieste). Mira el video tutorial aquí .

Este es un proyecto de investigación, por lo que puede leer sobre los algoritmos usados aquí .

¡Mirad! :-)

Es posible encontrar una expresión regular / solución significativa a partir de ejemplos si y solo si los ejemplos proporcionados describen bien el problema. Considere estos ejemplos que describen una tarea de extracción, estamos buscando códigos de artículo particulares; los ejemplos son pares de texto / extracción:

"The product code is 467-345A" -> "467-345A"
"The item 789-345B is broken"  -> "789-345B"

Un tipo (humano), mirando los ejemplos, puede decir: "los códigos de artículo son cosas como \ d ++ - 345 [AB]"

Cuando el código del artículo es más permisivo pero no hemos proporcionado otros ejemplos, no tenemos pruebas para entender bien el problema. Al aplicar la solución generada por humanos \ d ++ - 345 [AB] al siguiente texto, falla:

"On the back of the item there is a code: 966-347Z"

Debe proporcionar otros ejemplos para describir mejor qué es una coincidencia y qué no es una coincidencia deseada: --es decir:

"My phone is +39-128-3905 , and the phone product id is 966-347Z" -> "966-347Z"

El número de teléfono no es una identificación de producto, esto puede ser una prueba importante.

Ningún programa informático podrá generar una expresión regular significativa basada únicamente en una lista de coincidencias válidas. Déjame mostrarte por qué.

Suponga que proporciona los ejemplos 111111 y 999999, si la computadora genera:

1. Una expresión regular que coincide exactamente con esos dos ejemplos: (111111|999999)
2. Una expresión regular que coincide con 6 dígitos idénticos (\d)\1{5}
3. Una expresión regular que coincide con 6 unos y nueves [19]{6}
4. Una expresión regular que coincida con cualquier 6 dígitos \d{6}
5. Cualquiera de los tres anteriores, con límites de palabras, p. Ej. \b\d{6}\b
6. Cualquiera de los tres primeros, no precedido ni seguido por un dígito, p. Ej. (?<!\d)\d{6}(?!\d)

Como puede ver, hay muchas formas en las que los ejemplos se pueden generalizar en una expresión regular. La única forma de que la computadora cree una expresión regular predecible es exigirle que enumere todas las coincidencias posibles. Entonces podría generar un patrón de búsqueda que coincida exactamente con esas coincidencias.

Si no desea enumerar todas las coincidencias posibles, necesita una descripción de nivel superior. Eso es exactamente para lo que están diseñadas las expresiones regulares. En lugar de proporcionar una lista larga de números de 6 dígitos, simplemente le dice al programa que coincida con "cualquier seis dígitos". En la sintaxis de expresiones regulares, esto se convierte en \ d {6}.

Cualquier método para proporcionar una descripción de nivel superior que sea tan flexible como las expresiones regulares también será tan complejo como las expresiones regulares. Todas las herramientas como RegexBuddy pueden hacer es facilitar la creación y prueba de la descripción de alto nivel. En lugar de usar directamente la sintaxis de expresión regular concisa, RegexBuddy le permite usar bloques de construcción en inglés simple. Pero no puede crear la descripción de alto nivel para usted, ya que no puede saber mágicamente cuándo debería generalizar sus ejemplos y cuándo no.

Sin duda, es posible crear una herramienta que utilice texto de muestra junto con las pautas proporcionadas por el usuario para generar una expresión regular. La parte difícil en el diseño de una herramienta de este tipo es cómo le pide al usuario la información de guía que necesita, sin hacer que la herramienta sea más difícil de aprender que las expresiones regulares en sí mismas, y sin restringir la herramienta a trabajos de expresiones regulares comunes o expresiones regulares simples.

Sí, ciertamente es "posible"; Aquí está el pseudocódigo:

string MakeRegexFromExamples(<listOfPosExamples>, <listOfNegExamples>)
{
   if HasIntersection(<listOfPosExamples>, <listOfNegExamples>)
     return <IntersectionError>

   string regex = "";
   foreach(string example in <listOfPosExamples>)
   {
      if(regex != "")
      {
         regex += "|";
      }
      regex += DoRegexEscaping(example);
   }
   regex = "^(" + regex + ")$";

   // Ignore <listOfNegExamples>; they're excluded by definition

   return regex;
}

El problema es que hay un número infinito de expresiones regulares que coincidirán con una lista de ejemplos. Este código proporciona la expresión regular más simple / estúpida del conjunto, que básicamente coincide con cualquier cosa en la lista de ejemplos positivos (y nada más, incluidos los ejemplos negativos).

Supongo que el verdadero desafío sería encontrar la expresión regular más corta que coincida con todos los ejemplos, pero incluso entonces, el usuario tendría que proporcionar muy buenas entradas para asegurarse de que la expresión resultante sea "la correcta".

Creo que el término es "inducción". Quieres inducir una gramática regular.

No creo que sea posible con un conjunto finito de ejemplos (positivos o negativos). Pero, si mal no recuerdo, se puede hacer si hay un Oracle que se pueda consultar. (Básicamente, tendría que dejar que el programa le haga preguntas de sí / no al usuario hasta que esté contenido).

Es posible que desee jugar un poco con este sitio, es bastante bueno y parece que hace algo similar a lo que está hablando: http://txt2re.com

Hay un lenguaje dedicado a problemas como este, basado en prólogo. Se llama progol .

Como han mencionado otros, la idea básica es el aprendizaje inductivo, a menudo llamado ILP ( programación lógica inductiva ) en los círculos de IA.

El segundo enlace es el artículo wiki sobre ILP, que contiene una gran cantidad de material fuente útil si está interesado en aprender más sobre el tema.

@Yuval tiene razón. Estás viendo la teoría del aprendizaje computacional o "inferencia inductiva".

La pregunta es más complicada de lo que cree, ya que la definición de "aprender" no es trivial. Una definición común es que el alumno puede escupir respuestas cuando quiera, pero eventualmente, debe dejar de escupir respuestas o siempre escupir la misma respuesta. Esto supone un número infinito de entradas y no da absolutamente ninguna garantía sobre cuándo el programa tomará su decisión. Además, no se puede saber cuándo HA tomado su decisión porque aún podría generar algo diferente más adelante.

Según esta definición, estoy bastante seguro de que se pueden aprender idiomas normales. Según otras definiciones, no tanto ...

Investigué un poco en Google y CiteSeer y encontré estas técnicas / artículos:

• Identificación del idioma en el límite
• Probablemente aprendizaje aproximadamente correcto

También el "Aprendizaje de conjuntos regulares de consultas y contraejemplos" de Dana Angluin parece prometedor, pero no pude encontrar una versión PS o PDF, solo citas y artículos de seminario.

Parece que este es un problema complicado incluso en el nivel teórico.

Si es posible que una persona aprenda una expresión regular, entonces es fundamentalmente posible para un programa. Sin embargo, ese programa deberá estar correctamente programado para poder aprender. Afortunadamente, este es un espacio de lógica bastante finito, por lo que no sería tan complejo como enseñar un programa para poder ver objetos o algo así.