Ha ok, je ne connaissais pas cette variante syntaxique.
Pour répondre à ta question, il faut que tu te figures comment fonctionne un automate: en gros un ensembre d'états reliés entre eux par des chemins (les "transitions").
H[^o]*o est avantageux parce qu'il se résume au graphe suivant:
[H] -> [tout sauf o] -> [o] -> FIN
\-> [o] -> FIN
H.*o lui, se fait ainsi:
[H] -> [tout, y compris o] -> o -> FIN
\-> [o] -> FIN
Autrement dit, dans le premier cas, on a un automate déterministe (DFA), et dans le second cas on a un automate non-déterministe (NFA). La différence entre les deux, c'est que dans le cas du DFA, quand on est dans un état donné, il n'y a jamais deux transitions possible pour un même symbole en entrée (disons une lettre dans notre cas). Ca peut sembler pas grand chose, mais au niveau de l'implémentation et de la complexité, ça n'a rien à voir.
En effet, le parcours d'un automate DFA est par nature beaucoup plus rapide qu'un automate NFA parce que le premier peut s'effectuer en une seule passe et sans backtrack, alors que dans le second cas il faut soit le convertir en DFA (mais ça peut engendrer des DFA monstrueux, et ce n'est pas toujours envisageable), soit avoir un moteur NFA (qui backtracke ou qui parcourt en parallèle si on est riche en RAM), qui sont toujours (beaucoup) plus complexe et plus lent qu'un moteur DFA.
Evidemment, dans le cas de H.*o, si la chaine en entrée est pas trop grande, tu ne verras pas la différence en terme de traitement derrière, mais il n'empêche que le traitement que cela implique est "par nature" plus important.
[^] # Re: je me lance...
Posté par deadbeef . En réponse au message Expressions régulières: votre avis.... Évalué à 3.
Pour répondre à ta question, il faut que tu te figures comment fonctionne un automate: en gros un ensembre d'états reliés entre eux par des chemins (les "transitions").
H[^o]*o est avantageux parce qu'il se résume au graphe suivant:
[H] -> [tout sauf o] -> [o] -> FIN
\-> [o] -> FIN
H.*o lui, se fait ainsi:
[H] -> [tout, y compris o] -> o -> FIN
\-> [o] -> FIN
Autrement dit, dans le premier cas, on a un automate déterministe (DFA), et dans le second cas on a un automate non-déterministe (NFA). La différence entre les deux, c'est que dans le cas du DFA, quand on est dans un état donné, il n'y a jamais deux transitions possible pour un même symbole en entrée (disons une lettre dans notre cas). Ca peut sembler pas grand chose, mais au niveau de l'implémentation et de la complexité, ça n'a rien à voir.
En effet, le parcours d'un automate DFA est par nature beaucoup plus rapide qu'un automate NFA parce que le premier peut s'effectuer en une seule passe et sans backtrack, alors que dans le second cas il faut soit le convertir en DFA (mais ça peut engendrer des DFA monstrueux, et ce n'est pas toujours envisageable), soit avoir un moteur NFA (qui backtracke ou qui parcourt en parallèle si on est riche en RAM), qui sont toujours (beaucoup) plus complexe et plus lent qu'un moteur DFA.
Evidemment, dans le cas de H.*o, si la chaine en entrée est pas trop grande, tu ne verras pas la différence en terme de traitement derrière, mais il n'empêche que le traitement que cela implique est "par nature" plus important.
Si tu veux les maths derrière tout ça:
http://en.wikipedia.org/wiki/Deterministic_finite_state_mach(...)
http://en.wikipedia.org/wiki/Nondeterministic_finite_state_m(...)