Fonction PHP du jour : levenshtein()

Je vais tenter d’écrire périodiquement un billet afin de traiter d’une fonction PHP qui me semble indispensable, ou encore qui me semble simplement utile à connaître.

Pour aujourd’hui, la fonction sera levenshtein().

Présentation

Du nom de son auteur, Vladimir Levenshtein, la distance Levenshtein permet, en gros, de trouver un nombre représentant la distance entre deux chaînes de caractères.

Pour cela, l’algorithme détermine un coût basé sur le nombre de substitution, d’ajout et de suppression de caractères afin de transformer le premier mot vers le second. Plus les deux mots présenteront des différences, plus le nombre sera élevé.

Pour plus d’informations, je vous redirige sur la page de Wikipédia, d’où je me suis inspiré.

Utilisation

Prototypes :

int levenshtein (string $str1, string $str2)
int levenshtein (string $str1, string $str2, int $cost_ins, int $cost_rep, int $cost_del)

La fonction peut prendre deux ou cinq paramètres. Les trois paramètres supplémentaires permettent de personnaliser les poids attribués aux différentes actions effectuées (substitution, ajout, suppression). C’est donc une utilisation avancée.

Un nombre représentant la distance est retourné.

Exemple d’utilisation

Nous allons réaliser un exemple assez simple. Il va falloir trouver quel mot, parmi un dictionnaire, se rapproche le plus du mot entré par l’utilisateur.

  1. créer un formulaire avec un champ texte
  2. rechercher le mot le plus proche
  3. afficher l’information

Le formulaire est très simple, un champ texte et un bouton de validation, et c’est terminé.

<form action="" method="post">
    <p>
        <label for="word">Mot : </label>
        <input id="word" name="word" type="text" value="<?php echo $input; ?>" />
        <input type="submit" value="Chercher" />
    </p>
</form>

On y greffe maintenant notre code PHP.

<?php
// on défini notre dictionnaire basé sur les périphériques
$words = array('ecran', 'souris', 'clavier', 'imprimante', 'scanner', 'haut parleur');
$input = '';

// formulaire posté ?
if (isset($_POST['word']) && $input = trim($_POST['word'])) {
    // mots se rapprochant de la recherche
    $wordsFound = array();
    foreach ($words AS $word) {
        // calcule la distance Levenshtein
        $len = levenshtein($input, $word);

        // on a trouvé un mot exacte
        if ($len == 0) {
            $wordsFound = $word;
            break;
        }

        // si la distance est inférieur ou égale à 2 (pour ne pas prendre n'importe quel mot
        if (2 >= $len) {
            $wordsFound[] = $word;
        }
    }

    // on a trouvé un mot exacte
    if (is_string($wordsFound)) {
        echo '<p>Vous recherchez donc <strong>'.$input.'</strong></>';
    } elseif ($wordsFound) {
        if (count($wordsFound) == 1) { // un seul mot se rapproche au mieux du dictionnaire
            echo '<p>Vous recherchez sans doute <strong>'.$wordsFound[0].'</strong></p>';
        } else { // liste les mots se rapprochant de la recherche
            echo '<p>Vous recherchez peut-être l'un de ces périphériques : '.implode(',', $wordsFound).'</p>';
        }
    } else {
        // pas de mot se rapprochant de la recherche
        echo '<p>Nous n'avons trouvé aucun périphérique se rapprochant à votre demande.</p>';
    }
}
?>
<form action="" method="post">
    <p>
        <label for="word">Mot : </label>
        <input id="word" name="word" type="text" value="<?php echo $input; ?>" />
        <input type="submit" value="Chercher" />
    </p>
</form>

Les commentaires parlent d’eux même. Grâce à ce code, il est possible d’orienter l’utilisateur suivant sa recherche.

Conclusion

Bon, eh bien nous venons de créer un mini moteur de recherche 😉

Ce billet est avant tout là pour faire découvrir cette fonction, qui me semble tout de même utile. Attention tout de même, la fonction Levenshtein peut vite devenir consommatrice de ressource, à utiliser avec parcimonie.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Notifiez-moi des commentaires à venir via email. Vous pouvez aussi vous abonner sans commenter.