通过交换编辑距离

Question

编辑距离可以找到一个字符串到另一个字符串所需的插入，删除或替换的数量。我还想在此算法中包含交换。例如，“ apple”和“ appel”的编辑距离应为1。

Answer 1

您定义的编辑距离称为Damerau–Levenshtein距离。您可以在Wikipedia页面上找到可能的实现。

Answer 2

请参阅此处的算法。

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/

您可以为交换、添加、删除指定不同的成本。

m[i,j] = min(m[i-1,j-1]
         + if s1[i]=s2[j] then 0 else cost_swap fi,
         m[i-1, j] + cost_insert,
         m[i, j-1] + cost_delete ),  i=1..|s1|, j=1..|s2|