edit-distance - スワップで距離を編集

Question

編集距離は、ある文字列から別の文字列に必要な挿入、削除、または置換の数を見つけます。このアルゴリズムにスワップも含めたいと思います。たとえば、「apple」と「appel」の編集距離は 1 にする必要があります。

Answer 1

定義している編集距離は、ダメラウ - レーベンシュタイン距離と呼ばれます。ウィキペディアのページで可能な実装を見つけることができます。

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|