Optimización del algoritmo de distancia de Levenshtein
Tengo un procedimiento almacenado que usa la distancia de Levenshtein para determinar el resultado más cercano a lo que escribió el usuario. Lo único que realmente afecta la velocidad es la función que calcula la distancia de Levenshtein para todos los registros antes de seleccionar el registro con la distancia más baja (lo he verificado poniendo un 0 en lugar de la llamada a la función de Levenshtein). La tabla tiene 1,5 millones de registros, por lo que incluso el más mínimo ajuste puede reducirse unos segundos. En este momento todo el proceso dura más de 10 minutos. Aquí está el método que estoy usando:
ALTER function dbo.Levenshtein
(
@Source nvarchar(200),
@Target nvarchar(200)
)
RETURNS int
AS
BEGIN
DECLARE @Source_len int, @Target_len int, @i int, @j int, @Source_char nchar, @Dist int, @Dist_temp int, @Distv0 varbinary(8000), @Distv1 varbinary(8000)
SELECT @Source_len = LEN(@Source), @Target_len = LEN(@Target), @Distv1 = 0x0000, @j = 1, @i = 1, @Dist = 0
WHILE @j <= @Target_len
BEGIN
SELECT @Distv1 = @Distv1 + CAST(@j AS binary(2)), @j = @j + 1
END
WHILE @i <= @Source_len
BEGIN
SELECT @Source_char = SUBSTRING(@Source, @i, 1), @Dist = @i, @Distv0 = CAST(@i AS binary(2)), @j = 1
WHILE @j <= @Target_len
BEGIN
SET @Dist = @Dist + 1
SET @Dist_temp = CAST(SUBSTRING(@Distv1, @j+@j-1, 2) AS int) +
CASE WHEN @Source_char = SUBSTRING(@Target, @j, 1) THEN 0 ELSE 1 END
IF @Dist > @Dist_temp
BEGIN
SET @Dist = @Dist_temp
END
SET @Dist_temp = CAST(SUBSTRING(@Distv1, @j+@j+1, 2) AS int)+1
IF @Dist > @Dist_temp SET @Dist = @Dist_temp
BEGIN
SELECT @Distv0 = @Distv0 + CAST(@Dist AS binary(2)), @j = @j + 1
END
END
SELECT @Distv1 = @Distv0, @i = @i + 1
END
RETURN @Dist
END
¿A dónde debería ir desde aquí?