prikaz prve stranice dokumenta Algoritmi za podudaranje znakovnih nizova
  Download
PDF 4.3 MB
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

Institutional repository: Repository of the Faculty of Electrical Engineering, Mechanical Engineering and Naval Architecture

Cite this document

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

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

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

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 17 June 2024, https://urn.nsk.hr/urn:nbn:hr:179:530293

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 2024 June 17] Available at: https://urn.nsk.hr/urn:nbn:hr:179:530293

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

Metadata
TitleAlgoritmi 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
AuthorIvan Markić
MentorMaja Štula (mentor)
Committee memberMario Čagalj (predsjednik povjerenstva)
Committee memberMirjana Domazet Lošo (član povjerenstva)
Committee memberMatko Šarić (član povjerenstva)
Committee memberToni Perković (član povjerenstva)
Committee memberMarin Bugarić (član povjerenstva)
GranterUniversity of Split
Faculty of Electrical Engineering, Mechanical Engineering and Naval Architecture
(Department of Electronics and Computing)
Split
Defense date and country2022-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)
Languagecroatian
URN:NBNurn:nbn:hr:179:530293
Promotion2022
Study programmeTitle: 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 resourceText
Extent144 str.
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2022-11-23 12:26:55