4

それを解決するために多くのコードを見てきましたが、2 つの単語間の距離を表すために行列を使用している理由がわかりません。誰でも私に説明してもらえますか？

これが私が見つけたサンプルコードです：

public static int minDistance(String word1, String word2)
{
    int l1 = word1.length(), l2 = word2.length();

    int[][] d = new int[l1 + 1][l2 + 1];

    // the edit distance between an empty string and the prefixes of
    // word2
    for (int i = 0; i < l2 + 1; i++) {
        d[0][i] = i;
    }

    // the edit distance between an empty string and the prefixes of
    // word1
    for (int j = 0; j < l1 + 1; j++) {
        d[j][0] = j;
    }

    for (int i = 1; i < l1 + 1; i++) {
        for (int j = 1; j < l2 + 1; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                d[i][j] = d[i - 1][j - 1];
            } else {
                d[i][j] = min(1 + d[i][j - 1], 1 + d[i - 1][j],
                1 + d[i - 1][j - 1]); // min of insertion,
                // deletion, replacement
            }
        }
    }

    return d[l1][l2];
}
4

3 に答える 3

5

あなたのコードは、動的計画法を使用してレーベンシュタイン距離を計算しています。

配列dには最終的に、さまざまなサブ問題の解決策が含まれます。ここで、 は最初の単語の最初の文字と 2 番目の単語のd[i][j]最初の文字の間の距離です。エントリ と の間には関係があります。アルゴリズムは、必要なサブ問題が既に計算されているような方法でテーブルのエントリを計算します (これは動的計画法の部分です)。ijd[i][j]d[i-1][j]d[i][j-1]d[i-1][j-1]

于 2012-12-20T21:46:08.657 に答える
4

word1マトリックスには、[最後に] のすべての接頭辞と のすべての接頭辞の間の編集距離が含まれていますword2。

d[i][j] = edit distance between word1[0..(i-1)] and word2[0..(j-1)]

に興味がありd[l1][l2]ます。一般に、 を計算するには、3 つの小さい隣人、およびd[i][j]を調べる必要があります。そのため推移的に、少なくとも 1 つの座標がrespよりも小さい(そしてもう 1 つの座標は大きくない) すべてのエントリが必要です。例外は、2 つの文字とが等しい場合です。この場合、対角線の小さい方の隣人のみが必要です。d[i-1][j]d[i-1][j-1]d[i][j-1]d[i][j]ijword1[i-1]word2[j-1]

-1プレフィックス間の対応する編集距離が評価されていないことを示すために最初に行列を で埋め、d[l1][l2]必要な のキャッシュされた値d[i][j]が既に計算されている場合はその値を使用して を再帰的に計算し、再帰的に計算し、そうでない場合はその値を保存すると、マトリックスの領域はそのまま残る場合があります。等しい文字のペアが多数ある場合は領域が大きくなる可能性があり [2 つの単語が等しい場合は対角線のみが評価されます]、等しい文字のペアが少ない場合は小さな領域のみが評価されます。

一般的なケースでは、 を計算するために行列のほとんどが必要になるためd[l1][l2]、単純なアルゴリズムを使用して完全に行列を計算する方が、実際に必要な値だけを再計算して計算するよりも高速です。

より短いプレフィックスの値を保存しない場合、それらは を計算するために推移的に必要とされるため、から到達d[i][j]する各方法で再計算する必要があります。からさまざまな方法で に到達できるため、多くの再計算が発生し、一般的に非常に非効率的なアルゴリズムになります。d[i-a][j-b]d[i][j]d[i-a][j-b]d[i][j]

各行の計算は前の行のみを使用するため、長さの配列を 2 つだけ使用してmin{l1, l2} + 1メモリを節約できますが、単語が非常に長い場合を除き、大きな違いはなく、コードは次のように単純になります。完全な配列。

于 2012-12-20T21:37:12.683 に答える