Recherche phonétique en PHP

metaphone() calcule la clé metaphone de la chaîne de caractères str.

metaphone() est similaire à la fonction soundex() : elle créée une clé similaire pour des mots dont la prononciation est proche. C'est une fonction qui est plus précise que soundex() car elle prend en compte la prononciation anglaise. La clé metaphone générée est de taille variable.

metaphone() fonctionne en anglais, et n'utilise pas les spécificités de la langue française. Les résultats sur des termes français peuvent être des plus aléatoires.

Metaphone a été développée par Lawrence Philips philips@verity.com. Cette méthode est décrite dans le livre ["Practical Algorithms for Programmers", Binstock & Rex, Addison Wesley, 1995].

Source : www.php.net

levenshtein() calcule la distance Levenshtein entre deux chaînes de caractères. Elle retournera -1 si l'un des deux arguments contient plus de 255 caractères.

La distance Levenshtein est définie comme le nombre minimal de caractères qu'il faut remplacer, insérer ou modifier pour transformer la chaîne str1 en str2. La complexité de l'algorithme est en O(m*n), où n et m sont les tailles respectives de str1 et str2 : c'est plutôt bien, en comparaison de similar_text(), qui est en O(max(n,m)**3), mais cela reste très coûteux.

Dans sa forme la plus simple, levenshtein() va prendre uniquement deux chaînes de caractères comme paramètres, et calculer simplement le nombre d'insertions, de remplacements et d'effacements nécessaires pour transformer str1 en str2.

La deuxième variante de la fonction prend trois paramètres supplémentaires qui représentent les coûts d'insertions, de remplacements et d'effacements. C'est une version plus générale de la première fonction, mais qui est un peu moins efficace.

Source : www.php.net

Cet article décrit une méthode alternative pour faire des recherches dans une base de données. Il est certain que de faire des recherches textuelles (exact string comparaison) et l'utilisation d'expression régulière est très utile. Mais parfois nous avons besoin d'un petit coup de pouce pour trouver ce que nous cherchons. Heureusement pour nos, PHP offre des fonctions qui aide à faire des recherches phonétiques. Ces fonctions peuvent être très puissantes à condition de penser à les utiliser.

Je fais d'abord vous présenter le concept et ensuite je vous décrirais une implantation réelle dans un problème typique.

Le concept

La base

Orthographe phonétique : Orthographe qui transcrit la prononciation de manière univoque.

Source : www.lexilogos.com

Tout d'abord, les gens font des erreurs, et ils en font beaucoup. Combien de fois avez-vous rechercher un truc sur Google pour vous rendre compte que vous aviez fait une erreur de frappe? La recherche textuelle (exact string comparaison) à ses limites. D'abord, elle les termes recherchés doivent être exactement pareil. Si vous faites une erreur, vous ne trouverez pas ce que vous cherchez. Les expressions régulières sont de bonnes solutions si vous recherchez un pattern, mais ne vous aideront pas en cas d'erreur de syntaxe. Une comparaison phonétique de deux chaînes de caractères donne de bien meilleurs résultats (Exemple : Dissons = Dison).

En pratique

Le problème

Je travaillais sur un outil de gestion de temps pour une équipe de 35 personnes. Lorsque les gens recevaient une tâche, ils avaient à créer une tâche dans l'outil de gestion de temps (OGT). Par la suite, ils devaient entrer leurs temps dans l'OGT en indiquant sur quelle tâche ils travaillaient. Pour une tâche donnée, une ou plusieurs personnes pouvaient entrer du temps.

Après deux ans d'utilisations, la base de données de l'outil était devenue un vrai bordel (excuser l'expression). Deux personnes qui travaillant sur la même tâche, créaient chacun une tâche différente dans l'OGT. De plus, les gens donnaient des noms trop génériques à leurs tâches, donc il arrivait que les gens se trompent de tâche lors de l'ajout de temps. (En une année, environ 3000 tâches avaient été ajoutées dans l'OGT.)

La solution

