Približno poklapanje niske

Rasplinuta Vikimedija pretraga za "angry emoticon": "Da li ste mislili: andré emotions"

U računarstvu, približno poklapanje niske (često neformalno nazvano rasplinuto poklapanje niske) je tehnika pronalaženja niski koje približno odgovaraju obrascu (umesto tačno). Problem približnog poklapanja niske se uglavnom deli na dva potproblema: pronalaženje poklapanja približne podniske unutar date niske i pronalaženje niski u rečniku koji odgovaraju obrascu približno.

Pregled

Preciznost poklapanja se određuje na osnovu broja primitivnih operacija potrebnih za pretvaranje niske u tačno poklapanje. Ovaj broj se naziva edit rastojanje između niske i obrasca. Uobičajene primitivne operacije su:

• dodavanje: cot → coat
• brisanje: coat → cot
• zamena: coat → cost

Ove tri operacije mogu biti uopštene kao forma zamene dodavanjem NULL karaktera (ovde prikazanog simbolom *) gde god je karakter obrisan ili ubačen:

• dodavanje: co*t → coat
• brisanje: coat → co*t
• zamena: coat → cost

Nekada se u približnom poklapanju transpozicija, u kojoj se pozicije dva slova u niski zamene, tretira kao primitivna operacija. Promena cost u cots je primer transpozicije.

Različita približna poklapanja nameću različita ograničenja. Neka poklapanja koriste jednu opštu beztežinsku cenu, tj. ona predstavlja ukupan broj primitivnih operacija potrebnih da za pretvaranje poklapanja u obrazac. Na primer, ako je obrazac coil, foil se dobija jednom zamenom, coils jednim dodavanjem, oil jednim brisanjem, a foal sa dve zamene. Ako se sve operacije računaju kao jedna jedinica cene i ograničenje je postavljeno na jedan, foil, coils, i oil se računaju kao poklapanja, dok foal ne.

Druga poklapanja određuju broj operacija svakog tipa posebno, dok neka postavljaju ukupnu cenu ali dozvoljavaju različite vrednosti da budu dodeljene različitim operacijama. Neka poklapanja dozvoljavaju odvojene dodele ograničenja i vrednosti različitim grupama u obrascu.

Problem formulacije i algoritmi

Jedna moguća definicija približnog poklapanja niske je sledeća: Data je niska obrasca: $P=p_{1}p_{2}...p_{m}$ i niska teksta $T=t_{1}t_{2}\dots t_{n}$, pronaći podnisku $T_{j',j}=t_{j'}\dots t_{j}$ u T, koji ima najmanje edit rastojanje do obrasca P od svih mogućih podniski u T.

Pristup grubom silom (brute-force pristup) bi bio da se izračuna edit rastojanje do P za sve podniske u T, i onda odabrati podnisku sa najmanjim rastojanjem. Međutim, vremenska složenost ovog algoritma bi bila O(n³ m).

