Milan Miščević

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

U računarskoj praksi često se javlja slučaj kada želimo nešto naći, a nemamo odgovarajući uzorak (eng. pattern) za pretragu ili uzorak i/ili traženo posjeduju određeni procenat greške ili razlika. Kao odgovor na ovakav problem, javljaju se algoritmi koji su u mogućnosti da nađu traženo ili barem da rezultate pretrage svedu na razuman broj.

Pretraga sa greškom (eng. nonexact string (pattern) matching, approximate string matching, string matching with (that allows) errors) je vrsta pretraga gdje je dozvoljeno postojanje izvjesne razlike između uzorka i traženog.

Funkcije sličnosti

Rad nekih algoritama pretrage sa greškom zasniva se na funkcijama sličnosti (eng. similarity function). To su funkcije koje izračunavaju broj elementarnih operacija koje je potrebno izvršiti na prvim stringom da bi se dobio drugi string. Što je manji broj operacija potreban, dati stringovi su sličniji i obrnuto. Najpoznatije funkcije sličnosti su Levenštajnovo rastojanje (eng. Levenshtein distance), Hemingovo rastojanje (eng. Hamming distance), n-gram rastojanje (eng. n-gram distance) i druge. Takođe, postoje i njihove derivacije (eng. extension), kao što su Damerau-Levenštajnovo rastojanje (eng. Damerau-Levenshtein distance), uopšteno (težinsko) Levenštajnovo rastojanje (eng. generalized (weighted) Levenshtein distance) i druge. U ovoj oblasti, Levenštajnovo rastojanje je defakto standard.

Od elementarnih operacija nad stringovima najčešće su u upotrebi sledeće tri:

• ubacivanje karaktera (prvo -> pravo; eng. insert)
• izbacivanje karaktera (pravo -> prvo; eng. delete)
• zamjena karaktera (pravo -> prava; eng. substitution)

Levenštajnovo rastojanje koristi tri prethodno nabrojane. Damerau-Levenštajnovo rastojanje koristi i operaciju zamjene mjesta karaktera (prav -> prva; eng. transposition), dok Hemingovo rastojanje koristi samo jednu operaciju, a to je zamjena karaktera.

Neke funkcije različito vrednuju (eng. cost) različite operacije. Tako postoje nadogradnje Levenštajnovog rastojanja, gdje ubacivanje i izbacivanje karaktera vrijedi jednu operaciju, a zamjena dvije. U tom slučaju, zamjena se posmatra kao operacija koja se sastoji iz jednog izbacivanja i jednog ubacivanja.

Fonetsko kodiranje i algoritmi

Pored upotrebe funkcija sličnosti, postoje algoritmi čiji se rad zasniva na fonetskom kodiranju – fonetski algoritmi. U njima riječi se kodiraju prema načinu kako se izgovaraju. Suština ovakvih algoritama je da se riječi, koje se isto ili slično izgovaraju, koduju u iste kodove. Ovakvi algoritmi se prave različito za različite jezike. Upotreba algoritma drugog jezika ne donosi nikakve značajne rezultate.

Najpoznatiji algoritam ove grupe je saundeks (eng. soundex). Nerijetko se njegovo ime koristi kao sinonim za čitavu grupu.

Drugi poznatiji algoritmi su:

• Dejč-Mokotofov saundeks (eng. Daitch-Mokotoff soundex)
• Metafon (eng. Metaphone)
• Dvostruki metafon (eng. Double Metaphone)
• Sistem za identifikaciju države Njujork (eng. New York State Identification and Intelligence System)
• Kejverfon (eng. Caverphone)

Upotreba

Područja upotrebe algoritama pretrage sa greškom su višestruka i njihov broj, iz dana u dan, raste.

Jedno od najvažnijih područja upotrebe je molekularna biologija (eng. computational biology), gdje se upotrebljavaju za pretragu DNK ili RNK sekvenci nukleotida. Na taj se način pronalaze mutacije na genima ili sekvence nukleotida koje reprezentuju slične osobine ili funkcije ćelija. Takođe omogućava se konstruisanje stabla evolucije, jer su genetski materijali sličnih jedinki slični. Poznati algoritmi u ovoj oblasti su Nidlmen-Vunšov (eng. Needleman-Wunsch algorithm) i Smit-Votermenov algoritam (eng. Smith-Waterman algorithm).

Drugo važno područje upotrebe je obrada signala (eng. signal processing). To podrazumjeva algoritme za prepoznavanje glasa i korekciju greške (uklanjanje grešaka nastalih u prenosu). Ovo područje je dobilo zamah tek zadnjih nekoliko godina, zahvaljujući potrebi da se multimedijalni sadržaji pretražuju. Realno je očekivati sve bolje aplikacije za prepoznavanje glasa, pa čak i upotrebu računara bez tastature i miša.

Ne manje važno područje upotrebe je i korekcija grešaka u tekstovima (eng. text retrieval). Potreba za ovim seže, u računarskom smislu, daleko u prošlost u dvadesete godine prošlog vijeka, što ga čini i prvim područjem upotrebe, u vremenskom smislu. Na ovaj način se može procenat greške u dokumentima se može smanjiti za 80 %.

Uz pomoć velike baze riječi, internet pretraživači svojom asistencijom mogu pomoći u pretrazi Interneta.

Još neka područja upotrebe su prepoznavanje rukopisa (eng. handwriting recognition), detekcija malvera (eng. virus and intruder detection), kompresija slika (eng. image compression) i druga.