FriconiX
Des milliers de pictogrammes gratuits dessinés avec amour !

Distance de Levenshtein en mySQL

Introduction

Selon Wikipedia, la distance de Levenshtein est une distance, au sens mathématique du terme, donnant une mesure de la différence entre deux chaînes de caractères. Elle est égale au nombre minimal de caractères qu'il faut supprimer, insérer ou remplacer pour passer d’une chaîne à l’autre.

Cette distance peut être utilisée pour trouver une ligne dans une base de donnée SQL, même si les termes recherchés ne correspondent pas exactement aux champs de la table. En calculant la distance entre les mots-clés et les candidats potentiels, il devient possible de trouver le champs le plus proche (au sens de la distance de Levenshtein) dans la table. Cela peut être utile, par exemple pour trouver un pseudo, un nom d'utilisateur ou une ville, même si les mots-clés ne sont pas strictement identiques aux données de la table.

Prenons un exemple dans lequel nous supposerons que la base de données contient un champ contenant la chaîne de caractère "New-York". On demande à l'utilisateur le nom d'une ville, et il saisit les termes suivants :

Saisie Base de donénes Distance Analyse
New-York New-York 0 Les mots sont strictement identiques, la distance est nulle.
New York New-York 1 Une substitution.
NewYork New-York 1 Une insertion.
New-Yorke New-York 1 Une suppression.
NewYorke New-York 2 Une insertion et une suppression.
Paris New-York 8 Cinq substitutions et trois suppressions.

L'implémentation présentée sur cette page a été testée avec les version suivantes :

Implementation de la fonction

La première étape est l'implémentation de la fonction levenshtein dans mySQL. Sélectionnez la table où le calcul de la distance entre deux mots est requise et copiez le code SQL suivant (source http://www.artfulsoftware.com) :

DELIMITER $$
CREATE FUNCTION levenshtein( s1 VARCHAR(255), s2 VARCHAR(255) )
    RETURNS INT
    DETERMINISTIC
    BEGIN
        DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
        DECLARE s1_char CHAR;
        -- max strlen=255
        DECLARE cv0, cv1 VARBINARY(256);

        SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0;

        IF s1 = s2 THEN
            RETURN 0;
        ELSEIF s1_len = 0 THEN
            RETURN s2_len;
        ELSEIF s2_len = 0 THEN
            RETURN s1_len;
        ELSE
            WHILE j <= s2_len DO
                SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
            END WHILE;
            WHILE i <= s1_len DO
                SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1;
                WHILE j <= s2_len DO
                    SET c = c + 1;
                    IF s1_char = SUBSTRING(s2, j, 1) THEN
                        SET cost = 0; ELSE SET cost = 1;
                    END IF;
                    SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost;
                    IF c > c_temp THEN SET c = c_temp; END IF;
                    SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1;
                    IF c > c_temp THEN
                        SET c = c_temp;
                    END IF;
                    SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
                END WHILE;
                SET cv1 = cv0, i = i + 1;
            END WHILE;
        END IF;
        RETURN c;
    END$$
DELIMITER ;

Exécuter la requête sur le serveur.

Implémentation de la fonction Levenshtein dans mySQL

Assurez-vous que la requête ne présente pas d'erreur avant de poursuivre :

La requête pour l'ajout de la fonction Levenshtein a réussi

La fonction doit apparaitre dans la table sélectionnée. Cela peut prendre quelques minutes pour que la liste des fonctions soit rafraîchie. Rechargez la page si la requête s'est exécutée sans erreur et que la fonction n'apparait pas.

La fonction est ajoutée dans la table sélectionnée

Appel de la fonction

Avant d'exécuter des requêtes plus complexes, vérifions que la fonction fonctionne correctement. Exécutez la requête suivante :

SELECT levenshtein('New-York', 'Paris')

Elle doit retourner une distance de 8 :

Calcule de la distance de Levenshtein entre Paris et New-York

La fonction de Levenshtein peut maintenant être utilisée dans des requêtes SQL :

SELECT * FROM `cities` WHERE levenshtein('$keyword', `name`) BETWEEN 0 AND 4

La requête précédente retourne les champs de la table cities pour lesquels la distance entre la chaîne de caractère keyword et la colonne name est inférieure à 5. Faisons un essai avec le mot newyorke :

Exemple de requête SQL avec la distance de Levenshtein

That's all folks !

Voir aussi


Dernière mise à jour : 13/04/2019