Bolje rešenje, koje je predložio Selers, oslanja se na dinamičko programiranje. Ovde se problem drugačije formuliše: za svaku poziciju j u tekstu T i svaku poziciju i u obrascu P, izračunati najmanje edit rastojanje između prvih i karaktera obrasca $P_{i}$, i bilo koje podniske $T_{j',j}$ iz T koji se završava na poziciji j.

Za svaku poziciju j u tekstu T, i svaku poziciju i u obrascu P, proći kroz sve podniske u T završno sa pozicijom j, i odrediti koja od njih ima najmanje edit rastojanje do prvih i karaktera obrasca P. Zapisati najmanje rastojanje kao E(i, j). Nakon izračunavanja E(i, j) za sve i i j, možemo lako naći rešenje početnog problema: to je podniska za koju je E(m, j) najmanje (gde je m dužina obrasca P).

Izračunavanje E(m, j) je veoma slično izračunavanju edit rastojanja između dve niske. U stvari, možemo iskoristiti algoritam za izračunavanje Levenštajnovog rastojanja za izračunavanje E(m, j), jedina razlika je da moramo prva dva reda inicijalizovati nulama, i čuvati put izračunavanja, što je, zavisno da li koristimo E(i − 1,j), E(i,j − 1) ili E(i − 1,j − 1) u izračunavanju E(i, j).

U nizu koji sadrži vrednosti E(x, y) odaberemo najmanju vrednost u poslednjem redu, neka je to E(x₂, y₂), i pratimo put izračunavanja unazad, sve do nultog reda. Ako je polje do kog smo stigli E(0, y₁), onda je T[y₁ + 1] ... T[y₂] podniska od T sa najmanjim edit rastojanjem do obrasca P.

Za izračunavanje niza E(x, y) je potrebno O(mn) vremena koristeći algoritam koji primenjuje dinamičko programiranje, dok za deo traženja puta unazad treba O(n + m) vremena.

Onlajn nasuprot oflajn

Tradicionalno, algoritmi za približno poklapanje niske se klasifikuju u dve kategorije: onlajn i oflajn. Sa onlajn algoritmima obrazac se može obraditi pre pretrage, ali tekst ne može. Drugim rečima, onlajn tehnike rade pretragu bez indeksa. Rani algoritmi za onlajn približno poklapanje su predloženi od strane Vagnera i Fišera i Selersa. Oba algoritma su zasnovana na dinamičkom programiranju ali rešavaju različite probleme. Selersov algoritam pretražuje približno za podnisku u tekstu, dok algoritam Vagnera i Fišera izračunava Levenštajnovo rastojanje i odgovara jedino za rasplinutu pretragu rečnika.

Onlajn tehnike pretrage su unapređivane u više navrata. Možda je najpoznatije unapređenje bitap algotiram (takođe poznat kao šift-ili i šift-i algoritam) koji je veoma efikasan za relativno kratke niske obrazaca. Bitap algoritam predstavlja jezgro Juniks programskog alata za pretragu agrep. Pregled algoritama za onlajn pretragu je urađen od strane G. Navara.

Iako postoje veoma brze onlajn tehnike, njihov učinak na velikim količinama podataka je neprihvatljiv. Pretprocesiranje teksta ili indeksiranje čini pretragu drastično bržom. Danas postoji veliki broj algoritama za indeksiranje. Među njima su sufiksna stabla, metrička stabla i n-gram metode. Detaljan pregled tehnika indeksiranja koje omogućavaju pronalaženje proizvoljne podniske u tekstu je dao Navaro et al.. Računarski pregled rečničkih metoda (npr. metoda koje omogućavaju pronalaženje svi reči iz rečnika koje približno odgovaraju obrascu pretrage) je dao Bojcov .

Primene

Najčešća primena približnih poklapanja do skora je bila u proveri pisanja. Sa dostupnošću velikih količina DNK podataka, veoma važna primena je postala i proveravanje poklapanja sekvenci nukleotida. Približno poklapanje se takođe koristi u filtriranju nepoželjne imejl pošte. Poklapanje niski se ne može koristiti za većinu binarnih podataka, kao što su slike i muzika. Oni zahtevaju drugačije algoritme, kao što je akustični otisak.

Vidi još

• Rastojanje uređivanja
• Nidlmen-Vanšov algoritam
• Smit-Vatermanov algoritam
• Džaro–Vinklerovo rastojanje
• Levenštajnovo rastojanje
• Konceptualna pretraga
• Regularni izrazi za nerasplinuto (tačno) poklapanje
• Metafon
• Saundeks
• Agrep
• Detekcija plagijata

Reference

• ^ Baeza-Yates, R.; Navarro, G. (1996). „A faster algorithm for approximate string matching”. Ur.: Dan Hirchsberg; Gene Myers. Combinatorial Pattern Matching (CPM'96), LNCS 1075. Irvine, CA. str. 1—23. 
• ^ Baeza-Yates R, Navarro G. „Fast Approximate String Matching in a Dictionary” (PDF). Proc. SPIRE'98. IEEE CS Press. str. 14—22. 
• ^ Boytsov, Leonid (2011). „Indexing methods for approximate dictionary searching: Comparative analysis”. Jea Acm. 16 (1): 1—91. doi:10.1145/1963190.1963191. 
• ^ Cormen, Thomas; Leiserson, Rivest (2001). Introduction to Algorithms (2nd izd.). MIT Press. str. 364–7. ISBN 978-0-262-03293-3. 
• ^ Galil, Zvi; Apostolico, Alberto (1997). Pattern matching algorithms. Oxford [Oxfordshire]: Oxford University Press. ISBN 978-0-19-511367-9. 
• ^ 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. 
• ^ G, Myers (1999). „A fast bit-vector algorithm for approximate string matching based on dynamic programming”. Journal of the ACM. 46 (3): 395—415. doi:10.1145/316542.316550. 
• ^ Navarro, Gonzalo (2001). „A guided tour to approximate string matching”. ACM Computing Surveys. 33 (1). doi:10.1145/375360.375365. CiteSeerX: 10.1.1.96.7225. 
• ^ Navarro, Gonzalo; Ricardo Baeza-Yates; E. Sutinen; J. Tarhio (2001). „Indexing Methods for Approximate String Matching” (PDF). IEEE Data Engineering Bulletin. 24 (4): 19—27. 
• ^ Sellers, Peter H. (1980). „The Theory and Computation of Evolutionary Distances: Pattern Recognition”. Journal of Algorithms. 1 (4): 359—73. doi:10.1016/0196-6774(80)90016-4. 
• ^ Skiena, Steve (1998). Algorithm Design Manual (1st izd.). Springer. ISBN 978-0-387-94860-7. 
• ^ E, Ukkonen (1985). „Algorithms for approximate string matching”. Information and Control. 64: 100—18. doi:10.1016/S0019-9958(85)80046-2. 
• ^ Wagner R, Fischer M (1974). „The string-to-string correction problem”. Journal of the ACM. 21: 168—73. doi:10.1145/321796.321811. 
• ^ J. Zobel, P. Dart. Finding approximate matches in large lexicons. Software-Practice & Experience 25(3). str. 331–345, 1995.

Spoljašnje veze

• Flamingo Project
• Efficient Similarity Query Processing Project sa skorašnjim napretkom u približnom poklapanju niski zasnovanom na rastojanju uređivanja.
• StringMetric project Skala biblioteka za metrike niski i fonetske algoritme
• Natural project Javaskript biblioteka za procesiranje prirodnih jezika koja uključuje impementacije popularnih metrika niski