select avec distance de Levenshtein

**trucmuche2005** · 05/09/2017, 15h17

Bonjour !

Disons que j'ai une table nommée "personnes" avec une colonne primaire "id" et une colonne "nom".

J'aimerais aller chercher dans la table les lignes dont le "nom" est à une distance de Levenshtein d'au plus 2 de "motdetest", c'est à dire qu'il y a au plus 2 caractères de différence entre personnes.nom et "motdetest". Donc il devrait trouver par exemple la ligne avec "mutdetest" (1 différence), "motdeteste" (2 différences), "Motdetest" (0 différences), mais ne devrait pas trouver "mitduteest".

J'ai trouvé une fonction levenshtein à ajouter dans MySQL ici mais bien sûr, cela devient lent... Faire un "SELECT id FROM personnes WHERE 1" me prend 0.0002s, faire un "SELECT id FROM personnes WHERE levenshtein(listeMDS.nom, "abinot")<3" prend 0,8s. Bon, c'est pas encore la mort (hum) mais je me demandais s'il y avait moyen de faire mieux pour éviter de trop charger le serveur...

Mille mercis d'avance pour vos idées et conseils...

T.

**SQLpro** · 05/09/2017, 15h57

La distance de Levenshtein est massivement combinatoire. L'algorithme a donc un temps de réponse quadratique à exponentiel en fonction de la charge et ne doit donc pas être utilisé que sur des très petits volumes de données.

J'ai écrit des fonctions plus rapide de rapprochement de motifs que vous pouvez adapter à MySQmerde :
http://sqlpro.developpez.com/cours/s...aisons-motifs/

A +

**trucmuche2005** · 05/09/2017, 16h33

Merci à vous pour vos réponses ! Je viens d'implémenter la distance de Hamming en adaptant l'algorithme de SQLPro et là où une requête prenait 4s avec la distance de Levenshtein, cela n'en prend plus que 0,08s avec Hamming. Chouette donc :-)
Je vais encore tester mais je pense que c'est résolu :-)

Et voici la traduction de l'algorithme en MySQL, pour ceux que cela intéresserait à l'avenir :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
DELIMITER $$
CREATE FUNCTION hamming( src VARCHAR(255), cible VARCHAR(255) )
RETURNS INT
DETERMINISTIC
BEGIN
DECLARE cnt, i, l INT;
IF src IS NULL or cible IS NULL 
THEN RETURN NULL; 
END IF;
IF src = cible THEN 
RETURN 0;
END IF;
IF src='' OR cible='' THEN 
RETURN CHAR_LENGTH(src)+CHAR_LENGTH(cible);
END IF;
 
 
SET i=1;
SET l = CHAR_LENGTH(src);
IF (CHAR_LENGTH(cible)>l) THEN SET l = CHAR_LENGTH(cible); END IF;
 
SET cnt = 0;
 
myloop: WHILE i <= l DO
IF i > CHAR_LENGTH(src) THEN
	SET cnt = cnt+CHAR_LENGTH(cible)-CHAR_LENGTH(src)+1;
	LEAVE myloop;
END IF;
IF i > CHAR_LENGTH(cible) THEN
	SET cnt = cnt+CHAR_LENGTH(src)-CHAR_LENGTH(cible)+1;
	LEAVE myloop;
END IF;
IF SUBSTRING(src, i, 1) <> SUBSTRING(cible, i, 1) THEN
	SET cnt = cnt+1;
END IF;
 
SET i = i+1;
 
END WHILE;
RETURN cnt;
END $$
###

EDIT. Oui bon je vais aller un cran plus loin et implémenter ce que SQLPro appelle l'inférence basique car avec la distance de Hamming, les mots "mongrandmot" et "mMongrandmot" sont beaucoup plus différents que "mongrandmot" et "mongrandmott"... Ce qui n'est pas vraiment logique - ils ont tous les deux une distance de Levenshtein de 1. Je vais donc traduire son "inférence basique" et reviendrai vers vous pour vous faire un retour...

