Milan Miščević

Napomena: Ovaj post je treći od četiri dijela na temu pretrage sa greškom.

Levenštajnovo rastojanje (eng. Levenshtein distance) je veličina koja predstavlja minimalan broj elementarnih operacija koje je potrebno izvršiti na prvom stringu (s) da bi se dobio drugi string (t), gdje su operacije ubacivanje, izbacivanje i zamjena karaktera. Algoritam za izračunavanje ovog rastojanja razvio je ruski naučnik Vladimir Josifovič Levenštajn 1965. godine i prema njemu ovo rastojanje nosi ime. Ponegdje se u literaturi može sresti pod imenom operacija editovanja najmanje cijene (eng. minimum cost edit distance) ili samo operacija editovanja (eng. edit distance). Pripada grupi algoritama dinamičkog programiranja.

Levenštajnovo rastojanje predstavlja sličnost između dva stringa. Što je manje rastojanje, stringovi su sličniji jer je potrebno manje operacija izvršiti, i obrnuto. Najmanja moguća vrijednost koja se može dobiti je nula, kada su stringovi identični, što je prikazano u prvom primjeru.

Primjeri:

string s, t; int i;

s = “pravo”, t = “pravo”;
i = levenshteinDistance(s, t); // 0

s = “pravo”, t = “prvo”;
i = levenshteinDistance(s, t); // 1

s = “pravo”, t = “prvacic”;
i = levenshteinDistance(s, t); // 4

U drugom primjeru, potrebno je izvršiti samo jednu operaciju, a to je izbacivanje karaktera ‘a’. Treći primjer sadrži više rješenja i biće objašnjen kasnije.

Algoritam

Ovaj algoritam koristi matricu D = [d_ij]_(m+1)x(n+1), gdje je m dužina prvog, a n dužina drugog stringa. Prva kolona se popunjava brojevima od 0 do m, a prvi red 0 do n. Ostali elementi matrice, počevši od elementa d₂₂, uzimaju vrijednosti prema sledećoj formuli:

d_ij = min {d_(i-1)j + 1, d_i(j-1) + 1, d_(i-1)(j-1) + cost}

gdje je cost 0 ako su i-ti karakter stringa s i j-ti karakter stringa t isti ili 1 ako nisu. Vrijednost elementa d(m+1)(n+1) je Levenštajnovo rastojanje.

Kod funkcije levenshteinDistance(string s, string t) u C++-u:

unsigned int levenshteinDistance(string s, string t)
{
   unsigned int m = s.length();
   unsigned int n = t.length();
   unsigned int d[m+1][n+1], i, j, cost;

   // popunjavanje prve kolone
   for (i = 0; i <= m; i++) d[i][0] = i;
   // popunjavanje prvog reda
   for (j = 0; j <= n; j++) d[0][j] = j;

   for (i = 1; i <= m; i++)
   {
      for (j = 1; j <= n; j++)
      {
         cost = (s[i-1] == t[j-1]) ? 0 : 1;
         // trazenje minimuma
         d[i][j] = min(min(d[i-1][j] + 1, d[i][j-1] + 1), d[i-1][j-1] + cost);
      }
   }

   return d[m][n];
}

Za treći primjer matrica D izgleda ovako:

Matrica Levenštajnovog rastojanja za riječi 'pravo' i 'prvacic'

Očitavanje potrebnih operacija se vrši na sledeći način:

1. posmatra se element d_ij, koji je na početku element d_(m+1)(n+1)
2. gleda se odakle se pojavila njegova vrijednost
3. ukoliko je ona rezulatat elementa lijevo (d_i(j-1)), bilježi se ubacivanje j-tog elementa stringa t i prelaz na taj element
4. ukoliko je ona rezulatat elementa dijagonalno (d_(i-1)(j-1)) bilježi se zamjena i-tog karaktera stringa s u j-ti karakter stringa t, ali samo ako su oni različiti; prelaz na taj element se bilježi u oba slučaja
5. ukoliko je ona rezulatat elementa iznad (d_(i-1)j), bilježi se uklanjanje i-tog elementa stringa s
6. prelazimo preko svih obilježenih prelaza (može ih biti više) i ponavljamo od koraka 2
7. očitavanje matrice se završava kada dođemo do elementa d₁₁
8. očitavamo zabilježene operacije u obnutom redoslijedu

Za treći primjer matrica D sa prelazima izgleda ovako:

Matrica Levenštajnovog rastojanja za riječi 'pravo' i 'prvacic' sa prelazima

Sa poslednje matrice se može očitati sledeća tri rješenja:

1. ubacivanje ‘v’ (pravo -> prvavo), ubacivanje ‘c’ (prvavo -> prvacvo), zamjena ‘v’ u ‘i’ (prvacvo -> prvacio) i zamjena ‘o’ u ‘c’ (prvacio -> prvacic)
2. ubacivanje ‘v’ (pravo -> prvavo), zamjena ‘v’ u ‘c’ (prvavo -> prvaco), ubacivanje ‘i’ (prvaco -> prvacio) i zamjena ‘o’ u ‘c’ (prvacio -> prvacic)
3. ubacivanje ‘v’ (pravo -> prvavo), zamjena ‘v’ u ‘c’ (prvavo -> prvaco), zamjena ‘o’ u ‘i’ (prvaco -> prvaci) i ubacivanje ‘c’ (prvaci -> prvacic)

Za prva dva primjera matrice sa prelazima izgledaju ovako:

Matrice Levenštajnovog rastojanja za riječi 'pravo' i 'pravo' te 'pravo' i 'prvo' sa prelazima

Složenost

Vremenska i prostorna složenost ovog algoritma iznose Θ(mn). Ukoliko nije potrebno da se odrede operacije izmjene, već samo rastojanje, prostorna složenost se može redukovati na Θ(m), jer je potrebno da se alocira prostor za samo dva reda matrice.

Upotreba

Određivanje Levenštajnovog rastojanja je od značaja u sledećim aplikacijama:

• molekularna biologija (eng. computational biology) – pronalaženje najsličnije DNK ili RNK sekvence nukleotida
• provjera pravopisa (eng. spelling correction) i propoznavanje glasa (eng. speech recognition) – pronalaženje najsličnije, odnosno iste, riječi u rječniku
• detekcija plagijata (eng. plagiarism detection)
• revizija datoteka (eng. file revision) – ukoliko imamo dve velike, ali slične datoteke, isplativije je napraviti skritu koja jednu datoteku pretvara u drugu, nego je prebacivati (Unix komanda diff)
• problem osvježavanja sadržaja ekrana na daljinu (eng. remote screen update problem) – nalik reviziji datoteka, ali za sadržaj ekrana