スワップで距離を編集

Question

距離を編集すると、1つの文字列に必要な挿入、削除、または置換の数が検索されます。私はこのアルゴリズムのスワップも含めたいと思っています。たとえば、 "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・レーベンシュタイン距離と呼ばれています。可能な実装はWikipedia pageにあります。