edit-distance - 使用交换编辑距离

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|