Est-il possible pour un ordinateur "d'apprendre" une expression régulière à l'aide d'exemples fournis par l'utilisateur?

Question

Est-il possible pour un ordinateur pour "apprendre" une expression régulière par l'utilisateur fourni des exemples?

Pour clarifier:

• Je n'ai pas envie d'apprendre des expressions régulières.
• Je veux créer un programme qui "apprend" une expression régulière à partir des exemples qui sont de manière interactive fournie par un utilisateur, peut-être par la sélection de pièces à partir d'un texte ou la sélection de début ou de fin de marqueurs.

Est-il possible? Existe-il des algorithmes, des mots-clés, etc. qui je peux Google pour?

EDIT: Merci pour les réponses, mais je ne suis pas intéressé par outils qui offrent cette fonctionnalité. Je suis à la recherche d'information théorique, comme des articles, des tutoriels, code source, les noms des algorithmes, donc je peux créer quelque chose pour moi.

Answer 1

Le livre Une Introduction au Calcul de la Théorie d'Apprentissage contient un algorithme pour l'apprentissage d'un automate fini. Comme tout langage régulier est équivalent à un automate fini, il est possible d'apprendre quelques expressions régulières par un programme. Kearns et Vaillant montrer certains cas où il n'est pas possible d'apprendre un automate fini. Un problème connexe est l'apprentissage de Modèles de Markov cachés, qui sont probabilistes des automates qui peuvent décrire une séquence de caractères. Notez que la plupart des modernes "expressions régulières" utilisé dans les langages de programmation sont réellement plus fort que les langues, et donc parfois plus difficile à apprendre.

Answer 2

Pas de programme d'ordinateur ne sera jamais en mesure de générer une véritable expression régulière basée uniquement sur une liste de bonnes correspondances. Laissez-moi vous montrer pourquoi.

Supposons que vous offrent les exemples 111111 et 999999, devrait à l'ordinateur de générer:

1. Une regex qui correspondent exactement à ces deux exemples: (111111|999999)
2. Une expression régulière correspondant à 6 chiffres identiques (\d)\1{5}
3. Une expression régulière correspondant à 6 et les neuf, [19]{6}
4. Une expression régulière correspondant à 6 chiffres \d{6}
5. Aucun des trois ci-dessus, avec les limites de word, par exemple, \b\d{6}\b
6. De la première des trois, pas précédée ou suivie d'un chiffre, par exemple (?<!\d)\d{6}(?!\d)

Comme vous pouvez le voir, il existe de nombreuses façons dans les exemples qui peuvent être généralisées à une expression régulière. La seule façon pour que l'ordinateur puisse construire un prévisible expression régulière est d'exiger de vous à la liste de toutes les correspondances possibles. Ensuite, il pourrait générer un modèle de recherche qui correspond exactement à ces matchs.

Si vous ne voulez pas faire la liste de tous les matchs possibles, vous avez besoin d'un plus haut niveau de description. C'est exactement ce que les expressions régulières sont conçues pour offrir. Au lieu de fournir une longue liste de 6 chiffres, il vous suffit de dire au programme de match "six chiffres". Dans la syntaxe d'expression régulière, cela devient \d{6}.

Toute méthode de fournir un niveau supérieur de la description qui est aussi souple comme des expressions régulières seront aussi complexe que les expressions régulières. Tous les outils comme RegexBuddy pouvez faire est de rendre plus facile pour créer et tester la description de haut niveau. Au lieu d'utiliser le laconique de la syntaxe d'expression régulière directement, RegexBuddy vous permet d'utiliser l'anglais de tous les blocs de construction. Mais il ne peut pas créer la description de haut niveau pour vous, car il ne peut pas magiquement de savoir quand il doit généraliser vos exemples et quand il ne devrait pas.

Il est certainement possible de créer un outil qui utilise le texte d'exemple avec les lignes directrices fournies par l'utilisateur à générer une expression régulière. La partie la plus difficile dans la conception d'un tel outil est comment fait-il demander à l'utilisateur pour le guider l'information dont il a besoin, sans en faire l'outil le plus difficile à apprendre que les expressions régulières, eux-mêmes, et sans restriction de l'outil de communes regex emplois ou à de simples expressions régulières.

Answer 3

Oui, c'est certainement "possible"; Voici le pseudo-code:

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;
}

Le problème, c'est qu'il y a un nombre infini de regexs qui correspondent à une liste d'exemples. Ce code fournit le plus simple/plus stupide de regex dans l'ensemble, essentiellement de la correspondance de quoi que ce soit dans la liste des exemples positifs (et rien d'autre, y compris les exemples négatifs).

Je suppose que le vrai défi serait de trouver le plus court regex qui correspond à tous les exemples, mais même alors, l'utilisateur devra fournir de très bonnes entrées assurez-vous que l'expression était "la bonne".

Answer 4

Je crois que le terme est "induction". Vous voulez induire une grammaire régulière.

Je ne pense pas que ce soit possible avec un ensemble fini d'exemples (positifs ou négatifs). Mais, si je me souviens bien, cela peut être fait s’il existe un Oracle pouvant être consulté. (En gros, vous devez laisser le programme poser des questions oui / non à l'utilisateur jusqu'à ce qu'il soit contenu.)

Answer 5

Vous voudrez peut-être jouer un peu avec ce site, c'est plutôt cool et on dirait qu'il fait quelque chose de similaire à ce dont vous parlez: http://txt2re.com