Discussion :

[Adi81]

Bonjour à tous,

J'ai développé sous SQL Server la fonction de Levenshtein qui calcule la distance entre deux chaines de caractères.
Je pensais pouvoir l'utiliser lors de mon travail de recherche de doublons mais cette fonction s'avère être très lente et cela rend la recherche et traitement des doublons beaucoup trop long.


Pourriez vous m'aider à l'optimiser ?

Voici le code (un peu long):

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
 
CREATE FUNCTION DISTANCE_LEVENSHTEIN ( 
	@Chaine1 VARCHAR(8000),
	@Chaine2 VARCHAR(8000)
)  
RETURNS INT AS  
BEGIN 
 
DECLARE @Tableau TABLE( ID Int PRIMARY KEY, Valeur INT )
DECLARE  @len1 INT
DECLARE @len2 INT
DECLARE @i INT
DECLARE @j INT
DECLARE @tmp Int
DECLARE @v1 Int 
DECLARE @v2 Int 
DECLARE @v3 Int 
DECLARE @Vmin Int 
DECLARE @COUT INT
 
 
SET @len1 = LEN(@Chaine1) + 1
SET @len2 = LEN(@Chaine2) + 1
 
IF @len1= 1 OR @len2 = 1 
BEGIN 
	RETURN 9999 
END
 
/* Initialisation du tableau */
SET @i = 0
WHILE (@i < @len1*@len2)
BEGIN
	INSERT INTO @Tableau VALUES (@i, 0)
	SET @i = @i + 1
END
 
/* Initialisation de la premiere ligne */
SET @i = 0
WHILE (@i < @len1)
BEGIN
	SET @tmp = dbo.f( 0, @i, @len1 ) 
	UPDATE @Tableau SET Valeur = @i
		WHERE ID = @tmp
	SET @i = @i + 1
END
 
/* initialisation de la premiere colonne */
SET @i = 0
WHILE (@i < @len2)
BEGIN
	SET @tmp = dbo.f( @i, 0, @len1 ) 
	UPDATE @Tableau SET Valeur = @i
		WHERE ID = @tmp
	SET @i = @i + 1
END
 
/* On compare les deux chaines */
 
SET @i = 1
 
WHILE (@i <@len1) /* Colonne */
BEGIN
	SET @j = 1
	WHILE (@j < @len2) /* Ligne */
	BEGIN
 
		/* On regarde si les caractères correspondent */
		IF ( SUBSTRING(@chaine1,@i,1) = SUBSTRING(@chaine2,@j,1))
		BEGIN
			/* EGALITE */
			SET @COUT = 0		
		END
		ELSE
		BEGIN
			/* SUBSTITUTION, INSERTION */
			SET @COUT = 1
		END
 
		/* Lecture de la case de gauche */
		SELECT @v1 = Valeur+1 
		FROM @Tableau 
		WHERE ( ID = dbo.f( @j, @i-1, @len1 ) ) 
 
		/* Lecture de la case d au dessus */
		SELECT @v2 = Valeur+1 
		FROM @Tableau 
		WHERE ( ID = dbo.f( @j-1, @i, @len1 ) ) 
 
		/* Lecture de la case de diagonale gauche haute */
		SELECT @v3 = @COUT+ Valeur
		FROM @Tableau 
		WHERE ( ID = dbo.f( @j-1, @i-1, @len1 ) ) 
 
		/* On prend la valeur la plus petite et on l'insere dans la case actuelle */
 
		IF (@V1 <= @V2 AND @V1 <= @V3)
		BEGIN
			SET @Vmin =@V1
		END
		ELSE
		BEGIN
			IF (@V2 <= @V3)
			BEGIN
				SET @Vmin = @V2
			END
			ELSE
			BEGIN
				SET @Vmin = @V3
			END
		END		
 
 
		SET @tmp = dbo.f( @j, @i, @len1 )
		UPDATE @Tableau 
		SET Valeur = @Vmin
		WHERE ( ID = @tmp )
 
		SET @j = @j +1
	END
 
	SET @i = @i +1
END
 
 
/* On retourne le cout de la transformation */
SELECT @tmp = Valeur 
FROM @Tableau 
WHERE ( ID = dbo.f(@len2-1, @len1-1, @len1 ) ) 
 
 
RETURN (@tmp)
 
END

[SQLpro]

