Base de données ou structure appropriée pour faire correspondre des chaînes à des modèles regex

Question

J'ai un certain nombre de modèles regex. Quand une chaîne est entrée, je dois trouver tous les motifs qui correspondent à cette chaîne. Ceci est normalement un O (n) opération:

SELECT regex FROM regexes WHERE 'string' RLIKE regex 

Quel est le meilleur moyen de le faire? Existe-t-il des structures de base de données ou des systèmes de stockage optimisés pour effectuer une telle opération?

Answer 1

La réponse courte est 'Non' Aucune structure d'index n'est actuellement disponible sur les plateformes de SGBD qui indexeront les correspondances partielles d'une expression régulière comme celle-ci.

La réponse longue est qu'une constante principale sur une correspondance générique (par exemple 'foo_') peut être utilisée comme préfixe pour les correspondances d'index. De nombreuses plates-formes de SGBD optimiseront cela et utiliseront un index (si disponible) pour résoudre le préfixe. Cependant, ce n'est pas aussi intelligent qu'une regex complète, et l'indexation ne peut être utilisée que si vous avez un préfixe constant.

La réponse encore plus longue est qu'il existe des algorithmes tels que RETE qui optimisera les correspondances partielles comme ceci. Cela peut être applicable si vous pouvez exprimer vos correspondances en tant que règles de production en chaînage direct plutôt qu'en expressions régulières. Rete fonctionne en calculant des correspondances partielles et en ne présentant que des règles pouvant être atteintes à partir de cette correspondance partielle. Elle est donc plus efficace que O (n) (plus proche de O (log n) mais je ne suis pas sûre de l'exactitude complexité temporelle) pour faire correspondre n règles à un fait.

Answer 2

Une optimisation que vous pourriez mettre en œuvre, le cas échéant à votre cas, serait de classer vos regexes et les organiser en hiérarchies afin que:

• vous suffit de tester une poignée de Regexes plus général.

• pour toute expression rationnelle générale qui correspond, puis de tester la chaîne par rapport à toutes les expressions régulières de la même catégorie uniquement.

Par exemple, si vos chaînes d'entrée peuvent être quelque chose arbitrairement complexe et vous avez des milliers de regexes, vous pouvez les organiser dans des catégories comme:

• la catégorie \d+, ce qui permettrait de tester les modèles numériques (NSS, numéros de téléphone, etc.)

• la catégorie <.*?>, ce qui permettrait de tester la présence de balises HTML

• la catégorie \w+@\w+, ce qui pourrait tester la présence d'adresses e-mails

etc.

Si un modèle de racine ne correspond pas, alors vous éviter d'avoir à tester l'ensemble des gammes de modèles qui ne parviendrait pas de toute façon .

Je ne sais pas si cela correspondrait à votre domaine exact, mais c'est une optimisation possible.