Discussion :

[eyquem]

Je ne comprends strictement rien à des résultats de recherche de motif par regex.

Ceci, ça va, je comprends les 2 listes résultat du findall():

Code :

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

1
2
3
4
import re
ch = 'jeanBjacquesBrousseauBecrivain'
print re.findall('[a-z]B',ch)
print re.findall('[a-z]+B',ch)

['nB', 'sB', 'uB']
['jeanB', 'jacquesB', 'rousseauB']

Ensuite, j'ai pensé obtenir ['jeanB','jeanBjacquesB','jeanBjacquesBrousseauB','jacquesB',''jacquesBrousseauB','rousseauB']
avec ceci:

Code :

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

print re.findall('([a-z]+B)+',ch)

mais le résultat est

['rousseauB']

Enfin avec

Code :

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

print re.findall('(([a-z]+B)+)',ch)

le résultat me plonge dans la perplexité:

[('jeanBjacquesBrousseauB', 'rousseauB')]

Quelqu'un peut-il expliquer les deux derniers résultats ?
Merci

[dividee]

Je suis pas expert en RE mais je pense comprendre ce qui se passe.

Cela vient du fait que findall renvoie une liste de groupes si le pattern contient des groupes (cf la doc de la fonction findall).
Par exemple:

Code :

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

1
2
>>> re.findall('([a-z]+B)rou',ch)
['jacquesB']

Le résultat n'est pas un match de la RE complète, seulement du groupe.

Dans le premier cas tu as un groupe, mais avec un + derrière, ce qui fait que le groupe est à chaque fois écrasé par le match suivant, et il ne renvoie que le dernier match à l'intérieur du groupe.

Dans le second cas tu as deux groupes, l'un dans l'autre, ce qui fait qu'il te renvoie une liste de tuples. Le premier groupe est l'expression complète et le second le même que précédemment, d'où le résultat.
Si on utilise des parenthèses "non-groupantes":

Code :

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

1
2
3
4
>>> re.findall('(?:[a-z]+B)+',ch)
['jeanBjacquesBrousseauB']
>>> re.findall('(?:(?:[a-z]+B)+)',ch)
['jeanBjacquesBrousseauB']

Le résultat que tu pensais obtenir, tu ne l'auras jamais avec findall, car il ne retourne que des match qui ne se superposent pas (sauf, comme on vient de le voir, s'il y a des groupes imbriqués, mais tu n'arriveras pas a obtenir le résultat que tu pensais ainsi).

[eyquem]

Merci pour ta rapide réponse, dividee.
C'est bien ce que tu dis. Il aurait suffi que je lise attentivement le descriptif de findall().
J'ai énormément de mal avec group() et groups(). C'est ce qui doit faire que j'ai inconsciemment éloigné de ma mémoire que «If one or more groups are present in the pattern, return a list of groups;» pour findall().
Je vais creuser findall() pour essayer de comprendre à quoi ça sert véritablement. Je me demande si finditer() n'est plus généralement utile.

[dividee]

finditer n'est pas fondamentalement différent de findall, si ce n'est qu'il retourne un itérateur ce qui permet d'arrêter la recherche avant la fin, et des MatchObjects au lieu de strings.

je ne pense pas qu'il y ait moyen de trouver un résultat comme ['jeanB','jeanBjacquesB','jeanBjacquesBrousseauB','jacquesB',''jacquesBrousseauB','rousseauB'] avec l'une des fonctions de base des regexps car (à ma connaissance) dès qu'une regexp a matché qqch, elle s'y tient; il n'y a pas de backtracking.

[shadowsam]

Comme le disait dividee il n'y a apparemment aucun moyen de faire un match qui ne consomme pas la chaine de caractère qui vient d'être trouvée.
Mais tu peux ruser et faire un truc comme suit:

Code regexp :

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
import re
ch = 'jeanBjacquesBrousseauBecrivain'
 
compiled_re = {}
res = []
for i in xrange(1, len(ch)/2):
    try:
        reg_exp = compiled_re[i]
    except KeyError:
        reg_exp = compiled_re[i] = re.compile('((?:[a-z]+B){%d})' %i)
 
    res += re.findall(reg_exp,ch)
 
print res
 
>> ['jeanB', 'jacquesB', 'rousseauB', 'jeanBjacquesB', 'jeanBjacquesBrousseauB']

Pour l'explication, je précise dans l'expression régulière combien de fois le pattern "[a-z]+B" doit apparaitre. Donc de 1 a 3 fois dans mon exemple.
Le pattern '(?:' sert à ce que les parenthèses ne fassent pas de groupes mais juste définisse sur quelle portion de l'expression va s'appliquer le '{n}'. C'est un peut difficile a expliquer mais la doc est plus compréhensible que moi sur ce point

Voila pour une façon de faire. Maintenant il faut optimiser un peu les choses parce que si tu appliques cette méthode sur des centaines de string, cela risque de vite être gourmand en CPU.

