Discussion :

[Jérémy Lefevre]

Bonjour,
N'etant pas du tout familier avec les regex, je cherche le moyen de savoir si un objet string contient à la fin de la chaine une suite de chiffres de 1 ä 40000 suivi d'un caractere _ et suivi d'un chiffre 0 ou 1.
J'ai regardé au niveau de boost mais je suis un peux perdu quant à l'ecriture de la regex.
quelqu'un peut il me donner un petit coup de main la dessus?

Merci d'avance,

[JolyLoic]

Il y a deux aspects dans ta question :
- À quoi doit ressembler ma regex,
- À quoi va ressembler mon code en C++ qui exécute la regex.

Pour le premier, je ne peux que te conseiller d'aller vers un site comme regex101 qui te permettra de prototyper ta regex par essais/erreurs successifs.
Pour le second, il faudrait préciser un peu ce qu tu comptes en faire. Si tout ce que tu veux c'est savoir si la chaîne correspond, sans rien deander d'autre, regex_match est fait pour toi.

(ps : Plus besoin de passer par boost pour les regex si tu as un compilo pas trop vieux : C'est désormais dans le standard C++)

[Bousk]

Salut,

c'est pas vraiment (du tout) lié au C++ ?
Au feeling, je dirais .*?([1-3]?[0-9]{3}|4000)_[01]$.
Après faut tatoner.

[CosmoKnacki]

C'est jamais très pratique d'avoir à vérifier un rang numérique au sein d'une regex car on se retrouve coincé entre deux alternatives qui ont chacune leurs défauts.

La première consiste à vérifier le format avec une pattern sans tenir compte du rang numérique (ou peu) et de capturer la sous-chaîne de chiffres pour vérifier le rang par une autre voie (en faisant un transtypage de la sous-chaîne en int, puis une comparaison). L'avantage de cette méthode est qu'elle est relativement simple, l'inconvénient est de devoir sortir de la logique regex et d'ajouter une étape supplémentaire (mais ça ne doit quasiment pas impacter les performances). Une pattern de ce type doit faire l'affaire:(?<![0-9])([1-9][0-9]{0,4})_[01]\z (ou pour ECMAScript ou POSIX étendue (^|[^0-9])([1-9][0-9]{0,4})_[01]$, attention au décalage de numéro du groupe de capture).

L'autre méthode consiste à traduire le rang numérique en pattern, chose qui est particulièrement malaisée mais néanmoins possible. Pour rendre cette sous-pattern la plus efficace possible en réduisant au maximum le travail du moteur de regex, l'idée est de veiller à ce que le moteur suive le chemin le plus court possible. Exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
    [1-3][0-9]{0,4} # 30000 + 3000 + 300 + 30 + 3 = 33333
  |
    [5-9][0-9]{0,3} # 5000 + 500 + 50 + 5 = 5555
  |
    4 # 1112
    (?:
        [1-9][0-9]{0,2}
      |
        0
        (?:
            [1-9][0-9]?
          |
            0
            (?:
                [1-9]
              |
                0{0,2}
            )
        )?
    )

Cette sous-pattern bien que longue est conçue de telle manière qu'une fois le moteur engagé dans une branche, on peut être sûr que la correspondance ne peut pas être dans une autre branche. De plus les trois branches principales (nombres commençant par [1-3], [5-9] ou 4) sont classées par ordre de probabilité (il en va de même pour les branches inférieures).
Au final, cette sous-pattern se trouve être plus efficace qu'une expression plus factorisée. Son seul défaut est la présence de nombreux groupes qui peuvent représenter un très léger coût, mais cela ne concerne que les 1112 nombres commençant par 4 (au regard des 38888 autres, ça fait peu).

Donc on aboutit, une fois compactée et complétée, à l'expression suivante utilisable avec regex_search:

• version perl:
  

  Code :

  Sélectionner tout - Visualiser dans une fenêtre à part

  (?<![0-9])(?>[1-3][0-9]{0,4}|[5-9][0-9]{0,3}|4(?:[1-9][0-9]{0,2}|0(?:[1-9][0-9]?|0(?:[1-9]|0{0,2}))?))_[01]\z

• version ECMAScript (utilisable avec la STL):
  

  Code :

  Sélectionner tout - Visualiser dans une fenêtre à part

  (?:^|[^0-9])(?:[1-3][0-9]{0,4}|[5-9][0-9]{0,3}|4(?:[1-9][0-9]{0,2}|0(?:[1-9][0-9]?|0(?:[1-9]|0{0,2}))?))_[01]$

• version POSIX étendue (utilisable avec un moteur de type DFA):
  

  Code :

  Sélectionner tout - Visualiser dans une fenêtre à part

  (^|[^0-9])([1-3][0-9]{0,4}|[5-9][0-9]{0,3}|4([1-9][0-9]{0,2}|0([1-9][0-9]?|0([1-9]|0{0,2}))?))_[01]$

NB: En ce qui concerne la version perl de la pattern, il est possible de bénéficier d'une optimisation supplémentaire en utilisant la technique de discrimination du premier caractère. En effet, tel qu'elle est actuellement, le moteur va devoir tester les trois branches inutilement sur tous les caractères qui ne sont pas des chiffres si ceux-ci ne sont pas précédés d'un chiffre (à cause du lookbehind). Mais, avant même le démarrage de la marche normal du moteur, il est possible de lui faire tester la pattern uniquement sur les chiffres de la chaîne en ajoutant un lookahead au début, c'est à dire (?=[1-9]). Cet ajout permet une "pré-optimisation" qui mettra en œuvre un algorithme de recherche rapide pour déterminer les points de départ possibles de la pattern dans la chaîne. Cette étape de pré-optimisation se devant d'être très rapide, elle ne peut pas être déduite de l'analyse des trois branches, par contre l'ajout du lookahead va le permettre. Le bénéfice de cette technique se fera ressentir d'autant plus si la chaîne est longue et qu'elle contient peu de chiffres.