levenshtein()

La fonction levenshtein() calcule la distance de Levenshtein entre deux chaînes — le nombre minimal d'éditions de caractères uniques (insertions, suppressions ou substitutions) nécessaires pour transformer une chaîne en une autre. Une distance plus petite signifie que les chaînes se ressemblent davantage ; levenshtein() est donc l'outil de référence pour la correspondance approximative : correcteurs orthographiques, suggestions « vouliez-vous dire… ? », déduplication d'enregistrements quasi-identiques et classement des résultats de recherche par proximité.

Ce chapitre couvre la syntaxe, les pondérations de coût optionnelles, les différences avec les fonctions apparentées, les pièges courants et des exemples exécutables.

Syntaxe

levenshtein(string $string1, string $string2): int

Ou, avec des coûts d'édition personnalisés :

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

Paramètres

• $string1 — la première chaîne à comparer.
• $string2 — la seconde chaîne à comparer.
• $insertion_cost (optionnel) — coût de l'insertion d'un caractère. Par défaut 1.
• $replacement_cost (optionnel) — coût du remplacement d'un caractère. Par défaut 1.
• $deletion_cost (optionnel) — coût de la suppression d'un caractère. Par défaut 1.

La fonction retourne la distance de Levenshtein sous forme d'int. Avec les pondérations par défaut, cette distance est symétrique — levenshtein($a, $b) est égal à levenshtein($b, $a).

Exemple de base

La sortie de ce code est :

4

La fonction retourne 4 : transformer « Hello » en « World » nécessite quatre substitutions (H→W, e→o, l→r, o→d) ; seul le second l reste en place.

Comment la distance est calculée

Chaque opération d'édition compte comme une étape (avec les pondérations par défaut). La paire classique des manuels « kitten » → « sitting » nécessite trois éditions :

<?php
echo levenshtein("kitten", "sitting"); // 3
// k → s   (substitution)
// e → i   (substitution)
// (append) g   (insertion)
?>

Sortie :

3

levenshtein() est sensible à la casse

Les différences de casse comptent comme une édition, ce qui surprend souvent :

<?php
echo levenshtein("Hello", "hello"), "\n"; // 1  (H vs h)
echo levenshtein(strtolower("Hello"), strtolower("hello")), "\n"; // 0
?>

Sortie :

1
0

Pour une comparaison insensible à la casse, normalisez les deux chaînes avec strtolower() (ou mb_strtolower() pour le texte multioctet) avant d'appeler levenshtein().

Pondération différente des éditions

Lorsque les insertions, suppressions et remplacements ne doivent pas tous coûter le même prix, passez les trois arguments de coût. Ici, une suppression est rendue coûteuse :

<?php
// $insertion_cost = 1, $replacement_cost = 1, $deletion_cost = 5
echo levenshtein("cats", "cat", 1, 1, 5); // 5
?>

Sortie :

5

Supprimer le s final est une seule suppression, mais avec un coût de 5, la distance rapportée est 5. Cela est utile lorsqu'un type de faute de frappe doit être davantage pénalisé qu'un autre.

Utilisation pratique : suggestions « vouliez-vous dire ? »

Une tâche concrète courante consiste à trouver le mot connu le plus proche de la saisie d'un utilisateur :

<?php
$input = "comit";
$dictionary = ["commit", "command", "comment", "compile"];

$best = null;
$bestDistance = PHP_INT_MAX;

foreach ($dictionary as $word) {
    $d = levenshtein($input, $word);
    if ($d < $bestDistance) {
        $bestDistance = $d;
        $best = $word;
    }
}

echo "Did you mean: {$best}? (distance {$bestDistance})";
?>

Sortie :

Did you mean: commit? (distance 1)

Pièges

• Octets, pas caractères. levenshtein() opère sur des octets individuels, donc les caractères UTF-8 multioctets (accents, emoji, scripts non-latins) peuvent être mal comptés. Pour des résultats précis avec ce type de texte, translittérez ou comparez en ASCII normalisé.
• Les longues chaînes coûtent de la mémoire/du temps. La complexité est approximativement proportionnelle au produit des longueurs des deux chaînes ; évitez donc de l'utiliser sur des entrées très volumineuses.
• La casse et les espaces comptent. Supprimez les espaces et mettez en minuscules d'abord si ces différences doivent être ignorées.

Fonctions apparentées

• similar_text() — retourne le nombre de caractères communs (et un pourcentage optionnel) plutôt qu'une distance d'édition.
• soundex() et metaphone() — comparent les chaînes selon leur prononciation plutôt que leur orthographe.
• strcmp() — une comparaison stricte et sûre pour les données binaires qui indique seulement si les chaînes sont égales ou laquelle vient en premier.

Pratique