array ( 0 => 'index.php', 1 => 'PHP Manual', ), 'head' => array ( 0 => 'UTF-8', 1 => 'fr', ), 'this' => array ( 0 => 'function.levenshtein.php', 1 => 'levenshtein', 2 => 'Calcule la distance Levenshtein entre deux chaînes', ), 'up' => array ( 0 => 'ref.strings.php', 1 => 'Fonctions sur les chaînes de caractères', ), 'prev' => array ( 0 => 'function.lcfirst.php', 1 => 'lcfirst', ), 'next' => array ( 0 => 'function.localeconv.php', 1 => 'localeconv', ), 'alternatives' => array ( ), 'source' => array ( 'lang' => 'fr', 'path' => 'reference/strings/functions/levenshtein.xml', ), 'history' => array ( ), ); $setup["toc"] = $TOC; $setup["toc_deprecated"] = $TOC_DEPRECATED; $setup["parents"] = $PARENTS; manual_setup($setup); contributors($setup); ?>

levenshtein

(PHP 4 >= 4.0.1, PHP 5, PHP 7, PHP 8)

levenshtein — Calcule la distance Levenshtein entre deux chaînes

Description

levenshtein(
    string $string1,
    string $string2,
    int $insertion_cost = 1,
    int $replacement_cost = 1,
    int $deletion_cost = 1
): int

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/ou 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.

Liste de paramètres

string1

Une des chaînes à évaluer.

string2

Une des chaînes à évaluer.

insertion_cost

Définit le coût de l'insertion.

replacement_cost

Définit le coût du remplacement.

deletion_cost

Définit le coût de l'effacement.

Valeurs de retour

Cette fonction retourne la distance Levenshtein entre deux chaînes de caractères.

Historique

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.

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