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

Posté par  (site web personnel) . Modéré par Jaimé Ragnagna.
Étiquettes :
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.

Aller plus loin

  • # Dur

    Posté par  . É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  . É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…

        LinuxFr, parfois c'est bien de la MERDE : https://linuxfr.org/users/c2462250/journaux/ecriture-inclusive-feministes-et-wikipedia#comment-1793140

        • [^] # Re: Dur

          Posté par  . Évalué à 1.

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

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

          Posté par  . Évalué à 0.

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

    Posté par  . É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  (site web personnel) . É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.
  • # Démocratisation

    Posté par  (site web personnel) . É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  (site web personnel) . É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  (site web personnel) . É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  (site web personnel) . É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  (site web personnel) . É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  (site web personnel) . Évalué à 7.

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

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

        Posté par  (site web personnel) . É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  (site web personnel) . É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  (site web personnel) . É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  . É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  . É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  (site web personnel) . É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  (site web personnel) . É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  (site web personnel) . É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  (site web personnel) . É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  (site web personnel) . É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  (site web personnel) . É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  (site web personnel) . É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  (site web personnel) . É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  (site web personnel) . É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 à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.