Google libère la bibliothèque d'expressions rationnelles RE2

Posté par (page perso) . Modéré par Jaimé Ragnagna.
Tags :
35
16
mar.
2010
Internet
Le 11 mars Google a libéré le code source d'une bibliothèque d'expressions rationnelles appelée RE2.
RE2 a été faite pour répondre aux besoins de Google, elle est optimisée pour la rapidité, a une empreinte mémoire réduite, gère 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. 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ères 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ûts, 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 prendre en charge des fonctionnalités supplémentaires.
Est ainsi née la bibliothèque RE2, qui offre la plupart des fonctionnalités des expressions rationnelles implémentées dans le langage Perl (PCRE).
RE2 est une bibliothèque 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. Allez donc voir les comparaisons de performances entre PCRE et RE2 sur cette page.
Cette bibliothèque est très utilisée chez Google, par exemple dans Code Search, ou dans certains de leurs outils internes.
  • # Dur

    Posté par (page perso) . Évalué à 7.

    J'aime pas l'ampleur Google... Mais je l'aime bien quand même... Je crois qu'il faut que j'aille voir un psy.
    • [^] # Re: Dur

      Posté par (page perso) . Évalué à 4.

      > Milite pour un about:black sur les navigateurs ! ( シ Sauvons la
      > planète ツ )

      Si je ne m'abuse c'est (très très) légèrement plus coûteux en électricité de produire du noir (il faut filtrer la backlight) que du blanc (où on laisse plus ou moins passer toute la lumière) sur les LCD (contrairement aux CRT)... donc je suis pas sûr qu'un about:black sauve la planète... par contre ça la sauvera sûrement quand tout le monde aura un écran à LED !
      • [^] # Re: Dur

        Posté par . Évalué à 1.

        Et puis, pourquoi un Shi et un Tsu ? Je ne parles pas japonais, et je n'ai absolument aucune idée de ce que ça pourrait bien vouloir dire…
        • [^] # Re: Dur

          Posté par . Évalué à 1.

          シツ ça veut pas dire "trône des WC" en japonais ?

          --> []
        • [^] # Re: Dur

          Posté par (page perso) . Évalué à 0.

          Je pense que ça se traduit par :-) et (-:
  • # comparatif graphique

    Posté par (page perso) . Évalué à 6.

    le petit graphique en haut de cette page est très parlant
    http://swtch.com/~rsc/regexp/regexp1.html

    les trolleurs fous sont priés de noter que l'échelle de temps du second graphique est graduée en microsecondes

    "La liberté est à l'homme ce que les ailes sont à l'oiseau" Jean-Pierre Rosnay

    • [^] # Re: comparatif graphique

      Posté par . Évalué à 8.

      Et les trolleurs ils doivent aussi noter que tu pointes vers un papier de recherche qui date de 2007 alors que l'article décrivant l'implémentation de RE2, datant de 2010, est là : http://swtch.com/~rsc/regexp/regexp3.html ?

      Cela dit ça reste flatteur pour RE2 avec juste comme bémol que l'algo de RE2 a un temps de setup un peu long par rapport à PCRE qui n'est amorti que pour des tailles de texte supérieure à 64 octets.
    • [^] # Re: comparatif graphique

      Posté par (page perso) . Évalué à 8.

      Le graphique est parlant, mais il prend un cas pathologique qui ne correspond pas à une regexp qui ait du sens. C'est rare de faire des recherches sur a?a?a?a?a?a?a?a?a.

      Je m'étais un peu interessé à cette histoire de regexp via DFA qui serait plus rapide que les implementations usuelles à base de NFA après avoir lu la page de russ cox il y a quelques temps, j'avais même fait l'effort d'en implementer un pour finalement constater que ça allait notablement moins vite que pcre sur les classes de regexp "utiles". Au final on perd beaucoup de souplesse (bye bye les backreferences, et les {n} coutent chers puisqu'il faut ajouter n etats dans l'automate) pour gagner la garantie que le temps de calcul n'explosera pas exponentiellement dans des cas merdiques.
      • [^] # Re: comparatif graphique

        Posté par (page perso) . Évalué à 6.

        Ton post est un peu confu du fait que tu utilises NFA à la place du terme NFA avec backtracking.

        Il faut différencier la construction d'un automate fini (FA : DFA/NFA) et l'exécution de celui-ci pour être correct. Tous les algos, que je connaisse, construisent un automate fini.

        Un automate fini non-déterministe se construit facilement en un temps linéaire en la taille de l'expression. Un automate fini déterministe quant à lui se construit en un temps qui peut-être exponentiel (car le nombre d'état peut exploser car il s'agit +/- de construire des ensembles d'état du NFA).

        Au niveau de l'exécution d'un automate fini déterministe, le temps d'exécution est linéraire en la taille du texte à matcher.

        Dans le cas d'un automate non-déterministe (sans références arrières et autres joyeusetés), c'est proportionnel au produit la taille de l'expression et de la taille du texte à matcher. Cela consiste +/- à construire le DFA à la volée à l'exécution.

        Dans le cas non-déterministe avec excutation avec backtracking, qui n'est nécessaire réellement que quand on sort des langages réguliers (référence arrières, ...), on passe en exponentiel.

        Pour résumer,
        - DFA est le plus rapide en exécution : nul doute. DFA a coût important à la création. Ce qui probablement est la cause des lenteurs de ton test. Mais c'est surement la plus efficace si tu ré-utilises beaucoup de fois la DFA sur des textes différents avec une seule compilation
        - NFA sans backtracking est probablement le plus rapide en pratique (en moyenne).
        - NFA avec backtracking est dans la majorité des cas comme NFA sans backtracking mais à des cas limites (et des effets de bord qui font que aa* est plus rapide que a+, par exemple) qui peuvent être ennuyeux. C'est surtout la méthode la plus expressive au niveau langage.
  • # Démocratisation

    Posté par (page perso) . Évalué à 3.

    Bonne dépêche. Je rajouterais cependant que les expressions rationnelles ont été surtout démocratisé par le langage Perl qui l'a mis au coeur du langage dès ses débuts.

    De plus, la communauté Perl est toujours très active sur ce thème avec Perl6 dont la grammaire est écrite en expression rationnelle mais aussi via le mouvement "Modern Perl" ont l'ont peut (doit) utiliser le modificateur 'x' qui permet de mettre des espaces, des retours chariots et même des commentaires dans ses regex ! Cela permet d'avoir des expressions plus facilement compréhensible et donc au final moins de bogue et un code plus maintenable.
    • [^] # Re: Démocratisation

      Posté par (page perso) . Évalué à 10.

      Oui et non, si on regarde un peu l'historique des logiciels, les uns s'inspirant des autres on a ed>sed>awk>perl. Alors oui, les expressions régulières sont au cœur de perl, mais cela découle de son historique aux origines qui fleur bon l'Unix.
      • [^] # Re: Démocratisation

        Posté par (page perso) . Évalué à 4.

        Apparemment du meme auteur, je trouve cette page plus interessante:

        http://swtch.com/~rsc/regexp/regexp1.html

        On y voit grep et awk poutrer Perl, Python, Ruby et PCRE:

        http://pdos.csail.mit.edu/~rsc/regexp-img/grep1p.png

        Ca force le respect envers les "bons vieux outils a papa"...
        • [^] # Re: Démocratisation

          Posté par . Évalué à 3.

          Un bon vieil opinel coupe mieux le bois qu'un couteau suisse. Indeed.
          De la différence entre les petits outils dédiés et les gros outils qui font tout.

          J'entends par là que je ne suis pas moultement surpris que grep poutre des langages de programmation. Celui qui m'impressionne le plus (sur ce graphique), c'est awk...
      • [^] # Re: Démocratisation

        Posté par (page perso) . Évalué à 1.

        Attention, ne me faites pas dire ce que je n'ai pas dis ! Je n'ai pas dis que Perl avait inventé les regex ! Je sais bien que cela vient en gros de ed et que cela a été repris dans awk, puis dans Perl.

        Je parle de démocratisation à grande échelle. Ce n'est pas avec ed ni avec awk que les regex se sont démocratisées. D'ailleurs, la plupart des monolignes awk se résument à récupérer la colonne X..., chose qu'il fait très bien.

        Sinon, j'évoque l'avenir des regex et je vois que du coté de Perl, les évolutions proposées en 15 ans sont énormes. J'ai l'impression que les autres langages suivent. C'est peut être juste une impression.
        • [^] # Re: Démocratisation

          Posté par . Évalué à 9.

          Ben non, il y a plein de gens qui utilisent tous les jours des regexp dans sed/awk/vi/grep/php et qui ne veulent surtout pas s'approcher de perl. Je ne vois pas en quoi perl démocratise les regexp de ce point de vue, ni pourquoi ces langages "suivraient" perl.

          Le principal défaut des mongueurs est qu'ils sont persuadés que perl est à la fois l'apogée des langages, et la source ultime de tout progrès. Je n'y vois qu'un exemple de ce qu'il ne faut pas faire en programmation : le code write-only.
    • [^] # Re: Démocratisation

      Posté par . Évalué à -1.

      le modificateur 'x' qui permet de mettre des espaces, des retours chariots et même des commentaires dans ses regex !

      Woah révolutionnaire !
      http://docs.python.org/library/re.html#re.VERBOSE
      • [^] # Re: Démocratisation

        Posté par . Évalué à 1.

        Je ne comprends pas bien cette remarque avec une comparaison avec le langage Python ? Tu sembles suggérer que cette fonctionnalité a implémenté dans Python depuis longtemps.

        Le modificateur 'x' existe depuis que je connais Perl (au moins 10 ans) et de ce que j'ai pu lire, ce serait plutôt Python qui se serait calqué sur le modèle Perl des regex et non l'inverse.

        The re module was added in Python 1.5, and provides Perl-style regular expression patterns. Earlier versions of Python came with the regex module, which provided Emacs-style patterns. The regex module was removed completely in Python 2.5.
        Source : http://docs.python.org/dev/howto/regex.html
      • [^] # Re: Démocratisation

        Posté par . Évalué à 6.

        Forcément tu vas retrouver les mêmes features dans tous les langages qui utilisent la lib PCRE ;-) (PCRE = Perl Compatible Regular Expression).
        • [^] # Re: Démocratisation

          Posté par . Évalué à 2.

          au temps pour moi, c'était présenté comme une fonctionnalité révolutionnaire de Perl 6.
          • [^] # Re: Démocratisation

            Posté par (page perso) . Évalué à 2.

            Pas du tout. J'ai juste écrit que la grammaire Perl6 était écrite sous forme d'expression rationnelle. Ensuite, je parle de "Modern Perl" qui est plutôt un mouvement qui cherche à profiter des avancées sur Perl6 pour en intégrer dans Perl5 et qui de ce fait écrit du code Perl5 d'une autre manière...

            Je ne parle donc pas de révolution mais d'évolution ;-)
    • [^] # Re: Démocratisation

      Posté par (page perso) . Évalué à 7.

      et un code plus maintenable.
      Heu...on parle bien de Perl là ?

      Ok --->[]
      • [^] # Re: Démocratisation

        Posté par (page perso) . Évalué à 3.

        J'ai jamais réussi à bidouiller correctement un serveur de mail sauf justement qpsmtpd car le code est lisible et même moi, j'ai réussit à modifier des greffons et à écrire les miens ;-)

        De même, Email::Filter est un bonheur pour bidouiller les mails via le .forward. Au moins, tes filtres sont clairs et les possibilités proche du CPAN !

        C'est juste deux exemples de petits trucs que j'ai du toucher ces derniers temps.
      • [^] # Re: Démocratisation

        Posté par . Évalué à 3.

        Comment faire pour générer une chaîne de caractères aléatoires ? On utilise le code d'un programme écrit en Perl !

        Je sors aussi
  • # Corrections

    Posté par (page perso) . Évalué à 2.

    Dans « Qu'est-ce que c'est » :
    - « un jeu de chaînes » : « un ensemble de chaînes »
    - « de les trouver..., de LES récupérer, de LEUR appliquer... »

    Dans « L'histoire des expressions rationnelles » :
    - « machines d'états » : ajouter « automates » ?
    - « modèles rationnelles » : « modèles rationnels »

    Dans « Les optimisations » :
    - « Les références arrière sont indispensables, elles ne peuvent être supprimées des langages » : à mon avis, il faudrait préciser, parce qu'on peut très bien les supprimer d'un langage d'expressions rationnelles. Cela diminue son pouvoir d'expressivité, c'est tout.
    • [^] # Re: Corrections

      Posté par . Évalué à 5.

      Merci pour l'article, il manquait juste un extrait de wikipedia je trouve :

      De l'anglais regular expression dont l’abrégé est regexp, regex ou encore expreg. On emploie couramment le terme expression régulière car le terme anglais est regular expression qui s'abrège en regexp. Mais ne nous y trompons pas, en français, ce sont bien des expressions rationnelles.
      • [^] # Re: Corrections

        Posté par . Évalué à 1.

        C'est la deuxième fois que je vois cette remarque aujourd'hui, mais je n'en n'ai pas vu l'explication. Une expression "régulière" suivrait une ou des règles, ce qui me semble être le cas. "rationnel", ça semble sous-entendre que l'expression est douée de raison et si je vais un peu plus loin, qu'elle réfléchit. Alors que les expressions régulières ne font qu'appliquer les règles données.

        Alors d'où vient l'utilisation de "rationnelle"? Est-ce que c'est simplement l'usage qui veut ça, ou y a-t-il de vraies "raisons"?
        • [^] # Re: Corrections

          Posté par (page perso) . Évalué à 3.

          "rationnel", ça semble sous-entendre que l'expression est douée de raiso
          Non pas du tout ! Rationnel ne veut pas seulement dire doué de raison (au sens intelligence). Par exemple on parle de nombres rationnels (les fractions), on parle aussi de la raison d'une suite géométrique. On retrouve ce sens dans le mot «ratio» (proportion entre deux valeurs de même nature). C'est un terme "courant" en math. Après le rapport exacte avec les expressions rationnelles, je ne sais pas trop. Mais ce n'est pas choquant à utiliser.
          si je vais un peu plus loin, qu'elle réfléchit.
          Euh non, là tu confond avec un miroir...
          ----> []
          • [^] # Re: Corrections

            Posté par . Évalué à 2.

            J'intègre bien le fait que rationnel a plusieurs sens. J'ai utilisé "ça semble sous-entendre" car justement, j'ai l'impression que l'emploi dans "expression rationnelle" pourrait être plus proche de "raisonnement" que d'un ratio.

            Cette impression est peut-être fausse, je cherche simplement à comprendre.
        • [^] # Re: Corrections

          Posté par (page perso) . Évalué à 3.

          Parce que ce n'est pas une question de « règles », mais parce que ces expressions peuvent décrire un langage rationnel, tout comme peut le faire un automate fini déterministe. Il existe d'autres langages qui utilisent également des règles mais ne sont pas pour autant des langages rationnels.
          • [^] # Re: Corrections

            Posté par . Évalué à 3.

            Justement, j'avais vu ça sous le nom de "langages réguliers" (différents des langages algébriques représentés par un automate à pile si ma mémoire est bonne).

            Ce serait bien de comprendre exactement ce qu'entend le sens "rationnel".
            • [^] # Re: Corrections

              Posté par (page perso) . Évalué à 3.

              Je pense qu'il faut comprendre rationnel ici comme mécanique, reposant sur une méthode déductive. En effet, les règles de productions sont linéaires gauche ou droite (mais on ne mélange pas). Les mots du langages ne se construisent que dans un seul sens, comme dans une déduction logique.
        • [^] # Re: Corrections

          Posté par . Évalué à 1.

          Attention, je vais peut-être raconter des conneries ou tout du moins être dangereusement imprécis.

          Le "rationnel" vient des fractions rationnelles.

          En gros, si tu prends une fraction rationnelle que tu développes, tu obtiens un mot infini qui se reconnait très facilement avec un automate fini. Par exemple, 123/13=9.(461538)*.

          Pour les fractions d'entier, ça reste quand même très simple mais si on considère des trucs plus évolué à base de fraction polynomiales, on obtient des mots qui correspondent bien aux automates finis.
      • [^] # Re: Corrections

        Posté par (page perso) . Évalué à 1.

        Dans le cours d'informatique que j'avais eu, il y avait une distinction entre un langage rationnel et un langage régulier: l'un était défini par les règles:

        - le langage vide
        - des langages de mots d'une lettre.
        - des combinaisons de langages par union (\| en regexp).
        - des combinaisons de langages par concaténation (juxtaposition en regexp).
        - des répétitions d'un langage (* en regexp)

        et l'autre par le fait qu'il est reconnu par un automate fini. Je ne me souviens plus du tout lequel était nommé comment :)
        • [^] # Re: Corrections

          Posté par (page perso) . Évalué à 3.

          Si mes souvenir sont bons, on parle d'expression régulière (définit par des règles algébriques) et de langage rationnel (définit par un automate).
          Par exemple l'expression régulière "(a|b)?c" représente le langage rationnel {c,ac,bc}
    • [^] # Re: Corrections

      Posté par (page perso) . Évalué à 1.

      Merci pour les corrections.
      Pour les références arrières, ce que je voulais dire c'est qu'on ne peut pas les enlever d'un langage comme Perl, car comme tu le dis cela diminue leur expressivité mais aussi car on n'enlève pas une fonctionnalitée d'un langage comme cela simplement parce qu'elle est gourmande.
  • # RE2 et références arrières.

    Posté par (page perso) . Évalué à 6.

    Les références arrière sont indispensables, elles ne peuvent être supprimées des langages.

    Sauf que justement, RE2 les supprime! C'est comme ça qu'ils obtiennent le gain de vitesse...
    • [^] # Re: RE2 et références arrières.

      Posté par . Évalué à 2.

      En effet, d'après le site du projet [3] :

      The one significant exception is that RE2 drops support for backreferences and generalized zero-width assertions, because they cannot be implemented efficiently
      • [^] # Re: RE2 et références arrières.

        Posté par (page perso) . Évalué à 1.

        L'aspect important est le travail d'optimisation qui a été fait sur les algorithmes par l'auteur.
        RE2 n'implémente en effet pas toutes les expressions disponibles dans Perl:
        http://code.google.com/p/re2/wiki/Syntax
      • [^] # Re: RE2 et références arrières.

        Posté par (page perso) . Évalué à 2.

        Lorsqu'en Perl, on met

        m/toto.*?titi/

        je crois me souvenir qu'il ne fait pas de référence arrière du fait du ? après l'étoile. Il y a aussi la variante avec le + à la place du ? mais je ne l'ai jamais utilisé.
        • [^] # Re: RE2 et références arrières.

          Posté par . Évalué à 5.

          le ? après l'étoile ne sert pas plutôt pour éviter la "gloutonnerie" de l'* ?

          par exemple, si l'on veut matcher des balises façon XML

          <a>blabla</a>
          <a>blibli</a>

          si l'on fait m:<a>.*</a>: on va matcher blabla</a><a>blibli
          si l'on fait m:<a>.*?</a>: on va matcher blabla, puis blibli
        • [^] # Re: RE2 et références arrières.

          Posté par . Évalué à 1.

          La variante avec le +, c’est pour empêcher le moteur d’enregistrer des états pour le backtracking ; en gros, c’est "ce que je prend, je le rend jamais" (d’où le nom: opérateur possessif)

          Si tu veux en savoir plus, je te conseille ça: http://oreilly.com/catalog/9781565922570

          En gros, a++a ne fonctionnera jamais, au contraire de a+a. Cas d’utilisation typique: matcher une string C/C++: un machin entre guillemets doubles pouvant contenir des guillemets doubles échappés et des caractères d’échappement échappés (de tête):

          "(\.|[^"\])++"

          Sans le ++, cette expression reconnaît très bien : "hello\" alors qu’on ne le veut pas
  • # Bon, résultat ?

    Posté par (page perso) . Évalué à 1.

    Est-ce que perl, python, etc... vont finir par utiliser RE2 ou non ?

    Utilisant perl en tant qu'administrateur système, mis à part les backreference style "\1", il n'y a rien qui me manquerait dans RE2 (et encore, je les utilises rarement) quand je regarde les expressions grisées ici : http://code.google.com/p/re2/wiki/Syntax

    Question subsidiaire : il y a-t-il une différence entre "expressions rationnelles" et "expressions régulières" ?
    • [^] # License = frein ?

      Posté par (page perso) . Évalué à 1.

      Ah, mais en fait, la license n'est pas vraiment GPL. C'est plus du "faîtes ce que vous voulez avec ce morceau de code" : http://code.google.com/p/re2/source/browse/LICENSE
    • [^] # Re: Bon, résultat ?

      Posté par (page perso) . Évalué à 2.

      Question subsidiaire : il y a-t-il une différence entre expressions rationnelles et expressions régulières ?

      Oui, « expression régulière » est une traduction pas très heureuse de l'anglais « regular expression ». C'est plus correct en français d'utiliser « expression rationnelle ». Mais à part cela, c'est la même chose.
    • [^] # Re: Bon, résultat ?

      Posté par . Évalué à 2.

      J'ai cru voir qu'il y avait déjà un module en développement pour PHP, je suppose qu'il y en aura aussi pour d'autres langages (il suffit que quelqu'un s'y mette).

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.