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.
- créer un formulaire avec un champ texte
- rechercher le mot le plus proche
- 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.