Оптимизация алгоритма расстояния Левенштейна
У меня есть хранимая процедура, которая использует расстояние Левенштейна для определения результата, наиболее близкого к тому, что набрал пользователь. Единственное, что действительно влияет на скорость, - это функция, которая вычисляет расстояние Левенштейна для всех записей перед выбором записи с наименьшим расстоянием (я проверил это, поставив 0 вместо вызова функции Левенштейна). Таблица содержит 1,5 миллиона записей, поэтому даже малейшая корректировка может сбить несколько секунд. Прямо сейчас все это занимает более 10 минут. Вот метод, который я использую:
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
Куда мне идти отсюда?