levenshtein

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

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

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

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.

Historique

Version Description
8.0.0 Antérieur à cette version, levenshtein() devait être appelée avec soit deux soit cinq arguments.

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