Algoritmi za djelomično podudaranje znakovnih nizova

Ružić, Sanjin (2015) Algoritmi za djelomično podudaranje znakovnih nizova. Diploma thesis, Faculty of Science > Department of Mathematics.

[img]
Preview
PDF
Language: Croatian

Download (333kB) | Preview
[img] Archive (dodatni materijali ("programski dio"))
Language: Croatian

Download (293kB)

Abstract

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.

Item Type: Thesis (Diploma thesis)
Supervisor: Nogo, Goranka
Date: 2015
Number of Pages: 42
Subjects: NATURAL SCIENCES > Mathematics
Divisions: Faculty of Science > Department of Mathematics
Depositing User: Iva Prah
Date Deposited: 26 Oct 2015 13:16
Last Modified: 26 Oct 2015 13:16
URI: http://digre.pmf.unizg.hr/id/eprint/4311

Actions (login required)

View Item View Item