使用交换编辑距离

Question

编辑距离查找一个字符串到另一个字符串所需的插入，删除或替换次数。我想在这个算法中也包括掉换。例如，“apple”和“appel”应该给出编辑距离1.

Answer 1

请参阅此处的算法。

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| 

Answer 2

正在定义编辑距离被称为Damerau-Levenshtein距离。你可以在Wikipedia page上找到可能的实现。