Levenshtein编辑距离算法，支持C＃中两个相邻字母的换位

Question

我正在寻找一种计算Levenshtein编辑距离的算法，该算法还支持两个相邻字母在C＃中实施换位的情况。

例如单词“动物”和“ainmals”：字母“n”和“我” 不会被打进两个替换哪位会带来很大的距离之间 切换 - 而是在将进球作为两个字母转置-much更少距离 -

我在搜索

• computing Lichtenstein distance迄今达成，但它不包含更换
• this question

Answer 1

您需要添加附加条件使其成为“Damerau-Levenshtein距离”算法。因此，利用这里的例子：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 
       );