Edit Distance

Edit distance (Levenshtein distance) adalah jumlah minimum operasi — insert, delete, replace — yang diperlukan untuk mengubah string s menjadi string t. Masalah ini menjadi dasar spell checker, fuzzy string matching, DNA alignment, dan fitur auto-correct. Meskipun terlihat mirip dengan LCS, edit distance memperbolehkan tiga operasi sehingga recurrence-nya lebih kaya. Pada Chapter ini kita akan membedah state, tiga transisi dasar, optimasi ruang, dan variasi dengan biaya operasi berbeda.

Aturan: Tiga Operasi #

Untuk mengubah s menjadi t, kita boleh melakukan tiga operasi:

Insert: tambahkan satu karakter ke s.
Delete: hapus satu karakter dari s.
Replace: ganti satu karakter di s dengan karakter di t.

Setiap operasi berbiaya 1. Edit distance adalah jumlah minimum operasi.

Mekanisme: DP 2D dengan Tiga Transisi #

State: dp[i][j] — edit distance dari s[0..i-1] menjadi t[0..j-1].

Base case: dp[0][j] = j (insert j karakter), dp[i][0] = i (delete i karakter).

Recurrence:

text
Bila s[i-1] == t[j-1]:
    dp[i][j] = dp[i-1][j-1]              // tidak perlu operasi
Bila tidak:
    dp[i][j] = min(
        dp[i-1][j]   + 1,                // delete s[i-1]
        dp[i][j-1]   + 1,                // insert t[j-1]
        dp[i-1][j-1] + 1                 // replace s[i-1] dengan t[j-1]
    )

flowchart TD A["dp i j"] --> B{s[i-1] == t[j-1]?} B -- Ya --> C["dp i-1 j-1 (no cost)"] B -- Tidak --> D["min dp i-1 j +1, dp i j-1 +1, dp i-1 j-1 +1"] C --> E["dp i j = hasil"] D --> E

Kode: Edit Distance 2D #

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

int edit_distance(const std::string& s, const std::string& t) {
    int n = static_cast<int>(s.size());
    int m = static_cast<int>(t.size());
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
    for (int i = 0; i <= n; ++i) dp[i][0] = i;
    for (int j = 0; j <= m; ++j) dp[0][j] = j;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = std::min({
                    dp[i - 1][j] + 1,      // delete
                    dp[i][j - 1] + 1,      // insert
                    dp[i - 1][j - 1] + 1   // replace
                });
            }
        }
    }
    return dp[n][m];
}

int main() {
    std::string s = "kitten";
    std::string t = "sitting";
    std::cout << "Edit distance \"" << s << "\" -> \"" << t << "\" = "
              << edit_distance(s, t) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Edit distance "kitten" -> "sitting" = 3

Baris for (int i = 0; i <= n; ++i) dp[i][0] = i;: base case — mengubah s[0..i-1] menjadi string kosong butuh i delete.
Baris for (int j = 0; j <= m; ++j) dp[0][j] = j;: base case — mengubah string kosong menjadi t[0..j-1] butuh j insert.
Baris if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1];: karakter cocok — tidak ada operasi, ambil dari diagonal.
Baris dp[i - 1][j] + 1: opsi delete s[i-1]. Sisa s[0..i-2] → t[0..j-1], plus 1 operasi.
Baris dp[i][j - 1] + 1: opsi insert t[j-1] ke s. Sisa s[0..i-1] → t[0..j-2], plus 1 operasi.
Baris dp[i - 1][j - 1] + 1: opsi replace s[i-1] dengan t[j-1]. Sisa s[0..i-2] → t[0..j-2], plus 1 operasi.
Hasil 3: kitten → sitten (replace k→s), → sittin (replace e→i), → sitting (insert g). 3 operasi.

Visualisasi Tabel #

Untuk s = "ABC", t = "ADC":

text
      ""  A  D  C
  ""   0  1  2  3
   A   1  0  1  2
   B   2  1  1  2
   C   3  2  2  1