J'ai commencé à optimiser mais tu n'a pas posté le contenu de la fonction f...
Peut tu nous donner le code ???

A +

[Adi81]

Voila la fonction F :

Code :

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

1
2
3
4
5
6
 
CREATE FUNCTION f( @l Int, @c Int, @m Int ) 
  RETURNS Int AS 
BEGIN 
  RETURN ( @l * @m ) + @c 
END

[SQLpro]

je pense pas qu'on puisse faire grand chose de plus :

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
CREATE FUNCTION DISTANCE_LEVENSHTEIN (
   @Chaine1 VARCHAR(8000),
   @Chaine2 VARCHAR(8000)
) 
RETURNS INT AS 
BEGIN
 
-- gestion des effets de bord
-- null en entrée
IF @Chaine1 IS NULL OR @Chaine2 IS NULL
   RETURN NULL
 
-- identique
IF @Chaine1 = @Chaine2 
   RETURN 0
 
DECLARE @len1 INT
DECLARE @len2 INT
 
SET @len1 = LEN(@Chaine1) + 1
SET @len2 = LEN(@Chaine2) + 1
 
-- chaine vide avec chaine pleine
IF @len1= 1 OR @len2 = 1
BEGIN
   RETURN @len1 + @len2 - 2
END
 
DECLARE @Tableau TABLE(ID Int, Valeur INT)
DECLARE @i INT
DECLARE @j INT
DECLARE @tmp Int
DECLARE @v1 Int
DECLARE @v2 Int
DECLARE @v3 Int
DECLARE @Vmin Int
DECLARE @COUT INT
 
 
/* Initialisation du tableau */
SET @i = 0
WHILE (@i < @len1*@len2)
BEGIN
   INSERT INTO @Tableau VALUES (@i, 0)
   SET @i = @i + 1
END
 
/* Initialisation de la premiere ligne */
SET @i = 0
WHILE (@i < @len1)
BEGIN
   SET @tmp = 0 --dbo.f( 0, @i, @len1 ) <=> 0 * @len1 + @i
   UPDATE @Tableau SET Valeur = @i
      WHERE ID = @tmp
   SET @i = @i + 1
END
 
/* initialisation de la premiere colonne */
SET @i = 0
WHILE @i < @len2
BEGIN
   SET @tmp = @i * @len1 -- dbo.f( @i, 0, @len1 ) <=> @i * @len1 + 0
   UPDATE @Tableau SET Valeur = @i
      WHERE ID = @tmp
   SET @i = @i + 1
END
 
/* On compare les deux chaines */
 
SET @i = 1
 
WHILE @i <@len1 /* Colonne */
BEGIN
   SET @j = 1
   WHILE @j < @len2 /* Ligne */
   BEGIN
 
      /* On regarde si les caractères correspondent */
      IF SUBSTRING(@chaine1, @i, 1) = SUBSTRING(@chaine2, @j, 1)
         /* EGALITE */
         SET @COUT = 0      
      ELSE
         /* SUBSTITUTION, INSERTION */
         SET @COUT = 1
 
      /* Lecture de la case de gauche */
      SELECT @v1 = Valeur+1
      FROM   @Tableau
      WHERE  ID = @j * @len1 + @i - 1 -- dbo.f( @j, @i-1, @len1 ) <=> @j * @len1 + @i - 1 
 
      /* Lecture de la case d au dessus */
      SELECT @v2 = Valeur+1
      FROM   @Tableau
      WHERE  ID = (@j-1) * @len1 + @i -- dbo.f( @j-1, @i, @len1 ) <=> (@j-1) * @len1 + @i
 
      /* Lecture de la case de diagonale gauche haute */
      SELECT @v3 = @COUT+ Valeur
      FROM   @Tableau
      WHERE  ID = (@j-1) * @len1 + @i-1  -- dbo.f( @j-1, @i-1, @len1 ) <=> (@j-1) * @len1 + @i-1 
 
      /* On prend la valeur la plus petite et on l'insere dans la case actuelle */
      IF @V1 <= @V2 AND @V1 <= @V3
         SET @Vmin =@V1
      ELSE
         IF @V2 <= @V3
            SET @Vmin = @V2
         ELSE
            SET @Vmin = @V3
 
 
      SET @tmp = @j * @len1 +  @i --dbo.f( @j, @i, @len1 ) <=> @j * @len1 +  @i
      UPDATE @Tableau
      SET Valeur = @Vmin
      WHERE ID = @tmp
 
      SET @j = @j +1
   END
 
   SET @i = @i +1
