11

私はLevenshteinsEditDistanceアルゴリズムで遊んでいますが、これを拡張して、転置（つまり、隣接する文字の交換）を1つの編集としてカウントしたいと思います。変更されていないアルゴリズムは、別の文字列から特定の文字列に到達するために必要な挿入、削除、または置換をカウントします。たとえば、「KITTEN」から「SITTING」までの編集距離は3です。Wikipediaからの説明は次のとおりです。

  1. 子猫→座る（「k」を「s」に置き換える）
  2. シッテン→シッティン（「e」から「i」への置換）
  3. シッティン→シッティング（最後に「g」を挿入）。

同じ方法で、「CHIAR」から「CHAIR」までの編集距離は2です。

  1. CHIAR→CHAR（'I'を削除）
  2. CHAR→CHAIR（「I」を挿入）

隣接する2文字しか交換しないので、これを「1編集」として数えたいと思います。どうすればこれを行うことができますか？

4

3 に答える 3

19

ウィキペディアのアルゴリズムにはもう1つのケースが必要です。

if s[i] = t[j] then 
  d[i, j] := d[i-1, j-1]
else if i > 0 and j > 0 and s[i] = t[j - 1] and s[i - 1] = t[j] then
  d[i, j] := minimum
             (
               d[i-2, j-2] + 1 // transpose
               d[i-1, j] + 1,  // deletion
               d[i, j-1] + 1,  // insertion
               d[i-1, j-1] + 1 // substitution
             )
else
  d[i, j] := minimum
             (
               d[i-1, j] + 1,  // deletion
               d[i, j-1] + 1,  // insertion
               d[i-1, j-1] + 1 // substitution
             )
于 2010-10-29T20:10:42.917 に答える
1

動的計画法テーブルを更新する方法を変更する必要があります。元のアルゴリズムでは、長さが最大で1つ異なる2つの単語の末尾（または先頭）を考慮します。更新は、そのようなすべての可能性の最小です。

隣接する2つの場所での変更が1つとしてカウントされるようにアルゴリズムを変更する場合は、上記の最小値を、最大で2つ異なるテール（またはヘッド）で計算する必要があります。これをより大きな近隣に拡張することはできますが、その近隣のサイズが大きくなると複雑さが増します。

さらに一般化して、削除、挿入、または置換された文字に応じてコストを割り当てることができますが、ペア編集に割り当てるコストが2つの単一編集よりも低いことを確認する必要があります。そうでない場合、2つの単一編集は常に勝ちます。

単語をw1とw2とします

dist(i,j) = min(
                dist(i-2,j-2) && w1(i-1,i) == w2(j-1,j) else
                dist(i-1,j-1) && w1(i) == w2(j) else
                dist(i,j-1)   + cost(w2(j)),
                dist(i-1,j)   + cost(w1(i)),
                dist(i-1,j-1) + cost(w1(i), w2(j)),
                dist(i, j-2)  + cost(w2(j-1,j)),
                dist(i-2, j)  + cost(w1(i-1,i)),
                dist(i-2,j-2) + cost(w1(i-1,i), w2(j-1,j))
                )

つまり&&、これらの行は、条件が満たされた場合にのみ考慮されるべきであるということです。

于 2010-10-29T20:39:34.787 に答える
1

他の答えは、あなたが説明していると思うダメラウ・レーベンシュタインではなく、最適な文字列整列アルゴリズムを実装することです。

ここにいくつかの最適化を加えたOSAのJava実装があります： https ：//gist.github.com/steveash/5426191

于 2013-04-20T14:50:08.947 に答える