Edit: J'ai modifié un peu le code pour le rendre moins 'gourmand'. Enfin après ca va dépendre de l'utilisation que tu en fais.

[eyquem]

En fait, mon problème n'était pas de trouver un algorithme pour obtenir ['jeanB','jeanBjacquesB','jeanBjacquesBrousseauB','jacquesB',''jacquesBrousseauB','rousseauB'] à partir de ch = 'jeanBjacquesBrousseauBecrivain' , comme mon premier message le donne à croire.

Mon problème était de comprendre comment fonctionne findall() , parce que je pensais que cette fonction pouvait être utilisée pour la résolution d'un problème posé par lagdu, à savoir ce qu'il appelle «un contrôle syntaxique via les expressions régulières sur une variable de n lignes.
» :
http://www.developpez.net/forums/d68...iere-n-lignes/

J'ai voulu d'abord étudier le fonctionnement de findall() sur une chaine ch = 'jeanBjacquesBrousseauBecrivain' avant de passer à son utilisation sur une chaine du genre ch = 'jean\njacques\nrousseau\necrivain'.
Et c'est ainsi que je me suis aperçu que je ne comprenais rien à findall().

J'ai maintenant compris comment fonctionne findall() et je me suis remis en mémoire des choses que j'avais vues et oubliées sur les groupes.
Je trouve que les histoires qui concernent les groupes dans les regex sont extrêmement difficiles à maitriser. Pas à comprendre, à maitriser.
Il me semble que finditer() est sans doute plus souvent, et très, utile que findall(). En fait findall() renvoit tantôt ce que renvoit group() (quand il n'y a pas de groupe défini dans la regex employée), tantôt une liste de groupes (quand chaque match n'a lieu qu'à cause d'un seul groupe), tantôt une liste de tuples de groupes (quand plusieurs groupes sont concernés par un match). C'est plutôt à mon avis une fonction pour analyser les résultats de matchings. Tandis que finditer() est peut être plus utile pour obtenir des résultats facilement utilisables.
La compréhension de findall() est compliquée par le fait que findall() ne renvoit pas tous les groupes d'un match quand ce match a lieu sur une RE du genre (tatati)+ mais seulement le dernier tatati ayant matché.
D'ailleurs, dividee, si tu lis ceci, je pense que dans ce qui suit, tu commets une erreur d'énonciation:
« Dans le premier cas tu as un groupe, mais avec un + derrière, ce qui fait que le groupe est à chaque fois écrasé par le match suivant, et il ne renvoie que le dernier match à l'intérieur du groupe.»
Je pense que c'est en fait
« avec un + derrière, le groupe est à chaque fois écrasé par le groupe suivant, et il ne renvoie que le dernier groupe à l'intérieur du match.»
en prenant pour signification de match: "le match total, regroupant le plus grand nombre de groupes". Ce qui peut occasionner le malentendu si tu n'entends pas match de la meme facon.
Mais l'idée est bien la bonne. Je crois.


Ceci dit, maintenant que le problème est posé, il m'intéresse, même si je n'ai pas réellement besoin de le résoudre.
J'ai regardé ton code, shadowsam.
L'indice i varie de 1 à 14.
Pour i==1:
reg_exp = re.compile('(?:[a-z]+B)')
re.findall(reg_exp,ch) détecte tous les matchs à un seul motif de base: 'jeanB', 'jacquesB', 'rousseauB'

Pour i==2:
reg_exp = re.compile('(?:[a-z]+B)(?:[a-z]+B)')
re.findall(reg_exp,ch) détecte tous les matchs à 2 motifs de base:'jeanBjacquesB'
Il ne détecte pas 'jacquesBrousseauB' parce que 'jacquesB' a déjà été consommé.

Pour i==3:
reg_exp = re.compile('(?:[a-z]+B)(?:[a-z]+B)(?:[a-z]+B)')
re.findall(reg_exp,ch) détecte 'jeanBjacquesBrousseauB'
Pour i==4:
reg_exp = re.compile('(?:[a-z]+B){4}') ne permettra rien de détecter puisqu'il n'y a pas plus de 3 B

Je ne comprends pas pourquoi tu fais varier i de 1 à len(ch)/2. Les tours de boucles avec i>3 sont inutiles. Et pourquoi /2 ?
C'est mieux de faire
for i in xrange(1,ch.count('B')):

D'autre part , comme i s'incrémente de 1 à chaque tour,

Code :

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

1
2
try:
     reg_exp = compiled_re[i]

donne toujours une erreur: chaque indice n'apparait qu'une fois.


Euh... désolé, mais je crois que ton algo n'est pas très bon.

Je pense que l'idée selon laquelle «il n'y a apparemment aucun moyen de faire un match qui ne consomme pas la chaine de caractère qui vient d'être trouvée» est fausse: il y a les look ahead assertions qui permettent de tester l'aval sans le consommer. Mais ça doit être un peu délicat à manipuler.
docu Python Library Reference:
«(?=...)
Matches if ... matches next, but doesn't consume any of the string. This is called a lookahead assertion. For example, Isaac (?=Asimov) will match 'Isaac ' only if it's followed by 'Asimov'.»

