Algoritmalar
tr

Düzenleme Mesafesi

Dinamik Programlama O(m · n) O(m · n)

Bir dizeyi diğerine çevirmek için en az tek-karakter ekleme, silme veya değiştirme (Levenshtein).

εεSATURDAY
ε·········
S·········
U·········
N·········
D·········
A·········
Y·········
1/127

"" dizgisini "SATURDAY" dizgisinin ilk 0 karakterine çevirmek 0 ekleme gerektirir.

Değişmezdp[i][j], a'nın ilk i karakterini b'nin ilk j karakterine çevirmenin en ucuz yoludur.

edit-distance.c
int min3(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}
 
int editDistance(const char *a, const char *b) {
    int m = strlen(a), n = strlen(b);
    int dp[m + 1][n + 1];
 
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = j;
            else if (j == 0)
                dp[i][j] = i;
            else if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = 1 + min3(dp[i - 1][j - 1],
                                    dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

Düzenleme Mesafesi nasıl çalışır?

dp[i][j] = A'nın ilk i karakterini B'nin ilk j karakterine çevirmenin en ucuz yolu. Eşit karakterler bedava; değilse değiştir (köşegen), sil (üst), ekle (sol) seçeneklerinin iyisine 1 öde.

Ne zaman kullanılır?

Yazım denetimi, bulanık arama, diff, DNA mutasyon mesafesi.