Algoritmi za podudaranje znakovnih nizova: metodologija izgradnje domenskih modela vrednovanja klasičnih algoritama i novi algoritam s predobradom uzorka (CROSBI ID 455188)
Ocjenski rad | doktorska disertacija
Podaci o odgovornosti
Markić, Ivan
Štula, Maja
hrvatski
Algoritmi za podudaranje znakovnih nizova: metodologija izgradnje domenskih modela vrednovanja klasičnih algoritama i novi algoritam s predobradom uzorka
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.
Algoritmi za podudaranje znakovnih nizova ; domenski model rangiranja algoritama ; pristupi vrednovanja algoritama i metrike ; online egzaktni algoritmi s predobradom uzorka ; okvir za testiranje algoritama
nije evidentirano
engleski
String matching algorithms: methodology for building domain models for classical algorithms evaluation and a novel algorithm with pattern preprocessing
nije evidentirano
String matching algorithms ; domain algorithm ranking model ; algorithm evaluation approaches and metrics ; online exact algorithms with pattern preprocessing ; algorithm testing framework
nije evidentirano
Podaci o izdanju
144
04.11.2022.
obranjeno
Podaci o ustanovi koja je dodijelila akademski stupanj
Fakultet elektrotehnike, strojarstva i brodogradnje u Splitu
Split