Levenshteinova udaljenost

Ova metrika se široko koristi u informatici, posebno u sistemima za provjeru pravopisa, pretrazi teksta, obradi prirodnog jezika i analizi podataka. Njena osnovna svrha je mjerenje sličnosti između dva niza znakova.

Na primjer, kada pretraživač ili pravopisni korektor predloži riječ sličnu onoj koju ste unijeli, vrlo često koristi upravo Levenshteinovu udaljenost.

Izračunavanje se zasniva na konstrukciji matrice u kojoj svaka ćelija predstavlja minimalni broj operacija potrebnih da se prefiks prvog niza transformiše u prefiks drugog niza. Matrica se popunjava postepeno, pri čemu se u svakom koraku bira najjeftinija moguća transformacija.

Za razliku od Hammingove udaljenosti, Levenshteinova udaljenost može se koristiti i za nizove različitih dužina.

Primjer izračunavanja

Posmatrajmo dva niza :

$$ s = "kitten" $$

$$ t = "sitting" $$

Cilj je odrediti koliko je minimalno operacija potrebno da se niz « kitten » transformiše u niz « sitting ».

1. Zamjena
   Zamijeniti \( k \) sa \( s \) : $$ "kitten" \rightarrow "sitten" $$
2. Zamjena
   Zamijeniti \( e \) sa \( i \) : $$ "sitten" \rightarrow "sittin" $$
3. Umetanje
   Dodati \( g \) na kraj niza : $$ "sittin" \rightarrow "sitting" $$

Ukupno su potrebne tri operacije. Zato je Levenshteinova udaljenost između nizova « kitten » i « sitting » jednaka 3.

Da bi se ovaj postupak formalno opisao, konstruiše se matrica dimenzija \( (m+1) \times (n+1) \), gdje je \( m \) dužina prvog niza, a \( n \) dužina drugog niza.

U ovom primjeru:

$$ m = 6 \qquad n = 7 $$

Dodatni red i dodatna kolona služe za prikaz transformacija koje uključuju prazan niz.

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

Ćelija \( (0, j) \) predstavlja trošak transformacije praznog niza u prefiks drugog niza dužine \( j \). Taj trošak raste linearno jer je potrebno umetnuti sve znakove.

Slično tome, ćelija \( (i, 0) \) predstavlja trošak transformacije prefiksa prvog niza u prazan niz, što zahtijeva brisanje svih znakova.

Za svaku ćeliju \( (i, j) \), algoritam razmatra tri moguće operacije :

1. brisanje jednog znaka (vrijednost gornje ćelije \( +1 \)) ;
2. umetanje jednog znaka (vrijednost lijeve ćelije \( +1 \)) ;
3. zamjena jednog znaka (vrijednost dijagonalne ćelije).

Ako su znakovi identični, dodatni trošak zamjene je jednak nuli.

Matrica se zatim popunjava korak po korak, sve dok se ne dobije konačna vrijednost Levenshteinove udaljenosti.

	""	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

Na primjer, transformacija praznog niza u « s », « si », « sit » itd. zahtijeva po jednu dodatnu operaciju za svaki novi znak koji se umetne.

Slično tome, transformacija nizova « k », « ki », « kit » itd. u prazan niz ima trošak koji raste za jednu jedinicu pri svakom obrisanom znaku.

• Ćelija (1,1) predstavlja trošak zamjene znaka « k » znakom « s ». Vrijednost je jednaka 1, jer je potrebna samo jedna zamjena.
  
• Ćelija (2,2) odgovara trošku transformacije niza « ki » u « si ». Trošak ostaje jednak 1 zato što je drugi znak (i) identičan u oba niza.
• Ćelija (3,3) predstavlja trošak transformacije niza « kit » u « sit ». Vrijednost je i dalje 1, jer treće slovo (t) ostaje nepromijenjeno.
• Ćelija (4,4) daje trošak transformacije niza « kitt » u « sitt », koji je ponovo jednak 1, pošto se četvrti znak (t) ne mijenja.
• Ćelija (5,5) pokazuje trošak 2 za transformaciju niza « kitte » u « sitti », zbog zamjene \( e \rightarrow i \).
  
• Ćelija (6,6) prikazuje trošak transformacije niza « kitten » u « sittin », koji ostaje jednak 2 jer je posljednji znak (n) isti.
• Ćelija (6,7) daje ukupan trošak 3 za transformaciju niza « kitten » u « sitting », uz umetanje završnog znaka g.
  

Na taj način dolazi se do završne ćelije matrice, koja sadrži ukupni akumulirani trošak transformacije.

Donja desna ćelija \( (6,7) \) daje minimalni trošak potreban za transformaciju niza « kitten » u niz « sitting » : ukupno 3.

Dobijeni rezultat tačno odgovara Levenshteinovoj udaljenosti između ova dva niza : dvije zamjene i jedno umetanje.

Topologija inducirana Levenshteinovom udaljenošću

Levenshteinova udaljenost inducira strukturu metričkog prostora na skupu nizova znakova, slično Hammingovoj udaljenosti, jer zadovoljava osnovna aksiomska svojstva metrike.

