<- les variables   libxml ->

levenshtein

(PHP 3 >= 3.0.17, PHP 4 >= 4.0.1, PHP 5)

levenshtein --  Calcule la distance Levenshtein entre deux chaînes

Description

int levenshtein ( string str1, string str2 [, int cost_ins, int cost_rep, int cost_del] )

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.

Exemple 1. Exemple avec levenshtein()

<?php
// mot mal orthographié
$input = 'carrrot';

// tableau de mots à vérifier
$words  = array('apple','pineapple','banana','orange',
               'radish','carrot','pea','bean','potato');

// aucune distance de trouvée pour le moment
$shortest = -1;

// boucle sur les des mots pour trouver le plus près
foreach ($words as $word) {

   // calcule la distance avec le mot mis en entrée,
   // et le mot courant
   $lev = levenshtein($input, $word);

   // cherche une correspondance exacte
   if ($lev == 0) {

       // le mot le plus près est celui-ci (correspondance exacte)
       $closest = $word;
       $shortest = 0;

       // on sort de la boucle ; nous avons trouvé une correspondance exacte
       break;
   }

   // Si la distance est plus petite que la prochaine distance trouvée
   // OU, si le prochain mot le plus près n'a pas encore été trouvé
   if ($lev <= $shortest || $shortest < 0) {
       // définission du mot le plus près ainsi que la distance
       $closest  = $word;
       $shortest = $lev;
   }
}

echo "Mot entré : $input\n";
if ($shortest == 0) {
   echo "Correspondance exacte trouvée : $closest\n";
} else {
   echo "Vous voulez dire : $closest ?\n";
}

?>

L'exemple ci-dessus va afficher :

Mot entré : carrrot
Vous voulez dire : carrot ?

Voir aussi soundex(), similar_text() et metaphone().



Rechercher une fonction PHP

<- les variables   libxml ->

Réseaux sociaux

|Plus d'options...

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher les interactions avec les réseaux sociaux sur ces pages.

 

Nuage de mots clés

5 mots clés dont 0 définis manuellement (plus d'information...).

Avertissement

Cette page ne possède pas encore de mots clés manuels, ceci est donc un exemple automatique (les niveaux de pertinence sont fictifs, mais les liens sont valables). Pour tester le nuage avec une page qui contient des mots définis manuellement, vous pouvez cliquer ici.
function Gaudry levenshtein Signaler une erreur Stéphane Gaudry

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher le nuage de mots clés.

 

Références

  1. Consulter le document html Langue du document: fr Manuel PHP : http://be2.php.net, levenshtein

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

 

Structure du document

Astuce pour imprimer les couleurs des cellules de tableaux : http://www.gaudry.be/ast-rf-450.html
Aucun commentaire pour cette page

© Ce document issu de l′infobrol est enregistré sous le certificat Cyber PrInterDeposit Digital Numbertection. Enregistrement IDDN n° 5329-3961
Document créé le 27/09/06 22:45, dernière modification le Vendredi 17 Juin 2011, 12:12
Source du document imprimé : http://www.gaudry.be/php-rf-function.levenshtein.html Document affiché 2 fois ce mois de Juin.
St.Gaudry©07.01.02
Outils (masquer)
||
Recherche (afficher)
Recherche :

Utilisateur (masquer)
Navigation (masquer)
Apparence (afficher)
Stats (afficher)
15832 documents
452 astuces.
549 niouzes.
3099 definitions.
447 membres.
8115 messages.

Document genere en :
0,41 seconde

Mises à jour :
Mises à jour du site
Citation (masquer)
L'archer a un point commun avec l'homme de bien : quand sa flèche n'atteint pas le centre de la cible, il en cherche la cause en lui-même.

Confucius
 
l'infobrol
Nous sommes le Samedi 02 Juin 2012, 21:04, toutes les heures sont au format GMT+1.00 Heure, heure d'été (+1)