Vagner-Fišerov algoritam

U informatici, Vagner-Fišerov algoritam je algoritam dinamičkog programiranja koji meri Levenštajnovo rastojanje između dve niske karaktera.

Izračunavanje rastojanja

Vagner-Fišerov algoritam izračunava Levenštajnovo rastojanje na osnovu posmatranja, na primer ako napravimo matricu koja će da sadrži Levenštajnova rastojanja između svih prefiksa prve niske i svih prefiksa druge niske, onda možemo da izračunamo vrednosti u matrici tako što ćemo da „poplavimo“ matricu (takozvanim algoritmom „punjenje poplavom“ ili na eng. flood filling).Poslednja izračunata vrednost će predstavljati rastojanje između dve niske. Što je Levenštajnovo rastojanje dve niske veće, to se one više razlikuju među sobom.

Jednostavna implementacija, u obliku pseudokoda za funkciju LevenstajnovoRastojanje uzima dve niske, m je dužina niske s, i n je dužina niske t, i vraća njihovo Levenštajnovo rastojanje:

       int LevenstajnovoRastojanje(char s[1..m], char t[1..n])
 {
   // za svako i i j, d[i,j] ce predstavljati Levenstajnovo rastojanje 
   // izmedju prvih i karaktera niske s i prvih j karaktera niske t;
   // napomena, matrica d je velicine (m+1)*(n+1) 
   int d[0..m, 0..n]
  
   for i from 0 to m
     d[i, 0] := i // rastojanje od bilo koje prve niske do druge prazne niske
   for j from 0 to n
     d[0, j] := j // / rastojanje od bilo koje druge niske do prve prazne niske 
  
   for j od 1 do n
   {
     for i od 1 do m
     {
       if s[i] = t[j] then  
         d[i, j] := d[i-1, j-1]       // nije potrebna nikakva operacija
       else
         d[i, j] := minimum
                    (
                      d[i-1, j] + 1,  // operacija brisanja
                      d[i, j-1] + 1,  // operacija umetanja
                      d[i-1, j-1] + 1 // operacija zamene
                    )
     }
   }
  
   return d[m,n]
 }

Primer formiranja matrice:

		N	A	U	K	A
	0	1	2	3	4	5
B	1
U	2
K	3
A	4

		N	A	U	K	A
	0	1	2	3	4	5
B	1	1	2	3	4	5
U	2	2
K	3	3
A	4	4

		N	A	U	K	A
	0	1	2	3	4	5
B	1	1	2	3	4	5
U	2	2	2	2	3	4
K	3	3	3
A	4	4	3

		N	A	U	K	A
	0	1	2	3	4	5
B	1	1	2	3	4	5
U	2	2	2	2	3	4
K	3	3	3	3	2	3
A	4	4	3	4

		N	A	U	K	A
	'S' equals 'S'	1	2	3	4	5
B	1	'S' equals 'S'	2	3	4	5
U	2	2	'S' equals 'S'	'S' equals 'S'	3	4
K	3	3	3	3	'S' equals 'S'	3
A	4	4	3	4	3	'S' equals 'S'

Na kraju, u donjem desnom uglu se nalazi odgovor koliko možemo minimalno operacija da iskoristimo da bismo segment s[1..i] transformisali u segment t[1..j].

Dokaz korektnosti

Invarijanta algoritma je da možemo da transformišemo početni segment s[1…i] u t[1…j] koristeći minimalni broj operacija d[i,j]. Ovo važi jer:

Ovo je tačno u nultoj koloni i nultoj vrsti, jer s[1..i] može biti transformisan u praznu nisku t[1…0] tako što se jednostavno izbacuju svi i karakteri. Isto tako, možemo transformisati s[1..0] u t[1..j] jednostavno dodajući sve j karaktere.
Ako s[i]=t[j], i ako možemo da transformišemo s[1..i-1] u t[1..j-1] uz pomoć k operacija, onda to možemo da uradimo i segmentu s[1..i], ostavljajući poslednji karakter po strani.
U suprotnom, rastojanje je minimum od tri moguća načina da se transformacija uradi:
- Ako možemo da transformišemo s[1..i] u t[1..j] uz pomoć k operacija , to znači da možemo jednostavno da dodamo t[j] da bi posle toga dobili t[1..j] uz pomoć k+1 operacija (umetanje).
- Ako možemo da transformišemo s[1..i-1] u t[1..j] uz pomoć k operacija, to znači da možemo da uklonimo s[i] i da zatim uradimo istu transformaciju uz pomoć k+1 operacija. (brisanje).
- Ako možemo da transformišemo s[1..i-1] u t[1..j-1] uz pomoć k operacija, to znači da to možemo isto uraditi i segmentu s[1..i], i zameniti originalni s[i] sa t[j], uz pomoć k+1 operacija (zamena).
Broj operacija koje su zadužene da transformišu s[1..n] u t[1..m], je naravno broj koji je potreban da bi se svako s transformisalo u t, zbog toga je rezultat d(n,m).