J'ai décidé de modifier l'application (l'OGT) en ajoutant la possibilité de consulter des informations plus détaillées lors de la sélection d'une tâche lors de l'entrée de temps et en ajoutant un engin de recherche phonétique pour aider les employées à choisir la bonne tâche.

L'implantation

À côté de la liste déroulante contenant les tâches, j'ai ajouté deux icônes. La première icône (un ?) fait jaillir une fenêtre contenant un complément d'information concernant la tâche (une description, la date à laquelle la tâche a été créée, le nom de la personne qui à créer la tâche, etc). Le second icône (une loupe) fais jaillir une fenêtre contenant l'engin de recherche phonétique.

Un peu de code

La fonction metaphone() retourne une clé phonétique d'un mot. Par exemple : metaphone('dissons') = TSNS et metaphone('dison') = TSN.

La distance levenshtein entre les deux est de levenshtein(metaphone('dissons'), metaphone('dison')) = 1.

Essayez les :

metaphone() =

levenshtein(metaphone(), metaphone()) =

Ces deux exemples utilisent AJAX. Je parlerais d'AJAX dans un autre article.

Le tout dans une fonction

L'engin de recherche récupère d'abord la liste des titres de toutes les tâches à partir de la base de données. Ensuite, il fait une comparaison phonétique de chaque mot composant le titre avec le terme recherché. Si un mot se rapproche phonétiquement de l'autre, celui-ci est mis en évidence dans une liste des tâches dont au moins un mot du titre ressemble au terme recherché.

La fonction compare d'abord chaque mot des termes recherché à chaque mot du texte comparer (split() s'occupe de séparer les mots.) En suite, on calcule la clé metaphone du mot recherché avec chaque clé metaphone de la chaîne recherché, si la distance levenshtein séparant les deux deux clés est plus petite que la précision recherchée, on considère le mot pareil et on le met en gras.

<?php
///////////////////////////////////////////////////////////////////////
// Desc. : If the function find no match, it return false, but if the
// function find something, it return the find string with highlighted
// words.
//
// Author : Sébastien Brodeur (brodseba at un-programmeur-php dot ca
//
// Based on : www.php.net (author : silas at silaspalmer dot com)
//
// Created : 24 june 2004
//
// Input : $a_sLookingFor     What you are looking for.
//         $a_sOriginal       The searched string
//         $a_uiPrecision     The precision (Default 33.5%)
//
// Output : $sResult          The original text with highlighted words.
////////////////////////////////////////////////////////////////////////

function Highlight($a_sLookingFor, $a_sOriginal, $a_uiPrecision = 335)
{
   $sResult = $a_sOriginal;   // The returned string.

   // Explode into words
   $hwords = preg_split("/[\s\W]+/", $a_sLookingFor);
   $nwords = preg_split("/[\s\W]+/", $a_sOriginal);

   // For each word in $a_sLookingFor...
   foreach ($hwords as $hkey => $hayword)
   {
      $hs = metaphone($hayword);

      // For each word in $a_sOriginal...
      foreach ($nwords as $nkey => $needword)
      {
         $ns = metaphone($needword);

         // The first letter must be equal.
         if($ns[0] == $hs[0])
         {
            $distance = levenshtein($hs, $ns);
            $n_len = strlen($ns);
            $per = round(($distance / $n_len) * 1000);

            if($per < $a_uiPrecision)
            {
               // Highlight word in $a_sOriginal
               $sResult = str_replace($needword, "<b>$needword", $sResult);
               // If word already "bolded"...
               $sResult = str_replace("<b><b>", "<b>", $sResult);
               $sResult = str_replace("</b></b>", "</b>", $sResult);
            }
         }
      }
   }

   if($sResult == $a_sOriginal)
   {
      return false;
   }
   else
   {
      return $sResult;
   }
}
?>

Et voilà!

Noter que la fonction metaphone() donne de meilleurs résultats en anglais. Malgrés que certaines recherches en français donnent des résultats bizarres, elle répond au besoin que j'avais.

Il existe des alternatives à metaphone(). Je ne les ai pas essayés, vous devrez probablement jouer avec la précision pour arriver à de bons résultats.

