NewsLinuxFr > Google libère le moteur d'expressions rationnelles RE2

accroche

Courant mars Google a libéré le code source d'une librairie d'expressions rationnelles appelée RE2.
RE2 a été faite pour répondre aux besoins de Goggle, elle est optimisée pour la rapidité, a une empreinte mémoire réduite, supporte les threads et propose une alternative aux méthodes utilisées jusqu'à présent.
Cet article revisite brièvement l'histoire des expressions rationnelles, puis le problème posé par les références arrières et enfin l'apport de RE2 par rapport aux implémentations existantes.

liens

http://google-opensource.blogspot.com/2010/03/re2-principled-approach-to-regular.html L'annonce de Google
http://swtch.com/~rsc/regexp/ Les explications de l'auteur
http://code.google.com/p/re2/ Le code source de la librairie RE2
http://stormimon.developpez.com/dotnet/expressions-regulieres/ Un cours sur les expressions régulières
http://blog.chromium.org/2009/02/irregexp-google-chromes-new-regexp.html L'implémentation des expressions rationnelles dans le navigateur Google Chrome (pour le javascript)

corps de la dépêche

Qu'est ce que c'est?

Les expressions rationnelles sont une notation pour décrire un jeu de chaînes de caractères.
Elles se présentent sous la forme d'une suite de caractères, on appelle cette suite un motif.
Ce motif décrit une ou plusieurs chaînes de caractères pour permettre de les trouver dans du texte, de la récupérer et de lui appliquer des traitements tels que les remplacer.

Par exemple:
couleurs? trouvera couleur et couleurs

L'histoire des expressions rationnelles

Leurs prémices remontent aux années 50 avec le mathématicien Cole Kleene. Il créa les modèles réguliers afin de décrire des machines d'état simples.
Michael Rabin et Dana Scott ont ensuite proposé un traitement mathématique de ces modèles dans un article qui leur a valu le Prix Turing.
Le langage SNOBOL a été la première implémentation des modèles rationnelles, mais il ne comprenait pas encore toutes les fonctionnalités des expressions rationnelles.
Ken Thompson a ensuite implémenté la notation de Kleene dans un éditeur de texte appelé QED afin d'utiliser les motifs pour rechercher du texte.
Il a ensuite ajouté ces fonctionnalités dans l'éditeur ed. Depuis ce temps beaucoup de variations de l'adaptation originale de Thompson sont utilisées dans les outils tels qu’awk, Emacs, vi et lex.

Les références arrières

Les références arrière permettent d'ajouter de nombreuses fonctionnalités aux expressions rationnelles.

Par exemple:
(chat|chien)\1 détecte chatchat et chienchien mais pas chatchien ni chienchat.

Cependant la puissance que les références arrière apportent amène aussi un coût très élevé.
Dans le cas le plus défavorable, les implémentations connues telles que celle du langage Perl utilisent des algorithmes de recherche qui ont un coût exponentiel.
Les références arrière sont indispensables, elles ne peuvent être supprimées des langages.
Cependant leurs implémentations peuvent êtres améliorées, c'est ce qu'a fait Russ Cox.

Les optimisations

Afin de réduire leurs coût Russ Cox a revu les algorithmes a partir de ceux créés par Ken Thompson.
Il a entre autres réécrit ceux qui sont implémentés dans le programme grep et a aussi ajouté d’autres algorithmes afin de supporter des fonctionnalités supplémentaires.
Est ainsi née la librairie RE2, qui offre la plupart des fonctionnalités des expressions rationnelles implémentées dans le langage Perl (PCRE).
RE2 est une librairie C++ qui a l'avantage de garantir un temps d'exécution linéaire et non-plus exponentiel, avec une empreinte mémoire limitée.
Cette librairie est très utilisée chez Google, par exemple dans Code Search, ou des certains de leurs outils internes.

---