Algoritmi za djelomično podudaranje znakovnih nizova

master's thesis

• Author: Sanjin Ružić
• Mentor: Goranka Nogo (mentor)
• Committee member: Goranka Nogo (predsjednik povjerenstva)
• Committee member: Miljenko Marušić (član povjerenstva)
• Committee member: Goran Igaly (član povjerenstva)
• Committee member: Marko Vrdoljak (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2015-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: problem egzaktnog podudaranja; problem aproksimativnog podudaranja; problem podudaranja sa zamjenskim znakovima; dinamičko programiranje; programski jezik Java
• Keywords (english): exact string matching; approximate string matching; wildcard string matching; dynamic programming; programming language Java
• Language: croatian
• URN:NBN: urn:nbn:hr:217:400399
• Study programme: Title: 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 resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-02-05 15:54:22