1. Nenegativnost : Levenshteinova udaljenost između dva niza \( x \) i \( y \) uvijek je veća ili jednaka nuli, a \( D_L(x, y) = 0 \) ako i samo ako je \( x = y \). Drugim riječima, nijedna operacija nije potrebna da se niz transformiše u samog sebe, pa je udaljenost jednaka nuli isključivo kada su oba niza identična.
2. Simetrija : Levenshteinova udaljenost je simetrična, pa vrijedi \( D_L(x, y) = D_L(y, x) \). Broj operacija potrebnih za transformaciju niza \( x \) u niz \( y \) jednak je broju operacija potrebnih za transformaciju niza \( y \) u niz \( x \), jer su dozvoljene operacije reverzibilne.
3. Trokutna nejednakost : Uvijek vrijedi \( D_L(x, z) \leq D_L(x, y) + D_L(y, z) \). To znači da direktna udaljenost između nizova \( x \) i \( z \) nikada ne može biti veća od zbira udaljenosti dobijenih preko posrednog niza \( y \).

Ova svojstva garantuju da Levenshteinova udaljenost definiše metrički prostor na skupu nizova znakova.

Kao validna metrika, ona omogućava i definisanje pridružene inducirane metričke topologije.

Za poluprečnik \( r \) i niz \( x \), otvorena kugla sa centrom u \( x \) definiše se kao skup svih nizova \( y \) čija je udaljenost od \( x \) strogo manja od \( r \) :

$$ B(x, r) = \{ y \mid D_L(x, y) < r \} $$

Skup svih takvih otvorenih kugli čini bazu inducirane topologije.

Ovaj formalni okvir posebno je koristan u oblastima u kojima je pojam « bliskosti » između nizova znakova veoma važan. Na primjer, u sistemima za automatsku provjeru pravopisa riječ koja ima malu Levenshteinovu udaljenost od neke riječi iz rječnika može biti predložena kao moguća ispravka.

U tom kontekstu, nizovi znakova posmatraju se kao tačke metričkog prostora, dok inducirana topologija omogućava formalnu analizu njihove međusobne bliskosti.

Primjer

Posmatrajmo skup \( X \) sastavljen od nizova od tri znaka :

$$ X = \{"cat", "bat", "cut"\} $$

Bazu topologije definišemo pomoću otvorenih kugli poluprečnika \( r = 2 \), centriranih u svakom elementu skupa \( X \) :

$$ B(x, r) = \{ y \mid D_L(x, y) < r \} $$

Svaka otvorena kugla sadrži sve nizove koji se od centralnog niza razlikuju za najviše jednu operaciju prema Levenshteinovoj udaljenosti.

Napomena : Za poluprečnik \( r = 2 \) uključuju se samo nizovi čija je udaljenost strogo manja od 2. Dakle:

$$ B(x, 2) = \{ y \mid D_L(x, y) < 2 \} $$

Za definisanje zatvorene kugle, koja uključuje i granične tačke, koristi se ne-stroga nejednakost:

$$ \overline{B}(x, 2) = \{ y \mid D_L(x, y) \le 2 \} $$

Posmatrajmo sada otvorene kugle poluprečnika \( 2 \), centrirane u svakom elementu skupa \( X \) :

1. Otvorena kugla sa centrom u "cat"
   $$ B("cat", 2) = \{"cat", "bat"\} $$
   Ovi nizovi mogu se dobiti jedan iz drugog jednom zamjenom znaka.
2. Otvorena kugla sa centrom u "bat"
   $$ B("bat", 2) = \{"bat", "cat"\} $$
   Sadrži sve nizove koji se mogu transformisati u « bat » jednom operacijom.
3. Otvorena kugla sa centrom u "cut"
   $$ B("cut", 2) = \{"cut"\} $$
   Nijedan drugi niz iz skupa \( X \) nije na udaljenosti 1 od « cut », pa ova kugla sadrži samo taj niz.

Skupovi \( B("cat", 2) \), \( B("bat", 2) \) i \( B("cut", 2) \) formiraju bazu topologije inducirane Levenshteinovom udaljenošću za poluprečnik \( r = 2 \).

Iz ove baze mogu se konstruisati svi ostali otvoreni skupovi kao proizvoljne unije otvorenih kugli.

Na primjer, unija skupova \( B("bat", 2) \) i \( B("cut", 2) \) jeste:

$$ B("bat", 2) \cup B("cut", 2) $$

Pošto je:

$$ B("bat", 2) = \{"cat", "bat"\} $$

i

$$ B("cut", 2) = \{"cut"\} $$

dobijamo:

$$ B("bat", 2) \cup B("cut", 2) = \{"cat", "bat"\} \cup \{"cut"\} $$

$$ B("bat", 2) \cup B("cut", 2) = \{"cat", "bat", "cut"\} $$

Dobijeni skup je zato takođe otvoren skup inducirane topologije.

Na ovaj način dobija se metrička topologija na skupu \( X \), inducirana Levenshteinovom udaljenošću, u kojoj se svaki otvoreni skup može predstaviti kao unija elemenata baze.

I tako dalje.