mageekblog - Mot-clé - soundex - CommentairesLe blog personnel de Frédéric Hardy. Au menu, PHP, agilité, FreeBSD, cuisine et photographies.2021-12-02T08:20:54+01:00Frédéric Hardyurn:md5:26874ca5b8cd4cac8d08b0e68e64f63aDotclearDocteur Levenshtein, je présume ? - mageekguyurn:md5:c9c2ac00cc03257206e0df8ad79925a42011-10-17T17:22:05+02:002011-10-17T16:25:10+02:00mageekguy<p>@<a href="http://blog.mageekbox.net/?post/2011/10/12/Docteur-Levenshtein%2C-je-pr%C3%A9sume#c3350" rel="nofollow">Matthieu</a> : 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.</p>
<blockquote><pre><code><?php
$arg1 = 'directory';
$arg2 = 'DIRECTORY';
$arg3 = 'Directory';
var_dump(levenshtein($arg1, $arg2));
var_dump(levenshtein($arg1, $arg3));
var_dump(levenshtein(metaphone($arg1), metaphone($arg2)));
var_dump(levenshtein(metaphone($arg1), metaphone($arg3)));
?></code></pre></blockquote>Docteur Levenshtein, je présume ? - Matthieuurn:md5:f9395bb759728da80cb19e7884e2b5922011-10-14T21:19:55+02:002011-10-17T16:25:10+02:00Matthieu<p>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 ?</p>Docteur Levenshtein, je présume ? - Amauryurn:md5:1c360d2822f8e790f68bac10db21e7612011-10-14T16:00:44+02:002011-10-14T16:06:57+02:00Amaury<p>Merci pour cet intéressant article.<br />
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 (<a href="http://pecl.php.net/package/stem" title="http://pecl.php.net/package/stem" rel="nofollow">http://pecl.php.net/package/stem</a>) 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.</p>Docteur Levenshtein, je présume ? - francois.murn:md5:2bfefd34b35e20c6ac62e8f7ee7a59122011-10-14T00:04:51+02:002011-10-14T06:33:51+02:00francois.m<p>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.<br />
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.<br />
Ou alors en choisissant bien son wording de paramètres !</p>Docteur Levenshtein, je présume ? - Ivan Enderlinurn:md5:becd16dcd633a8724a42000f806978fc2011-10-13T09:34:10+02:002011-10-13T12:41:45+02:00Ivan Enderlin<p>@Julien Breux: s/Enderline/Enderlin/ <img src="/themes/default/smilies/wink.png" alt=";-)" class="smiley" /> et quand j'ai écris cet algorithme, j'étais encore jeune (2ème année de fac) …</p>
<p>@mageekguy : Ça ne m'aurait pas dérangé une seconde !</p>
<p>Il existe un livre vraiment génial sur le sujet <q>Algorithms on Strings</q>, par Maxime Crochemore, Christophe Hancart et Thierry Lecroq.</p>
<p>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.</p>
<p>Il existait en français à une époque mais je crois qu'il n'a jamais été réédité.</p>
<p>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 <a href="http://j.mp/nOHw8P" title="http://j.mp/nOHw8P" rel="nofollow">gratuitement au format PDF</a> !</p>
<p>La version anglaise doit être <a href="http://www.cambridge.org/gb/knowledge/isbn/item1172625/?site_locale=en_GB" title="http://www.cambridge.org/gb/knowledge/isbn/item1172625/?site_locale=en_GB" rel="nofollow">achetée</a>.</p>Docteur Levenshtein, je présume ? - Julien Breuxurn:md5:df172773604bdfcfabf1664f3a4590182011-10-12T18:30:43+02:002011-10-12T19:11:07+02:00Julien Breux<p>@Mageekguy : Merci pour l'article !<br />
@Ivan Enderline : Ravis de voir que l'âme du chercheur n'est pas loin !</p>Docteur Levenshtein, je présume ? - mageekguyurn:md5:27bda1f26ae95a0c0d6c0c4726c5584e2011-10-12T14:56:44+02:002011-10-12T13:58:21+02:00mageekguy<p>@<a href="http://blog.mageekbox.net/?post/2011/10/12/Docteur-Levenshtein%2C-je-pr%C3%A9sume#c3338" rel="nofollow">Mathieu ROBIN</a> : 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.</p>
<p>Ce n'est pas comme s'il s'agissait d'un traitement récurrent.</p>Docteur Levenshtein, je présume ? - Mathieu ROBINurn:md5:e144836f3dbd7aaba0351c06a64ba2fc2011-10-12T14:49:10+02:002011-10-12T13:58:21+02:00Mathieu ROBIN<p>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.</p>
<p>Ou alors ça fait partie de ce que tu as allégé pour simplifier ton article ?</p>Docteur Levenshtein, je présume ? - mageekguyurn:md5:76f108dd12f656cecda04a1f010978542011-10-12T14:40:33+02:002011-10-12T13:41:30+02:00mageekguy<p>@<a href="http://blog.mageekbox.net/?post/2011/10/12/Docteur-Levenshtein%2C-je-pr%C3%A9sume#c3334" rel="nofollow">Ivan Enderlin</a> : je savais que tu n'allais pas pouvoir t'en empêcher :).</p>
<p>Pour être honnête, j'ai même pensé écrire ce billet à quatre mains avec toi, afin que tu apportes la touche mathématique.</p>Docteur Levenshtein, je présume ? - mageekguyurn:md5:922127b7ab01b9f433365ca908f881de2011-10-12T14:36:18+02:002011-10-12T13:36:52+02:00mageekguy<p>@<a href="http://blog.mageekbox.net/?post/2011/10/12/Docteur-Levenshtein%2C-je-pr%C3%A9sume#c3335" rel="nofollow">Julien</a> : tu as raison, j'ai corrigé, merci.</p>
<p>Il y a au moins un qui lit le code en détail ;).</p>Docteur Levenshtein, je présume ? - Julienurn:md5:be181b653c7321b6d4124102b6bbfa472011-10-12T14:27:58+02:002011-10-12T13:38:40+02:00Julien<p>J'ai peut-être mal saisi mais ce ne devrait pas plutôt être <code>$levenshtein = levenshtein(metaphone($availableArgument), $userMetaphone);</code>
au lieu de <code>$levenshtein = levenshtein(metaphone($availableArgument), $userArgument);</code> ?</p>
<p>Très intéressant sinon, merci.</p>Docteur Levenshtein, je présume ? - Ivan Enderlinurn:md5:93f608ef3ad0f2202de47f539e68703f2011-10-12T14:15:39+02:002011-10-12T13:34:39+02:00Ivan Enderlin<p>Hello :-),</p>
<p>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.</p>
<p>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 : <a href="http://mozilla.hoa-project.net/Aquila/literature/html/." title="http://mozilla.hoa-project.net/Aquila/literature/html/." rel="nofollow">http://mozilla.hoa-project.net/Aqui...</a></p>
<p>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.</p>
<p>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 : <a href="http://mozilla.hoa-project.net/Aquila/literature/html/#Search_with_an_approximated_patterns_with_differences." title="http://mozilla.hoa-project.net/Aquila/literature/html/#Search_with_an_approximated_patterns_with_differences." rel="nofollow">http://mozilla.hoa-project.net/Aqui...</a> 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 ;-).</p>Docteur Levenshtein, je présume ? - Guileurn:md5:e50b213c2a7f71856fdd6d48870b2a592011-10-12T13:56:51+02:002011-10-12T13:09:15+02:00Guile<p>Ah merci!</p>
<p>C'est clair que le coup du --testIt était piègeux ^_^</p>Docteur Levenshtein, je présume ? - Steufurn:md5:4e4a76296c5666cbf3e2287c9f406d4f2011-10-12T13:17:52+02:002011-10-12T12:34:48+02:00Steuf<p>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.</p>
<p>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.</p>
<p>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...</p>Docteur Levenshtein, je présume ? - Sébastien Doucheurn:md5:7fce372ea9eee676058f37ccef3335c22011-10-12T13:14:04+02:002011-10-12T12:18:04+02:00Sébastien Douche<p>>Or, à chaque fois, les utilisateurs avaient tapé --testit au lieu de --testIt</p>
<p>En même temps il faut être pervers pour mettre des majuscules dans les options ! <img src="/themes/default/smilies/smile.png" alt=":)" class="smiley" /></p>Docteur Levenshtein, je présume ? - Jérémyurn:md5:f8820f395fcd1ae7a0f7da0b9efce8c52011-10-12T13:09:47+02:002011-10-12T12:18:04+02:00Jérémy<p>Article très très intéressant comme à votre habitude ! <img src="/themes/default/smilies/smile.png" alt=":)" class="smiley" /></p>
<p>Grâce à vous je connais maintenant une nouvelle fonction très intéressante (levenshtein) !</p>
<p>Bonne continuation !</p>