Mauvaises performances des expressions régulières ?

Publié par Eyal Schneider le 21 mai 2009 Le package java.util.regex a été ajouté à Java dans la version 1.4. C’est un outil très puissant et il faut devenir maître pour l’utiliser correctement. Même lorsqu’une expression régulière est vraie, elle peut être très lente si elle n’est pas écrite intelligemment. Continuez à lire si vous souhaitez comprendre la cause des problèmes, ou faites défiler jusqu'à la fin de la page où vous trouverez 10 conseils utiles pour améliorer les performances des expressions régulières en Java.

Est-ce vraiment si lent ?

Disons que nous voulons sélectionner uniquement les lignes contenant la séquence de caractères « a » et « b ». La bonne solution pourrait être : (a*b*)* Cependant, si vous exécutez l'expression avec, par exemple, la chaîne « aaaaaaaaaaaaaaaaaaaaaaaaaaaax » , cela prendra plusieurs minutes avant qu'elle se termine et ne signale aucune correspondance ! Bien sûr, la meilleure expression régulière dans ce cas serait : (a|b)* Cela prend moins d'une milliseconde sur ma machine avec la même chaîne. Il y a clairement un problème de performances ici.

Pourquoi cela arrive-t-il?

Comme la plupart des moteurs d'expressions rationnelles, Java utilise une approche NFA (Non-Deterministic Finite Automata). Le moteur analyse les composants regex un par un et avance en conséquence dans la chaîne d'entrée. Et il peut revenir au début pour trouver des alternatives appropriées s’il se retrouve dans une « impasse ». Des résultats alternatifs sont obtenus en utilisant des structures régulières telles que des quantificateurs ( *, +, ? ) et des alternances (par exemple a|b|c|d ). Cette technique de recherche est appelée backtracking. Dans le terrible exemple ci-dessus, le moteur examinera TOUTES les décompositions en séries du symbole « a » en séries plus petites jusqu'à ce qu'il se rende compte qu'il n'y a aucune correspondance. Cet exemple montre comment l'algorithme de backtracking peut aboutir à une estimation de temps exponentielle (en fonction de la longueur de la chaîne d'entrée). Cela montre également une propriété importante de la NFA : il y aura toujours les pires cas qui correspondent presque au modèle. Si une correspondance est trouvée, la recherche s'arrête. L’autre approche principale à utiliser dans les regex est DFA (Deterministic Finite Automaton). Dans cette approche, l'expression régulière construit en fait un automate utilisé pour parcourir les chaînes d'entrée caractère par caractère sans revenir en arrière. Cela donne un temps linéaire à l'ensemble de l'entrée, quelle que soit la complexité de l'expression régulière. Au lieu d'analyser séquentiellement une chaîne à la recherche de correspondances (comme dans NFA), DFA simule une analyse parallèle. Alors pourquoi Java (et .NET, Perl, Python, Ruby, PHP, etc.) utilise-t-il NKA et non DKA qui a un bien meilleur comportement ? La raison en est que NKA présente un certain nombre d’avantages importants :

Compile plus rapidement et nécessite beaucoup moins de mémoire
Permet certaines fonctionnalités utiles (voir le tutoriel de Sun pour plus de détails ) :

Capture de groupe et backlinks
Vérification de position
Quantificateurs étendus (gourmands et paresseux)

Il est important de noter que les termes populaires NKA et DKA sont imprécis lorsqu’ils sont utilisés dans le contexte d’expressions régulières. En théorie, ces deux modèles ont la même puissance de calcul. Cela signifie que vous ne pouvez pas écrire une expression régulière dans un modèle d’automate qui serait impossible à exprimer dans un autre. En pratique, il faut davantage de capacités pour que les deux types d’implémentation divergent en termes de sémantique. Les moteurs NKA offrent plus de flexibilité, ce qui les rend supérieurs au DKA en termes de puissance de calcul. En raison de la rapidité de DFA et des fonctionnalités uniques de NFA, il existe deux méthodes « préfabriquées » supplémentaires pour implémenter des expressions régulières. Certaines implémentations utilisent les deux types (par exemple GNU egrep, qui sélectionne un moteur spécifique lors de l'exécution), et certaines ont réussi à implémenter une version véritablement hybride (par exemple les expressions rationnelles Tcl) avec tous les avantages.

Conseil

Voici quelques conseils pour éviter les problèmes d’efficacité des regex en Java. Beaucoup d’entre eux visent à réduire les rendements.

1) Pré-compilation

Banal, mais mérite d'être mentionné. Si vous utilisez l'expression rationnelle plus d'une fois, assurez-vous de la compiler à l'avance :

// компиляция p = Pattern.compile(regex, flags); … // использование Matcher a = p.matcher(input);

2) Quantificateurs paresseux vs quantificateurs gourmands

