Optimisation des expressions régulières

Ecrire les RegEx plus efficacement

Ce site ne sera plus alimenté de contenu après août 2014. Tous les nouveaux articles seront redigés pour www.waitingforcode.com

Les expressions régulières sont un outil très puissant dans le développement. Sans elles, il serait quasiment impossible d'analyser un document ou de vérifier la cohérence de certains modèles des mots comme URLs. Cependant, elles ne sont pas sans failles et doivent être utilisées correctement pour apporter un réel gain à l'application.

A travers cet article on verra le fonctionnement des expressions régulières. Tout d'abord on se concentrera à le décrire. On abordera alors la notion de backtracking. Dans la seconde partie on se concentrera sur les éléments qui permettent de mieux optimiser les expressions régulières.

Problème du RegEx : backtracking

Le package java.util.regex a été rajoutée dans la version 1.4 du Java. C'est lui qui facilite toute la gestion des expressions régulières. Elles sont gérées selon l'approche appelée Non-deterministic Finite Automation (NFA). Son principe de base consiste à analyser chaque caractère dès le début à la fin d'une chaîne de caractères et à en extraire les fragments correspondant au modèle de l'expression régulière.

La spécificité de l'approche NFA s'appelle backtracking. Grâce à cette fonctionnalité, l'expression régulière (RegEx) est capable de revenir au début de la chaîne analysée pour la vérifier contre un deuxième modèle (par exemple dans le cas où l'on utilise l'opérateur "ou" - "|"). Regardons comment ça fonctionne sur l'exemple de cette expression "(b(\\w+)s|b(\\w+)t)\\s+", qu'on appliquera sur cette phrase "boooooooooooooooooooooooooooooooooooooooaseeeeeeee ".

Voici le schéma de fonctionnement :

  1. La JVM choisit la première partie de RegEx qui sélectionne tout mot commençant par b, contenant des lettres et se terminant par s avec un espace.
  2. L'analyse commence avec "b". Elle enchaîne ensuite toutes les lettres jusqu'à invalider le mot (avec dernier "e") car il ne se termine pas par s.
  3. On vérifie ensuite la deuxième expression qui admet tout mot commençant par b, contenant des lettres et se terminant par t avec un espace. Cette deuxième vérification commence là où la précédente, c'est-à-dire au début du mot.
  4. L'analyse a lieu selon le même schéma que pour la première partie d'expression. L'analyse échouera exactement au même endroit.

