1

C＃で実装されている2つの隣接する文字が転置される場合もサポートする、レーベンシュタイン編集距離を計算するためのアルゴリズムを探しています。

たとえば、「animals」と「ainmals」という単語：「n」と「i」の文字を切り替えると、2つの置換としてスコアが付けられず、距離が長くなりますが、代わりに2つの文字の転置としてスコアが付けられます。はるかに短い距離-

検索でこれまでに到達したもの

4

2 に答える 2

6

ウィキペディアの実装を参照してください。文字交換のケースを含めるようにアルゴリズムを簡単に適応させることができます。例えば：

//bla bla. I'm just copying the code on the Wikipedia.
 d[i, j] := minimum
                   (
                     d[i-1, j] + 1,  // a deletion
                     d[i, j-1] + 1,  // an insertion
                     d[i-1, j-1] + 1, // a substitution
                   )

// This single statement is all you need:
if(s[i-1]==t[j-2] && s[i-2]==t[j-1])
   d[i,j] := minimum
                  (
                      d[i,j],               //cost without swapping 
                      d[i-2,j-2]+something  //cost with swapping. probably something=1 
                  );
于 2012-04-16T17:32:43.060 に答える
1

「Damerau–Levenshtein 距離」アルゴリズムにするために、追加の条件を追加する必要があります。したがって、次の例を使用してください: http://www.dotnetperls.com/levenshteinステップ 6 の直後に次の条件を追加するだけです。

 //** Step 7 to make it Damerau–Levenshtein distance
      if (i > 1 && j > 1 && (s[i - 1] == t[j - 2]) && (s[i - 2] == t[j - 1]))
      {
             d[i, j] = Math.Min(
                            d[i, j],
                            d[i - 2, j - 2] + cost   // transposition
                         );
      }
于 2014-09-16T21:10:33.770 に答える