Implémentation de la distance Levenshtein pour la recherche mysql / fuzzy?

Je voudrais pouvoir rechercher un tableau comme suit pour smith et obtenir tout ce qu’il y a dans 1 variance.

Les données:

 O'Brien
 Smithe
 Dolan
 Smuth
 Wong
 Smoth
 Gunther
 Smiht

J’ai cherché à utiliser la distance Levenshtein quelqu’un sait-il comment mettre en œuvre avec elle?

Afin de rechercher efficacement à l’aide de la distance levenshtein, vous avez besoin d’un index spécialisé efficace, tel qu’un arbre bk . Malheureusement, aucun système de firebase database que je connaisse, y compris MySQL, n’implémente des index bk-tree. Cela est encore plus compliqué si vous recherchez une recherche en texte intégral, au lieu d’un seul terme par ligne. En d’autres termes, je ne peux penser à aucun moyen de faire de l’indexation en texte intégral d’une manière qui permette d’effectuer une recherche basée sur la distance de levenshtein.

Une implémentation de la distance damerau-levenshtein peut être trouvée ici: Algorithme de Damerau-Levenshtein: Levenshtein avec transpositions L’amélioration par rapport à la distance de Levenshtein pure est que l’échange de caractères est considéré. Je l’ai trouvé dans les commentaires du lien de schnaader, merci!

Il y a une implémentation mysql UDF de la fonction Levenshtein Distance

https://github.com/jmcejuela/Levenshtein-MySQL-UDF

Il est implémenté en C et a de meilleures performances que la “requête de distance MySQL Levenshtein” mentionnée par schnaader

La fonction donnée pour lévenshtein <= 1 ci-dessus n'est pas correcte - elle donne des résultats incorrects pour, par exemple, "lit" et "enchère".

J’ai modifié la “requête de distance MySQL Levenshtein” donnée ci-dessus, dans la première réponse, pour accepter une “limite” qui l’accélère un peu. Fondamentalement, si vous vous souciez seulement de Levenshtein <= 1, définissez la limite à "2" et la fonction retournera la distance exacte de levenshtein si elle est 0 ou 1; ou un 2 si la distance exacte de levenshtein est 2 ou plus.

Ce mod le rend 15% à 50% plus rapide – plus votre mot de recherche est long, plus l’avantage est important (parce que l’algorithme peut céder plus tôt.) Par exemple, sur 200 000 mots “rire”, l’original prend 3 min 47 sec sur mon ordinateur portable, contre 1:39 pour la version “limite”. Bien sûr, ils sont tous deux trop lents pour une utilisation en temps réel.

Code:

DELIMITER $$ CREATE FUNCTION levenshtein_limit_n( s1 VARCHAR(255), s2 VARCHAR(255), n INT) RETURNS INT DETERMINISTIC BEGIN DECLARE s1_len, s2_len, i, j, c, c_temp, cost, c_min 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, c_min = 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 and c_min < n DO -- if actual levenshtein dist >= limit, don't bother computing it SET s1_char = SUBSTRING(s1, i, 1), c = i, c_min = 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; IF c < c_min THEN SET c_min = c; END IF; END WHILE; SET cv1 = cv0, i = i + 1; END WHILE; END IF; IF i <= s1_len THEN -- we didn't finish, limit exceeded SET c = c_min; -- actual distance is >= c_min (ie, the smallest value in the last computed row of the masortingx) END IF; RETURN c; END$$ 

Je mets en place une recherche basée sur Levenshtein ou Damerau-Levenshtein (probablement le dernier) pour des recherches multiples sur un texte indexé, basé sur un article de Gonzalo Navarro et Ricardo Baeza-yates: texte du lien

Après avoir construit un tableau de suffixes ( voir wikipedia ), si vous êtes intéressé par une chaîne avec au plus k mésappariements avec la chaîne de recherche, divisez la chaîne de recherche en k + 1 morceaux; au moins un de ceux-ci doit être intact. Recherchez les sous-chaînes par recherche binary sur le tableau des suffixes, puis appliquez la fonction de distance au patch autour de chaque élément correspondant.

vous pouvez utiliser cette fonction


 CREATE FUNCTION `levenshtein` (texte s1, texte s2) RETURNS int (11)
     DÉTERMINISTIQUE
 COMMENCER 
     DÉCLARE s1_len, s2_len, i, j, c, c_temp, coût INT; 
     DÉCLARE s1_char CHAR; 
     DECLARE cv0, cv1 text; 
     SET s1_len = CHAR_LENGTH (s1), s2_len = CHAR_LENGTH (s2), cv1 = 0x00, j = 1, i = 1, c = 0; 
     SI s1 = s2 PUIS 
       RETOUR 0; 
     ELSEIF s1_len = 0 ALORS 
       RETOUR s2_len; 
     ELSEIF s2_len = 0 PUIS 
       RETOUR s1_len; 
     AUTRE 
       WHILE j <= s2_len DO 
         SET cv1 = CONCAT (cv1, UNHEX (HEX (j))), j = j + 1; 
       FIN EN TEMPS; 
       Tandis que je <= 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; 
           SI s1_char = SUBSTRING (s2, j, 1) ALORS  
             SET cost = 0;  ELSE SET cost = 1; 
           FIN SI; 
           SET c_temp = CONV (HEX (SUBSTRING (cv1, j, 1)), 16, 10) + coût; 
           SI c> c_temp ALORS SET c = c_temp;  FIN SI; 
             SET c_temp = CONV (HEX (SUBSTRING (cv1, j + 1, 1)), 16, 10) + 1; 
             SI c> c_temp ALORS  
               SET c = c_temp;  
             FIN SI; 
             SET cv0 = CONCAT (cv0, UNHEX (HEX (c))), j = j + 1; 
         FIN EN TEMPS; 
         SET cv1 = cv0, i = i + 1; 
       FIN EN TEMPS; 
     FIN SI; 
     RETOUR c; 
   FIN

