Combinaison de plusieurs expressions régulières dans un automate

Disons que j’ai une liste d’expressions régulières (lues depuis une source externe – fichier, firebase database, etc.). Je veux vérifier laquelle de ces expressions régulières correspond une chaîne.

Je peux créer une itération à travers toutes ces expressions régulières et les associer, mais la liste pourrait être très longue et il s’agit là d’une opération cruciale.

Je peux combiner toutes ces expressions régulières en une seule (avec | entre elles), mais le problème est que je ne peux identifier que la première expression régulière correspondante, pas toutes.

Une autre idée pourrait être de créer un automate pour toutes ces expressions régulières et de marquer les états finaux avec, disons, les index de l’expression régulière correspondante. Je regardais http://cs.au.dk/~amoeller/automaton/ , une bibliothèque qui semble capable de travailler avec des expressions régulières et un automate, mais je ne suis pas sûre qu’elle puisse être étendue pour résoudre mon problème.

As-tu d’autres idées?

Pour clarifier certains commentaires, j’ai ajouté un exemple de code:

import java.util.regex.Matcher; import java.util.regex.Pattern; public class PatternTest { public static void main(Ssortingng[] args) { Pattern p = Pattern.comstack("(a(?:b|c)a)|((?:a|b)ba)|(ab(?:a|c))"); Matcher m = p.matcher("aba"); System.out.println(m.matches()); System.out.println(m.groupCount()); for (int i = 0, n = m.groupCount(); i < n; i++) { System.out.println(m.group(i)); } } }

va imprimer

 true 3 aba aba null

Comme vous pouvez le constater, seul le premier groupe est jumelé et je ne vois pas de moyen de faire correspondre les deux autres.

Autres découvertes – En utilisant la bibliothèque d’automates ci-dessus, le problème sera réduit à ce qui suit: si vous concaténez deux ou plusieurs automates, comment identifier un état final auquel l’automate original correspond?

dk.brics.automaton ne le prend pas directement en charge, mais vous pouvez généraliser la représentation des automates (et des opérations correspondantes) afin de distinguer différents types d’états acceptés. Commencez par append un champ int, par exemple, à la classe State et utilisez-le chaque fois que ‘accept’ est défini.

J’ai implémenté une telle solution basée sur dk.brics.automaton, vous pouvez la trouver ici. https://github.com/fulmicoton/multiregexp

Pour une réponse définitive (s’il en existe une), nous aurions besoin d’informations supplémentaires, telles que:

Vous dites que la liste des regex est énorme; Peux-tu être plus précis? Milliers? Des millions? Des milliards et des milliards?
Qui a écrit ces regex et savent-ils ce qu’ils font? Les expressions rationnelles sont-elles soigneusement testées (pour l’exactitude et la performance) avant d’être ajoutées à la liste?
Dans votre exemple de code, vous utilisez la méthode matches() , qui requirejs l’expression régulière pour décrire la chaîne entière. Il agit comme si la regex était vraiment
\A(?:(a(?:b|c)a)|((?:a|b)ba)|(ab(?:a|c)))\z
qui correspond à "aba" mais pas "aaba" ou "abaa" . Si vous avez utilisé des expressions rationnelles dans d’autres outils ou dans d’autres langages avant d’utiliser Java, ce comportement pourrait vous surprendre. Traditionnellement, on dit toujours qu’une chaîne “correspond” à une expression rationnelle si cette expression décrit une sous-chaîne de la chaîne, même une chaîne de longueur nulle. Pour obtenir ce comportement en Java, vous devez utiliser la méthode find() Matcher.
Existe-t-il des facteurs communs que vous pouvez extraire de toutes les expressions rationnelles de la liste, tels que la longueur minimale ou maximale, les sous-chaînes communes ou les sous-ensembles de caractères partagés? Par exemple, toute chaîne correspondant à l’un de vos exemples de modèle doit également correspondre à [abc]{3} . Si tel est le cas, vous pouvez créer des filtres en fonction de ces filtres (peut-être des expressions rationnelles, peut-être pas) avant que la correspondance sérieuse ne commence. (Je ne le suggérerais pas si vous utilisiez Perl, qui est déjà un bloc avec des optimisations de ce type, mais Java n’est pas trop fier d’accepter un peu d’aide. ☺)

Mais je me sens plutôt en sécurité en vous conseillant de choisir des expressions rationnelles séparées plutôt que de les concaténer en une seule. Le Frankenregex ne fonctionnerait pas nécessairement mieux, et le dépannage serait un cauchemar! Vous pouvez pré-comstackr tous les objects Pattern, créer un object Matcher à l’avance et le réutiliser pour toutes les correspondances, comme ceci:

 m.reset(s).usePattern(p);

Voici une démo . Je ne peux faire aucune garantie (vous êtes toujours à la merci de celui qui a écrit les expressions rationnelles, pour une chose), mais si une solution est possible, je pense que c’est l’approche la plus prometteuse.