Javaでレーベンシュタイン距離を計算する方法は？

投稿日: 2019-10-18 2022-10-13
タグ: Algorithms

1. 序章

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

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

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

レーベンシュタイン距離は、2つのストリング間の非類似度の尺度です。数学的には、2つのストリング xとyが与えられます。、距離は、xをyに変換するために必要な文字編集の最小数を測定します。

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

文字の挿入c
文字の削除c
文字cのc‘への置換

例： x =’shot’およびy=’spot’の場合、’h’を’p’に置き換えることで’shot’を’spot’に変換できるため、2つの間の編集距離は1です。

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

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

編集距離のアプリケーションのいくつかは次のとおりです。

スペルチェッカー–テキストのスペルミスを検出し、辞書で最も近い正しいスペルを見つけます
盗用検出（参照– IEEE Paper ）
DNA分析–2つの配列間の類似性を見つける
音声認識（参照– Microsoft Research ）

3. アルゴリズムの定式化

それぞれ長さmとnの2つの文字列xとyを取りましょう。各Stringをx[1：m]およびy [1：n]。と表すことができます。

変換の最後に、両方の Strings が同じ長さになり、各位置に一致する文字が含まれることがわかっています。したがって、各 String、の最初の文字を考慮すると、次の3つのオプションがあります。

置換：
1. x[1]をy[1] に置き換えるコスト（ D1 ）を決定します。両方の文字が同じである場合、このステップのコストはゼロになります。そうでない場合、コストは1つになります
2. 手順1.1を実行すると、両方のStringsが同じ文字で始まることがわかります。したがって、総コストは、ステップ1.1のコストと、残りの String x [2：m]をy [2：n]に変換するコストの合計になります。
挿入：
1. x に文字を挿入して、yの最初の文字と一致させます。このステップのコストは1になります。
2. 2.1以降、yから1文字を処理しました。したがって、総コストは、ステップ2.1（つまり、1）のコストと、完全な x [1：m]を残りのy（y [2： n]）
消す：
1. xから最初の文字を削除します。このステップのコストは1になります。
2. 3.1以降、 x から1文字を処理しましたが、完全なyはまだ処理されていません。総コストは、3.1（つまり、1）のコストと、残りのxを完全なyに変換するコストの合計になります。

ソリューションの次の部分は、これら3つから選択するオプションを見つけることです。どのオプションが最終的に最小コストにつながるかわからないため、すべてのオプションを試して、最適なオプションを選択する必要があります。

4. ナイーブな再帰的実装

セクション3の各オプションの2番目のステップは、ほとんど同じ編集距離の問題ですが、元の文字列のサブ文字列にあることがわかります。これは、各反復後に同じ問題が発生することを意味しますが、小さい文字列を使用します。

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

D（x [1：m]、y [1：n]） =分{

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の一方または両方が空になったときです。

両方のStringsが空の場合、それらの間の距離はゼロです。
Strings の一方が空の場合、一方を他方に変換するには多数の挿入/削除が必要になるため、それらの間の編集距離はもう一方の String、の長さになります。：
- 例：1つの String が“ dog” で、他の 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. 動的計画法アプローチ

再帰呼び出しを分析すると、サブ問題の引数は元の文字列のサフィックスであることがわかります。これは、 m * n の一意の再帰呼び出し（[X200X ]mおよびnは、xおよびyのサフィックスの数です。したがって、最適解の複雑さは2次式 O（m * n）である必要があります。

いくつかのサブ問題を見てみましょう（セクション＃4で定義された漸化式による）：

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]）。単純な実装で行うようにこれを3回計算する代わりに、これを1回計算して、必要に応じて結果を再利用できます。

この問題には重複するサブ問題がたくさんありますが、サブ問題の解決策がわかれば、元の問題の答えを簡単に見つけることができます。したがって、動的計画法ソリューションの定式化に必要な両方のプロパティ、つまり重複サブ問題と最適部分構造があります。

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

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

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つにすぎず、他のメトリックのいくつかはコサイン類似性（トークンベースのアプローチを使用し、文字列をベクトルと見なします）、ダイス係数です。、など。

いつものように、例の完全な実装はGitHubのにあります。

getdocs

13036