Comment trouver un « ensemble minimal spanning » pour une collection d'expressions régulières?

Question

CONTEXTE:

J'ai un peu petite (actuellement moins de 100), mais collection croissante des expressions régulières, et je veux optimiser le processus de détermination d'une chaîne de texte donnée qui du SRE dans ma collection correspondre à la chaîne de texte.

Certains des sources renouvelables ont une relation de commande - par exemple si je sais que les matchs string $ t / windows / i alors je sais aussi que $ t /windows.*2000/i correspond. Ainsi, lors du test $ t contre la chose dans ma collection, je peux aller tester / windows / i si je l'ai déjà testé $ t contre /windows.*2000/i et a trouvé un match (bien que si /windows.*2000/i-t pas correspondent alors bien sûr I ne peuvent pas passer le test contre / windows / i).

Notez que rien du SRE dans ma collection sont tout à fait équivalent (pour une paire de REs il y a au moins une chaîne de texte qui correspond à l'un et fait pas correspondent l'autre).

STRATÉGIE:

Je veux construire un graphe orienté G avec un noeud pour chaque RE dans ma collection et un bord dirigé pour chaque paire de REs avec une relation de commande (A -> des moyens B « match contre A implique match contre B »), et trouver un « ensemble de découpage minimum » de noeuds du graphe (ensemble minimal de noeuds S de telle sorte que chaque noeud dans le mensonge G sur un chemin orienté qui provient en S).

LA PARTIE FACILE:

Il y a beaucoup d'algorithmes librement disponibles pour travailler avec acyclique orienté graphiques. Donc, une fois que le graphe G est construit pour ma collection de (qui REs étant distinct doit garantir que G est acyclique) Je ne pense pas avoir beaucoup de difficulté à trouver un algorithme approprié pour trouver un ensemble Spanning minimal G.

OÙ JE BESOIN D'AIDE:

Je voudrais trouver un moyen efficace de trouver toutes les relations de commande entre le SRE dans ma collection - et peut-être aussi pour vous assurer que deux REs de la collection sont équivalentes (je besoin d'un moyen de vérifier automatiquement comme nouveaux REs sont ajoutés).

Mes recherches sur le Web (essentiellement au hasard) ont ainsi mis en place au moins une revendication plausible qu'un moyen raisonnable de calculer ce que (le cas échéant) relation de commande existe entre deux REs n'existe en effet, mais pas encore retroussé les descriptions d'une algorithme complet.

Quelqu'un sait-il d'une implémentation existante (pour comparer SRE) qui est raisonnablement efficace, disponible gratuitement, et (idéalement) mis en œuvre soit dans l'un des langages de script populaires ou C / C ++?

Answer 1

Je ne sais pas si vous avez la flexibilité en termes de la bibliothèque d'expressions régulières que vous devez utiliser, mais vous pouvez regarder RE2 dont Set interface peut correspondre à plusieurs regexes simultanément. Notez que RE2 utilise principalement une approche DFA, et ne supporte pas toutes les expressions rationnelles dispose que d'autres, pour la plupart retours en arrière, les implémentations font.