C#中支持两个相邻字母转置的Levenshtein编辑距离算法

Question

我正在寻找一种计算 Levenshtein 编辑距离的算法，该算法也支持在 C# 中实现的两个相邻字母转置的情况。

例如单词“animals”和“ainmals”：字母“n”和“i”之间的切换不会被记为两个替换——这将产生很大的距离——而是将被记为两个字母的转置——更短的距离-

到目前为止我在搜索中所达到的

• 计算 Lichtenstein 距离 但它不包含替换
• 这个问题

Answer 1

请参阅维基百科上的实现。您可以轻松地调整算法以包括字母交换的情况。例如：

//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 
                  );