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