et pour l’obtenir comme XX% utiliser cette fonction


 CREATE FUNCTION `levenshtein_ratio` (texte s1, texte s2) RETURNS int (11)
     DÉTERMINISTIQUE
 COMMENCER 
     DECLARE s1_len, s2_len, max_len INT; 
     SET s1_len = LONGUEUR (s1), s2_len = LONGUEUR (s2); 
     SI s1_len> s2_len ALORS  
       SET max_len = s1_len;  
     AUTRE  
       SET max_len = s2_len;  
     FIN SI; 
     RETOUR RONDE ((1 - LEVENSHTEIN (s1, s2) / max_len) * 100); 
   FIN

Si vous voulez seulement savoir si la distance de levenshtein est au maximum de 1, vous pouvez utiliser la fonction MySQL suivante.

 CREATE FUNCTION `lv_leq_1` ( `s1` VARCHAR( 255 ) , `s2` VARCHAR( 255 ) ) RETURNS TINYINT( 1 ) DETERMINISTIC BEGIN DECLARE s1_len, s2_len, i INT; SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), i = 1; IF s1 = s2 THEN RETURN TRUE; ELSEIF ABS(s1_len - s2_len) > 1 THEN RETURN FALSE; ELSE WHILE SUBSTRING(s1,s1_len - i,1) = SUBSTRING(s2,s2_len - i,1) DO SET i = i + 1; END WHILE; RETURN SUBSTRING(s1,1,s1_len-i) = SUBSTRING(s2,1,s2_len-i) OR SUBSTRING(s1,1,s1_len-i) = SUBSTRING(s2,1,s2_len-i+1) OR SUBSTRING(s1,1,s1_len-i+1) = SUBSTRING(s2,1,s2_len-i); END IF; END 

Ceci est fondamentalement une étape unique dans la description récursive de la distance de levenshtein. La fonction retourne 1, si la distance est au maximum de 1, sinon elle renvoie 0.

Comme cette fonction ne calcule pas complètement la distance de levenshtein, elle est beaucoup plus rapide.

Vous pouvez également modifier cette fonction de telle sorte qu’elle renvoie true si la distance de levenshtein est d’au plus 2 ou 3, en l’appelant de manière récursive. Si MySQL ne prend pas en charge les appels récursifs, vous pouvez copier deux fois les versions légèrement modifiées de cette fonction et les appeler à la place. Mais vous ne devriez pas utiliser la fonction récursive pour calculer la distance exacte de levenshtein.

J’ai eu un cas spécialisé de recherche à distance et après avoir installé l’UDF Damerau-Levenshtein dans MySQL, j’ai constaté que la requête prenait trop de temps. Je suis venu avec la solution suivante:

  • J’ai un espace de recherche très ressortingctif (chaîne de 9 caractères limitée aux valeurs numériques).

Créez une nouvelle table (ou ajoutez des colonnes à votre table cible) avec des colonnes pour chaque position de caractère dans votre champ cible. c’est à dire. Mon VARCHAR (9) a fini avec 9 colonnes TINYINT + 1 colonne Id qui correspond à ma table principale (append des index pour chaque colonne). J’ai ajouté des déclencheurs pour que ces nouvelles colonnes soient toujours mises à jour lorsque ma table principale est mise à jour.

Pour effectuer une requête k-distance, utilisez le prédicat suivant:

(Column1 = s [0]) + (Column2 = s [1]) + (Column3 = s [2]) + (Column4 = s [3]) + …> = m

où s est votre chaîne de recherche et m est le nombre requirejs de caractères correspondants (ou m = 9 – d dans mon cas où d est la distance maximale que je veux retourner).

Après le test, j’ai trouvé qu’une requête sur 1 million de lignes nécessitant 4,6 secondes en moyenne renvoyait les identifiants correspondants en moins d’une seconde. Une deuxième requête pour renvoyer les données des lignes correspondantes dans ma table principale a également pris moins d’une seconde. (La combinaison de ces deux requêtes en tant que sous-requête ou jointure a eu pour conséquence des durées d’exécution beaucoup plus longues et je ne sais pas pourquoi.)

Bien que ce ne soit pas Damerau-Levenshtein (ne tient pas compte de la substitution), cela suffit à mes fins.

Bien que cette solution ne soit probablement pas adaptée à un espace de recherche plus grand, elle a très bien fonctionné pour ce cas ressortingctif.

Sur la base de la réponse de Chella et de l’ article de Ryan Ginstrom, une recherche floue pourrait être mise en œuvre en tant que telle:

 DELIMITER $$ CREATE FUNCTION fuzzy_subssortingng( 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(0))), 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; SET j = 1; WHILE j <= s2_len DO SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10); IF c > c_temp THEN SET c = c_temp; END IF; SET j = j + 1; END WHILE; RETURN c; END$$ DELIMITER ;