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

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é.

Supongamos que proporciona los ejemplos 111111 y 999999, si el equipo 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 ones y nueves [19]{6}
4. Una expresión regular que coincida con 6 dígitos \d{6}
5. Cualquiera de los tres anteriores, con límites de palabras, por ejemplo, \b\d{6}\b
6. Cualquiera de los tres primeros, no precedida o seguida de un dígito, por ejemplo, (?<!\d)\d{6}(?!\d)

Como puede ver, hay muchas maneras en que los ejemplos se pueden generalizar en una expresión regular. La única manera para que el equipo construya una expresión regular predecible es requerir que listes todas las posibles coincidencias. Entonces podría generar un patrón de búsqueda que coincida exactamente con esas coincidencias.

Si no quieres enumere todas las posibles coincidencias, necesita una descripción de nivel superior. Eso es exactamente lo que las expresiones regulares están diseñadas para proporcionar. En lugar de proporcionar una larga lista de números de 6 dígitos, simplemente le dices 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 haz que sea más fácil crear y probar 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. 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 debería.

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

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

Regex Generator++ la herramienta en línea genera una expresión regular a partir de ejemplos proporcionados utilizando un algoritmo de búsqueda GP. El algoritmo GP es impulsado por una aptitud multiobjetiva que conduce a un mayor rendimiento y una estructura de solución más simple (navaja de Occam). Esta herramienta es una aplicación demostrativa de la Máquina Lerning Lab, Trieste Univeristy (Università degli studi di Trieste). Por favor mira el video tutorial aquí.

Este es un proyecto de investigación para que pueda leer sobre algoritmos usados aquí.

¡Contemplen! :-)

Encontrar una regex/solución significativa a partir de ejemplos es posible 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 elementos particulares; los ejemplos son pares texto / extracción:

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

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

Cuando el código del elemento 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"

Tiene que proporcionar otros ejemplos, con el fin de describir mejor lo que es una coincidencia y lo que no es una coincidencia deseada: -- i. e:

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

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

Sí, es ciertamente "posible" ;Aquí está el pseudo-có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, básicamente coincidiendo con cualquier cosa en la lista de ejemplos positivos (y nada más, incluyendo cualquiera de 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 tener que proporcionar muy buenas entradas para asegurarse de que la expresión resultante era "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 Oráculo al que se pueda consultar. (Básicamente tendrías que dejar que el programa le haga al usuario preguntas sí/no hasta que estuviera contenido.)

Es posible que desee jugar con este sitio un poco, es bastante genial y suena como si hiciera algo similar a lo que estás hablando: http://txt2re.com

Hay un lenguaje dedicado a problemas como este, basado en prolog. Se llama progol .

Como otros han mencionado, 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 es correcto. Estás viendo la teoría del aprendizaje computacional ,o " inferencia inductiva. "

La pregunta es más complicada de lo que piensas, 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 ningún garauntee sobre cuándo el programa alcanzará su decisión. Además, no se puede decir cuándo ha llegado a su decisión porque aún podría generar algo diferente más tarde.

Por esta definición, estoy bastante seguro de que los idiomas regulares son aprendibles. Por otras definiciones, no tanto...

He hecho algunas investigaciones sobre Google y CiteSeer y encontré estas técnicas / documentos:

• Identificación lingüística en el límite
• Probablemente aproximadamente aprendizaje 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 documentos de seminarios.

Parece que este es un problema complicado incluso en la teoría nivel.

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