Essayer d'utiliser la distance de Levenshtein dans la requête T-SQL - Optimiser l'aide SVP

Question

J'essaie d'utiliser un algorithme de levenshtein que j'ai trouvé sur le 'net pour calculer la valeur la plus proche d'un terme de recherche. Afin de mettre en œuvre la correspondance de terme floue. Ma requête actuelle dure environ 45 secondes. J'espère pouvoir l'optimiser. J'ai déjà ajouté des index pour les champs pour lesquels je calcule la valeur levenshtein. La fonction levenshtein que j'ai trouvée n'est peut-être pas la plus optimisée et je ne prends aucun crédit dans sa mise en œuvre. Voici cette fonction:

CREATE FUNCTION [dbo].[LEVENSHTEIN](@s NVARCHAR(MAX), @t NVARCHAR(MAX)) 
/* 
Levenshtein Distance Algorithm: TSQL Implementation 
by Joseph Gama 

http://www.merriampark.com/ldtsql.htm 

Returns the Levenshtein Distance between strings s1 and s2. 
Original developer: Michael Gilleland http://www.merriampark.com/ld.htm 
Translated to TSQL by Joseph Gama 

Fixed by Herbert Oppolzer/devio 
as described in http://devio.wordpress.com/2010/09/07/calculating-levenshtein-distance-in-tsql 
*/ 
RETURNS INT AS 
BEGIN 

    DECLARE @d NVARCHAR(MAX), @LD INT, @m INT, @n INT, @i INT, @j INT, 
    @s_i NCHAR(1), @t_j NCHAR(1),@cost INT 

    --Step 1 
    SET @n = LEN(@s) 
    SET @m = LEN(@t) 
    SET @d = REPLICATE(NCHAR(0),(@n+1)*(@m+1)) 
    IF @n = 0 
    BEGIN 
    SET @LD = @m 
    GOTO done 
    END 
    IF @m = 0 
    BEGIN 
    SET @LD = @n 
    GOTO done 
    END 

    --Step 2 
    SET @i = 0 
    WHILE @i <= @n BEGIN 
    SET @d = STUFF(@d,@i+1,1,NCHAR(@i))  --d(i, 0) = i 
    SET @i = @i+1 
    END 

    SET @i = 0 
    WHILE @i <= @m BEGIN 
    SET @d = STUFF(@d,@i*(@n+1)+1,1,NCHAR(@i)) --d(0, j) = j 
    SET @i = @i+1 
    END 

    --Step 3 
    SET @i = 1 
    WHILE @i <= @n BEGIN 
    SET @s_i = SUBSTRING(@s,@i,1) 

    --Step 4 
    SET @j = 1 
    WHILE @j <= @m BEGIN 
     SET @t_j = SUBSTRING(@t,@j,1) 
     --Step 5 
     IF @s_i = @t_j 
     SET @cost = 0 
     ELSE 
     SET @cost = 1 
     --Step 6 
     SET @d = STUFF(@d,@j*(@n+1)+@i+1,1, 
     NCHAR(dbo.MIN3(
      UNICODE(SUBSTRING(@d,@j*(@n+1)+@i-1+1,1))+1, 
      UNICODE(SUBSTRING(@d,(@j-1)*(@n+1)+@i+1,1))+1, 
      UNICODE(SUBSTRING(@d,(@j-1)*(@n+1)+@i-1+1,1))+@cost) 
     )) 
     SET @j = @j+1 
    END 
    SET @i = @i+1 
    END  

    --Step 7 
    SET @LD = UNICODE(SUBSTRING(@d,@n*(@m+1)+@m+1,1)) 

done: 
    RETURN @LD 
END 

Et voici la requête que je utilise:

SELECT [Address], [dbo].[LEVENSHTEIN](@searchTerm, [Address]) As LevenshteinDistance 
FROM Streets 
Order By LevenshteinDistance 

Je ne suis pas un DBA donc s'il vous plaît pardonnez mon ignorance dans les meilleures pratiques - c'est pourquoi je suis ici pour apprendre :). Je ne veux vraiment pas décharger ce traitement dans la couche de gestion et j'espère pouvoir le conserver dans la couche de données mais avec seulement 16k enregistrements prenant 45 secondes pour le traiter, il n'est actuellement pas utilisable. C'est seulement avec un petit sous-ensemble des enregistrements qui comprendra l'ensemble du magasin de données une fois que j'ai fini de traiter les fichiers d'entrée. Merci d'avance.

Answer 1

Si vous le souhaitez courir très vite, envisagez de créer une dll en C#. Il va améliorer votre vitesse de 150%;)

Voici mon blog qui vous explique comment le faire.

http://levenshtein.blogspot.com/2011/04/how-it-is-done.html

Answer 2

Vous devriez lire ce fil et ces liens: http://www.vbforums.com/showthread.php?t=575471