levenshtein
(PHP 4 >= 4.0.1, PHP 5, PHP 7)
levenshtein — Calcule la distance Levenshtein entre deux chaînes
Description
$str1
, string $str2
)$str1
, string $str2
, int $cost_ins
, int $cost_rep
, int $cost_del
)
La distance Levenshtein est définie comme le nombre
minimal de caractères qu'il faut remplacer, insérer ou supprimer
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.
Liste de paramètres
-
str1 -
Une des chaînes à évaluer.
-
str2 -
Une des chaînes à évaluer.
-
cost_ins -
Définit le coût de l'insertion.
-
cost_rep -
Définit le coût du remplacement.
-
cost_del -
Définit le coût de l'effacement.
Valeurs de retour
Retourne 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.
Exemples
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 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éfinition 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() - Calcule la clé soundex
- similar_text() - Calcule la similarité de deux chaînes
- metaphone() - Calcule la clé metaphone
Document créé le 30/01/2003, dernière modification le 26/10/2018
Source du document imprimé : https://www.gaudry.be/php-rf-levenshtein.html
L'infobrol est un site personnel dont le contenu n'engage que moi. Le texte est mis à disposition sous licence CreativeCommons(BY-NC-SA). Plus d'info sur les conditions d'utilisation et sur l'auteur.
Références
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.