END
 
 
/* On retourne le cout de la transformation */
SELECT @tmp = Valeur
FROM   @Tableau
WHERE  ID = (@len2-1) * @len1 + @len1-1 -- dbo.f(@len2-1, @len1-1, @len1 ) <=> (@len2-1) * @len1 + @len1-1
 
 
RETURN @tmp
 
END

En revanche, il est sans doute intéressant de la redévelopper en C++ et la mettre en dll ("fonction étendue") en V 2000, sinon en V 2005 il est très interressant de la redévelopper avec C# en SQL CLR.
Les seules problématiques dans ces deux cas de figure sont celles liées à la collation.

Pour finir, s'il faut gérer la collation dans la fonction, il faudra démultiplié par 4 cette fonction avec deux paramètres supplémentaires :

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
CREATE FUNCTION DISTANCE_LEVENSHTEIN 
       (@Chaine1 VARCHAR(8000), @Chaine2 VARCHAR(8000), @CS BIT = 0, @AS BIT = 0)
 
RETURNS INT AS 
BEGIN
 
[...]
     SET @COUT =
     CASE
        WHEN @CS = 0 AND @AS = 0
           THEN CASE 
                   WHEN SUBSTRING(@chaine1, @i, 1) 
                         = SUBSTRING(@chaine2, @j, 1) COLLATE Latin1_General_CI_AI
                      THEN 0
                   ELSE 1
                END
        WHEN @CS = 1 AND @AS = 0
           THEN CASE 
                   WHEN SUBSTRING(@chaine1, @i, 1) 
                         = SUBSTRING(@chaine2, @j, 1) COLLATE Latin1_General_CS_AI
                      THEN 0
                   ELSE 1
                END
        WHEN @CS = 0 AND @AS = 1
           THEN CASE 
                   WHEN SUBSTRING(@chaine1, @i, 1) 
                         = SUBSTRING(@chaine2, @j, 1) COLLATE Latin1_General_CI_AS
                      THEN 0
                   ELSE 1
                END
        WHEN @CS = 1 AND @AS = 1
           THEN CASE 
                   WHEN SUBSTRING(@chaine1, @i, 1) 
                         = SUBSTRING(@chaine2, @j, 1) COLLATE Latin1_General_BIN
                      THEN 0
                   ELSE 1
                END
      END

PS : puis-je la publier sur mon site SQL pro ? Bien entendu avec ton nom d'auteur... et si tu as une référence de site web ou un mail protégé, cela y figurera.

A +

[WOLO Laurent]

Déjà, pour ce qui saute à l'oeil nu

Code :

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

1
2
3
4
5
6
7
8
 
* Initialisation du tableau */ 
SET @i = 0 
WHILE (@i < @len1*@len2) 
BEGIN 
   INSERT INTO @Tableau VALUES (@i, 0) 
   SET @i = @i + 1 
END

Je lui préfère une variante comme celle-ci:

Code :

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

1
2
3
4
5
6
set @taille=@len1*@len2
WHILE (@i < @taille) 
BEGIN 
   INSERT INTO @Tableau VALUES (@i, 0) 
   SET @i = @i + 1 
END

Pour le reste, nous continuons à chercher.

[Adi81]

Merci pour ta réponse

Bien entendu, tu peux la reprendre pour ton site. C'est surtout grâce à votre aide que j'ai pu la développer donc je ne me sent pas particulièrement propriétaire.

A bientôt.

[SQLpro]

Oh Oui, laurent, j'ai pas vu ça !!!!

Mais y va falloir adpater car cela ne donne pas la bonne réponse :

sans la modif de laurent :
SELECT dbo.DISTANCE_LEVENSHTEIN ('marcoussis', 'marcassin')
donne 3 ce qui est exact

avec la modif de laurent :
donne 109 !!!

A +

[WOLO Laurent]

D'ou est ce que ce problème peut provenir ?
Je teste et je vous tiens au courant des résultats

[Adi81]

Attention tout de même car il y a une faute de frappe dans ton code SQLpro lors de l'initialisation de la premiere ligne.
Il ne faut pas mettre

Code :

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

SET @tmp = 0

mais

Code :

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

SET @tmp = @i

Ton erreur vient peut être de la