En effet, grâce à cette dernière, l'ordinateur ne voit plus les choses uniquement en noir et blanc, mais en niveau de gris.
En clair, lorsque la logique floue est utilisée, une réponse à une question ne sera pas forcément un 1 ou un 0 , mais un nombre compris entre 0 et 1.
Septique ? Cela peut se comprendre, et pourtant, les utilisateurs de Git, par exemple, voit régulièrement, surtout s'il tape aussi mal que moi, les effets de la logique floue.
En effet, Git, lorsqu'il ne reconnait pas l'un des arguments qui lui est passé, a le bon goût de proposer des alternatives possibles et surtout crédibles.
Je me suis d'ailleurs toujours demandé la raison pour laquelle cela a été implémenté dans Git vu son ergonomie exécrable, mais c'est peut être l'illustration parfaite du fait que le besoin crée la fonctionnalité, et de toute façon, ce n'est pas la question.
Ainsi, si par maladresse, vous tapez par exemple satus
au lieu de status
, Git vous proposera des alternatives :
fch@Storm:~/Atoum(master *) 165> git satus git: 'satus' is not a git command. See 'git --help'. Did you mean this? status
L'intérêt est évident, et j'ai donc décidé d'implémenter la même chose dans atoum, mon framework de tests unitaires pour PHP 5.3, d'autant plus que j'ai eu quelques rapports de bug m'informant que l'argument --testIt
, qui permet d'exécuter simplement les tests unitaires de atoum, ne fonctionnait pas.
Or, à chaque fois, les utilisateurs avaient tapé --testit
au lieu de --testIt
.
Il existe plusieurs fonctions permettant de faire de la logique floue en PHP dans ce contexte, tel que soundex()
, metaphone()
et levenshtein()
, qui donne son titre à ce billet.
Les fonctions soundex()
et metaphone()
permettent d'obtenir, sous la forme d'une chaîne de caractères, ce que j'appelerais une empreinte sonore
de la chaîne de caractères qu'elles reçoivent en argument.
En effet, à la différence de md5()
ou sha1()
qui calcule l'empreinte d'une chaîne de caractères à partir des symboles qui la compose, soundex()
et metaphone()
calculent l'empreinte à partir de la façon dont la chaîne se prononce.
Ainsi, si les empreintes sha-1 des chaînes toto
et ToTo
seront différentes, leurs empreintes sonores seront identiques puisque ces deux chaînes se prononcent de la même manière.
De même, si les empreintes sha-1 des chaînes status
et statu
seront très différentes, leurs empreintes sonores seront par contre très proche.
C'est d'ailleurs la raison pour laquelle nous allons utiliser la fonction levenshtein()
, puisqu'elle permet de calculer une distance entre deux chaînes de caratères.
Deux chaînes identiques auront ainsi une distance de 0, tandis que deux chaînes différentes auront une distance plus ou moins grande en fonction de leur degré de similitude.
Concrètement, il suffit donc de calculer l'empreinte sonore de l'argument saisi par l'utilisateur et qui n'a pas été reconnu comme valide, puis de calculer la distance de levenshtein de cette empreinte avec l'empreinte sonore de chaque argument possible.
Il y a en effet de fortes chances que l'argument ayant la proximité la plus proche avec l'argument saisi par l'utilisateur soit celui que ce dernier a voulu utiliser.
<?php $availableArguments = array('--directory', '--testIt', '--configuration'); $userArgument = '--direct'; $userMetaphone = metaphone($userArgument); $minLevenshtein = null; $closestArgument = null; foreach ($availableArguments as $availableArgument) { $levenshtein = levenshtein(metaphone($availableArgument), $userMetaphone); if ($minLevenshtein === null || $levenshtein < $minLevenshtein) { $minLevenshtein = $levenshtein; $closestArgument = $availableArgument; } } var_dump($closestArgument); ?>
Le code ci-dessous a évidemment été très simplifié, mais l'idée générale telle qu'elle a été implémentée dans atoum est bien présente, ce qui permet d'obtenir le résultat suivant :
fch@Storm:~/Atoum(master *) 167> php scripts/runner.php --direcdory tests/classes Error: Argument '--direcdory' is unknown, did you mean '--directories' ?
Évidemment, ce mécanisme a ses limites, et si l'utilisateur fait vraiment n'importe quoi, il ne permettra pas de corriger le tir.
Cependant, dans la très grande majorité des cas, il donne d'excellent résultat et permet d'améliorer l'expérience utilisateur de manière significative.
De plus, cette technique a deux inconvénients dont il faut tenir compte afin d'en tirer le meilleur parti.
Tout d'abord, les fonctions soundex()
et metaphone()
sont particulièrement adaptées à la langue anglaise, et il faudra donc se tourner vers des variantes des algorithmes sous-jacents pour gérer efficacement d'autres langages.
Ensuite, ces fonctions sont relativement gourmandes en ressource, et il est donc impératif de prendre cela en compte leur de leur mise en œuvre, sous peine d'obtenir des mauvaises performances en fonction du volume et de la nature des information à traiter.
16 réactions
1 De Jérémy - 12/10/2011, 13:09
Article très très intéressant comme à votre habitude !
Grâce à vous je connais maintenant une nouvelle fonction très intéressante (levenshtein) !
Bonne continuation !
2 De Sébastien Douche - 12/10/2011, 13:14
>Or, à chaque fois, les utilisateurs avaient tapé --testit au lieu de --testIt
En même temps il faut être pervers pour mettre des majuscules dans les options !
3 De Steuf - 12/10/2011, 13:17
J'ai déjà fais des algorithmes de recherche sur la base de soundex couplé à levenshtein pour intégrer dans les résultats des alternatives et les ordonner par rapport à un scroring... Bref.
La principale difficulté (dans le cadre de moteur de recherche complet) c'est de trouver le juste équilibre, sans compter que comme préciser pour soundex il faut passer par des algorithme dépendant de la langue utilisée sous peine de trouver des résultats parfois bizarres.
Cette méthode pose néanmoins un soucis c'est sur les chaines courtes ou le système n'est pas du tout fiable et parfois beaucoup trop "flou", en gros plus la chaîne est longue plus fine est la correspondance, plus la chaîne est courte et plus on peut se retrouver avec des résultats qui n'ont strictement rien avoir...
4 De Guile - 12/10/2011, 13:56
Ah merci!
C'est clair que le coup du --testIt était piègeux ^_^
5 De Ivan Enderlin - 12/10/2011, 14:15
Hello :-),
J'ai quelques remarques et compléments à faire à propos de ton article. Il existe des algorithmes plus rapides que l'algorithme de Levenshtein ou alors plus abstraits/génériques. Pour la première catégorie, je citerai l'algorithme de recherche par motifs approchés (avec différences, basé sur la monotonie de la diagonale), et pour la seconde catégorie, je citerai la distance de Hamming.
J'ai étudié ça quelques mois (par hasard) avant de travailler pour Mozilla pendant mon stage (il y a de ça bientôt 3 ans je crois). J'ai réutilisé ces connaissances pour proposer une version améliorer de la recherche dans les pages Web. Le projet s'appelait Aquila et on trouvera tout ici : http://mozilla.hoa-project.net/Aqui...
Dans la section 3.1.1 Pattern matching algorithms, paragraphe Approximated search, on trouvera un court résumé de mon étude sur les différents algorithmes avec les plus et les moins (ça tient en quelques paragraphes, on s'intéresse à un en particulier ici). La section 3.1.2 s'intéresse aux approches phonétiques pour ceux que ça intéresse. En fait, c'est plutôt un bref état de l'art.
J'ai implémenté et adapté l'algorithme de recherche par motifs approchés à PHP. Cet algorithme est présent en annexe de ce document : http://mozilla.hoa-project.net/Aqui... Je te conseille d'y jeter un oeil. Il est simple (dans sa structure, mais pas à comprendre !) et rapide. Je n'ai pas fait de comparaison avec ta solution, je te laisse le soin de le faire ;-).
6 De Julien - 12/10/2011, 14:27
J'ai peut-être mal saisi mais ce ne devrait pas plutôt être
$levenshtein = levenshtein(metaphone($availableArgument), $userMetaphone);
au lieu de$levenshtein = levenshtein(metaphone($availableArgument), $userArgument);
?Très intéressant sinon, merci.
7 De mageekguy - 12/10/2011, 14:36
@Julien : tu as raison, j'ai corrigé, merci.
Il y a au moins un qui lit le code en détail ;).
8 De mageekguy - 12/10/2011, 14:40
@Ivan Enderlin : je savais que tu n'allais pas pouvoir t'en empêcher :).
Pour être honnête, j'ai même pensé écrire ce billet à quatre mains avec toi, afin que tu apportes la touche mathématique.
9 De Mathieu ROBIN - 12/10/2011, 14:49
Je me disais que plutôt que de recalculer l'empreinte de tous les arguments envisageables à chaque fois : ne serait t-il pas pertinent de les calculer au préalable et du coup d'utiliser le résultat directement dans le code de comparaison ? Quitte à laisser un commentaire à chaque ligne pour expliquer à quoi correspond chaque empreinte.
Ou alors ça fait partie de ce que tu as allégé pour simplifier ton article ?
10 De mageekguy - 12/10/2011, 14:56
@Mathieu ROBIN : inutile, le mécanisme se déclenche uniquement en cas d'argument invalide et le volume et le type des données manipulées ne le justifie pas.
Ce n'est pas comme s'il s'agissait d'un traitement récurrent.
11 De Julien Breux - 12/10/2011, 18:30
@Mageekguy : Merci pour l'article !
@Ivan Enderline : Ravis de voir que l'âme du chercheur n'est pas loin !
12 De Ivan Enderlin - 13/10/2011, 09:34
@Julien Breux: s/Enderline/Enderlin/
et quand j'ai écris cet algorithme, j'étais encore jeune (2ème année de fac) …
@mageekguy : Ça ne m'aurait pas dérangé une seconde !
Il existe un livre vraiment génial sur le sujet
, par Maxime Crochemore, Christophe Hancart et Thierry Lecroq.Les trois auteurs sont des références dans le domaine (et tous sont français !) au niveau international et ce livre est une référence absolue.
Il existait en français à une époque mais je crois qu'il n'a jamais été réédité.
En revanche, je viens de découvrir sur le site de l'auteur principal (Maxime Crochemore) que le livre en français est téléchargeable gratuitement au format PDF !
La version anglaise doit être achetée.
13 De francois.m - 14/10/2011, 00:04
Comme le souligne Steuf, il faut bien garder à l'esprit les limites de ce genre d'algo. Si par mégarde deux chaînes ont une distance proche, la mauvaise frappe de l'une pourrait malencontreusement mener à l'autre, ce qui peut être catastrophique dans le cas de commandes.
On pourrait palier à cela en ne gardant le correctif que si la distance entre les deux empreintes les plus proches est supérieure à un seuil de tolérance.
Ou alors en choisissant bien son wording de paramètres !
14 De Amaury - 14/10/2011, 16:00
Merci pour cet intéressant article.
Sujet connexe : Pour faire de la recherche sur des mots (au contraire de la recherche sur des commandes, qui est le sujet de cet article), on a souvent besoin de pouvoir en extraire les racine lexicales. La bibliothèque Stem (http://pecl.php.net/package/stem) est là pour ça. Elle fonctionne très bien, et il est possible de choisir d'installer des packages dans un assez grand nombre de langues.
15 De Matthieu - 14/10/2011, 21:19
Pourquoi ne pas faire un levenshtein() directement entre le mot tapé et les commandes possibles ? Quel est l'intérêt ici de passer par la consonance des mots, étant donné qu'il s'agit de corriger une faute de frappe, qui se limite généralement à 1 ou 2 caractères ?
16 De mageekguy - 17/10/2011, 17:22
@Matthieu : L'utilisation de metaphone() n'a rien d'obligatoire mais permet d'avoir une plus grande précision, et donc de pouvoir, dans les cas optimum, substituer l'argument mal saisi par l'utilisateur par l'argument qu'il voulait effectivement utiliser.