[shadowsam]

Fiou, ca c'est du pavé.

Sans reprendre en détail la totalité du commentaire, j'ai juste écris ca vite fait pour montrer comment on pouvait jouer avec.

-La raison pour laquelle j'ai fais ce dictionnaire d'expression régulière compilé c'est en me disant que la chaine "ch" n'est pas la seule à être tester mais est incluses dans un élément plus important. Dans ce cas la la création des expression régulière de comparaison est factorisée.
Dans le cas contraire, si il n'y a qu'une unique chaine, je ne vois pas trop l'intérêt de faire un traitement automatique.

-Pour les look-ahead, le soucis c'est "Matches if ... matches next" donc en fait tu ne match pas le look-ahead, il te sert juste à "regarder en avant". Et je ne voyais pas vraiment de moyen de l'utiliser pour le résultat qu'on voulait.

Encore une fois se n'était qu'un exemple, je ne sais pas quel résultat tu veux tu nous dis juste que tu ne comprends pas un certain comportement.

[dividee]

Ce que je voulais dire c'est que les RE sont déterministes; pour un motif et une chaîne données, il n'y a au plus qu'un seul 'match' possible. Par opposition à un fonctionnement non-déterministe, comme en Prolog, où quand une solution est trouvée on peut défaire le dernier choix effectué et chercher une autre solution (backtracking).
Par exemple:

Code :

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

1
2
3
4
>>> import re
>>> ch = 'jeanBjacquesBrousseauBecrivain'
>>> re.match('.+B',ch).group(0)
'jeanBjacquesBrousseauB'

Car par défaut le + est glouton.
Il y a aussi la version minimale de +:

Code :

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

1
2
>>> re.match('.+?B',ch).group(0)
'jeanB'

Mais il n'y a toujours qu'une réponse (au plus).

Dans une certaine acceptation de ce qu'est un 'match' d'un motif, on pourrait supposer que le motif .+B puisse matcher 'jeanBjacquesB' sur la chaîne d'exemple, mais ce n'est pas le cas.

findall (ou finditer) relance une recherche après la dernière position consommée, mais il n'y a pas moyen, par exemple, de relancer la recherche du début en disant 'je veux une autre solution que celle déjà trouvée'.

La réponse à laquelle tu t'attendais dans ton premier post aurait nécessité ce genre de backtracking.

[eyquem]

Sur ce sujet, en fait je ne veux rien. Je regarde un peu, je butine... Comme je disais, c'est juste une curiosité née à cause d'un autre problème. Et comme je n'ai pas trop de temps pour aller à fond dans tous les problèmes à la fois, celui ci passe au second plan.
Mais merci quand même d'avoir répondu. J'ai bien compris que tu n'as pas passé 3 jours sur le sujet. Il y a des choses maladroites dans ton code, me semble-t-il, mais aussi de l'astuce. J'ai mis un moment à comprendre que tu enregistres en dictionnaire et en liste des RegexObjects. Ça m'a paru bizarre au premier abord mais l'idée est astucieuse, en ce sens qu'elle brise l'a priori que j'avais que les expressions compilées sont quelque chose de spécial par rapport à d'autres variables manipulées dans un programme. Je retiens cette astuce pour un problème futur peut être. En fait quand on met en liste des chaines de caractères on ne fait rien d'autre que, dans l'ordinateur, mettre des ChainesObjects en liste. Il me semble.

[shadowsam]

Je pense que la raison principale du fait qu'il n'y pas vraiment de moyen de ne pas consommer une partie de la chaine (cf. l'explication particulièrement bien foutue de dividee) est juste une question de complexité d'algorithme.

Si on pouvait autoriser une reg_exp à ne pas consommer une chaine, le worst case deviendrait infini. Tout simplement parce que si tu ne "consomme" jamais ta chaine dans ton expression, il n'y a aucune raison que l'algo ne s'arrête, à moins de définir une condition d'arrêt toi-même, mais aujourd'hui cela n'est pas possible.
L'average case quant à lui serait incalculable de façon précise car dépendant de la façon dont tu as écris ton expression mais de toute façon plus violent.

Aujourd'hui la complexité d'un calcul d'expression régulière est déjà assez compliqué sans en rajouter.


Pour résoudre ton cas, la façon la plus simple consiste a faire le match minimum:

Code :

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

re.match('.+?B',ch)

et ensuite de faire des manipulations 'à la main'. Cela sera de toute façon plus efficace que de faire N match avec des expression régulières.

[eyquem]

Ouaaaahhhhh... Intéressants posts.... déterminisme, backtracking, worst case, average case...on voit que vous en connaissez un rayon sur les regex. Je creuserai le sujet plus tard à partir des pistes que vous me donnez.
Mais là je sature un peu sur les regex et il n'y a pas qu'elles dans la vie. Globalement je comprends ce que vous avez écrit et je suis d'accord. Salut.