Алгоритм редактирования расстояния Левенштейна, который поддерживает транспонирование двух соседних букв в C#

Question

Я ищу алгоритм для вычисления расстояния редактирования Левенштейна, который также поддерживает случай, в котором транспонируются две соседние буквы, который реализован в C#.

например, слова "животные" и "животные": переключение между буквами "n" и "i" не будет оцениваться как две замены - которые будут занимать большое расстояние - но вместо этого будет оцениваться как транспонирование двух букв - гораздо больше меньше расстояния

чего я достиг в поисках

• вычисление расстояния Лихтенштейна, но оно не содержит замен
• этот вопрос

Answer 1

Вам необходимо добавить дополнительное условие, чтобы сделать его алгоритмом "расстояние Дамерау – Левенштейна". Итак, используя пример здесь: http://www.dotnetperls.com/levenshtein вам просто нужно добавить следующее условие сразу после шага 6:

 //** Step 7 to make it Damerau–Levenshtein distance
      if (i > 1 && j > 1 && (s[i - 1] == t[j - 2]) && (s[i - 2] == t[j - 1]))
      {
             d[i, j] = Math.Min(
                            d[i, j],
                            d[i - 2, j - 2] + cost   // transposition
                         );
      }

Answer 2

Смотрите реализацию в Википедии. Вы можете легко адаптировать алгоритм, чтобы включить регистр для замены букв. Например:

//bla bla. I'm just copying the code on the Wikipedia.
 d[i, j] := minimum
                   (
                     d[i-1, j] + 1,  // a deletion
                     d[i, j-1] + 1,  // an insertion
                     d[i-1, j-1] + 1, // a substitution
                   )

// This single statement is all you need:
if(s[i-1]==t[j-2] && s[i-2]==t[j-1])
   d[i,j] := minimum
                  (
                      d[i,j],               //cost without swapping 
                      d[i-2,j-2]+something  //cost with swapping. probably something=1 
                  );