Pour constater la malfaisance du backtracking, on se basera sur un autre exemple, le texte "Lorem ipsum..." collé plusieurs fois. Entre les phrases on a rajouté des mots qui correspondront presque à notre RegEx. Ces mots-là commencent avec la lettre recherchée, contiennent ensuite plein d'autres lettres, mais ne se terminent pas comme le veut le RegEx. Le RegEx se présente d'ailleurs de cette manière : "(\\sb(\\w+)s\\s|\\sc(\\w+)s\\s)" (tout mot débutant par espace+b ou espace+c, contenant plusieurs mot à l'intérieur, et se terminant par s+espace). Le code de test se présence ainsi :

import org.apache.commons.io.FileUtils;

public class RegexTest{
	private static Pattern p=Pattern.compile("(\\sb(\\w+)s\\s|\\sc(\\w+)s\\s)");

	public static void main(final String[] args){
		String txt = "";
		String fileName = "test.txt";
		try{
			for(int i=0; i<30; i++){
				txt+=FileUtils.readFileToString(new File("/home/bartosz/regex/"+fileName));
			}
			long start=System.nanoTime();
			Matcher m=p.matcher(txt);
			while(m.find()){
				System.out.println("Found group : "+m.group(1));
			}
			long end=System.nanoTime();
			System.out.println("Execution\'s time is : "+(end-start)/1000000000.0+" seconds");
		}
		catch(IOException e){
			e.printStackTrace();
		}
	}
}

Le temps d'exécution pour la recherche sur le texte avec les mots presque correspondant au modèle est en moyenne 3.2 secondes. Ceci, entre autres, à cause des allers-retours que l'application doit faire sur des mots très longs. Maintenant lançons le même code, mais avec des mots raccourcis. A place d'avoir 60 lettres à l'intérieur des mots presque correspondants, on en aura moins que 10. L'exécution du RegEx sur ce texte est presque trois fois plus rapide (1.2 secondes en moyenne). Ce test prouve bien le plus grand danger des expressions régulières : les mots presque correspondant au modèle mélangés avec backtracking. Si vous souhaitez effectuer ce petit benchmark de votre côté, voici les 2 fichiers utilisés : dans un zip compressé.

Optimiser RegEx

Comme on a pu voir dans le paragraphe précédent, les lenteurs dans l'exécution des expressions régulières ont lieu quand le modèle est admet beaucoup de possibilités (toutes les lettres entre deux autres lettres) et quand le texte contient des mots presque correspondant. La première chose à faire est donc de restreindre les possibilités du modèle. C'est vrai que dans notre besoin (tous les mots entre deux lettres) cela peut être difficile, mais on peut l'appliquer par exemple aux modèles dont les contraintes sont pré-définies, comme les adresses URLs, les noms des fichiers ou les adresses des rues.

Une seconde optimisation peut être l'utilisation des possessive quantifiers (quantificateurs possessifs) qui permettent d'éliminer le backtracking. La spécificité de ces quantificateurs repose dans le fait qu'ils essaient de faire correspondre le modèle à une chaîne de caractères exactement une seule fois. Si le matching échoue, l'analyse de la chaîne va être continuée sans retourner au point de l'analyse précédente (celle qui a echoué).

Une troisième piste à explorer sont des reluctant quantifiers (quantificateurs réticents). Les quantificateurs normaux, appelés greedy, tentent de faire correspondre fragment le plus long. Ensuite, en cas d'échec, ils retourner au début de la phrase analysée. Dans le cas des quantificateurs réticents, la correspondance se base sur le fragment le plus court. Une fois ce fragment trouvé, l'analyse continue vers avant. Ces quantificateurs sont utiles si l'on sait que les correspondances doivent être courtes.

Il faut également faire attention au format des expressions et l'optimiser au maximum. Par exemple l'expression "(white|whitest|whity)" pourrait être optimisée de cette manière : "whit(e|est|y)". L'application irait alors chercher une chaîne de caractères qui commence par whit et qui contient par la suite e, est ou y. Dans le cas de cette expression non-optimisée, le système ira voir chaque mot correspondant à un des trois modèles, à chaque fois recommençant dès le début (backtracking).

Une pratique d'optimisation est également la pré-compilation des modèles. Quand on sait qu'un RegEx sera utilisé plusieurs fois, on peut le traiter comme l'attribut statique d'une classe, pour qu'il soit initialisé une fois pour toutes. Ou alors, si l'on a besoin de l'appliquer dans une méthode sur plusieurs textes, on peut le préparer avant le début de notre boucle for.

Grâce à ces multiples exemples, on a vu que les expressions régulières sont un élément très puissant qui permet d'extraire tout et n'importe quoi d'un document. Cependant ce caractère universel a également ses défauts, illustrés majoritairement par le backtracking. Même si l'on a vu des moyens de le réduire avec les quantificateurs et des expressions très détaillées, il faut garder cette caractéristique du RegEx en tête.

Bartosz KONIECZNY Expressions régulières

Une question ? Une remarque ?

*

*

Moi

Développeur d'applications Internet et journaliste passionné par l'adjectif français. Un aigle polonais orienté vers la progression, volant très haut et écoutant du zouk après les matches du foot français.

Vous appréciez mon travail ?

Pour contribuer au développement de ce site, ou pour remercier pour des articles rédigés, vous pouvez faire un don.

Un conseil Symfony2

Comment récupérer le SecurityContext dans la vue ?

Dans Symfony2 on peut récupérer le SecurityContext directement dans les templates de vue.

Pour ce faire, utilisez la ligne suivante (s'applique seulement pour les templates PHP) :

$viewUser = $view->container->get('security.context')->getToken();