Ovaj dokaz ne potvrđuje da je broj d[i,j] stvarno minimalni broj operacija; to je mnogo teži dokaz, uključuje kontradikciju u kojoj pretpostavimo da je d[i,j] manji od minimuma tri mogućih načina transformacija, i koristimo tu pretpostavku da pokažemo da jedan od ta tri načina nije minimum.

Moguća poboljšanja

Moguća poboljšanja ovog algoritma uključuju sledeće:

Možemo da adaptiramo algoritam tako da zauzima manje prostora, pa će nam prostorna složenost biti O(m) umesto O(mn), jer je samo potrebno da se prethodna vrsta i tekuća vrsta čuvaju u bilo kom trenutku.
Možemo da čuvamo broj umetanja, brisanja, i zamene odvojeno, ili čak pozicije na kojima se javljaju, koje su uvek j.
Možemo da normalizujemo rastojanje do intervala [0,1].
Ako bismo posmatrali samo rastojanje, i ako bi ono bilo manje od praga k, onda je dovoljno da se izračuna dijagonala širine 2k+1 u matrici. Na ovaj način, algoritam može imati vremensku složenost O(kl), gde je l dužina najkraće niske.^[1]
Možemo da damo različite cene troškova umetanja, brisanja, i zamene. Možemo takođe da damo cene troškova koje zavise od karaktera koji ubacujemo, brišemo ili zamenjujemo.
Ako inicijalizujemo prvu vrstu matrice sa 0, algoritam može da se iskoristi za takozvano Približno Pretraživanje Niske u tekstu (approximate string matching ili fuzzy string searching).^[2] Ova modifikacija pruža krajnju poziciju podudarnih subniski teksta. Da bi odredili početnu poziciju podudarnih subniski, broj umetanja i brisanja se može čuvati odvojeno, i može se iskoristiti da se izračuna početna pozicija pocevši od zadnje pozicije.^[3]
Ovaj algoritam loše paralelno računa, zbog velikog broja zavisnih podataka. Međutim, sve cene troškova mogu biti izračunate paralelno, i algoritam se može modifikovati tako da izvodi minimum funkcija u fazama kako bi izbegao zavisnost.
Posmatrajući dijagonale umesto vrste, i koristeći takozvanu lenju procenu (lazy evaluation), možemo da nađemo Levenštajnovo rastojanje i da dobijemo vremensku složenost O(m(1+d)) (d je Levenštajnovo rastojanje). Ovaj način je mnogo brži od algoritma običnog dinamičkog programiranja ako je rastojanje malo.^[4]

Gornje i donje granice

Levenštajnovo rastojanje ima nekoliko prostih gornjih i donjih granica koje su korisne u primenama u kojima se računaju i upoređuju. Ovo uključuje da:

Uvek je barem razlika u veličini dve niske.
U većini slučajeva je dužina duže niske.
Nula je ako i samo ako su niske identične.
Ako su niske istih veličina, Hamingovo rastojanje je gornja granica Levenštajnovog rastojanja.

Reference

^ Gusfield 1997.
^ Navarro, G. (2001). „A guided tour to approximate string matching”. ACM Computing Surveys. 33 (1): 31—88. doi:10.1145/375360.375365.
^ Bruno Woltzenlogel Paleo. An approximate gazetteer for GATE based on levenshtein distance Архивирано на веб-сајту Wayback Machine (8. мај 2013). Student Section of the European Summer School in Logic, Language and Information (ESSLLI), 2007.
^ Allison, L. (1992). „Lazy Dynamic-Programming can be Eager”. Inf. Proc. Letters. 43 (4): 207—12. doi:10.1016/0020-0190(92)90202-7.

Literatura

Gusfield, Dan (1997). Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge, UK: Cambridge University Press. ISBN 978-0-521-58519-4.
R.A. Wagner and M.J. Fischer. 1974. „The String-to-String Correction Problem”. Journal of the ACM. 21 (1): 168—173. .

Spoljašnje veze

A detailed description of how to implement the Wagner-Fischer algorithm and closely related algorithms.

[FOOTNOTEGusfield1997-1] Gusfield 1997.

[2] Navarro, G. (2001). „A guided tour to approximate string matching”. ACM Computing Surveys. 33 (1): 31—88. doi:10.1145/375360.375365.

[3] Bruno Woltzenlogel Paleo. An approximate gazetteer for GATE based on levenshtein distance Архивирано на веб-сајту Wayback Machine (8. мај 2013). Student Section of the European Summer School in Logic, Language and Information (ESSLLI), 2007.

[4] Allison, L. (1992). „Lazy Dynamic-Programming can be Eager”. Inf. Proc. Letters. 43 (4): 207—12. doi:10.1016/0020-0190(92)90202-7.

[1]

[2]

[3]

[4]