Quelle est la raison pour laquelle il est conseillé d'ordonner les sous-chaînes dans les expressions rationnelles en fonction de leur longueur ?

Question

Le plus long le premier

>>> p = re.compile('supermanutd|supermanu|superman|superm|super')

le plus court le premier

>>> p = re.compile('super|superm|superman|supermanu|supermanutd')

Pourquoi la première expression rationnelle la plus longue est-elle privilégiée ?

Answer 1

Les alternatives dans les regex sont testées dans l'ordre que vous indiquez, donc si la première branche correspond, la regex ne vérifie pas les autres branches. Cela n'a pas d'importance si vous avez seulement besoin de tester la correspondance, mais si vous voulez extraire du texte en fonction de la correspondance, alors cela a de l'importance.

Le tri par longueur n'est nécessaire que lorsque les chaînes les plus courtes sont des sous-chaînes des chaînes les plus longues. Par exemple, lorsque vous avez un texte :

supermanutd
supermanu
superman
superm

puis avec votre premier Rx vous obtiendrez :

>>> regex.findall(string)
[u'supermanutd', u'supermanu', u'superman', u'superm']

mais avec un deuxième Rx :

>>> regex.findall(string)
[u'super', u'super', u'super', u'super', u'super']

Testez vos expressions rationnelles avec http://www.pythonregex.com/

Answer 2

Comme le dit @MBO, les alternatives sont testées dans l'ordre où elles sont écrites, et si l'une d'entre elles correspond, le moteur RE passe à la suivante.
Ce comportement est commun aux moteurs RE de type Perl et remonte à la conception par les Bell Labs, en 1985, de la bibliothèque RE pour l'édition 8 d'Unix.
Notez que POSIX 2 (de 1991) a une autre définition, insistant sur la correspondance la plus longue à gauche pour l'ensemble de l'ER et, sous réserve de cela, pour chaque sous-expression à tour de rôle (dans l'ordre lexical). Dans POSIX 2, l'ordre des alternatives n'a pas d'importance.

Cependant, la différence de comportement est souvent : non pertinente (si vous ne faites que tester), masquée par un retour en arrière (si la correspondance la plus courte fait échouer le reste de l'ER), ou compensée par le reste de l'ER qui correspond à la partie que la correspondance la plus longue "aurait dû" - de sorte que la plupart des gens n'en sont pas conscients.

Answer 3

Je suppose que c'est parce qu'ils sont comparés dans cet ordre et qu'il est plus rapide de comparer des sous-chaînes plus courtes. A titre d'exemple extrême, une correspondance entre une lettre unique et une énorme chaîne sera beaucoup plus efficace si la lettre unique (qui sera probablement à l'origine de la majorité des correspondances de toute façon) est testée en premier.

Mais dans la pratique, il faut mesurer et non deviner. Si vous avez besoin d'une fonction de recherche performante, testez les variations par rapport à des données de test représentatives.

Answer 4

Le conseil auquel vous faites référence dépend du fait que le moteur regex tente de faire correspondre les composants de l'alternance dans un ordre strictement de gauche à droite, comme cela est documenté pour le module Python re.

Le tri des sous-chaînes par ordre décroissant de longueur n'est qu'un cas particulier d'un problème plus large qui se pose lorsque l'on essaie d'extraire une série d'éléments. Le principe général est de placer les sous-exemples les plus spécialisés en premier. Par exemple, vous écrivez l'analyse lexicale d'un analyseur de formules. Vous avez une sous-régex "float constant" et une sous-régex "int constant". Votre première tentative d'analyse de la sous-exemple "float" est susceptible de correspondre également à des constantes "int". Si c'est le cas, vous avez deux choix : (1) écrire une sous-régex float plus compliquée qui ne correspond pas aux constantes int (2) placer votre sous-régex int en premier.