En voici quelque'une :

DoubleMetaPhone
Phonex (en français)
Soundex 2 (algorithme qui retourne une clé de 4 caractères maximum, donc moins précis. En français.)

Cet article vous a plu? Lisez mes autres articles pour découvrir d'autres trucs.

Sébastien Brodeur

Il est strictement interdit de reproduire ce texte sans la permission écrite de l'auteur.

Commentaire(s)

Sébastien Brodeur - 2006-11-20 01:14:45

Vous pouvez maintenant ajouter des commentaires.

John Doe - 2007-07-17 07:52:37

Bonjour,
Comment avez-vous valider le bon fonctionnement de la fonction metaphone() ?
Avez-vous effectuer une batterie de tests ?
Peut-on les connaître ?

Sébastien Brodeur - 2007-07-17 07:59:49

La fonction metaphone() donne de bon résultat avec des termes anglais. C'est pourquoi je cherchais une implantation de la fonctione metaphone() pour la langage française.

Donc, il arrive souvent que des résultats surprenant fassent leur apparition.

Essayé le par vous même, ce n'est pas parfait mais c'est mieux que rien.

Fred - 2007-10-22 07:46:18

Effectivement,en français les résultats sont curieux et provoquent pas mal de faux résultats. Par exemple MICHAUD, MICHAULT, MICHAUX retournent tous un résultat différent alors que normalement le résultat devrait être le même... C'est un exemple parmis plein d'autres. Le pb c'est qu'en anglais toutes les lettres se prononcent, alors que ce n'est pas le cas, loin de là, français. Un algorithme comme Phonex est préférable car il prend en compte une partie des différences, mais ce n'est pas encore la panacée...

Ajouter un commentaire

Haut de la page

Imprimmer cette page

