Edit Distance (rastojanje između stringova)

Edit Distance (uređivačko rastojanje, poznato i kao Levenštajnovo rastojanje) je klasičan problem dinamičkog programiranja u kome se meri najmanji broj operacija potrebnih da se jedan string pretvori u drugi.

Dozvoljene operacije su:

• ubacivanje znaka,
• brisanje znaka,
• zamena jednog znaka drugim.

Svaka operacija ima cenu 1.

---

Definicija problema

Data su dva stringa:

• s – početni string,
• t – ciljni string.

Potrebno je odrediti najmanji broj operacija kojima se string s pretvara u string t.

Primer:

• s = "kitten"
• t = "sitting"

Rezultat je 3:

kitten → sitten   (zamena k sa s)
sitten → sittin   (zamena e sa i)
sittin → sitting  (ubacivanje g na kraj)

---

Zašto dinamičko programiranje?

Ako posmatramo prefikse stringova (njihove početne delove), problem se prirodno razlaže na manje podprobleme: da bismo pretvorili "kitten" u "sitting", dovoljno je znati rešenja za kraće prefikse, na primer "kitte" → "sittin".

Edit Distance ima obe osobine potrebne za dinamičko programiranje:

• optimalnu podstrukturu – optimalno rešenje sastoji se od optimalnih rešenja za kraće prefikse,
• preklapajuće podprobleme – isti par prefiksa javlja se u mnogo različitih grana rekurzije.

---

DP stanje

Definišemo:

dp[i][j] = najmanji broj operacija
           da se prvih i znakova stringa s
           pretvori u prvih j znakova stringa t

Konačno rešenje je dp[n][m], gde su n i m dužine stringova.

---

Početni uslovi

• dp[0][j] = j – od praznog stringa do j znakova dolazimo sa j ubacivanja,
• dp[i][0] = i – od i znakova do praznog stringa dolazimo sa i brisanja.

---

Prelaz (DP relacija)

Posmatramo poslednje znakove prefiksa, s[i-1] i t[j-1]. Ako su jednaki, ne treba nam nova operacija:

dp[i][j] = dp[i-1][j-1]

Ako su različiti, biramo najjeftiniju od tri operacije:

dp[i][j] = 1 + min(
    dp[i-1][j],     // brisanje znaka s[i-1]
    dp[i][j-1],     // ubacivanje znaka t[j-1]
    dp[i-1][j-1]    // zamena s[i-1] sa t[j-1]
)

---

DP tabela za primer kitten → sitting

Vrste odgovaraju prefiksima stringa s = "kitten", a kolone prefiksima stringa t = "sitting". Oznaka ε predstavlja prazan string. Tabela se popunjava red po red, sleva nadesno, jer svako polje zavisi samo od polja iznad, levo i gore-levo.

	ε	s	i	t	t	i	n	g
ε	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3

Rešenje je u donjem desnom uglu: dp[6][7] = 3. Na primer, polje dp[1][1] (k → s) iznosi 1, jer su znakovi različiti, a najmanja od tri susedne vrednosti je 0.

---

Implementacija (C++)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>   // za funkciju min
using namespace std;

// Najmanji od tri broja
int min3(int a, int b, int c) {
    return min(a, min(b, c));
}

int main() {
    string s, t;
    cin >> s >> t;

    int n = s.size();
    int m = t.size();

    // dp[i][j] - najmanji broj operacija da se prvih i znakova
    // stringa s pretvori u prvih j znakova stringa t.
    // vector umesto niza dp[n + 1][m + 1], jer niz promenljive
    // dužine nije standardni C++ i za duge stringove ne staje na stek.
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0)
                dp[i][j] = j;                    // ubacujemo j znakova
            else if (j == 0)
                dp[i][j] = i;                    // brišemo i znakova
            else if (s[i - 1] == t[j - 1])
                dp[i][j] = dp[i - 1][j - 1];     // poslednji znakovi su isti
            else
                dp[i][j] = 1 + min3(
                    dp[i - 1][j],     // brisanje znaka s[i-1]
                    dp[i][j - 1],     // ubacivanje znaka t[j-1]
                    dp[i - 1][j - 1]  // zamena s[i-1] sa t[j-1]
                );
        }
    }

    cout << "Edit distance: " << dp[n][m] << endl;
    return 0;
}

---

Optimizacija memorije: dva reda umesto cele tabele

Za računanje reda i potreban je samo red i − 1. Zato je dovoljno čuvati dva reda, pa memorija pada sa O(n · m) na O(m).

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;

    int n = s.size();
    int m = t.size();

    // Za red i potreban je samo red i - 1, pa čuvamo dva reda.
    vector<int> prethodni(m + 1), tekuci(m + 1);

    // Red i = 0: od praznog stringa do prvih j znakova stringa t
    for (int j = 0; j <= m; j++)
        prethodni[j] = j;

    for (int i = 1; i <= n; i++) {
        tekuci[0] = i;   // j = 0: brišemo svih i znakova

        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1])
                tekuci[j] = prethodni[j - 1];
            else
                tekuci[j] = 1 + min({prethodni[j],        // brisanje
                                     tekuci[j - 1],       // ubacivanje
                                     prethodni[j - 1]});  // zamena
        }

        swap(prethodni, tekuci);   // tekući red postaje prethodni
    }

    // Posle poslednje zamene rezultat je u nizu prethodni
    cout << "Edit distance: " << prethodni[m] << endl;
    return 0;
}

Ovom varijantom dobijamo samo broj operacija. Ako treba ispisati i koje operacije su izvršene, potrebna je cela tabela, jer se put rekonstruiše unazad od dp[n][m]. Upravo to radi interaktivni primer ispod.

---

Vremenska i prostorna složenost

• Vremenska složenost: O(n · m)
• Prostorna složenost: O(n · m) sa celom tabelom, odnosno O(m) sa dva reda

gde su n i m dužine stringova.

Interaktivni primer: DP tabela i niz operacija

Unesi dva kratka stringa (najviše 12 znakova) i pritisni dugme. Prikazaće se popunjena DP tabela, označen put kojim se dolazi do rešenja i redosled operacija.

Praktična primena

Edit Distance se koristi u:

• proveri pravopisa i predlaganju ispravki („Da li ste mislili...?”),
• pretrazi koja toleriše greške u kucanju,
• bioinformatici, za poređenje DNK sekvenci,
• obradi prirodnog jezika i poređenju sličnosti tekstova.

---

Veza sa drugim DP problemima

• Longest Common Subsequence (LCS) – ista struktura tabele nad dva stringa; ako su dozvoljena samo brisanja i ubacivanja, rastojanje je n + m − 2·LCS.
• Grid DP – svako polje zavisi od suseda gore, levo i dijagonalno.
• Problemi poravnanja stringova (sequence alignment).

Razumevanje ovog problema predstavlja veliki korak ka savladavanju naprednog dinamičkog programiranja.