Par défaut, les quantificateurs ( * + ? ) sont gourmands. Cela signifie qu'ils commencent à correspondre avec la séquence la plus longue possible, puis reviennent progressivement si nécessaire. Si vous savez à l’avance que les matchs seront généralement courts, vous devez utiliser des quantificateurs paresseux. Ils commencent par le plus petit match et avancent si nécessaire. Disons que nous voulons trouver uniquement les lignes qui correspondent à la séquence « bonjour ». Le .*hello.* normal fera tout correctement, mais si nous savons que « bonjour » apparaît généralement plus près du début du texte, alors .*?hello.* fonctionnera plus rapidement en moyenne.

3) Utilisez des quantificateurs super gourmands lorsque cela est possible

Contrairement aux quantificateurs paresseux, qui affectent les performances mais n’affectent pas le comportement normal, les quantificateurs super gourmands peuvent en réalité changer la signification d’une expression régulière. Lorsque *+ est utilisé à la place de * , la première correspondance sera gourmande (c'est-à-dire la plus grande possible comme s'il s'agissait simplement de *), mais il n'y aura pas de solution de secours en cas d'échec, même si cela entraîne l'échec de la recherche entière. Quand cela pourrait-il être utile ? Disons que nous devons trouver du texte entre guillemets. Le \"[^\"]*\" normal fonctionnera très bien. Cependant, il créera une indentation inutile dans les cas négatifs (par exemple, « bla bla bla). L'utilisation de \"[^\"]*+\" éliminera rollbacks sans changer le sens de l’expression. Le regroupement indépendant produit le même effet et donne encore plus de contrôle (voir le tutoriel de Sun ).

4) Évitez la capture de groupe

Toute expression entre parenthèses est considérée comme un groupe par défaut. Cela a un léger impact sur les performances. Rendez vos groupes « incapturables » autant que possible en les commençant par (? : au lieu de ( .

5) Utilisez judicieusement l’entrelacement

Lorsque l'entrelacement est utilisé (par exemple Paul|Jane|Chris ), l'ordre dans lequel le moteur essaie de faire correspondre les options est le même que l'ordre dans lequel elles apparaissent. Vous pouvez profiter de cette fonctionnalité et placer les options les plus courantes plus près du début. Cela améliorera le temps de réponse positif moyen.

6) Évitez toute ambiguïté

Écrivez les expressions rationnelles de manière à minimiser le nombre de correspondances différentes dans la chaîne d'entrée. Par exemple : l'expression régulière (a*b*)* donnée en début d'article permet d'interpréter la chaîne "aabb" de trop nombreuses façons : (a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Regexp (a|b)*, par contre, n'interprète que des combinaisons positivement. Ceci est très important pour réduire les retours dans les cas de quasi- correspondance.

7) Aperçu

L'aperçu vous permet d'ajouter des restrictions sur les séquences à gauche/droite de la position actuelle. En particulier, avec une anticipation négative, vous pouvez rechercher des lignes qui ne contiennent pas de séquence (que ferions-nous sans cela !). Comment cela peut-il contribuer à augmenter la productivité ? Disons que nous voulons récupérer l'URL de la balise de lien. Considérez l'expression rationnelle suivante : a .* href=(\S*).*/ pour les balises normales, cette expression ne correspondra à l'adresse que si le texte contient l'attribut "href" (\S est utilisé pour tous les caractères sauf les délimiteurs). Mais sur certaines balises inhabituelles, par exemple, un rollback se produira. Par exemple : « a href= href=href=…. href=quelque chose. L'expression rationnelle suivante empêchera que cela se produise lors du remplacement du « .* » dans une expression par quelque chose qui ne correspond pas à « href » : a ((?!href).)* href=(\S*)((?!href).)*/

8) Précisez la longueur

Java contient un optimiseur d'expression rationnelle qui vérifie la longueur de la chaîne d'entrée par rapport aux longueurs minimale et maximale obtenues à partir de l'expression régulière. Cela vous permet d'arrêter immédiatement la recherche dans certains cas. Pour faciliter ce mécanisme, le nombre de répétitions doit être spécifié autant que possible (par exemple, [01]{6} correspond à toutes les chaînes binaires de six caractères).

9) Sélectionnez des lignes identiques

Parfois, des chaînes identiques sont masquées à l'intérieur de groupes ou d'alternatives : (hello|hell|heel) Cette expression peut être simplifiée en : he(llo|ll|el) En faisant cela, nous donnons plus d'informations à l'optimiseur d'expression rationnelle.

10) Testez votre expression rationnelle

Il peut être judicieux de tester d’abord l’expression régulière lorsqu’elle sera utilisée dans une application critique en termes de performances. Écrivez un micro-benchmark qui teste votre expression sur diverses données d'entrée. Assurez-vous de tester sur des données de différentes longueurs, ainsi que sur des données qui correspondent étroitement à votre échantillon.

Liens:

http://java.sun.com/docs/books/tutorial/essential/regex/index.html http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page =1 http://www.softec.st/en/OpenSource/DevelopersCorner/RegularExpressions/RegularExpressionEngines.html http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics -de-traitement-d'expression/