J'ai un fichier de bibliographie au format bibtex o=F9
dans beaucoup d'entr=E9es le num=E9ro de volume est
indiqu=E9 par erreur dans le champ "number".
Je voudrais donc tester pour chaque entr=E9e si
le champ volume est renseign=E9, si ce n'est pas
le cas tester le champ number et le cas =E9ch=E9ant
supprimer number et modifier volume comme il
faut.
Auriez vous des pistes pour r=E9oudre mon probl=E8me ?
À (at) Tue, 06 Nov 2007 16:44:50 +0100, Olivier Miakinen <om+ écrivait (wrote):
Je comprendrais bien si le dernier « . » de l'expression était remplacé par « [^#"] ». Mais là, vu que toutes les répétitions sont rendues « non gourmandes » (par *?), je ne vois pas ce qui assure qu'un # ne sera pas associé au . plutôt qu'à l'expression « #.*?n ».
Parce que dans une alternative d'une expression rationnelle Perl (mais c'est aussi vrai pour quasiment tous les moteurs de regexp), c'est toujours la première branche reconnue qui est retenue même si s'autres pouvaient "mieux" convenir ("première" au sens "de gauche à droite" et "mieux" au sens plus ou moins gourmande).
-- Paul Gaborit - <http://perso.enstimac.fr/~gaborit/>
À (at) Tue, 06 Nov 2007 16:44:50 +0100,
Olivier Miakinen <om+news@miakinen.net> écrivait (wrote):
Je comprendrais bien si le dernier « . » de l'expression était remplacé
par « [^#"] ». Mais là, vu que toutes les répétitions sont rendues « non
gourmandes » (par *?), je ne vois pas ce qui assure qu'un # ne sera pas
associé au . plutôt qu'à l'expression « #.*?n ».
Parce que dans une alternative d'une expression rationnelle Perl (mais
c'est aussi vrai pour quasiment tous les moteurs de regexp), c'est
toujours la première branche reconnue qui est retenue même si s'autres
pouvaient "mieux" convenir ("première" au sens "de gauche à droite" et
"mieux" au sens plus ou moins gourmande).
--
Paul Gaborit - <http://perso.enstimac.fr/~gaborit/>
À (at) Tue, 06 Nov 2007 16:44:50 +0100, Olivier Miakinen <om+ écrivait (wrote):
Je comprendrais bien si le dernier « . » de l'expression était remplacé par « [^#"] ». Mais là, vu que toutes les répétitions sont rendues « non gourmandes » (par *?), je ne vois pas ce qui assure qu'un # ne sera pas associé au . plutôt qu'à l'expression « #.*?n ».
Parce que dans une alternative d'une expression rationnelle Perl (mais c'est aussi vrai pour quasiment tous les moteurs de regexp), c'est toujours la première branche reconnue qui est retenue même si s'autres pouvaient "mieux" convenir ("première" au sens "de gauche à droite" et "mieux" au sens plus ou moins gourmande).
-- Paul Gaborit - <http://perso.enstimac.fr/~gaborit/>
Olivier Miakinen
Parce que dans une alternative d'une expression rationnelle Perl (mais c'est aussi vrai pour quasiment tous les moteurs de regexp), c'est toujours la première branche reconnue qui est retenue même si d'autres pouvaient "mieux" convenir ("première" au sens "de gauche à droite" et "mieux" au sens plus ou moins gourmande).
Ah, je l'ignorais. Merci de la précision !
Parce que dans une alternative d'une expression rationnelle Perl (mais
c'est aussi vrai pour quasiment tous les moteurs de regexp), c'est
toujours la première branche reconnue qui est retenue même si d'autres
pouvaient "mieux" convenir ("première" au sens "de gauche à droite" et
"mieux" au sens plus ou moins gourmande).
Parce que dans une alternative d'une expression rationnelle Perl (mais c'est aussi vrai pour quasiment tous les moteurs de regexp), c'est toujours la première branche reconnue qui est retenue même si d'autres pouvaient "mieux" convenir ("première" au sens "de gauche à droite" et "mieux" au sens plus ou moins gourmande).
Ah, je l'ignorais. Merci de la précision !
Stephane Chazelas
2007-11-06, 17:17(+01), Paul Gaborit:
À (at) Tue, 06 Nov 2007 16:44:50 +0100, Olivier Miakinen <om+ écrivait (wrote):
Je comprendrais bien si le dernier « . » de l'expression était remplacé par « [^#"] ». Mais là, vu que toutes les répétitions sont rendues « non gourmandes » (par *?), je ne vois pas ce qui assure qu'un # ne sera pas associé au . plutôt qu'à l'expression « #.*?n ».
Parce que dans une alternative d'une expression rationnelle Perl (mais c'est aussi vrai pour quasiment tous les moteurs de regexp)
Pas d'accord sur ce point. Je dirais que c'est une specificité de perl. Les ERE standard par exemple, au contraire essaieront souvent de matcher le plus long.
Example avec GNU grep:
~$ echo aaaa | grep -Eo 'a|a+' aaaa ~$ echo aaaa | perl -nle 'print for /a|a+/g' a a a a
c'est toujours la première branche reconnue qui est retenue même si s'autres pouvaient "mieux" convenir ("première" au sens "de gauche à droite" et "mieux" au sens plus ou moins gourmande).
-- Stéphane
2007-11-06, 17:17(+01), Paul Gaborit:
À (at) Tue, 06 Nov 2007 16:44:50 +0100,
Olivier Miakinen <om+news@miakinen.net> écrivait (wrote):
Je comprendrais bien si le dernier « . » de l'expression était remplacé
par « [^#"] ». Mais là, vu que toutes les répétitions sont rendues « non
gourmandes » (par *?), je ne vois pas ce qui assure qu'un # ne sera pas
associé au . plutôt qu'à l'expression « #.*?n ».
Parce que dans une alternative d'une expression rationnelle Perl (mais
c'est aussi vrai pour quasiment tous les moteurs de regexp)
Pas d'accord sur ce point. Je dirais que c'est une specificité
de perl. Les ERE standard par exemple, au contraire essaieront
souvent de matcher le plus long.
Example avec GNU grep:
~$ echo aaaa | grep -Eo 'a|a+'
aaaa
~$ echo aaaa | perl -nle 'print for /a|a+/g'
a
a
a
a
c'est
toujours la première branche reconnue qui est retenue même si s'autres
pouvaient "mieux" convenir ("première" au sens "de gauche à droite" et
"mieux" au sens plus ou moins gourmande).
À (at) Tue, 06 Nov 2007 16:44:50 +0100, Olivier Miakinen <om+ écrivait (wrote):
Je comprendrais bien si le dernier « . » de l'expression était remplacé par « [^#"] ». Mais là, vu que toutes les répétitions sont rendues « non gourmandes » (par *?), je ne vois pas ce qui assure qu'un # ne sera pas associé au . plutôt qu'à l'expression « #.*?n ».
Parce que dans une alternative d'une expression rationnelle Perl (mais c'est aussi vrai pour quasiment tous les moteurs de regexp)
Pas d'accord sur ce point. Je dirais que c'est une specificité de perl. Les ERE standard par exemple, au contraire essaieront souvent de matcher le plus long.
Example avec GNU grep:
~$ echo aaaa | grep -Eo 'a|a+' aaaa ~$ echo aaaa | perl -nle 'print for /a|a+/g' a a a a
c'est toujours la première branche reconnue qui est retenue même si s'autres pouvaient "mieux" convenir ("première" au sens "de gauche à droite" et "mieux" au sens plus ou moins gourmande).
-- Stéphane
Olivier Miakinen
Parce que dans une alternative d'une expression rationnelle Perl (mais c'est aussi vrai pour quasiment tous les moteurs de regexp)
Pas d'accord sur ce point. Je dirais que c'est une specificité de perl. Les ERE standard par exemple, au contraire essaieront souvent de matcher le plus long.
Example avec GNU grep:
~$ echo aaaa | grep -Eo 'a|a+' aaaa ~$ echo aaaa | perl -nle 'print for /a|a+/g' a a a a
Sais-tu ce qu'il en est des PCRE (en principe compatible Perl mais il y a des exceptions) ?
Parce que dans une alternative d'une expression rationnelle Perl (mais
c'est aussi vrai pour quasiment tous les moteurs de regexp)
Pas d'accord sur ce point. Je dirais que c'est une specificité
de perl. Les ERE standard par exemple, au contraire essaieront
souvent de matcher le plus long.
Example avec GNU grep:
~$ echo aaaa | grep -Eo 'a|a+'
aaaa
~$ echo aaaa | perl -nle 'print for /a|a+/g'
a
a
a
a
Parce que dans une alternative d'une expression rationnelle Perl (mais c'est aussi vrai pour quasiment tous les moteurs de regexp)
Pas d'accord sur ce point. Je dirais que c'est une specificité de perl. Les ERE standard par exemple, au contraire essaieront souvent de matcher le plus long.
Example avec GNU grep:
~$ echo aaaa | grep -Eo 'a|a+' aaaa ~$ echo aaaa | perl -nle 'print for /a|a+/g' a a a a
Sais-tu ce qu'il en est des PCRE (en principe compatible Perl mais il y a des exceptions) ?
Stephane Chazelas
2007-11-06, 18:08(+01), Olivier Miakinen: [...]
Parce que dans une alternative d'une expression rationnelle Perl (mais c'est aussi vrai pour quasiment tous les moteurs de regexp)
Pas d'accord sur ce point. Je dirais que c'est une specificité de perl. Les ERE standard par exemple, au contraire essaieront souvent de matcher le plus long.
Example avec GNU grep:
~$ echo aaaa | grep -Eo 'a|a+' aaaa ~$ echo aaaa | perl -nle 'print for /a|a+/g' a a a a
Sais-tu ce qu'il en est des PCRE (en principe compatible Perl mais il y a des exceptions) ?
C'est une "feature" documentee des regexps de perl, donc ca sera je pense dans les PCRE et probablement toutes les regexps derivees ou inspirees de perl/PCRE.
-- Stéphane
2007-11-06, 18:08(+01), Olivier Miakinen:
[...]
Parce que dans une alternative d'une expression rationnelle Perl (mais
c'est aussi vrai pour quasiment tous les moteurs de regexp)
Pas d'accord sur ce point. Je dirais que c'est une specificité
de perl. Les ERE standard par exemple, au contraire essaieront
souvent de matcher le plus long.
Example avec GNU grep:
~$ echo aaaa | grep -Eo 'a|a+'
aaaa
~$ echo aaaa | perl -nle 'print for /a|a+/g'
a
a
a
a
Sais-tu ce qu'il en est des PCRE (en principe compatible Perl mais il y
a des exceptions) ?
C'est une "feature" documentee des regexps de perl, donc ca sera
je pense dans les PCRE et probablement toutes les regexps
derivees ou inspirees de perl/PCRE.
Parce que dans une alternative d'une expression rationnelle Perl (mais c'est aussi vrai pour quasiment tous les moteurs de regexp)
Pas d'accord sur ce point. Je dirais que c'est une specificité de perl. Les ERE standard par exemple, au contraire essaieront souvent de matcher le plus long.
Example avec GNU grep:
~$ echo aaaa | grep -Eo 'a|a+' aaaa ~$ echo aaaa | perl -nle 'print for /a|a+/g' a a a a
Sais-tu ce qu'il en est des PCRE (en principe compatible Perl mais il y a des exceptions) ?
C'est une "feature" documentee des regexps de perl, donc ca sera je pense dans les PCRE et probablement toutes les regexps derivees ou inspirees de perl/PCRE.
-- Stéphane
Paul Gaborit
À (at) Tue, 06 Nov 2007 18:08:40 +0100, Olivier Miakinen <om+ écrivait (wrote):
Parce que dans une alternative d'une expression rationnelle Perl (mais c'est aussi vrai pour quasiment tous les moteurs de regexp)
Pas d'accord sur ce point. Je dirais que c'est une specificité de perl. Les ERE standard par exemple, au contraire essaieront souvent de matcher le plus long.
[... suivi d'un exemple tout à fait pertinent avec GNU grep...]
Ah, donc c'est loin d'être universel.
Sais-tu ce qu'il en est des PCRE (en principe compatible Perl mais il y a des exceptions) ?
Bon, effectivement ce n'est pas universel. Là-dessus, je me suis beaucoup avancé !
Je pense que ce choix (dans Perl) a été fait pour des raisons d'efficacité (*).
Le GNU grep propose aussi l'option -P (ou --perl-regexp) qui permet d'adopter un comportement similaire à Perl. Mais cette option, même si elle est reconnue n'est pas toujours supportée (elle ne l'est ni sous FreeBSD ni sous Ubuntu par exemple).
Quant à PCRE, c'est sûr que c'est comme avec Perl. Petit extrait de la doc de PCRE (en anglais) :
The matching process tries each alternative in turn, from left to right, and the first one that succeeds is used. If the alternatives are within a subpattern (defined below), "succeeds" means matching the rest of the main pattern as well as the alternative in the subpattern.
(*) D'un point de vue conceptuel, je me demande si la version permettant de choisir la branche la plus longue est vraiment implémentable par un simple automate à états finis puisque le choix ne peut plus s'effectuer par de simples backtracks...
-- Paul Gaborit - <http://perso.enstimac.fr/~gaborit/>
À (at) Tue, 06 Nov 2007 18:08:40 +0100,
Olivier Miakinen <om+news@miakinen.net> écrivait (wrote):
Parce que dans une alternative d'une expression rationnelle Perl (mais
c'est aussi vrai pour quasiment tous les moteurs de regexp)
Pas d'accord sur ce point. Je dirais que c'est une specificité
de perl. Les ERE standard par exemple, au contraire essaieront
souvent de matcher le plus long.
[... suivi d'un exemple tout à fait pertinent avec GNU grep...]
Ah, donc c'est loin d'être universel.
Sais-tu ce qu'il en est des PCRE (en principe compatible Perl mais il y
a des exceptions) ?
Bon, effectivement ce n'est pas universel. Là-dessus, je me suis
beaucoup avancé !
Je pense que ce choix (dans Perl) a été fait pour des raisons
d'efficacité (*).
Le GNU grep propose aussi l'option -P (ou --perl-regexp) qui permet
d'adopter un comportement similaire à Perl. Mais cette option, même si
elle est reconnue n'est pas toujours supportée (elle ne l'est ni sous
FreeBSD ni sous Ubuntu par exemple).
Quant à PCRE, c'est sûr que c'est comme avec Perl. Petit extrait de la
doc de PCRE (en anglais) :
The matching process tries each alternative in turn, from left to
right, and the first one that succeeds is used. If the alternatives
are within a subpattern (defined below), "succeeds" means matching
the rest of the main pattern as well as the alternative in the
subpattern.
(*) D'un point de vue conceptuel, je me demande si la version
permettant de choisir la branche la plus longue est vraiment
implémentable par un simple automate à états finis puisque le choix ne
peut plus s'effectuer par de simples backtracks...
--
Paul Gaborit - <http://perso.enstimac.fr/~gaborit/>
À (at) Tue, 06 Nov 2007 18:08:40 +0100, Olivier Miakinen <om+ écrivait (wrote):
Parce que dans une alternative d'une expression rationnelle Perl (mais c'est aussi vrai pour quasiment tous les moteurs de regexp)
Pas d'accord sur ce point. Je dirais que c'est une specificité de perl. Les ERE standard par exemple, au contraire essaieront souvent de matcher le plus long.
[... suivi d'un exemple tout à fait pertinent avec GNU grep...]
Ah, donc c'est loin d'être universel.
Sais-tu ce qu'il en est des PCRE (en principe compatible Perl mais il y a des exceptions) ?
Bon, effectivement ce n'est pas universel. Là-dessus, je me suis beaucoup avancé !
Je pense que ce choix (dans Perl) a été fait pour des raisons d'efficacité (*).
Le GNU grep propose aussi l'option -P (ou --perl-regexp) qui permet d'adopter un comportement similaire à Perl. Mais cette option, même si elle est reconnue n'est pas toujours supportée (elle ne l'est ni sous FreeBSD ni sous Ubuntu par exemple).
Quant à PCRE, c'est sûr que c'est comme avec Perl. Petit extrait de la doc de PCRE (en anglais) :
The matching process tries each alternative in turn, from left to right, and the first one that succeeds is used. If the alternatives are within a subpattern (defined below), "succeeds" means matching the rest of the main pattern as well as the alternative in the subpattern.
(*) D'un point de vue conceptuel, je me demande si la version permettant de choisir la branche la plus longue est vraiment implémentable par un simple automate à états finis puisque le choix ne peut plus s'effectuer par de simples backtracks...
-- Paul Gaborit - <http://perso.enstimac.fr/~gaborit/>
Olivier Miakinen
Quant à PCRE, c'est sûr que c'est comme avec Perl. Petit extrait de la doc de PCRE (en anglais) :
The matching process tries each alternative in turn, from left to right, and the first one that succeeds is used. If the alternatives are within a subpattern (defined below), "succeeds" means matching the rest of the main pattern as well as the alternative in the subpattern.
Encore merci !
Quant à PCRE, c'est sûr que c'est comme avec Perl. Petit extrait de la
doc de PCRE (en anglais) :
The matching process tries each alternative in turn, from left to
right, and the first one that succeeds is used. If the alternatives
are within a subpattern (defined below), "succeeds" means matching
the rest of the main pattern as well as the alternative in the
subpattern.
Quant à PCRE, c'est sûr que c'est comme avec Perl. Petit extrait de la doc de PCRE (en anglais) :
The matching process tries each alternative in turn, from left to right, and the first one that succeeds is used. If the alternatives are within a subpattern (defined below), "succeeds" means matching the rest of the main pattern as well as the alternative in the subpattern.
Encore merci !
talon
Paul Gaborit wrote:
Je pense que ce choix (dans Perl) a été fait pour des raisons d'efficacité (*).
D'efficacité j'en doute. Le moteur d'expressions de perl est connu pour être notoirement inefficace. http://swtch.com/~rsc/regexp/regexp1.html
--
Michel TALON
Paul Gaborit <Paul.Gaborit@invalid.invalid> wrote:
Je pense que ce choix (dans Perl) a été fait pour des raisons
d'efficacité (*).
D'efficacité j'en doute. Le moteur d'expressions de perl est connu pour
être notoirement inefficace.
http://swtch.com/~rsc/regexp/regexp1.html
Je pense que ce choix (dans Perl) a été fait pour des raisons d'efficacité (*).
D'efficacité j'en doute. Le moteur d'expressions de perl est connu pour être notoirement inefficace. http://swtch.com/~rsc/regexp/regexp1.html
--
Michel TALON
Stephane Chazelas
2007-11-6, 21:16(+00), Michel Talon:
Paul Gaborit wrote:
Je pense que ce choix (dans Perl) a été fait pour des raisons d'efficacité (*).
D'efficacité j'en doute. Le moteur d'expressions de perl est connu pour être notoirement inefficace. http://swtch.com/~rsc/regexp/regexp1.html [...]
Cet article (au demeurant tres interessant et bien ecrit) traite de cas particulier pathologique et met perl/python/ruby dans le meme panier. En gros, il n'affirme pas grand chose d'utile quant a l'efficacité du moteur de regexp de perl en general.
Voir http://www.perlmonks.org/?node_idY7262 pour une discussion de cet article (features l'auteur de l'article).
Et je trouve que le contenu de cet article aurait plutot tendance a donner credit a la pensee de Paul ci-dessus.
-- Stéphane
2007-11-6, 21:16(+00), Michel Talon:
Paul Gaborit <Paul.Gaborit@invalid.invalid> wrote:
Je pense que ce choix (dans Perl) a été fait pour des raisons
d'efficacité (*).
D'efficacité j'en doute. Le moteur d'expressions de perl est connu pour
être notoirement inefficace.
http://swtch.com/~rsc/regexp/regexp1.html
[...]
Cet article (au demeurant tres interessant et bien ecrit) traite
de cas particulier pathologique et met perl/python/ruby dans le
meme panier. En gros, il n'affirme pas grand chose d'utile quant
a l'efficacité du moteur de regexp de perl en general.
Voir http://www.perlmonks.org/?node_idY7262 pour une discussion
de cet article (features l'auteur de l'article).
Et je trouve que le contenu de cet article aurait plutot
tendance a donner credit a la pensee de Paul ci-dessus.
Je pense que ce choix (dans Perl) a été fait pour des raisons d'efficacité (*).
D'efficacité j'en doute. Le moteur d'expressions de perl est connu pour être notoirement inefficace. http://swtch.com/~rsc/regexp/regexp1.html [...]
Cet article (au demeurant tres interessant et bien ecrit) traite de cas particulier pathologique et met perl/python/ruby dans le meme panier. En gros, il n'affirme pas grand chose d'utile quant a l'efficacité du moteur de regexp de perl en general.
Voir http://www.perlmonks.org/?node_idY7262 pour une discussion de cet article (features l'auteur de l'article).
Et je trouve que le contenu de cet article aurait plutot tendance a donner credit a la pensee de Paul ci-dessus.
-- Stéphane
Paul Gaborit
À (at) Tue, 06 Nov 2007 23:01:29 GMT, Stephane Chazelas écrivait (wrote):
2007-11-6, 21:16(+00), Michel Talon:
Paul Gaborit wrote:
Je pense que ce choix (dans Perl) a été fait pour des raisons d'efficacité (*).
D'efficacité j'en doute. Le moteur d'expressions de perl est connu pour être notoirement inefficace. http://swtch.com/~rsc/regexp/regexp1.html [...]
Cet article (au demeurant tres interessant et bien ecrit) traite de cas particulier pathologique et met perl/python/ruby dans le meme panier. En gros, il n'affirme pas grand chose d'utile quant a l'efficacité du moteur de regexp de perl en general.
Le cas pathologique ne me semble utilisé que pour faciliter la démonstrattion. Mais l'auteur indique bien que c'est applicable à toutes les expressions rationnelles (sans extension). Et il a évidemment raison puisqu'il a été démontré qu'un automate à états finis est l'implémentation la plus rapide pour les expressions rationnelles (sans extension). Par contre, la création de cet automate peut être très longue et son occupation en mémoire très grande. Et je suis sûr qu'on peut trouver des cas pathologiques permettant d'exploser le temps de compilation et/ou la place mémoire occupée par l'approche DFA alors qu'ils seraient sans effet sur l'approche récursive avec backtracks (l'auteur l'évoque d'ailleurs et son implémentation par création dynamique des états tente de minimiser cet inconvénient).
De plus, les propositions de gestion de quelques extensions courantes des regexp sont parfois loin d'être performantes (ex: {n,m}). Sans parler de toutes les extensions existantes du moteur Perl qui ne sont pas du tout abordées dans l'article.
La technique proposée par l'auteur consistant à compiler différement les regexp avec ou sans extension ne me semble par une proposition très réaliste. Il faudrait déjà commencer par le cas le plus courant: l'utilisation d'une regexp pour chercher un simple mot dans un grand texte alors que la fonction 'index' va très nettement plus vite. Et là, NFA, DFA et autres implémentations peuvent toujours se rhabiller. Par contre, certains développeurs Perl proposent d'intégrer plusieurs moteurs de regexp entre lesquels le programmeur pourra choisir selon les cas. Cela me semble plus intéressant.
Pour revenir au cas qui nous intéresse, dans un moteur de regexp implémenté comme celui de Perl (approche récursive avec backtracks), la traitement de l'alternative en choisissant la première branche qui est reconnue est évidemment plus rapide qu'une approche privilégiant la branche la plus longue. C'était donc bien un choix d'efficacité.
Dernière chose : le moteur de regexp de Perl évolue toujours. Une présentation de David Landgren de Perl 5.10 donne quelques aperçus :
<http://www.landgren.net/perl/fpw2006/new.html>
(la partie concernant le moteur de regexp est en fin de document.)
Extrait :
- l'implémentation n'est plus recursive - le moteur a été restructuré en profondeur par Dave Mitchell et Yves Orton - alternatives examinés via une structure de tri - optimisation Aho-Corasick (où commencer à chercher) ...
-- Paul Gaborit - <http://perso.enstimac.fr/~gaborit/>
À (at) Tue, 06 Nov 2007 23:01:29 GMT,
Stephane Chazelas <cette.adresse@est.invalid> écrivait (wrote):
2007-11-6, 21:16(+00), Michel Talon:
Paul Gaborit <Paul.Gaborit@invalid.invalid> wrote:
Je pense que ce choix (dans Perl) a été fait pour des raisons
d'efficacité (*).
D'efficacité j'en doute. Le moteur d'expressions de perl est connu pour
être notoirement inefficace.
http://swtch.com/~rsc/regexp/regexp1.html
[...]
Cet article (au demeurant tres interessant et bien ecrit) traite
de cas particulier pathologique et met perl/python/ruby dans le
meme panier. En gros, il n'affirme pas grand chose d'utile quant
a l'efficacité du moteur de regexp de perl en general.
Le cas pathologique ne me semble utilisé que pour faciliter la
démonstrattion. Mais l'auteur indique bien que c'est applicable à
toutes les expressions rationnelles (sans extension). Et il a
évidemment raison puisqu'il a été démontré qu'un automate à états
finis est l'implémentation la plus rapide pour les expressions
rationnelles (sans extension). Par contre, la création de cet automate
peut être très longue et son occupation en mémoire très grande. Et je
suis sûr qu'on peut trouver des cas pathologiques permettant
d'exploser le temps de compilation et/ou la place mémoire occupée par
l'approche DFA alors qu'ils seraient sans effet sur l'approche
récursive avec backtracks (l'auteur l'évoque d'ailleurs et son
implémentation par création dynamique des états tente de minimiser cet
inconvénient).
De plus, les propositions de gestion de quelques extensions courantes
des regexp sont parfois loin d'être performantes (ex: {n,m}). Sans
parler de toutes les extensions existantes du moteur Perl qui ne sont
pas du tout abordées dans l'article.
La technique proposée par l'auteur consistant à compiler différement
les regexp avec ou sans extension ne me semble par une proposition
très réaliste. Il faudrait déjà commencer par le cas le plus courant:
l'utilisation d'une regexp pour chercher un simple mot dans un grand
texte alors que la fonction 'index' va très nettement plus vite. Et
là, NFA, DFA et autres implémentations peuvent toujours se rhabiller.
Par contre, certains développeurs Perl proposent d'intégrer plusieurs
moteurs de regexp entre lesquels le programmeur pourra choisir selon
les cas. Cela me semble plus intéressant.
Pour revenir au cas qui nous intéresse, dans un moteur de regexp
implémenté comme celui de Perl (approche récursive avec backtracks),
la traitement de l'alternative en choisissant la première branche qui
est reconnue est évidemment plus rapide qu'une approche privilégiant
la branche la plus longue. C'était donc bien un choix d'efficacité.
Dernière chose : le moteur de regexp de Perl évolue toujours. Une
présentation de David Landgren de Perl 5.10 donne quelques aperçus :
<http://www.landgren.net/perl/fpw2006/new.html>
(la partie concernant le moteur de regexp est en fin de document.)
Extrait :
- l'implémentation n'est plus recursive
- le moteur a été restructuré en profondeur par Dave Mitchell et
Yves Orton
- alternatives examinés via une structure de tri
- optimisation Aho-Corasick (où commencer à chercher)
...
--
Paul Gaborit - <http://perso.enstimac.fr/~gaborit/>
À (at) Tue, 06 Nov 2007 23:01:29 GMT, Stephane Chazelas écrivait (wrote):
2007-11-6, 21:16(+00), Michel Talon:
Paul Gaborit wrote:
Je pense que ce choix (dans Perl) a été fait pour des raisons d'efficacité (*).
D'efficacité j'en doute. Le moteur d'expressions de perl est connu pour être notoirement inefficace. http://swtch.com/~rsc/regexp/regexp1.html [...]
Cet article (au demeurant tres interessant et bien ecrit) traite de cas particulier pathologique et met perl/python/ruby dans le meme panier. En gros, il n'affirme pas grand chose d'utile quant a l'efficacité du moteur de regexp de perl en general.
Le cas pathologique ne me semble utilisé que pour faciliter la démonstrattion. Mais l'auteur indique bien que c'est applicable à toutes les expressions rationnelles (sans extension). Et il a évidemment raison puisqu'il a été démontré qu'un automate à états finis est l'implémentation la plus rapide pour les expressions rationnelles (sans extension). Par contre, la création de cet automate peut être très longue et son occupation en mémoire très grande. Et je suis sûr qu'on peut trouver des cas pathologiques permettant d'exploser le temps de compilation et/ou la place mémoire occupée par l'approche DFA alors qu'ils seraient sans effet sur l'approche récursive avec backtracks (l'auteur l'évoque d'ailleurs et son implémentation par création dynamique des états tente de minimiser cet inconvénient).
De plus, les propositions de gestion de quelques extensions courantes des regexp sont parfois loin d'être performantes (ex: {n,m}). Sans parler de toutes les extensions existantes du moteur Perl qui ne sont pas du tout abordées dans l'article.
La technique proposée par l'auteur consistant à compiler différement les regexp avec ou sans extension ne me semble par une proposition très réaliste. Il faudrait déjà commencer par le cas le plus courant: l'utilisation d'une regexp pour chercher un simple mot dans un grand texte alors que la fonction 'index' va très nettement plus vite. Et là, NFA, DFA et autres implémentations peuvent toujours se rhabiller. Par contre, certains développeurs Perl proposent d'intégrer plusieurs moteurs de regexp entre lesquels le programmeur pourra choisir selon les cas. Cela me semble plus intéressant.
Pour revenir au cas qui nous intéresse, dans un moteur de regexp implémenté comme celui de Perl (approche récursive avec backtracks), la traitement de l'alternative en choisissant la première branche qui est reconnue est évidemment plus rapide qu'une approche privilégiant la branche la plus longue. C'était donc bien un choix d'efficacité.
Dernière chose : le moteur de regexp de Perl évolue toujours. Une présentation de David Landgren de Perl 5.10 donne quelques aperçus :
<http://www.landgren.net/perl/fpw2006/new.html>
(la partie concernant le moteur de regexp est en fin de document.)
Extrait :
- l'implémentation n'est plus recursive - le moteur a été restructuré en profondeur par Dave Mitchell et Yves Orton - alternatives examinés via une structure de tri - optimisation Aho-Corasick (où commencer à chercher) ...
-- Paul Gaborit - <http://perso.enstimac.fr/~gaborit/>