Sel [3][3] = 1: ganti B dengan D. Operasi minimum 1.

Optimasi Ruang: Rolling Array #

Karena dp[i][j] hanya bergantung pada baris i-1 dan baris i (untuk sel kiri), gunakan dua array 1D:

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

int edit_distance_1d(const std::string& s, const std::string& t) {
    int n = static_cast<int>(s.size());
    int m = static_cast<int>(t.size());
    std::vector<int> prev(m + 1), cur(m + 1);
    for (int j = 0; j <= m; ++j) prev[j] = j;
    for (int i = 1; i <= n; ++i) {
        cur[0] = i;
        for (int j = 1; j <= m; ++j) {
            if (s[i - 1] == t[j - 1]) {
                cur[j] = prev[j - 1];
            } else {
                cur[j] = std::min({prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + 1});
            }
        }
        std::swap(prev, cur);
    }
    return prev[m];
}

int main() {
    std::string s = "kitten";
    std::string t = "sitting";
    std::cout << "Edit distance (1D) = " << edit_distance_1d(s, t) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Edit distance (1D) = 3

Baris std::vector<int> prev(m + 1), cur(m + 1);: dua array 1D. prev = baris i-1, cur = baris i.
Baris cur[0] = i;: base case untuk kolom 0 — delete i karakter dari s.
Baris std::swap(prev, cur);: tukar peran setelah selesai satu baris.
Memori: O(min(n, m)) alih-alih O(n·m). Penghematan besar untuk string panjang.

Variasi: Biaya Operasi Berbeda #

Dalam beberapa skenario, biaya operasi berbeda. Misalnya: insert dan delete biaya 1, tetapi replace biaya 2 (setara delete + insert):

cpp
int cost_insert = 1, cost_delete = 1, cost_replace = 2;

if (s[i - 1] == t[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1];
} else {
    dp[i][j] = std::min({
        dp[i - 1][j] + cost_delete,
        dp[i][j - 1] + cost_insert,
        dp[i - 1][j - 1] + cost_replace
    });
}

Variasi lain: hanya insert + delete (tidak ada replace). Edit distance ini = n + m - 2·LCS(s, t) — disebut LCS distance.

Damerau-Levenshtein: Tambahan Transpose #

Operasi keempat: transpose dua karakter berdekatan. Cocok untuk typo umum seperti “teh” → “the”. Recurrence menjadi:

text

Bila i >= 2 dan j >= 2 dan s[i-1] == t[j-2] dan s[i-2] == t[j-1]:
    dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1)

Aplikasi: spell checker yang lebih akurat untuk kesalahan pengetikan.

Tabel Kompleksitas #

Versi	Waktu	Ruang	Catatan
Tabel 2D penuh	`O(n·m)`	`O(n·m)`	Rekonstruksi mudah
Rolling array	`O(n·m)`	`O(min(n,m))`	Tidak ada rekonstruksi
Damerau-Levenshtein	`O(n·m)`	`O(n·m)`	Tambahan operasi transpose
Dengan biaya variabel	`O(n·m)`	sama	Modifikasi konstanta biaya

Aplikasi Praktis #

Spell checker: kata salah dieja → kata benar dengan edit distance kecil.
DNA sequence alignment: algoritma Needleman-Wunsch adalah generalisasi edit distance dengan skor match/mismatch.
Fuzzy search: cari record yang “mirip” dengan query.
Diff tools: algoritma Myers untuk diff menggunakan edit distance dengan optimasi khusus.

Ringkasan #

Edit distance: jumlah minimum insert/delete/replace untuk mengubah s ke t.
State dp[i][j], recurrence: match → dp[i-1][j-1], mismatch → min(delete, insert, replace) + 1.
Base case: dp[0][j] = j, dp[i][0] = i.
Optimasi ruang dengan rolling array: O(min(n, m)) memori.
Variasi: biaya operasi berbeda, tambahan transpose (Damerau-Levenshtein), LCS distance.