**trucmuche2005** · 07/09/2017, 13h19

Bien le bonjour !

@sqlpro : J'ai adapté votre "inférence basique" à MySQL (et je joins le code ci-dessous pour simple partage), mais je me suis vraiment interrogé concernant votre portion de code ici :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
-- première passe source vers cible
WHILE @I <= @L
BEGIN
   SET @C = SUBSTRING(@SOURCE, @I, 1)
   IF CHARINDEX(@C, @CIBLE, @J) > 0
   BEGIN
      SET @COUNT1 = @COUNT1 + 1
      SET @J = CHARINDEX(@C, @CIBLE, @J) + 1
      SET @I = @I + 1  
      CONTINUE
   END
   SET @I = @I + 1
END

Si je comprends bien, l'instruction "SET @I = @I + 1" est réalisée quelle que soit la valeur de la condition testée. Ne serait-il donc pas plus simple d'écrire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
-- première passe source vers cible
WHILE @I <= @L
BEGIN
   SET @C = SUBSTRING(@SOURCE, @I, 1)
   IF CHARINDEX(@C, @CIBLE, @J) > 0
   BEGIN
      SET @COUNT1 = @COUNT1 + 1
      SET @J = CHARINDEX(@C, @CIBLE, @J) + 1
   END
   SET @I = @I + 1
END

