Construire un Regex Compositeur

Question

Je lisais l'idée du projet Java described here:

L'utilisateur donne des exemples de ce qu'il veut et ne veut pas correspondre. Le programme essaie de déduire une regex qui correspond aux exemples. Ensuite, il génère des exemples qui correspondent et ne correspondent pas. L'utilisateur corrige les exemples erronés et compose une nouvelle regex. Itérativement, vous obtenez une regex assez proche de ce dont vous avez besoin.

Cela me semble être une idée vraiment intéressante. Est-ce que quelqu'un a une idée sur la façon de faire cela? Ma première idée était quelque chose comme un algorithme génétique, mais j'aimerais beaucoup de votre part.

Answer 1

Vous pouvez essayer d'utiliser un algorithme d'inférence de base qui a été utilisé dans d'autres applications. J'ai mis en œuvre un très basique basé sur la construction d'une machine d'état. Cependant, cela ne tient compte que des échantillons positifs. Le code source est sur http://github.com/mvaled/inferdtd

Devrait être intéressé par le AutomataInferrer.py qui est très simple.

Answer 2

RegexBuilder semble avoir beaucoup de fonctionnalités que vous recherchez.

Answer 3

En fait, cela commence à ressembler de plus en plus à une application de compilation. En fait, si je me souviens bien, le compilateur Aho Dragon utilise un exemple regex pour compiler un compilateur DFA. C'est l'endroit pour commencer. Cela pourrait être un projet de compilateur vraiment cool.

Si cela est trop, vous pouvez approcher comme une optimisation en plusieurs passes pour affiner plus loin et plus loin, mais il sera tout d'abord des années algo prédéfinies:

passe d'abord: Vous voulez correspondre Cat, les prises boîtes Résultat:/Cat | captures | boîtes/

Second Pass: Recherchez les conditions de départ similaires: Résultat:/Ca (t | tches | ans)/

Second Pass: Recherchez les conditions Ending similaires: Résultat:/Ca (t | tch | an) s */

Troisième Pass: Rechercher possibilité d'affinement comme des répétitions et des conditions négatives

Answer 4

Le programme tente d'en déduire une expression rationnelle qui correspond aux exemples

Je ne pense pas que c'est une question utile de demander . Vous devez savoir sémantiquement ce que vous devez représenter pour en déduire quelque chose. Lorsque vous écrivez une expression régulière, vous avez un but: accepter des URL, accepter des courriels, extraire des jetons du code, etc. Je redéfinirais la question comme suit: étant donné une base de connaissances et une sémantique pour l'expression régulière, calculons la plus petite regex. Cela va un peu plus loin, parce que vous avez un langage naturel qui tente d'expliquer une expression générale et nous savons tous comment il devient ambigu! Vous devez avoir une explication sémantique. Sans cela, la meilleure chose que vous pouvez faire pour les exemples est de calculer regex qui couvre toute la chaîne de la liste ok.

algorithme de couverture:

Populate Ok Liste
Populate Liste non ok
Vérifiez les répétitions
Vérifier les contradictions (la même chaîne ne peut pas être à la fois la liste)
Créer déterministes Finite Automata (DFA) à partir de Ok Liste où les chaînes de la liste sont des états finaux
Simplifiez le DFA en éliminant les états répétitifs. ([1] 4.4)
Convertir DFA en expression régulière. ([1] 3.2.2)
test liste Ok et pas la liste ok

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

de post-scriptum J'ai eu de l'expérience avec la programmation génétique et je pense que c'est vraiment un problème pour votre problème. Puisque la fonction objectif est vraiment légère, il est préférable d'évaluer avec un seul processeur, ce qui peut prendre beaucoup de temps. Pour avoir une expression plus courte, vous devez juste minimiser le DFA. Mais GA peut éventuellement produire des résultats intéressants.

Answer 5

Il existe un algorithme qui fait exactement cela pour les exemples positifs.

L'expression régulière est équivalente à DFA (Deterministic Finite Automata). La stratégie est la plupart du temps toujours la même:

Regardez Alergia (pour la théorie) et l'algorithme MDI (pour une utilisation réelle) si générer un automate déterministe est suffisant.

L'algorithme Alergia et MDI sont tous deux décrits ici: http://www.info.ucl.ac.be/~pdupont/pdupont/pdf/icml2k.pdf

Si vous voulez générer des modèles plus petits, vous pouvez utiliser un autre algorithme. L'article décrit est ici: http://www.grappa.univ-lille3.fr/~lemay/publi/TCS02.ps.gz

Sa page d'accueil est ici: http://www.grappa.univ-lille3.fr/~lemay

Si vous souhaitez utiliser exemple négatif, je vous suggère d'utiliser une règle simple (coloration) qui empêchent deux états du DFA être fusionné.

Si vous posez la question à ces personnes, je suis sûr qu'elles partageront leur source de code.

J'ai fait le même type d'algorithme pendant mon doctorat. pour les automates probabilistes. Cela signifie que vous pouvez associer une probabilité à chaque chaîne, et j'ai créé un programme C++ qui "apprend" des automates pondérés.

Principalement ces travaux d'algorithme comme ça:

d'exemples positifs: {abb, aba, abbb}

créer la DFA simple qui acceptent exactement tous ces exemples:

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

x catifs Je dois dire y en lisant la lettre «a» par exemple. Les états sont x, y, z, t et v. (Z) signifie que c'est un état fini.

puis « fusion » états du DFA:. (Ici par exemple le résultat après la fusion des états y et t

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

le nouvel état (y, t) est un état terminal obtenir en fusionnant y et Maintenant, le DFA peut accepter: a (a | b) * et il est facile de construire l'expression régulière à partir de l'AFD

un choix qui fait la différence entre les algorithmes

Answer 6

Je suis un peu en retard, mais il y a un moyen de résoudre ce problème au moyen de la programmation génétique. La programmation génétique (GP) est une technique évolutive d'apprentissage automatique dans laquelle une solution candidate pour un problème donné est représentée comme un arbre de syntaxe abstraite.

Plusieurs études ont été publiées sur la façon d'utiliser GP afin de trouver une expression régulière qui correspond à un ensemble donné d'exemples. Vous pouvez trouver les articles et les détails here

Une webapp qui fait ceci est hébergé à regex.inginf.units.it. Le code source derrière l'application a été publié publiquement sur github