Попытка использовать расстояние Левенштейна в T-SQL-запросах - Помогите, пожалуйста, оптимизация - PullRequest
Новая
       20

Попытка использовать расстояние Левенштейна в T-SQL-запросах - Помогите, пожалуйста, оптимизация

2 голосов
/ 13 декабря 2010

Я пытаюсь использовать алгоритм Левенштейна, который я нашел в сети, чтобы вычислить значение, наиболее близкое к поисковому запросу.Для реализации нечеткого соответствия терминов.Мой текущий запрос выполняется около 45 секунд.Я надеюсь, что смогу оптимизировать это.Я уже добавил индексы для полей, для которых я рассчитал значение Левенштейна.Функция Левенштейна, которую я нашел, может быть не самой оптимизированной, и я не воздаю должное ее реализации.Вот эта функция: 

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

И вот запрос, который я использую: 

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

Я не администратор баз данных, поэтому, пожалуйста, простите мое невежество в любых лучших практиках - этопочему я здесь, чтобы учиться :).Я действительно не хочу переложить эту обработку на бизнес-уровень и надеюсь сохранить ее на уровне данных, но из-за обработки только 16 тыс. Записей, занимающих 45 секунд, в настоящее время она непригодна для использования.Это только с небольшим подмножеством записей, которые будут составлять все хранилище данных, как только я закончу обработку входных файлов.Заранее спасибо.

Ответы [ 2 ]

5 голосов
/ 31 октября 2011

Если вы хотите, чтобы он работал очень быстро, подумайте о создании dll в C #.Это улучшит вашу скорость на 150%;)

Вот мой блог, который объясняет вам, как это сделать.

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

2 голосов
/ 04 февраля 2011

Вы должны прочитать эту ветку и эти ссылки: http://www.vbforums.com/showthread.php?t=575471

...