???
A première vue, cela ne change strictement rien... Juste ou pas ? (sauf que cela fait économiser deux lignes de code, donc 4 au total puisque c'est la même chose sur la seconde passe). Dites-moi si je fais fausse route... :-)

En outre, je me demandais comment avoir une idée "intuitive de cette distance inférence basique" (que je note dist_IB). Avec Levenshtein, c'est très clair, par exemple. Mais moins avec dist_IB, il me semble.
Par exemple, dist_IB("test", "testt") = 4 alors que dist_IB("machin", "machinn") = 6 et dist_IB("constitution", "constitutionn") = 12... alors que le même phénomène a lieu pour chaque mot : l'ajout d'une lettre à la fin. Ne serait-il pas pertinent de "ramener" cette mesure en rapport avec la longueur des mots ?? Mais alors comment (pour que cela reste symétrique et que "testt" ne soit pas plus loin de "test" que l'est "constitutionn" de "constitution") ??

Levenshtein permet de compter le nombre de fautes de frappe et cela permet de créer un algorithme qui apparie des mots tapés par l'utilisateur avec des mots prédéfinis en tolérant par exemple un maximum de 4 fautes de frappe pour apparier. Ainsi, avec Levenshtein, "testt" sera apparié à "test" et "constitutionn" à "constitution", ce qui me paraît normal.

Mais avec dist_IB, si je fixe un seuil quelconque de tolérance pour apparier un mot "mal orthographié" avec son analogue connu, je suis sûr que l'algorithme va rater dès que les mots deviendront "grands". Si je fixe un seuil de 5, "testt" sera apparié à "test" mais "constitutionn" ne le sera pas avec "constitution"...

Quel est votre avis ? Faut-il changer de méthode ? Les mots que je dois comparer ont une longueur comprise entre 4 et 20 caractères, grand grand max...

Merci encore et à bientôt !

T.

Remarque. Pour l'adaptation ci-dessous, je me suis permis d'ajouter des "cas de base" où la source et la cible sont identiques ou null.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
DELIMITER $$
CREATE FUNCTION distance_inference_basique( src VARCHAR(255), cible VARCHAR(255) )
RETURNS INT
DETERMINISTIC
BEGIN
DECLARE COUNT1, COUNT2 INT;
DECLARE I, J, L INT;
DECLARE C CHAR(1);
 
## CAS ELEMENTAIRES 
IF SOURCE IS NULL or CIBLE IS NULL 
THEN RETURN NULL; 
END IF;
IF SOURCE = CIBLE THEN 
RETURN 0;
END IF;
 
## LES AUTRES CAS, MAINTENANT !
SET COUNT1 = 0;
SET COUNT2 = 0;
 
SET I = 1;
SET J = 1;
SET L = CHAR_LENGTH(SOURCE);
 
premiere_passe:WHILE I <= L DO
   SET C = SUBSTRING(SOURCE, I, 1);
   IF LOCATE(C, CIBLE, J) > 0 THEN
      SET COUNT1 = COUNT1 + 1 ;
      SET J = LOCATE(C, CIBLE, J) + 1 ;
   END IF;
   SET I = I + 1;
END WHILE;
 
IF COUNT1 = 0 THEN RETURN 0; END IF;
 
SET I = 1;
SET J = 1;
SET L = CHAR_LENGTH(CIBLE);
 
seconde_passe:WHILE I <= L DO 
   SET C = SUBSTRING(CIBLE, I, 1);
   IF LOCATE(C, SOURCE, J) > 0 THEN
      SET COUNT2 = COUNT2 + 1;
      SET J = LOCATE(C, SOURCE, J) + 1;
   END IF;
   SET I = I + 1;
END WHILE;
 
IF COUNT1 < COUNT2 THEN
   SET COUNT1 = COUNT2;
END IF;
 
RETURN COUNT1;
END $$

**tbc92** · 07/09/2017, 14h06

Visiblement , la fonction dist_IB ne renvoie pas un indicateur de distance, mais un indicateur de similarité : plus le nombre est grand, plus les 2 chaines se ressemblent. Ici , quand les 2 chaines sont identiques, tu as un test dédié pour renvoyer 0, mais la procédure d'origine renvoyait en fait la longueur de la chaine.

Et à l'opposé, la fonction renvoie 0 quand les 2 chaines n'ont aucun caractère en commun.

Si tu veux une distance (grande quand peu de caractères communs, et 0 quand les 2 chaines sont identiques), tu dois modifier un peu le code ; par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
L1 = length (@SOURCE) ;
L2 = length (@CIBLE) ;
LL = L1 ;
if L2 > LL then LL = L2 ;
 
// Calcul de Count1 avec l'algo actuel 
return   ( LL-Count1) / LL  ;

**trucmuche2005** · 11/09/2017, 17h01

Merci... soupir. Être plus attentif. Être plus attentif. Être plus attentif. Être plus attentif. Être plus attentif...
Par contre avec ce calcul, une différence d'une lettre sur un mot de 4 caractères engendre une distance de 25% tandis que la même différence d'une lettre sur un mot de 10 caractères engendre une distance de 10%. Pourtant, c'est la même différence donc j'aimerais faire en sorte que la distance soit la même... Hmmm... Je bloque...

EDIT. Il semblerait que (LMAX - COUNT1) soit la valeur qui m'intéresse... Pour des mots de 4 lettres comme des mots de 10 lettres, si je fais une faute de frappe sur une lettre, cela retourne 1.

**SQLpro** · 11/09/2017, 17h14

Réfléchit :
si tu as un QCM avec 10 questions et que tu fais une erreur, est-ce plus ou moins grave qu'une erreur avec un QCM à 4 questions ???

A +

**trucmuche2005** · 11/09/2017, 17h24

En fait j'ai deux options et il faut que je me fixe sur l'une ou l'autre. Soit je m'intéresse à une estimation du nombre de fautes de frappe et du coup, le plus précis est levenshtein (mais il est lent, d'où ma recherche d'un autre algorithme) soit je m'intéresse à la distance entre deux mots et là, il paraît effectivement normal que "concurrenR" soit plus proche de "concurrent" que "tesR" ne l'est de "test".
Juste que c'est deux optiques différentes et j'oscille un peu entre les deux, pour le moment... Je vais y re-réfléchir...

select avec distance de Levenshtein [MySQL-5.6]

Requêtes MySQL

Discussions similaires

Partager

Partager