Rastojanje uređivanja

U teoriji informacija i računarstvu, rastojanje uređivanja između dve niske je broj operacija potrebnih da se jedna od njih transformiše u drugu. Rastojanje uređivanja nalazi primenu u obradi prirodnih jezika gde se automatsko ispravljanje pravopisnih grešaka vrši izborom jednog od kandidata za ispravku pogrešno napisane reči izborom reči iz rečnika koje imaju malo rastojanje uređivanja u odnosu na zadatu reč. U bioinformatici, može da se koristi za određivanje sličnosti DNK sekvenci, koji mogu da se gledaju kao niska karaktera A, C, G i T.

Različite definicije rastojanja uređivanja koriste različite skupove operacija nad niskama. Operacije Levenštajnovog rastojanja su brisanje, ubacivanje, ili zamena karaktera u niski. Pošto je to najčešća metrika, Levenštajnovno rastojanje je uobičajeno ono na šta se misli pod "Rastojanjem uređivanja".

Formalna definicija i osobine

Za date dve niske $a$ i $b$ na azbuci $\Sigma$ (npr. skup ASCII karaktera), rastojanje $d(a,b)$ uređivanja niski je najkraći niz operacija koje transformišu $a$ u $b$. Jedan od najjednostavnijih skupova operacija uređivanja je definisan od strane Levenštajna 1966. godine:

Ubacivanje jednog simbola. Ako je $a=uv$, onda ubacivanjem simbola $x$ dobijamo niz $uxv$. Ovo se takođe može predstaviti kao $\varepsilon \rightarrow x$ , koristeći $\varepsilon$ kao oznaku za praznu nisku.

Brisanje jednog simbola menja $uxv$ u $uv$ ($x\rightarrow \varepsilon$).

Zamena jednog simbola $x$ za simbol $y\neq x$ menja $uxv$ u $uyv$ ($x\rightarrow y$).

U Levenštajnovoj originalnoj definiciji, svaka od ovih operacija ima jediničnu cenu(osim zamene karaktera sa samim sobom što nema cenu), tako da Levenštajnova je udaljenost jednaka minimalnom broju operacija potrebnih da se $a$ transformiše u $b$.

Dodatne primitivne operacije su predlagane. Česta greška prilikom kucanja teksta je transpozicija dva susedna karaktera, formalno karakterisana kao operacija koja menja $uxyz$ u $uyxz$ gde $x,y\in \Sigma$. . Kao zadatak korekcije OCR izlaza, operacije povezivanje i razdvajanje se koriste za zamenu jednog karaktera u dva i obrnuto.

Druge varijante rastojanja uređivanja dobijaju se ograničavanjem seta operacija. Udaljenost najduže zajedničke podniske je udaljenost uređivanja sa ubacivanjem i brisanjem kao jedine dve operacije, obe sa jediničnom cenom. Slično, dopuštanjem samo zamene(opet po jediničnoj ceni), dobija se Hamingovo Rastojanje, koje mora biti ograničeno na niske sa istim brojem karaktera. Džaro-Vinkler rastojanje se dobija kao rastojanje uređivanja u kome je samo transpozicija dozvoljena.

Primer

Levenštajnovo rastojanje između reči "kitten" i "sitting" je 3.

1. kitten $\rightarrow$ sitten("k" zamenjeno sa "s")
2. kitten $\rightarrow$ sittin("e" zamenjeno sa "i")
3. kitten $\rightarrow$ sitteng(dodato "g")

Najduža zajednička podniska (dozvoljena samo ubacivanja i brisanja) daje rastojanje od 5.

1. kitten $\rightarrow$ itten (obrisano "k" sa nulte pozicije)
2. itten $\rightarrow$ sitten (dodato "s" na nultu poziciju)
3. sitten $\rightarrow$ sittn (obrisano "e" sa četvrte pozicije)
4. sittn $\rightarrow$ sittin (dodato na "i" četvrtu poziciju)
5. sittin $\rightarrow$ sitting (dodato na "g" šestu poziciju)

Osobine

Rastojanje uređivanja sa ne-negativnim cenama zadovoljava aksiome metrike, praveći metrički prostor niski kada su naredni uslovi zadovoljeni:

• Svaka operacija uređivanja ima pozitivnu cenu;
• za svaku operaciju, postoji inverzna operacija sa istom cenom.

Sa ovim osobinama metričke aksiome su zadovoljene:

$d(a,a)=0$, pošto svaki string može trivijalno da se transformiše u samog sebe koristeći tačno nula operacija.

$d(a,b)>0$, kada $a\neq b$, pošto je neophodno izvršiti makar jednu operaciju čija cena nije 0.

$d(a,b)=d(b,a)$ po jednakosti cena svake od operacija i njihovog inverza.

Nejednakost trougla: $d(a,c)\leq d(a,b)+d(b,c)$.

Levenštajnovo rastojanje i Najduža zajednička podniska sa jediničnim cenama operacija zadovoljavaju gorenavedene uslove.

Druge korisne osobine rastojanja udaljenosti jediničnih cena su:

• Najduža zajednička podniska je gornje ograničena sumom dužina para niski.
• Najduža zajednička podniska je gornje ograničenje Levenštajnovog rastojanja.
• Za niske iste dužine, Hamingovo rastojanje je gornja granica Levenštajnovog rastojanja.

Bez obzira na cenu, naredna osobina važi za sva rastojanja uređivanja:

• Kada $a$ i $b$ dele zajednički prefiks, ovaj prefiks ne utiče na rastojanje. Formalno, kada $a=uv$ i $b=uw$ , onda $d(a,b)=d(v,w)$ . Ovo omogućava poboljšanje vremena izvršavanja računa vezanih za rastojanje uređivanja jer se česti prefiksi i sufiksi mogu preskočiti u linearnom vremenu.

Računanje

Prvi algoritam za računanje minimalnog rastojanja uređivanja dve niske je objavio Damarau 1964. godine.

Opšti algoritam

Korišćenjem Levenštajnovih originalnih operacija, rastojanje uređivanja između $a=a1\ldots an$ i $b=b1\ldots bm$ je dat kao $d_{mn}$, definisano rekurzivno:

${\begin{aligned}d_{i0}&=\sum _{k=1}^{i}w_{\mathrm {del} }(b_{k}),&&\quad {\text{for}}\;1\leq i\leq m\\d_{0j}&=\sum _{k=1}^{j}w_{\mathrm {ins} }(a_{k}),&&\quad {\text{for}}\;1\leq j\leq n\\d_{ij}&={\begin{cases}d_{i-1,j-1}&{\text{for}}\;a_{j}=b_{i}\\\min {\begin{cases}d_{i-1,j}+w_{\mathrm {del} }(b_{i})\\d_{i,j-1}+w_{\mathrm {ins} }(a_{j})\\d_{i-1,j-1}+w_{\mathrm {sub} }(a_{j},b_{i})\end{cases}}&{\text{for}}\;a_{j}\neq b_{i}\end{cases}}&&\quad {\text{for}}\;1\leq i\leq m,1\leq j\leq n.\end{aligned}}$

Ovaj algoritam može da se uopšti kako bi podržavao transpozicije dodavanjem dodatnog člana u rekurzivnoj klauzi za minimizaciju.

Jednostavan, rekurzivni način računanja ovog problema je eksponencijalne vremenske složenosti. Tako da se uobičajeno računa pomoću algoritma dinamičkog programiranja zvanog Vagner-Fišer. Nakon završetka Vagner-Fišerovog algoritma, minimalni niz operacija uređivanja može da se pročita unazad prateći operacije korišćene tokom algoritma, počevši od $d_{mn}$.

Ovaj algoritam je pripada klasi vremenske složenosti $\Theta (mn)$. Kada se konstruiše potpuna tabela, prostorna složenost je takođe $\Theta (mn)$; ovo može da se poboljša na $\Theta (min(m,n))$ usled činjenice da u bilo kom trenutku, algoritmu samo trebaju 2 reda(ili dve kolone) u memoriji. Implementiranjem ove optimizacije gubi se mogućnost pamćenja samog niza operacija uređivanja. Rešenje linearne prostorne složenosti je nudi Hiršbergov Algoritam.

Poboljšani algoritmi

Ukonen je opisao nekoliko varijanti poboljšanja gorenavedenog Vagner-Fišer algoritma, jedna od kojih uzima dve niske i maksimalno rastojanje uređivanja $s$ , i vraća $min(s,d)$ . To uspeva računajući i skladišteći samo deo tabele u okolini dijagonale. Ovaj algoritam zahteva $\Theta (s*min(m,n))$ vreme, gde su $m$ i $n$dužine niski. Prostorna složenost je $\Theta (s^{2})$ ili $\Theta (s)$ , u zavisnosti od toga da li niz operacija treba da se pročita ili ne.

Primena

Rastojanje uređivanja nalazi primenu u računskoj biologiji i obradi prirodnih jezika, npr. ispravljanju pravopisnih ili OCR grešaka i traženjem približnog poklapanja niski, gde je cilj naći poklapanja za kratke niske u mnogo dužim tekstovima, u situacijama kada se mali broj razlika očekuje.

Razni algoritmi postoje za rešavanje sličnih tipova problema.

• Hiršbergov algoritam računa optimalno poravnanje dve niske, gde je optimalnost definisana minimizovanjem rastojanja uređivanja.
• Traženje približne niske može da se formuliše u terminima rastojanja uređivanja. Ukonenov algoritam iz 1985. uzima nisku $p$, nazvanu uzorak, i konstantu $k$. Onda pravi deterministički konačni automat koji pronalazi, u proizvoljnoj niski $s$, podnisku čije je rastojanje uređivanja do $p$ najviše $k$. Sličan algoritam za traženje približne niske je bitap algoritam, takođe definisan u terminima rastojanja uređivanja.
• Levenštajnov automat je konačni automat koji prepoznaje set niski unutar ograničenog rastojanja uređivanja fiksne referentne niske.

Spoljašnje veze

• Text::WagnerFischer, Perl implementacija Vagner-Fišer rastojanja uređivanja