1前書き

この記事では、レーベンシュタイン距離、あるいは編集距離として説明します。ここで説明されているアルゴリズムは1965年にロシアの科学者、ウラジミールレーベンシュタインによって考案されました。

このアルゴリズムの反復的および再帰的なJava実装を提供します。


2レーベンシュタイン距離とは何ですか?

Levenshtein距離は、2つの

Stringsの間の非類似性の尺度です。数学的には、2つの

Strings


x



y

が与えられた場合、距離は

x



y__に変換するのに必要な最小文字数を測定します。

通常、3種類の編集が許可されています。

  1. 文字の挿入

    c

  2. 文字の削除

    c


  3. c



    c

    で置き換える

例:


x = ‘shot’

および

y =’ spot’

の場合、

‘shot’

は ‘

h

‘を ‘

p

‘に置き換えることで

‘spot’

に変換できるため、両者の編集距離は1です。

問題の特定のサブクラスでは、各タイプの編集に関連したコストが異なる場合があります。

たとえば、キーボードの近くにある文字との置き換えにかかるコストが少なく、それ以外の場合はコストが高くなります。簡単にするために、この記事ではすべてのコストを同じにします。

距離編集の用途には、次のものがあります。

  1. スペルチェッカー – テキストのスペルミスを検出して

辞書で最も近い正しいつづり
。盗作の検出(参照 –


IEEE Paper


。 DNA分析 – 2つの配列間の類似性の発見

  1. 音声認識(参照 –


3アルゴリズム定式化

長さがそれぞれ

m



n

の2つの

String x



y

を取りましょう。

それぞれの

String



x[1:m]

および__y[1:n]として表すことができます。

変換の終わりに、両方の

Strings

は同じ長さになり、各位置に一致する文字があることがわかります。したがって、各__Stringの最初の文字を考慮すると、3つの選択肢があります。

  1. 代用:


    1. x[1]



      y[1]

      に置き換えるコスト(

      D1

      )を求めます。の

両方の文字が同じ場合、このステップのコストはゼロになります。そうでなければ、
それから費用は1つになります
..ステップ1.1の後、両方の

Strings

が同じ文字で始まることがわかりました。

キャラクター。したがって、総コストは今度はステップのコストの合計になります。
1.1と残りの

String x[2:m]

をに変換するコスト

y[2:n]

。挿入:


  1. y

    の最初の文字と一致するように

    x

    に文字を挿入します。

このステップのコストは1になります
.. 2.1以降は、

y

から1文字処理しました。それ故に合計

コストは、今度はステップ2.1のコスト(すなわち1)とコストとの合計になる。
完全な

x[1:m]

を残りの

y(y[2:n])

に変換する方法
。削除:


  1. x

    から最初の文字を削除すると、このステップのコストは

1
.. 3.1以降は、

x

から1文字処理しましたが、完全な

y

まだ処理されていません。総コストは、3.1(すなわち、1)のコストと残りの_x_を完全な_y_に変換するコストとの合計となる。

解決策の次の部分は、これら3つの中からどのオプションを選択するかを考え出すことです。どのオプションが最後に最小コストになるかわからないので、すべてのオプションを試して最良のものを選択する必要があります。


4単純再帰的実装

セクション#3の各オプションの2番目のステップは、ほとんど同じ編集距離の問題ですが、元の

Strings.

のサブストリング上であることがわかります。これは、各反復の後で、同じ問題だがより小さい

Strings.

で終わることを意味します。

この観察は、再帰的アルゴリズムを定式化するための鍵です。再帰関係は次のように定義できます。


D(x[1:m]、y[1:n])


= min \ {

__D(x[2:m]、y[2:n])+ x[1]をy[1]に置き換えるコスト


D(x[1:m]、y[2:n])1、


D(x[2:m]、y[1:n])1


}

再帰的アルゴリズムの基本ケースも定義する必要があります。このケースでは、一方または両方の

Strings

が空になったときです。

  1. 両方の

    Strings

    が空の場合、それらの間の距離はゼロです.


  2. Strings

    の1つが空の場合、その間の編集距離

それらを他の__Stringの長さにします。

  • 例:1つの

    String



    “dog”

    で、他の

    String



    “”

(空)、空にするには空の

String

に3回挿入するか、空にするには3回削除する必要があります。したがって、それらの間の編集距離は3です。

このアルゴリズムの単純で再帰的な実装

public class EditDistanceRecursive {

   static int calculate(String x, String y) {
        if (x.isEmpty()) {
            return y.length();
        }

        if (y.isEmpty()) {
            return x.length();
        }

        int substitution = calculate(x.substring(1), y.substring(1))
         + costOfSubstitution(x.charAt(0), y.charAt(0));
        int insertion = calculate(x, y.substring(1)) + 1;
        int deletion = calculate(x.substring(1), y) + 1;

        return min(substitution, insertion, deletion);
    }

    public static int costOfSubstitution(char a, char b) {
        return a == b ? 0 : 1;
    }

    public static int min(int... numbers) {
        return Arrays.stream(numbers)
          .min().orElse(Integer.MAX__VALUE);
    }
}

  • このアルゴリズムは指数関数的に複雑です** 各ステップで、3つの再帰呼び出しに分岐し、

    O(3 ^ n)

    複雑さを構築します。

次のセクションでは、これを改善する方法について説明します。


5動的計画法アプローチ

再帰呼び出しを分析すると、副問題の引数は元の

Stringsのサフィックスであることがわかります。これは、

m

n

個の固有の再帰呼び出ししかないことを意味します(ここで、

m



n



x



y

のサフィックスの数です)。 。それゆえ、最適解の複雑さは、二次関数であるべきであり、

O(m

n)__である。

副次問題のいくつかを見てみましょう(セクション4で定義されている回帰関係に従って)。


  1. D(x[1:m]、y[1:n])

    の副問題は__D(x[2:m]、y[2:n])、D(x[1:m]、

y[2:n])



D(x[2:m]、y[1:n])



D(x[1:m]、y[2:n])

の副問題は

D(x[2:m]、y[3:n])、D(x[1:m]、

y[3:n])



D(x[2:m]、y[2:n])



D(x[2:m]、y[1:n])

の副問題は

D(x[3:m]、y[2:n])、D(x[2:m]、

y[2:n])



D(x[3:m]、y[1:n])__

3つの場合すべてにおいて、副問題の1つは__D(x[2:m]、y[2:n])です。必要に応じて結果を再利用してください。

この問題には多くの重複する副問題がありますが、副問題の解決策を知っていれば、元の問題に対する答えを簡単に見つけることができます。そのため、動的プログラミングソリューションを作成するために必要な両方のプロパティ、つまりhttps://en.wikipedia.org/wiki/Overlapping

subproblems[オーバーラッピングサブ問題]とhttps://en.wikipedia.org/wiki/Optimal

substructure[最適サブ構造]。


memoization

を導入することで、単純な実装を最適化できます。つまり、副問題の結果を配列に格納し、キャッシュされた結果を再利用できます。

あるいは、テーブルベースのアプローチを使用してこれを繰り返し実装することもできます。

static int calculate(String x, String y) {
    int[][]dp = new int[x.length() + 1][y.length() + 1];

    for (int i = 0; i <= x.length(); i++) {
        for (int j = 0; j <= y.length(); j++) {
            if (i == 0) {
                dp[i][j]= j;
            }
            else if (j == 0) {
                dp[i][j]= i;
            }
            else {
                dp[i][j]= min(dp[i - 1][j - 1]
                 + costOfSubstitution(x.charAt(i - 1), y.charAt(j - 1)),
                  dp[i - 1][j]+ 1,
                  dp[i][j - 1]+ 1);
            }
        }
    }

    return dp[x.length()][y.length()];
}

  • このアルゴリズムは再帰的な実装よりもはるかに優れています。しかし、それはかなりのメモリ消費を伴います。

これは、現在のセルの値を見つけるためにテーブル内の3つの隣接セルの値のみが必要であることを観察することによってさらに最適化できます。


6. 結論

この記事では、レーベンシュタイン距離とは何か、および再帰的アプローチと動的計画法に基づくアプローチを使用してそれを計算する方法について説明しました。

レーベンシュタイン距離は、文字列の類似性の尺度の1つに過ぎず、他のメトリックのいくつかはhttps://en.wikipedia.org/wiki/Cosine

similarity[Cosine Similarity](トークンベースのアプローチを使用し、文字列をベクトルと見なします)です。

https://en.wikipedia.org/wiki/S%C3%B8rensen%E2%80%93Dice


coefficient[Dice Coefficient]など

いつものように、例の完全な実装はhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-1[over on GitHub]で見つけることができます。