Connaissez vous un moyen (un outil) permettant de fusionner 2 ou
plusieurs expressions régulières en une unique expression ?
Théoriquement cela me semble possible, mais je ne suis pas un expert en
théorie des graphes/automates...
Le but est d'essayer de gagner en vitesse en élaborant une expression
compliquée plutôt que d'essayer de matcher consécutivement plusieurs
expressions.
Nobody can fix the economy. Nobody can be trusted with their finger on the button. Nobody's perfect. VOTE FOR NOBODY.
Laurent Wacrenier
Jym écrit:
C'est une factorisation. Vu qu'il existe des algorithmes pour faire celà dans les arithmétiques polynomiale ou booleene, ça doit être faisable dans l'arithmétique des expressions rationnelles.
Pas sur à 100% : les regexp n'ont pas de bonne spropriétés mathématiques genre commutativité ou distributivité (enfin, ça dépend pour quelles opérations). En plus, l'étoile doit vraiment foutre le bordel dans toute tentative de factorisation.
Remarque, dans certains cas, ce n'est pas la peine de s'embeter avec tout ça. Pour l'ensemble des mots dont la longueur est inférieure à une longueur déterminée, il suffit de précalculer la liste des mots vérifiant l'expression et de faire une bonne vielle table de hachage. Y'a pas plus rapide à l'execution.
Jym <moyen@loria.fr> écrit:
C'est une factorisation. Vu qu'il existe des algorithmes pour faire
celà dans les arithmétiques polynomiale ou booleene, ça doit être
faisable dans l'arithmétique des expressions rationnelles.
Pas sur à 100% : les regexp n'ont pas de bonne spropriétés mathématiques
genre commutativité ou distributivité (enfin, ça dépend pour quelles
opérations). En plus, l'étoile doit vraiment foutre le bordel dans toute
tentative de factorisation.
Remarque, dans certains cas, ce n'est pas la peine de s'embeter avec
tout ça. Pour l'ensemble des mots dont la longueur est inférieure à
une longueur déterminée, il suffit de précalculer la liste des mots
vérifiant l'expression et de faire une bonne vielle table de hachage.
Y'a pas plus rapide à l'execution.
C'est une factorisation. Vu qu'il existe des algorithmes pour faire celà dans les arithmétiques polynomiale ou booleene, ça doit être faisable dans l'arithmétique des expressions rationnelles.
Pas sur à 100% : les regexp n'ont pas de bonne spropriétés mathématiques genre commutativité ou distributivité (enfin, ça dépend pour quelles opérations). En plus, l'étoile doit vraiment foutre le bordel dans toute tentative de factorisation.
Remarque, dans certains cas, ce n'est pas la peine de s'embeter avec tout ça. Pour l'ensemble des mots dont la longueur est inférieure à une longueur déterminée, il suffit de précalculer la liste des mots vérifiant l'expression et de faire une bonne vielle table de hachage. Y'a pas plus rapide à l'execution.
Laurent Wacrenier
Manu écrit:
PCRE par exemple peut optimiser ses expressions en sachant quelle est la première lettre que doit avoir le motif et celle ci peut être plus difficile à déterminée dans le cas d'une expression complexe.
Je vais voir l'API PCRE donc.
Y'a pas grand chose aux dernière nouvelles, c'est juste une mini optimisation.
Au passage, un optimiseur digne de ce nom pourrait remplacer le [0-9]+ final par un [0-9] simple si on n'a pas à travailler sur le motif recherché.
Toutes les chaînes vérifiant toto[0-9]+ vérifient toto[0-9] et réciproquement.
Manu <nobody@guzu.net> écrit:
PCRE par exemple peut optimiser ses expressions en sachant quelle est
la première lettre que doit avoir le motif et celle ci peut être plus
difficile à déterminée dans le cas d'une expression complexe.
Je vais voir l'API PCRE donc.
Y'a pas grand chose aux dernière nouvelles, c'est juste une mini
optimisation.
Au passage, un optimiseur digne de ce nom pourrait remplacer le [0-9]+
final par un [0-9] simple si on n'a pas à travailler sur le motif
recherché.
Toutes les chaînes vérifiant toto[0-9]+ vérifient toto[0-9] et
réciproquement.
PCRE par exemple peut optimiser ses expressions en sachant quelle est la première lettre que doit avoir le motif et celle ci peut être plus difficile à déterminée dans le cas d'une expression complexe.
Je vais voir l'API PCRE donc.
Y'a pas grand chose aux dernière nouvelles, c'est juste une mini optimisation.
Au passage, un optimiseur digne de ce nom pourrait remplacer le [0-9]+ final par un [0-9] simple si on n'a pas à travailler sur le motif recherché.
Toutes les chaînes vérifiant toto[0-9]+ vérifient toto[0-9] et réciproquement.
Manu
Laurent Wacrenier wrote:
Je vais voir l'API PCRE donc.
Y'a pas grand chose aux dernière nouvelles, c'est juste une mini optimisation.
Oui ça a l'air d'être interne. Je disais ça parce que j'étais resté sur mon idée d'une API du style:
re = regexp_compile("toto[0-9]+") regexp_add(re, "tata[0-9]+") regexp_add(re, "^titi et gros minet.*$")
regexp_match(re, str)
Au passage, un optimiseur digne de ce nom pourrait remplacer le [0-9]+ final par un [0-9] simple si on n'a pas à travailler sur le motif recherché.
Toutes les chaînes vérifiant toto[0-9]+ vérifient toto[0-9] et réciproquement.
OK (mais il m'a fallu un peu de temps).
Laurent Wacrenier wrote:
Je vais voir l'API PCRE donc.
Y'a pas grand chose aux dernière nouvelles, c'est juste une mini
optimisation.
Oui ça a l'air d'être interne.
Je disais ça parce que j'étais resté sur mon idée d'une API du style:
re = regexp_compile("toto[0-9]+")
regexp_add(re, "tata[0-9]+")
regexp_add(re, "^titi et gros minet.*$")
regexp_match(re, str)
Au passage, un optimiseur digne de ce nom pourrait remplacer le [0-9]+
final par un [0-9] simple si on n'a pas à travailler sur le motif
recherché.
Toutes les chaînes vérifiant toto[0-9]+ vérifient toto[0-9] et
réciproquement.
Y'a pas grand chose aux dernière nouvelles, c'est juste une mini optimisation.
Oui ça a l'air d'être interne. Je disais ça parce que j'étais resté sur mon idée d'une API du style:
re = regexp_compile("toto[0-9]+") regexp_add(re, "tata[0-9]+") regexp_add(re, "^titi et gros minet.*$")
regexp_match(re, str)
Au passage, un optimiseur digne de ce nom pourrait remplacer le [0-9]+ final par un [0-9] simple si on n'a pas à travailler sur le motif recherché.
Toutes les chaînes vérifiant toto[0-9]+ vérifient toto[0-9] et réciproquement.
OK (mais il m'a fallu un peu de temps).
Laurent Wacrenier
Manu écrit:
Je vais voir l'API PCRE donc.
Y'a pas grand chose aux dernière nouvelles, c'est juste une mini optimisation.
Oui ça a l'air d'être interne.
L'optimisation de pcre dont je parlais se fait avec pcre_study(). La limite est
At present, studying a pattern is useful only for non-anchored patterns that do not have a single fixed starting character. A bitmap of possi- ble starting bytes is created.
Je disais ça parce que j'étais resté sur mon idée d'une API du style:
re = regexp_compile("toto[0-9]+") regexp_add(re, "tata[0-9]+") regexp_add(re, "^titi et gros minet.*$")
S'il n'a pas une vue complete du code, ça risquerait d'être très gourmand.
regexp_match(re, str)
Manu <nobody@guzu.net> écrit:
Je vais voir l'API PCRE donc.
Y'a pas grand chose aux dernière nouvelles, c'est juste une mini
optimisation.
Oui ça a l'air d'être interne.
L'optimisation de pcre dont je parlais se fait avec pcre_study().
La limite est
At present, studying a pattern is useful only for non-anchored patterns
that do not have a single fixed starting character. A bitmap of possi-
ble starting bytes is created.
Je disais ça parce que j'étais resté sur mon idée d'une API du style:
re = regexp_compile("toto[0-9]+")
regexp_add(re, "tata[0-9]+")
regexp_add(re, "^titi et gros minet.*$")
S'il n'a pas une vue complete du code, ça risquerait d'être très gourmand.
Y'a pas grand chose aux dernière nouvelles, c'est juste une mini optimisation.
Oui ça a l'air d'être interne.
L'optimisation de pcre dont je parlais se fait avec pcre_study(). La limite est
At present, studying a pattern is useful only for non-anchored patterns that do not have a single fixed starting character. A bitmap of possi- ble starting bytes is created.
Je disais ça parce que j'étais resté sur mon idée d'une API du style:
re = regexp_compile("toto[0-9]+") regexp_add(re, "tata[0-9]+") regexp_add(re, "^titi et gros minet.*$")
S'il n'a pas une vue complete du code, ça risquerait d'être très gourmand.
regexp_match(re, str)
Nicolas Le Scouarnec
Google est très avare de résultats quand on lui demande regexp minimal determinist union ... Normal, puisque ce qu'on minimise ce n'est pas les regexp, mais les
NFA ou DFA qu'elles représentent! Chercher plutôt DFA minimization
Oui, mais comme on peut passer de l'un a l'autre, je voulais plutot voir s'il y avait un logiciel qui faisait cela, et qu'ils y a une "équivalence", meme si la notion de minimalité vient avec les automates.
-- Nicolas Le Scouarnec
Google est très avare de résultats quand on lui demande regexp minimal
determinist union ...
Normal, puisque ce qu'on minimise ce n'est pas les regexp, mais les
NFA ou DFA qu'elles représentent! Chercher plutôt DFA minimization
Oui, mais comme on peut passer de l'un a l'autre, je voulais plutot
voir s'il y avait un logiciel qui faisait cela, et qu'ils y a une
"équivalence", meme si la notion de minimalité vient avec les
automates.
Google est très avare de résultats quand on lui demande regexp minimal determinist union ... Normal, puisque ce qu'on minimise ce n'est pas les regexp, mais les
NFA ou DFA qu'elles représentent! Chercher plutôt DFA minimization
Oui, mais comme on peut passer de l'un a l'autre, je voulais plutot voir s'il y avait un logiciel qui faisait cela, et qu'ils y a une "équivalence", meme si la notion de minimalité vient avec les automates.
-- Nicolas Le Scouarnec
James Kanze
Jérémy JUST wrote:
On Mon, 14 Feb 2005 20:28:58 +0100 Manu wrote:
Le but est d'essayer de gagner en vitesse en élaborant une expression compliquée plutôt que d'essayer de matcher consécutivement plusieurs expressions.
Si j'ai bien compris, tu veux (entre autres) mettre en facteur les chaînes communes à plusieurs motifs?
L'idée est peut-être saugrenue ceci dit :)
Non-non, elle est intéressante, et souvent évoquée. Mais la solution va dépendre du dialecte de regexp, et va rarement être optimale à coup sûr.
En Perl, par exemple, tu peux utiliser Regexp::Optimizer : http://search.cpan.org/~dankogai/Regexp-Optimizer-0.15/
La véritable question, c'est est-ce qu'on peut le limiter à de vraies expressions rationnelles, ou est-ce qu'il faut supporter toutes les extensions ad hoc. Parce que pour les vraies expressions rationnelles, la solution simple est d'en créer un automate fini. Ce qui serait le même, indépendamment de la forme de l'expression initiale.
-- James Kanze home: www.gabi-soft.fr Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34
Jérémy JUST wrote:
On Mon, 14 Feb 2005 20:28:58 +0100
Manu <nobody@guzu.net> wrote:
Le but est d'essayer de gagner en vitesse en élaborant une
expression compliquée plutôt que d'essayer de matcher
consécutivement plusieurs expressions.
Si j'ai bien compris, tu veux (entre autres) mettre en facteur les
chaînes communes à plusieurs motifs?
L'idée est peut-être saugrenue ceci dit :)
Non-non, elle est intéressante, et souvent évoquée. Mais la
solution va dépendre du dialecte de regexp, et va rarement
être optimale à coup sûr.
En Perl, par exemple, tu peux utiliser Regexp::Optimizer :
http://search.cpan.org/~dankogai/Regexp-Optimizer-0.15/
La véritable question, c'est est-ce qu'on peut le limiter à de
vraies expressions rationnelles, ou est-ce qu'il faut supporter
toutes les extensions ad hoc. Parce que pour les vraies
expressions rationnelles, la solution simple est d'en créer un
automate fini. Ce qui serait le même, indépendamment de la forme
de l'expression initiale.
--
James Kanze home: www.gabi-soft.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34
Le but est d'essayer de gagner en vitesse en élaborant une expression compliquée plutôt que d'essayer de matcher consécutivement plusieurs expressions.
Si j'ai bien compris, tu veux (entre autres) mettre en facteur les chaînes communes à plusieurs motifs?
L'idée est peut-être saugrenue ceci dit :)
Non-non, elle est intéressante, et souvent évoquée. Mais la solution va dépendre du dialecte de regexp, et va rarement être optimale à coup sûr.
En Perl, par exemple, tu peux utiliser Regexp::Optimizer : http://search.cpan.org/~dankogai/Regexp-Optimizer-0.15/
La véritable question, c'est est-ce qu'on peut le limiter à de vraies expressions rationnelles, ou est-ce qu'il faut supporter toutes les extensions ad hoc. Parce que pour les vraies expressions rationnelles, la solution simple est d'en créer un automate fini. Ce qui serait le même, indépendamment de la forme de l'expression initiale.
-- James Kanze home: www.gabi-soft.fr Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34
tiissa
Manu wrote:
Laurent Wacrenier wrote:
Toutes les chaînes vérifiant toto[0-9]+ vérifient toto[0-9] et réciproquement.
OK (mais il m'a fallu un peu de temps).
Moi je n'ai pas compris.
A ma connaissance, "toto00" vérifie toto[0-9]+ mais pas toto[0-9] puisque la chaîne n'est pas terminée. Du coup, si mon langage est définit par toto[0-9], je n'ai pas envie d'y compter "toto00".
Pour certaines applications ce n'est peut-être pas un problème, mais je n'ai rien vu dans le fil précisant un tel contexte.
Qu'ai-je mal compris ?
Manu wrote:
Laurent Wacrenier wrote:
Toutes les chaînes vérifiant toto[0-9]+ vérifient toto[0-9] et
réciproquement.
OK (mais il m'a fallu un peu de temps).
Moi je n'ai pas compris.
A ma connaissance, "toto00" vérifie toto[0-9]+ mais pas toto[0-9]
puisque la chaîne n'est pas terminée.
Du coup, si mon langage est définit par toto[0-9], je n'ai pas envie d'y
compter "toto00".
Pour certaines applications ce n'est peut-être pas un problème, mais je
n'ai rien vu dans le fil précisant un tel contexte.
Toutes les chaînes vérifiant toto[0-9]+ vérifient toto[0-9] et réciproquement.
OK (mais il m'a fallu un peu de temps).
Moi je n'ai pas compris.
A ma connaissance, "toto00" vérifie toto[0-9]+ mais pas toto[0-9] puisque la chaîne n'est pas terminée. Du coup, si mon langage est définit par toto[0-9], je n'ai pas envie d'y compter "toto00".
Pour certaines applications ce n'est peut-être pas un problème, mais je n'ai rien vu dans le fil précisant un tel contexte.
Qu'ai-je mal compris ?
Cedric Foll
Manu wrote:
Bonjour,
Connaissez vous un moyen (un outil) permettant de fusionner 2 ou plusieurs expressions régulières en une unique expression ? Théoriquement cela me semble possible, mais je ne suis pas un expert en théorie des graphes/automates... Le but est d'essayer de gagner en vitesse en élaborant une expression compliquée plutôt que d'essayer de matcher consécutivement plusieurs expressions.
L'idée est peut-être saugrenue ceci dit :)
Il y a une bibliothèque Perl développée par un mongueur perl français qui fait ça (David Landgren). cf http://search.cpan.org/~dland/Regexp-Assemble-0.09/Assemble.pm
Connaissez vous un moyen (un outil) permettant de fusionner 2 ou
plusieurs expressions régulières en une unique expression ?
Théoriquement cela me semble possible, mais je ne suis pas un expert en
théorie des graphes/automates...
Le but est d'essayer de gagner en vitesse en élaborant une expression
compliquée plutôt que d'essayer de matcher consécutivement plusieurs
expressions.
L'idée est peut-être saugrenue ceci dit :)
Il y a une bibliothèque Perl développée par un mongueur perl français
qui fait ça (David Landgren).
cf http://search.cpan.org/~dland/Regexp-Assemble-0.09/Assemble.pm
Connaissez vous un moyen (un outil) permettant de fusionner 2 ou plusieurs expressions régulières en une unique expression ? Théoriquement cela me semble possible, mais je ne suis pas un expert en théorie des graphes/automates... Le but est d'essayer de gagner en vitesse en élaborant une expression compliquée plutôt que d'essayer de matcher consécutivement plusieurs expressions.
L'idée est peut-être saugrenue ceci dit :)
Il y a une bibliothèque Perl développée par un mongueur perl français qui fait ça (David Landgren). cf http://search.cpan.org/~dland/Regexp-Assemble-0.09/Assemble.pm
À (at) Wed, 16 Feb 2005 00:24:13 +0100, Cedric Foll écrivait (wrote):
Il y a une bibliothèque Perl développée par un mongueur perl français qui fait ça (David Landgren). cf http://search.cpan.org/~dland/Regexp-Assemble-0.09/Assemble.pm
Mais se pose alors la question de la sémantique du moteur. Pour rappel, selon les moteurs, l'expression (a|aa) ne reconnaît pas toujours la même chose.
Perl ne reconnaîtra jamais 'aa' (il retient la première alternative acceptable quelle que soit sa longueur) alors que certains moteurs cherchent la correspondance la plus longue possible (et donc potentiellement 'aa').
Regexp::Assemble optimise évidemment en respectant la sémantique du moteur RE de Perl.
-- Paul Gaborit - <http://www.enstimac.fr/~gaborit/>
À (at) Wed, 16 Feb 2005 00:24:13 +0100,
Cedric Foll <cedric.foll@ac-rouen.fr> écrivait (wrote):
Il y a une bibliothèque Perl développée par un mongueur perl français qui fait
ça (David Landgren).
cf http://search.cpan.org/~dland/Regexp-Assemble-0.09/Assemble.pm
Mais se pose alors la question de la sémantique du moteur. Pour rappel, selon
les moteurs, l'expression (a|aa) ne reconnaît pas toujours la même chose.
Perl ne reconnaîtra jamais 'aa' (il retient la première alternative acceptable
quelle que soit sa longueur) alors que certains moteurs cherchent la
correspondance la plus longue possible (et donc potentiellement 'aa').
Regexp::Assemble optimise évidemment en respectant la sémantique du moteur RE
de Perl.
--
Paul Gaborit - <http://www.enstimac.fr/~gaborit/>
À (at) Wed, 16 Feb 2005 00:24:13 +0100, Cedric Foll écrivait (wrote):
Il y a une bibliothèque Perl développée par un mongueur perl français qui fait ça (David Landgren). cf http://search.cpan.org/~dland/Regexp-Assemble-0.09/Assemble.pm
Mais se pose alors la question de la sémantique du moteur. Pour rappel, selon les moteurs, l'expression (a|aa) ne reconnaît pas toujours la même chose.
Perl ne reconnaîtra jamais 'aa' (il retient la première alternative acceptable quelle que soit sa longueur) alors que certains moteurs cherchent la correspondance la plus longue possible (et donc potentiellement 'aa').
Regexp::Assemble optimise évidemment en respectant la sémantique du moteur RE de Perl.
-- Paul Gaborit - <http://www.enstimac.fr/~gaborit/>
