1. Algoritmi za podudaranje znakovnih nizova: metodologija izgradnje domenskih modela vrednovanja klasičnih algoritama i novi algoritam s predobradom uzorka
- Author
-
Markić, Ivan and Štula, Maja
- Subjects
algorithm evaluation approaches and metrics ,online exact algorithms with pattern preprocessing ,TECHNICAL SCIENCES. Computing. Data Processing ,domenski model rangiranja algoritama ,Elektrotehnika ,algorithm testing framework ,pristupi vrednovanja algoritama i metrike ,udc:621.3(043.3) ,TEHNIČKE ZNANOSTI. Računarstvo. Obradba informacija ,Algoritmi za podudaranje znakovnih nizova ,online egzaktni algoritmi s predobradom uzorka ,okvir za testiranje algoritama ,String matching algorithms ,Electrical engineering ,domain algorithm ranking model - 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. 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.
- Published
- 2022