Оптимизация алгоритма расстояния Левенштейна - PullRequest
Новая
       30

Оптимизация алгоритма расстояния Левенштейна

3 голосов
/ 27 мая 2010

У меня есть хранимая процедура, которая использует расстояние Левенштейна для определения результата, наиболее близкого к тому, что набрал пользователь. Единственное, что действительно влияет на скорость, это функция, которая вычисляет расстояние Левенштейна для всех записей перед выбором записи с наименьшим расстоянием (я проверил это, поставив 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

Куда мне идти отсюда?

1 Ответ

6 голосов
/ 27 мая 2010

То, как я делал это в прошлом, - это сохранение «базы данных» (фактически словаря слов для корректора орфографии) в виде дерева.

Затем я использовал подпрограмму ветвей и границ для поиска ближайших подходящих записей. Для небольших расстояний время экспоненциально на расстоянии. Для больших расстояний он является линейным по размеру словаря, как вы видите сейчас.

Ветвление и ограничение - это, в основном, обход дерева дерева в глубину, но с бюджетом ошибок. На каждом узле вы отслеживаете текущее расстояние Левенштейна, а если оно превышает бюджет, вы обрезаете эту ветвь дерева.

Сначала вы делаете прогулку с нулевым бюджетом. Это только найдет точные совпадения. Если вы не нашли совпадения, вы идете с бюджетом в один. Это позволит найти совпадения на расстоянии 1. Если вы не найдете ни одного, то вы делаете это с бюджетом 2, и так далее. Это звучит неэффективно, но, поскольку каждая прогулка занимает намного больше времени, чем предыдущая, во время последней прогулки преобладает последняя.

Добавлено: набросок кода (простите мой C): 

// dumb version of trie node, indexed by letter. You can improve.
typedef struct tnodeTag {
  tnodeTag* p[128];
} tnode;

tnode* top; // the top of the trie

void walk(tnode* p, char* s, int budget){
  int i;
  if (*s == 0){
    if (p == NULL){
      // print the current trie path
    }
  }
  else if (budget >= 0){
    // try deleting this letter
    walk(p, s+1, budget-1);
    // try swapping two adjacent letters
    if (s[1]){
      swap(s[0], s[1]);
      walk(p, s, budget-1);
      swap(s[0], s[1]);
    }
    if (p){
      for (i = 0; i < 128; i++){
        // try exact match
        if (i == *s) walk(p->p[i], s+1, budget);
        // try replacing this character
        if (i != *s) walk(p->p[i], s+1, budget-1);
        // try inserting this letter
        walk(p->p[i], s, budget-1);
      }
    }
  }
}

По сути, вы имитируете удаление письма, пропуская его и ища в том же узле. Вы симулируете вставку письма, убирая три без продвижения s. Вы имитируете замену буквы, действуя так, как будто буква совпадает, даже если это не так. Когда вы освоитесь, вы можете добавить другие возможные несоответствия, например, заменить 0 на O, а 1 на L или I - глупые вещи вроде этого.

Возможно, вы захотите добавить аргумент массива символов для представления текущего слова, которое вы найдете в дереве.

...