Interrogation efficace d'une chaîne de caractères par rapport à plusieurs regex

Question

Disons que j'ai 10 000 regex et une chaîne de caractères et que je veux savoir si la chaîne de caractères correspond à l'une d'entre elles et obtenir toutes les correspondances. La façon triviale de le faire serait d'interroger la chaîne une par une en fonction de toutes les regex. Existe-t-il un moyen plus rapide et plus efficace de le faire ?

EDIT : J'ai essayé de le substituer avec des DFA (lex) Le problème est que cela ne donne qu'un seul motif. Si j'ai une chaîne "hello" et les motifs "[H|h]ello" et ".{0,20}ello", le DFA ne correspondra qu'à l'un d'entre eux, mais je veux que les deux correspondent.

Answer 1

Si vous pensez en termes de "10 000 regex", vous devez modifier vos processus de réflexion. Au minimum, pensez en termes de "10 000 chaînes cibles à faire correspondre". Ensuite, cherchez des méthodes non regex construites pour traiter les situations de "charges de chaînes cibles", comme les machines Aho-Corasick. Franchement, cependant, il semble que quelque chose ait déraillé bien plus tôt dans le processus que le choix de la machine à utiliser, puisque 10 000 chaînes cibles ressemble beaucoup plus à une consultation de base de données qu'à une correspondance de chaînes.

Answer 2

Il faudrait avoir un moyen de déterminer si une expression donnée est "additive" par rapport à une autre. Créer une sorte de "hiérarchie" de regex permettant de déterminer que toutes les regex d'une certaine branche ne correspondent pas.

Answer 3

Vous pourriez les combiner en groupes de 20.

(?=(regex1)?)(?=(regex2)?)(?=(regex3)?)...(?=(regex20)?)

Tant que chaque regex a zéro (ou au moins le même nombre de) groupes de capture, vous pouvez regarder ce qui a été capturé pour voir quel(s) motif(s) correspond(ent).

Si regex1 correspond, le groupe de capture 1 aura son texte correspondant. Dans le cas contraire, il sera undefined / None / null /...

Answer 4

Si vous utilisez de vraies expressions régulières (celles qui correspondent aux langages réguliers de la théorie formelle des langages, et non pas un truc non régulier à la Perl), alors vous avez de la chance, car les langages réguliers sont fermés par union. Dans la plupart des langages regex, le tube (|) est une union. Vous devriez donc être en mesure de construire une chaîne de caractères (représentant l'expression régulière que vous voulez) comme suit :

(r1)|(r2)|(r3)|...|(r10000)

où les parenthèses servent à regrouper, et non à faire correspondre. Tout ce qui correspond à cette expression régulière correspond à au moins une de vos expressions régulières d'origine.

Answer 5

Je dirais que c'est un travail pour un vrai analyseur syntaxique. Un point médian pourrait être un Grammaire d'expression de l'analyse grammaticale (PEG) . Il s'agit d'une abstraction de plus haut niveau du filtrage, dont l'une des caractéristiques est que vous pouvez définir une grammaire entière au lieu d'un seul motif. Il existe des implémentations très performantes qui fonctionnent en compilant votre grammaire en bytecode et en l'exécutant dans une VM spécialisée.

avertissement : le seul que je connaisse est LPEG une bibliothèque pour Lua et il n'a pas été facile (pour moi) de saisir les concepts de base.