使用交換編輯距離

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上找到可能的實現。