Algoritmi za podudaranje znakovnih nizova

Markić, Ivan

doctoral thesis

Algoritmi za podudaranje znakovnih nizova

metodologija izgradnje domenskih modela vrednovanja klasičnih algoritama i novi algoritam s predobradom uzorka

Split: University of Split, Faculty of Electrical Engineering, Mechanical Engineering and Naval Architecture, 2022. urn:nbn:hr:179:530293

Markić, Ivan

University of Split
Faculty of Electrical Engineering, Mechanical Engineering and Naval Architecture
Department of Electronics and Computing

Cite this document

APA 6th Edition

Markić, I. (2022). Algoritmi za podudaranje znakovnih nizova : metodologija izgradnje domenskih modela vrednovanja klasičnih algoritama i novi algoritam s predobradom uzorka (Doctoral thesis). Split: University of Split, Faculty of Electrical Engineering, Mechanical Engineering and Naval Architecture. Retrieved from https://urn.nsk.hr/urn:nbn:hr:179:530293

MLA 8th Edition

Markić, Ivan. "Algoritmi za podudaranje znakovnih nizova : metodologija izgradnje domenskih modela vrednovanja klasičnih algoritama i novi algoritam s predobradom uzorka." Doctoral thesis, University of Split, Faculty of Electrical Engineering, Mechanical Engineering and Naval Architecture, 2022. https://urn.nsk.hr/urn:nbn:hr:179:530293

Chicago 17th Edition

Harvard

Markić, I. (2022). 'Algoritmi za podudaranje znakovnih nizova : metodologija izgradnje domenskih modela vrednovanja klasičnih algoritama i novi algoritam s predobradom uzorka', Doctoral thesis, University of Split, Faculty of Electrical Engineering, Mechanical Engineering and Naval Architecture, accessed 23 September 2023, https://urn.nsk.hr/urn:nbn:hr:179:530293

Vancouver

Markić I. Algoritmi za podudaranje znakovnih nizova : metodologija izgradnje domenskih modela vrednovanja klasičnih algoritama i novi algoritam s predobradom uzorka [Doctoral thesis]. Split: University of Split, Faculty of Electrical Engineering, Mechanical Engineering and Naval Architecture; 2022 [cited 2023 September 23] Available at: https://urn.nsk.hr/urn:nbn:hr:179:530293

IEEE

I. Markić, "Algoritmi za podudaranje znakovnih nizova : metodologija izgradnje domenskih modela vrednovanja klasičnih algoritama i novi algoritam s predobradom uzorka", Doctoral thesis, University of Split, Faculty of Electrical Engineering, Mechanical Engineering and Naval Architecture, Split, 2022. Available at: https://urn.nsk.hr/urn:nbn:hr:179:530293

Cite this item: https://urn.nsk.hr/urn:nbn:hr:179:530293

Please login to the repository to save this object to your list.

Metadata

Title	Algoritmi za podudaranje znakovnih nizova : metodologija izgradnje domenskih modela vrednovanja klasičnih algoritama i novi algoritam s predobradom uzorka
Title (english)	String matching algorithms : methodology for building domain models for classical algorithms evaluation and a novel algorithm with pattern preprocessing
Author	Ivan Markić
Mentor	Maja Štula (mentor)
Committee member	Mario Čagalj (predsjednik povjerenstva)
Committee member	Mirjana Domazet Lošo (član povjerenstva)
Committee member	Matko Šarić (član povjerenstva)
Committee member	Toni Perković (član povjerenstva)
Committee member	Marin Bugarić (član povjerenstva)
Granter	University of Split Faculty of Electrical Engineering, Mechanical Engineering and Naval Architecture (Department of Electronics and Computing) Split
Defense date and country	2022-11-04, Croatia
Scientific / art field, discipline and subdiscipline	TECHNICAL SCIENCES Computing Data Processing
Universal decimal classification (UDC)	621.3 - Electrical engineering
Abstract	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.
Abstract (english)	Choosing an efficient algorithm for strings matching in a text is a challenging process. The algorithm execution can be affected by various factors such as the processor power, the size of the computer memory, or the programming language capabilities. This doctoral thesis presents the methodology for building domain models for strings matching algorithms evaluation based on pattern entropy, expressing the algorithm's efficiencyusing hardware and software platform independent metrics. The developed methodology is focused on algorithms for exact string comparison to match the pattern in the text without a prior knowledge of the text structure. The methodology ranks algorithms according to their efficiency using the properties of the pattern being searched, and does not depend on the implementation of the algorithm or the computer architecture and therefore provides an independent way of selecting an algorithm for a particular application domain. The methodology for building domain models for evaluating algorithms has been experimentally confirmed on two domains, the DNA domain, and the natural language domain. The doctoral thesis also presents a new algorithm for exact string matching. The heuristic technique of passing through a pattern using odd and evenpositions of characters, in combination with the data obtained by preprocessing the pattern, is shaped in the algorithm rules. Defined heuristic rules are used to skip unnecessary comparisons of pattern characters. The accuracy and reliability of the algorithm were experimentally evaluated.
Keywords
Keywords (english)
Language	croatian
URN:NBN	urn:nbn:hr:179:530293
Promotion	2022
Study programme	Title: Electrical Engineering and Information Technology Study programme type: university Study level: postgraduate Academic / professional title: doktor/doktorica znanosti, područje tehničkih znanosti, polje elektrotehnika (doktor/doktorica znanosti, područje tehničkih znanosti, polje elektrotehnika)
Type of resource	Text
Extent	144 str.
File origin	Born digital
Access conditions	Open access
Terms of use
Repository	Repository of the Faculty of Electrical Engineering, Mechanical Engineering and Naval Architecture
Created on	2022-11-23 12:26:55