Naslov
Algoritmi za podudaranje znakovnih nizova: metodologija izgradnje domenskih modela vrednovanja klasičnih algoritama i novi algoritam s predobradom uzorka
(String matching algorithms: methodology for building domain models for classical algorithms evaluation and a novel algorithm with pattern preprocessing)

Autori
Markić, Ivan

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, doktorska disertacija

Mjesto
Split

Datum
04.11

Godina
2022

Stranica
144

Mentor
Štula, Maja

Ključne riječi
Algoritmi za podudaranje znakovnih nizova ; domenski model rangiranja algoritama ; pristupi vrednovanja algoritama i metrike ; online egzaktni algoritmi s predobradom uzorka ; okvir za testiranje algoritama
(String matching algorithms ; domain algorithm ranking model ; algorithm evaluation approaches and metrics ; online exact algorithms with pattern preprocessing ; algorithm testing framework)

Sažetak
Odabir učinkovitog algoritma za podudaranje znakovnih nizova u tekstu izazovan je proces. Na izvršavanje algoritma mogu utjecati razni čimbenici poput jačine procesora, veličine radne memorije računala ili mogućnosti programskog jezika. U ovome radu predstavljena je metodologija izgradnje domenskih modela vrednovanja algoritama za podudaranje znakovnih nizova u tekstu temeljena na entropiji uzorka, izražavajući učinkovitost algoritma korištenjem metrika neovisnih o hardverskoj i softverskoj platformi. Razvijena metodologija je usmjerena prema algoritmima za egzaktnu usporedbu znakova prilikom podudaranja uzorka u tekstu bez prethodne spoznaje strukture teksta. Metodologija rangira algoritme prema njihovoj učinkovitosti koristeći svojstva uzorka koji se pretražuje, a ne ovisi o implementaciji algoritma ni o računalnoj arhitekturi te stoga pruža neovisan način odabira algoritma za određenu domenu primjene. Metodologija izgradnje domenskih modela vrednovanja algoritama eksperimentalno je potvrđena na dvije domene, DNA domeni i domeni prirodnog jezika. U radu je prezentiran i novi algoritam za egzaktno podudaranje znakovnih nizova. Heuristička tehnika prolaska kroz uzorak pomoću neparnih i parnih pozicija znakova u kombinaciji s podacima dobivenim predobradom uzorka oblikovana je pravilima algoritma. Definirana heuristička pravila koriste se za preskakanje nepotrebnih usporedbi znakova uzorka. Točnost i pouzdanost algoritma je eksperimentalno vrednovana.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA