编辑距离（带有交换操作）

Question

编辑距离是指将一个字符串转换成另一个字符串所需的插入、删除或替换操作的次数。我想在该算法中还包括交换操作。例如，“apple”和“appel”的编辑距离应为1。

- Raja Roy

Answer 1

你所定义的编辑距离被称为 Damerau-Levenshtein距离。你可以在Wikipedia页面上找到可能的实现方法。

- a3nm

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|

- Rajendran T

---

你所回答的是替换而不是交换。在我上面给出的例子中，将第二个字符串中的“el”交换为“le”，从而与第一个字符串匹配。 - Raja Roy