Discussion :

[Sakalam]

Bonjour,

Je m'arrache les cheveux pour réussir à écrire un motif qui décrirait les chaînes de caractères s'écrivant avec, par exemple, un A, deux B et deux C au plus.

Ainsi, les chaînes :
CAC, CAB, BAB
seraient reconnues

mais pas BABA ou CACA (utilisant deux fois la lettre A)

Existe-t-il un moyen avec une expression régulière d'exprimer cela. J'ai épluché la doc, notamment les fameux slides d'Hugo Etiévant, mais je n'arrive pas à goupiller les opérateurs pour obtenir le résultat voulu.

Merci de vos suggestions

Sakalam

[Blustuff]

Ca s'écrit facilement sous la forme négative. Dans un programme PHP c'est tout à fait jouable d'utiliser l'expression régulière ne reconnaissant que les mots n'appartenant pas à ce langage.

[Sakalam]

Mon problème porte principalement sur les occurrences des lettres (dans l'exemple que je donnais, on pouvait n'utiliser qu'un seul A).

La négation serait donc de définir les mots qui s'écrivent avec deux A ou + ?

Comment combiner cette contrainte avec celles des autres lettres (un OR) ?

Je continue à chercher, mais je ne suis pas un pro des regexp, (>=2 et <2 c'est aussi difficile pour moi à écrire...) alors si vous pouviez être un peu explicites, je vous serai très reconnaissant.

S.

[mathieu]

je pense que les expression régulières sont plus pratique si tu connais la position de chaque lettre

là tu poses des conditions sur les lettres quelques soit leur position donc dans ce cas je ferrais plutôt un parcours de la chaine en comptant le nombre de chaque caractère et à la fin je regarde si le compte est bon

[Korko Fain]

Il te serai possible de faire ça en regex MAIS seulement si ton mot est tres court car il te faudrait faire tout les cas acceptables.
Parcourir la chaine et compter est à mon avis bien mieux et plus rapide.

[Blustuff]

Sakalam, oui, c'est ça.

Un mot qui s'écrit avec 2 a :

Code :

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

.*a.*a.*

avec 3 b :

Code :

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

.*b.*b.*b.*

Tu cherches les mots qui s'écrivent avec au plus un a, deux b et deux c. La négation de la proposition "w est un mot cherché" s'écrit effectivement :

w s'écrit avec au moins 2 a, ou au moins trois b, ou au moins trois c.

Pour s'en convaincre, il suffit de voir que tout mot qui répond à cette seconde condition ne répond pas à la première, et que tout mot qui répond à la première ne peut pas répondre à la seconde.

Ce qui donne l'expression régulière :

.*a.*a.*|.*b.*b.*b.*|.*c.*c.*c.*

L'automate complémentaire est sacrément moins beau...

[Korko Fain]

ce n'est pas . qu'il faut utiliser mais [^a]

[Blustuff]

Pas si on inverse la tendance à la gourmandise, ce qui sera plus lisible. Cf la documentation de preg.

[Korko Fain]

non puisque meme si tu inverse la gourmandise, .* comprend le caractère a donc il sera compris dedans.

Et de toute façons, on t'apprendra toujours à eviter AU MAXIMUM le ., TOUJOURS préférer les classes ou les options qui sont BEAUCOUP moins gourmandes pour le moteur de regex.

Tu peux utiliser une syntaxe comme celle-ci :

Code :

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

#^(?:[^a]*?a){6}[^a]*$#

Pour trouver des mots qui contiennent 6 'a' et rien de plus.
1 mot a la fois
Sinon tu peux faire 1 mot par ligne et tu ajoutes apres le # de fin un 'm'

[Blustuff]

Inverser la tendance à la gourmandise, ça veut dire qu'on prends le minimum de caractères. Ce qui signifie que dès qu'on trouve un a, on sort du .*

Code :

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

1
2
3
4
5
6
7
8
9
10
11
$ExpressionReguliere = "/a.*a|b.*b.*b|c.*c.*c/U";
// ou bien
$ExpressionReguliere = "/(?:a.*){2}|(?:b.*){3}|(?:c.*){3}/U";
// ou bien ...
 
echo !preg_match($ExpressionReguliere, "abcdaba") ? "VRAI" : "FAUX";
echo "\n";
echo !preg_match($ExpressionReguliere, "abbcd") ? "VRAI" : "FAUX";
echo "\n";
echo !preg_match($ExpressionReguliere, "accdbc") ? "VRAI" : "FAUX";
echo "\n";

Code :

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

1
2
3
FAUX
VRAI
FAUX

Choisissez votre solution, elles fonctionnent très bien toutes les trois.

[Korko Fain]

C'est comme quand tu code en objet et que tu met tous tes attributs et tes méthodes en public, ça fonctionne mais c'est crade
Toujours réduire au plus petit ensemble possible pour eviter les surprises ^^

[Blustuff]

Il faut toujours préciser ce qu'on appelle "propre", "crade", "sale" etc. et au maximum éviter de l'utiliser. Ces termes sont très à la mode, et ont la particularité de masquer les raisons qui font qu'on utilise ou qu’on n’utilise pas une solution.

Ici, la propreté d'une expression régulière pourrait être sa lisibilité. Demandez-vous simplement laquelle est la plus lisible. On peut revenir à vos raisons, aussi : "la rapidité". Et c'est là que la théorie énoncée plus haut sur l'ignorance que crée la qualification "sale" se voit en pratique. Le temps que vous gagnez à ne pas utiliser de points, vous le perdez à utiliser des regroupements. C'est donc typiquement un cas, où l'argument de la vitesse n'est pas valable, car si on voulait faire vite, il faudrait systématiquement développer les expressions, et faire quelque chose qui va à l'encontre de la lisibilité.

Réduire l'ensemble des possibilité n'est pas un avantage de votre expression régulière. Avec le flag s ajouté, les langages reconnus sont strictement les mêmes. On ne gagne donc rien.

Il faut avoir un minimum de maîtrise de ces choses là, avant de se permettre de qualifier quelque chose de "sale".

Les solutions ici, n'ont rien de propre, ou de sale. Elles conviennent toutes, et n'ont pas d'inconvénient qui vale la peine d'un débat.

Sakalam, choisissez la solution qui vous la plus claire à vos yeux.

[Sakalam]

Je suis content d'avoir initié un débat sur la propreté ou la saleté dans les expressions régulières.
Cela dit, pour revenir à mon problème qui était, pour simplifier :
La liste des mots s'écrivant avec un A au maximum et deux C au maximum,
si je passe par la négation, étant donné que les mots à tester seront extraits d'un dictionnaire du français, est que je suis aussi obligé de dire que le mot recherché est sans D, sans E, sans F, sans G...

L'expression devient alors un peu longue (mais s'il n'y a pas d'autre moyen, je serai bien obligé de l'écrire ainsi)


Sakalam


PS
Aimez vous les uns les autres!

[Blustuff]

Peut être que les expressions régulières ne sont pas adaptées à votre problème, qu'il est d'ailleurs difficile de saisir. Si vous voulez exclure des lettres, la modification de l'expression est simple.

[Sakalam]

Je n'ai peut-être pas été assez clair effectivement, mais imaginez que vous avez une petite tablette en bois devant vous portant sept lettres et que vous vouliez savoir tous les mots que l'on peut faire avec ces sept lettres...

Il est possible que les expressions régulières ne sont pas adaptées à mon problème. Je voulais réduire la taille de l'espace global pour la résolution d'un problème de jeu de lettres, un genre de prétraitement qui éliminerait les mots impossibles avec les lettres en main.

Je continue le combat

S.

[Korko Fain]

Premierement Blustuff avant de sous entendre que je ne maitrise pas les regex j'aimerai vous voir plus souvent sur ce forum à aider à ce propos.

Ensuite, je soutien mon terme de "crade" qui signifie l'inverse de ce que l'on apprend à tout codeur lors de sa formation : "la Propreté du code". La propreté ne signifie pas uniquement la lisibilité mais aussi la sécurité, la rapidité du code. Il faut toujours que le code soit le plus pret possible de la demande et compréhensible du lecteur.

Le fait qu'il faille OBLIGATOIREMENT le U (ou le ?) comme option pour que votre regex fonctionne n'aide pas à sa compréhension. Le terme français du . est "n'importe quel caractère". Ceci n'aide pas à la compréhension par un qidam qui ne connait pas les regex. Il est bien plus simple de comprendre "n'importe quel caractère hormis le a".

Et si vous passez plus de temps à écrire [^a] que . c'est de l'ordre de la milliseconde et il sera bien plus long à revenir sur un code qui accepte trop que de développer un code qui est restreint à ce qui est nécéssaire. Je parle en connaissance de cause sur des problèmes de sécurité notemment.

Et quant à l'option s, faire une regex comme [abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789] revien aussi à la meme chose que [a-zA-Z0-9]. Il y a toujours plusieurs chemins pour arriver à la meme chose, mais ils ne sont pas tous aussi bons. Je n'ai pas pour autant dit que ma solution soit la meilleure possible.

Mais il est vrai que ce n'est qu'un problème de présentation ici on peut dire... La différence au niveau du temps est de l'ordre de 10^-5 secondes et encore

[Blustuff]

En fait pour ce problème, l'utilisation des expressions régulières de cette manière ne va pas accèlérer l'algorithme.

Le nombre de mots qu'on peut former avec 7 lettres est inférieur à 8! c'est à dire à peu près à un million. Dans ce sens, vérifier qu'un mot appartient au dictionnaire, avec une table de hashage se fait dans un temps raisonnable, mais trop long pour vous ?

Il paraît qu'il y a 60 000 mots dans la langue française. Tester les mots un par un peut vite revenir cher, il n'y a qu'un petit facteur entre 60 000 et un million.

Si vous avez plusieurs recherches à faire, vous pouvez créer un index. Un index alphabétique tout bête en forme d'arbre est facile à parcourir si vous savez les lettres que vous avez en main.

Mots qui commencent par un a <- on y va seulement si on a un a
| Mots qui commencent par aa <- on y va seulement si on a un deuxième a
| Mots qui commencent par ab <- on y va seulement si on a un b
| ...
Mots qui commencent par un b <- on y va seulement si on a un b
| ...
...

L'index est facile à construire à partir d'une liste de mot (on ne construit que les branches qui mènent à un mot) et facile à parcourir. On considèrera beaucoup moins que 60 000 noeuds dans l'index.


Dans les autres solutions, il y a une fonction qui calcule les lettres d'un mot :

http://fr.php.net/manual/fr/function.count-chars.php

[Blustuff]

Ensuite, je soutien mon terme de "crade" qui signifie l'inverse de ce que l'on apprend à tout codeur lors de sa formation : "la Propreté du code". La propreté ne signifie pas uniquement la lisibilité mais aussi la sécurité, la rapidité du code. Il faut toujours que le code soit le plus pret possible de la demande et compréhensible du lecteur.

Justement, j'en parlais. Votre solution ne présente ni rapidité, ni sécurité, ni lisibilité supplémentaire. Elle est bonne, c'est tout.

Code :

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

a.*a

se lit parfaitement, "a", quelque chose entre les deux, et un autre "a".

C'est lisible pour la même raison que celle qui fait qu'on emploie des automates non déterministes : ils sont plus simples à appréhender, mais pas à simuler. L'expression ci-dessus peut être écrite par un automate non déterministe extrêmement simple. Trois états représentant chacun le nombre de a lus. On passe d'un état au suivant par une transition pour acceptant "a". Le dernier état est final. On rajoute des transitions d'un état vers lui même, pouvant accepter n'importe quel caractère, y compris le a. La déterminisation revient à retirer le a.

L'argument du non déterminisme peut vous sembler peu crédible. Mais le plus connu des algorithmes de création d'automate à partir d'une expression régulière est la preuve qu'on comprend beaucoup mieux cet automate non déterministe : il est la composition d'éléments d'automate, correspondant à la composition d'éléments de l'expression régulière. Dans la définition d'expression régulière, cette utilisation de l'étoile est tout à fait correcte. La notion de gourmandise est ajoutée pour l'implantation, sans quoi on perd beaucoup en efficacité.

L'utilisation de .* c'est éviter de penser à comment c'est implémenté en dessous, ce qui est une pratique courante dans les langages de haut niveaux. Je me base sur l'intuition qu'on a des expressions régulières pour l'écrire. Pour le lecteur qui ne connaît pas les expressions régulières, au contraire, le "." et l'"*" sont les choses qu'on voit le plus vite. Il lira exactement ce que j'ai précisé plus haut :

un "a", n'importe quelle série de caractère, et un autre "a"

La sémantique est parfaitement claire, la concision aidant.

Si le U vous gêne, utilisez le "?" derrière l'étoile, qui a le même effet, mais localement. Syntaxiquement, ce n'est pas pire que d'éviter la capture des parenthèses.

En termes de sécurité, il vaut mieux savoir comment fonctionnent les fonctions qu'on utilise. Les options y compris, car sans elles, on loupe un certain nombre de subtilités, qui effectivement amèneraient à décourager l'utilisation du ".". Si quelqu'un doit écrire un système de sécurité et qu'il ne comprend pas les expressions régulières PERL qu'il doit utiliser, effectivement, dans ce cas précis, apprenez lui à ne pas utiliser le ".".

Mais il est vrai que ce n'est qu'un problème de présentation ici on peut dire... La différence au niveau du temps est de l'ordre de 10^-5 secondes et encore

Pour des chaines de quelques dizaines de caractères, la différence est inférieure. Elle est de l'ordre de la microseconde pour une expression dont le temps d'éxécution est de l'ordre de dizaine de microseconde. Par ailleurs, il est difficile de savoir quelle expression régulière sera la plus rapide, et les benchmark penchent du coté d'expressions sans point, mais sans parenthèses non plus.