prikaz prve stranice dokumenta Algoritmi za djelomično podudaranje znakovnih nizova
  Download
PDF 325.95 KB
master's thesis
Algoritmi za djelomično podudaranje znakovnih nizova
Zagreb: University of Zagreb, Faculty of Science, 2015. urn:nbn:hr:217:400399
Ružić, Sanjin
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Ružić, S. (2015). Algoritmi za djelomično podudaranje znakovnih nizova (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:400399

Ružić, Sanjin. "Algoritmi za djelomično podudaranje znakovnih nizova." Master's thesis, University of Zagreb, Faculty of Science, 2015. https://urn.nsk.hr/urn:nbn:hr:217:400399

Ružić, Sanjin. "Algoritmi za djelomično podudaranje znakovnih nizova." Master's thesis, University of Zagreb, Faculty of Science, 2015. https://urn.nsk.hr/urn:nbn:hr:217:400399

Ružić, S. (2015). 'Algoritmi za djelomično podudaranje znakovnih nizova', Master's thesis, University of Zagreb, Faculty of Science, accessed 01 June 2024, https://urn.nsk.hr/urn:nbn:hr:217:400399

Ružić S. Algoritmi za djelomično podudaranje znakovnih nizova [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2015 [cited 2024 June 01] Available at: https://urn.nsk.hr/urn:nbn:hr:217:400399

S. Ružić, "Algoritmi za djelomično podudaranje znakovnih nizova", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2015. Available at: https://urn.nsk.hr/urn:nbn:hr:217:400399

Metadata
TitleAlgoritmi za djelomično podudaranje znakovnih nizova
AuthorSanjin Ružić
MentorGoranka Nogo (mentor)
Committee memberGoranka Nogo (predsjednik povjerenstva)
Committee memberMiljenko Marušić (član povjerenstva)
Committee memberGoran Igaly (član povjerenstva)
Committee memberMarko Vrdoljak (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2015-09-25, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
U ovom radu obradili smo algoritme koji rješavaju problem podudaranja znakovnih nizova. Promatrali smo tri različita problema: problem egzaktnog podudaranja, problem aproksimativnog podudaranja te problem podudaranja sa zamjenskim znakovima. Pritom smo se vise usredotočili na posljednje dvije klase problema. Za svaku od klasa naveli smo jedan ili vise najznačajnijih algoritama koji rješava dotični problem. Tako smo za problem egzaktnog podudaranja znakovnih nizova, uz naivni algoritam, analizirali i klasične algoritme kao sto su Rabin-Karpov, Knuth-Morris-Prattov te Boyer-Mooreov. Za svaki od njih objasnili smo osnovnu ideju te pokazali vremensku složenost. Za problem aproksimativnog podudaranja znakovnih nizova odabrali smo Wagner-Fischerov algoritam temeljen na ideji dinamičkog programiranja koji računa edit-udaljenost između dvaju stringova. Detaljno smo dokazali njegovu korektnost te vremensku složenost. Iako on sam ne rješava problem aproksimativnog podudaranja znakovnih nizova kako smo ga mi u radu definirali, vidjeli smo da se njegovom sitnom modifikacijom koju je uveo Sellers moze rješiti i naš problem. Na kraju, za problem podudaranja stringova sa zamjenskim znakovima predstavili smo tri rješenja. Prvo rješenje se zasniva na regularnim izrazima koji su zapravo puno ekspresivniji nego je nama potrebno pa imaju relativno veliku vremensku složenost. Drugo rješenje je dobiveno rekurzivnim algoritmom koji smo optimizirali koristeći dinamičko programiranje. Posljednje rješenje se zasniva na ideji backtrackinga, a u usporedbi s preostala dva ima najmanju prosječnu vremensku složenost. Sve spomenute algoritme smo implementirali u programskom jeziku Java uz zaključak da se dobiveni eksperimentalni rezultati podudaraju s teoretskim.
Abstract (english)
In this thesis we studied string matching algorithms. We analyzed three different problems: exact, approximate and wildcard string matching. We focused on last two classes of algorithms. We mentioned one or more most significant representatives of each class. For exact string matching, beside naive algorithm, we also analyzed classic algorithms such as Rabin-Karp, Knuth-Morris-Pratt and Boyer-Moore. For each of them we described main idea and determined complexity. For approximate string matching, we chose Wagner-Fischer algorithm which is based on dynamic programming. It computes edit distance between two strings. While it does not solve problem of approximate string matching as we defined it, we saw that it can be modified in order to solve our problem, too. This modification was introduced by Sellers. Finally, for wildcard string matching we presented three solutions. First one was based on regular expressions which are in fact more expressive than we need so they have relative high complexity. Second solution was recursive algorithm which is further optimized by dynamic programming. Last solution is based on idea of backtracking, and in comparison with another two solutions had lowest average time complexity. We implemented all mentioned algorithms in programming language Java. Conclusions were that all experimental results coincide with theoretical results.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:400399
Study programmeTitle: Computer Science and Mathematics
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2019-02-05 15:54:22