Calcule la distance Levenshtein entre deux chaînes

# levenshtein

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

levenshtein — Calcule la distance Levenshtein entre deux chaînes

### Description

function 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

- soundex() - Calcule la clé soundex
- similar_text() - Calcule la similarité de deux chaînes
- metaphone() - Calcule la clé metaphone

`↑` and `↓` to navigate • `Enter` to select • `Esc` to close • `/` to open