Articles Services Portefolio Liens Mes blogs Mon blog sur le PHP Mon blog sur l'analyste web Clients	Recherche phonétique en PHP metaphone() calcule la clé metaphone de la chaîne de caractères str. metaphone() est similaire à la fonction soundex() : elle créée une clé similaire pour des mots dont la prononciation est proche. C'est une fonction qui est plus précise que soundex() car elle prend en compte la prononciation anglaise. La clé metaphone générée est de taille variable. metaphone() fonctionne en anglais, et n'utilise pas les spécificités de la langue française. Les résultats sur des termes français peuvent être des plus aléatoires. Metaphone a été développée par Lawrence Philips philips@verity.com. Cette méthode est décrite dans le livre ["Practical Algorithms for Programmers", Binstock & Rex, Addison Wesley, 1995]. Source : www.php.net levenshtein() calcule la distance Levenshtein entre deux chaînes de caractères. Elle retournera -1 si l'un des deux arguments contient plus de 255 caractères. La distance Levenshtein est définie comme le nombre minimal de caractères qu'il faut remplacer, insérer ou modifier pour transformer la chaîne str1 en str2. La complexité de l'algorithme est en O(mn), où n et m sont les tailles respectives de str1 et str2 : c'est plutôt bien, en comparaison de similar_text(), qui est en O(max(n,m)3), mais cela reste très coûteux. Dans sa forme la plus simple, levenshtein() va prendre uniquement deux chaînes de caractères comme paramètres, et calculer simplement le nombre d'insertions, de remplacements et d'effacements nécessaires pour transformer str1 en str2. La deuxième variante de la fonction prend trois paramètres supplémentaires qui représentent les coûts d'insertions, de remplacements et d'effacements. C'est une version plus générale de la première fonction, mais qui est un peu moins efficace. Source : www.php.net Cet article décrit une méthode alternative pour faire des recherches dans une base de données. Il est certain que de faire des recherches textuelles (exact string comparaison) et l'utilisation d'expression régulière est très utile. Mais parfois nous avons besoin d'un petit coup de pouce pour trouver ce que nous cherchons. Heureusement pour nos, PHP offre des fonctions qui aide à faire des recherches phonétiques. Ces fonctions peuvent être très puissantes à condition de penser à les utiliser. Je fais d'abord vous présenter le concept et ensuite je vous décrirais une implantation réelle dans un problème typique. Le concept La base Orthographe phonétique* : Orthographe qui transcrit la prononciation de manière univoque. Source : www.lexilogos.com Tout d'abord, les gens font des erreurs, et ils en font beaucoup. Combien de fois avez-vous rechercher un truc sur Google pour vous rendre compte que vous aviez fait une erreur de frappe? La recherche textuelle (exact string comparaison) à ses limites. D'abord, elle les termes recherchés doivent être exactement pareil. Si vous faites une erreur, vous ne trouverez pas ce que vous cherchez. Les expressions régulières sont de bonnes solutions si vous recherchez un pattern, mais ne vous aideront pas en cas d'erreur de syntaxe. Une comparaison phonétique de deux chaînes de caractères donne de bien meilleurs résultats (Exemple : Dissons = Dison). En pratique Le problème Je travaillais sur un outil de gestion de temps pour une équipe de 35 personnes. Lorsque les gens recevaient une tâche, ils avaient à créer une tâche dans l'outil de gestion de temps (OGT). Par la suite, ils devaient entrer leurs temps dans l'OGT en indiquant sur quelle tâche ils travaillaient. Pour une tâche donnée, une ou plusieurs personnes pouvaient entrer du temps. Après deux ans d'utilisations, la base de données de l'outil était devenue un vrai bordel (excuser l'expression). Deux personnes qui travaillant sur la même tâche, créaient chacun une tâche différente dans l'OGT. De plus, les gens donnaient des noms trop génériques à leurs tâches, donc il arrivait que les gens se trompent de tâche lors de l'ajout de temps. (En une année, environ 3000 tâches avaient été ajoutées dans l'OGT.) La solution J'ai décidé de modifier l'application (l'OGT) en ajoutant la possibilité de consulter des informations plus détaillées lors de la sélection d'une tâche lors de l'entrée de temps et en ajoutant un engin de recherche phonétique pour aider les employées à choisir la bonne tâche. L'implantation À côté de la liste déroulante contenant les tâches, j'ai ajouté deux icônes. La première icône (un ?) fait jaillir une fenêtre contenant un complément d'information concernant la tâche (une description, la date à laquelle la tâche a été créée, le nom de la personne qui à créer la tâche, etc). Le second icône (une loupe) fais jaillir une fenêtre contenant l'engin de recherche phonétique. Un peu de code La fonction metaphone() retourne une clé phonétique d'un mot. Par exemple : metaphone('dissons') = TSNS et metaphone('dison') = TSN. La distance levenshtein entre les deux est de levenshtein(metaphone('dissons'), metaphone('dison')) = 1. Essayez les : metaphone() = levenshtein(metaphone(), metaphone()) = Ces deux exemples utilisent AJAX. Je parlerais d'AJAX dans un autre article. Le tout dans une fonction L'engin de recherche récupère d'abord la liste des titres de toutes les tâches à partir de la base de données. Ensuite, il fait une comparaison phonétique de chaque mot composant le titre avec le terme recherché. Si un mot se rapproche phonétiquement de l'autre, celui-ci est mis en évidence dans une liste des tâches dont au moins un mot du titre ressemble au terme recherché. La fonction compare d'abord chaque mot des termes recherché à chaque mot du texte comparer (split() s'occupe de séparer les mots.) En suite, on calcule la clé metaphone du mot recherché avec chaque clé metaphone de la chaîne recherché, si la distance levenshtein séparant les deux deux clés est plus petite que la précision recherchée, on considère le mot pareil et on le met en gras. <?php /////////////////////////////////////////////////////////////////////// // Desc. : If the function find no match, it return false, but if the // function find something, it return the find string with highlighted // words. // // Author : Sébastien Brodeur (brodseba at un-programmeur-php dot ca // // Based on : www.php.net (author : silas at silaspalmer dot com) // // Created : 24 june 2004 // // Input : $a_sLookingFor What you are looking for. // $a_sOriginal The searched string // $a_uiPrecision The precision (Default 33.5%) // // Output : $sResult The original text with highlighted words. //////////////////////////////////////////////////////////////////////// function Highlight($a_sLookingFor, $a_sOriginal, $a_uiPrecision = 335) { $sResult = $a_sOriginal; // The returned string. // Explode into words $hwords = preg_split("/[\s\W]+/", $a_sLookingFor); $nwords = preg_split("/[\s\W]+/", $a_sOriginal); // For each word in $a_sLookingFor... foreach ($hwords as $hkey => $hayword) { $hs = metaphone($hayword); // For each word in $a_sOriginal... foreach ($nwords as $nkey => $needword) { $ns = metaphone($needword); // The first letter must be equal. if($ns[0] == $hs[0]) { $distance = levenshtein($hs, $ns); $n_len = strlen($ns); $per = round(($distance / $n_len) * 1000); if($per < $a_uiPrecision) { // Highlight word in $a_sOriginal $sResult = str_replace($needword, "<b>$needword", $sResult); // If word already "bolded"... $sResult = str_replace("<b><b>", "<b>", $sResult); $sResult = str_replace("</b></b>", "</b>", $sResult); } } } } if($sResult == $a_sOriginal) { return false; } else { return $sResult; } } ?> La fonction compare d'abord chaque mot des termes recherché à chaque mot du texte comparer (split() s'occupe de séparer les mots.) En suite, on calcule la clé metaphone du mot recherché avec chaque clé metaphone de la chaîne recherché, si la distance levenshtein séparant les deux deux clés est plus petite que la précision recherchée, on considère le mot pareil et on le met en gras. Et voilà! Noter que la fonction metaphone() donne de meilleurs résultats en anglais. Malgrés que certaines recherches en français donnent des résultats bizarres, elle répond au besoin que j'avais. Il existe des alternatives à metaphone(). Je ne les ai pas essayés, vous devrez probablement jouer avec la précision pour arriver à de bons résultats. En voici quelque'une : DoubleMetaPhone Phonex (en français) Soundex 2 (algorithme qui retourne une clé de 4 caractères maximum, donc moins précis. En français.) Cet article vous a plu? Lisez mes autres articles pour découvrir d'autres trucs. Sébastien Brodeur Il est strictement interdit de reproduire ce texte sans la permission écrite de l'auteur. Commentaire(s) Sébastien Brodeur - 2006-11-20 01:14:45 Vous pouvez maintenant ajouter des commentaires. John Doe - 2007-07-17 07:52:37 Bonjour, Comment avez-vous valider le bon fonctionnement de la fonction metaphone() ? Avez-vous effectuer une batterie de tests ? Peut-on les connaître ? Sébastien Brodeur - 2007-07-17 07:59:49 La fonction metaphone() donne de bon résultat avec des termes anglais. C'est pourquoi je cherchais une implantation de la fonctione metaphone() pour la langage française. Donc, il arrive souvent que des résultats surprenant fassent leur apparition. Essayé le par vous même, ce n'est pas parfait mais c'est mieux que rien. Fred - 2007-10-22 07:46:18 Effectivement,en français les résultats sont curieux et provoquent pas mal de faux résultats. Par exemple MICHAUD, MICHAULT, MICHAUX retournent tous un résultat différent alors que normalement le résultat devrait être le même... C'est un exemple parmis plein d'autres. Le pb c'est qu'en anglais toutes les lettres se prononcent, alors que ce n'est pas le cas, loin de là, français. Un algorithme comme Phonex est préférable car il prend en compte une partie des différences, mais ce n'est pas encore la panacée... Ajouter un commentaire Votre nom (optionnel) Votre commentaire Code : Haut de la page Imprimmer cette page	Les gens qui ont consulter cet article, ont aussi consultez ceux-ci : Qu'est-ce qu'AJAX et comment l'utiliser
Copyright © 2010 Sébastien Brodeur Tous droits réservés. Confidentialité Dernière modification : 14 février 2009

Clients