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 :

SQL 5.5.57-0 / ubuntu0.14.04.1
SQL 5.6.39-cll-lve

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.

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

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.

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 :

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 :

That's all folks !

Voir aussi

Dernière mise à jour : 23/11/2021