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

C'est ainsi que fonctionnent les lexers.

Les expressions régulières sont converties en un seul automate non déterministe (NFA) et éventuellement transformées en un automate déterministe (DFA).

L'automate résultant essaiera de faire correspondre toutes les expressions régulières en même temps et réussira sur l'une d'entre elles.

Il existe de nombreux outils qui peuvent vous aider dans ce domaine, ils sont appelés "générateur de lexiques" et il existe des solutions qui fonctionnent avec la plupart des langues.

Vous ne dites pas quel langage vous utilisez. Pour les programmeurs C, je suggérerais de jeter un coup d'œil à l'outil re2c outil. Bien sûr, le traditionnel (f)lex est toujours une option.

Answer 2

J'ai rencontré un problème similaire dans le passé. J'ai utilisé une solution similaire à celle suggérée par akdom .

J'ai eu la chance que mes expressions régulières comportent généralement une sous-chaîne qui doit apparaître dans toutes les chaînes qu'elles correspondent. J'ai pu extraire ces sous-chaînes à l'aide d'un analyseur syntaxique simple et les indexer dans un FSA en utilisant les algorithmes d'Aho-Corasick. L'index a ensuite été utilisé pour éliminer rapidement toutes les expressions régulières qui ne correspondent pas trivialement à une chaîne donnée, ne laissant que quelques expressions régulières à vérifier.

J'ai publié le code sous la LGPL en tant que module Python/C. Voir esmre sur l'hébergement de code Google .

Answer 3

Nous avons dû faire cela sur un produit sur lequel j'ai travaillé une fois. La solution consistait à compiler toutes vos regex dans un fichier de type Machine à états finis déterministe (également appelé automate fini déterministe ou DFAE ). Le DFA pourrait alors être parcouru caractère par caractère sur votre chaîne et déclencherait un événement "match" chaque fois qu'une des expressions correspondrait.

Avantages sont il fonctionne rapidement (chaque caractère n'est comparé qu'une fois) et ne devient pas plus lent si vous ajoutez plus d'expressions.

Inconvénients sont qu'il faut un énorme de données pour l'automate, et de nombreux types d'expressions régulières ne sont pas pris en charge (par exemple, les rétro-références).

Celui que nous avons utilisé a été codé à la main par un fou de templates C++ dans notre entreprise à l'époque, donc malheureusement je n'ai pas de solutions FOSS à vous indiquer. Mais si vous cherchez regex ou expression régulière avec " DFAE "vous trouverez des éléments qui vous mettront sur la bonne voie.

Answer 4

Martin Sulzmann Il a fait pas mal de travail dans ce domaine. Il a un projet HackageDB expliqué brièvement ici qui utilisent dérivés partiels semble être fait sur mesure pour cela.

Le langage utilisé est Haskell et sera donc très difficile à traduire vers un langage non fonctionnel si tel est le souhait (je pense que la traduction vers de nombreux autres langages FP serait encore assez difficile).

Le code n'est pas basé sur la conversion en une série d'automates puis sur leur combinaison, mais sur la manipulation symbolique des regex elles-mêmes.

De plus, le code est très expérimental et Martin n'est plus professeur mais a un "emploi rémunéré"(1), il peut donc ne pas être intéressé/incapable de fournir une aide ou une contribution.

---

1. c'est une blague - j'aime les professeurs, moins les intelligents essaient de travailler, plus j'ai de chance d'être payé !

Answer 5

10 000 regexen hein ? Eric Wendelin La suggestion d'une hiérarchie semble être une bonne idée. Avez-vous pensé à réduire l'énormité de ces regexen à quelque chose comme une structure arborescente ?

Un exemple simple : Toutes les regexen nécessitant un nombre pourraient se ramifier à partir d'une regex vérifiant ce nombre, toutes les regexen n'en nécessitant pas se ramifiant à leur tour. De cette façon, vous pourriez réduire le nombre de comparaisons réelles à un chemin le long de l'arbre au lieu de faire chaque comparaison sur 10 000.

Cela nécessiterait de décomposer le regexen fourni en genres, chaque genre ayant un test partagé qui les exclurait en cas d'échec. De cette façon, vous pourriez théoriquement réduire considérablement le nombre de comparaisons réelles.

Si vous deviez effectuer cette opération au moment de l'exécution, vous pourriez analyser les expressions régulières données et les "classer" dans des genres prédéfinis (le plus facile à faire) ou dans des genres comparatifs générés à ce moment-là (moins facile à faire).

Votre exemple de comparaison de "hello" avec "[H|h]ello" et ".{0,20}ello" ne sera pas vraiment aidé par cette solution. Un cas simple où cela pourrait être utile serait le suivant : si vous avez 1000 tests qui ne renvoient vrai que si "ello" existe quelque part dans la chaîne et que votre chaîne de test est "goodbye", vous n'aurez qu'à faire le seul test sur "ello" et vous saurez que les 1000 tests qui l'exigent ne fonctionneront pas, et de ce fait, vous n'aurez pas à les faire.