(PHP 4 >= 4.0.1, PHP 5, PHP 7, PHP 8)
levenshtein — Calcule la distance Levenshtein entre deux chaînes
$string1,$string2,$insertion_cost = 1,$replacement_cost = 1,$deletion_cost = 1
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 string1 en
string2. La complexité de l'algorithme
est en O(m*n),
où n et m sont les tailles
respectives de string1 et
string2 : 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.
Si insertion_cost, replacement_cost
et/oru deletion_cost sont différent de 1,
l'algorithme s'adapte pour choisir la transformation la moins coûteuse.
E.g. si $insertion_cost + $deletion_cost < $replacement_cost,
Aucun remplacement ne sera effectué, mais plutôt des insertions et suppressions.
string1Une des chaînes à évaluer.
string2Une des chaînes à évaluer.
insertion_costDéfinit le coût de l'insertion.
replacement_costDéfinit le coût du remplacement.
deletion_costDéfinit le coût de l'effacement.
Cette fonction retourne la distance Levenshtein entre deux chaînes de caractères.
| Version | Description |
|---|---|
| 8.0.0 | Antérieur à cette version, levenshtein() devait être appelée avec soit deux soit cinq arguments. |
| 8.0.0 |
Antérieur à cette version, levenshtein() retournait -1
si l'une des chaînes d'arguments dépassait 255 caractères.
|
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 ?