prikaz prve stranice dokumenta Algoritmi za podudaranje znakovnih nizova
No public access
undergraduate thesis
Algoritmi za podudaranje znakovnih nizova
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2016. urn:nbn:hr:168:782950
Maršić, Marin
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Maršić, M. (2016). Algoritmi za podudaranje znakovnih nizova (Undergraduate thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:782950

Maršić, Marin. "Algoritmi za podudaranje znakovnih nizova." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2016. https://urn.nsk.hr/urn:nbn:hr:168:782950

Maršić, Marin. "Algoritmi za podudaranje znakovnih nizova." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2016. https://urn.nsk.hr/urn:nbn:hr:168:782950

Maršić, M. (2016). 'Algoritmi za podudaranje znakovnih nizova', Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 30 November 2024, https://urn.nsk.hr/urn:nbn:hr:168:782950

Maršić M. Algoritmi za podudaranje znakovnih nizova [Undergraduate thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2016 [cited 2024 November 30] Available at: https://urn.nsk.hr/urn:nbn:hr:168:782950

M. Maršić, "Algoritmi za podudaranje znakovnih nizova", Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2016. Available at: https://urn.nsk.hr/urn:nbn:hr:168:782950

Metadata
TitleAlgoritmi za podudaranje znakovnih nizova
Title (english)String Matching Algorithms
AuthorMarin Maršić
MentorAndrea Aglić-Aljinović (mentor)
Committee memberAndrea Aglić Aljinović (predsjednik povjerenstva)
Committee memberMario Krnić (član povjerenstva)
Committee memberAna Žgaljić Keko (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2016-07-11, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Abstract
U ovom radu obradili smo najosnovnije metode za podudaranje znakovnih nizova i kompresiju teksta. Za svaki od ovih tipova analizirali smo nekoliko najbitnijih algoritama. Algoritme za podudaranje znakovnih nizova podijelili smo na one za egzaktno i aproksimativno podudaranje. Algoritmi egzaktnog podudaranja tražili su dani znakovni uzorak u tekstu, dok su algoritmi aproksimativnog podudaranja tražili riječi slične našem uzorku. Osim naivnog algoritma za egzaktno podudaranje znakovnih nizova, obradili smo i Rabin-Karpov, Knuth-Morris-Prattov, Boyer-Mooreov algoritam te strukturu podataka sufiksnog stabla koja ima veliku primjenu na ovom problemu. Za rješavanje problema aproksimativnog podudaranja koristili smo algoritam računanja edit udaljenosti. Na kraju smo obradili tri algoritma za kompresiju teksta: Shannon-Fanoov, Huffmanovi i Lempel–Ziv–Welshev.
Abstract (english)
In this thesis we covered the most basic methods for string matching and text compression. For each of these two types of algorithms, we analyzed a few of the most important algorithms. We split string matching algorithms into two groups, those for exact string matching and those for approximate string matching. Exact string matching algorithms searched for a given pattern in the text, while the approximate string matching algorithms searched for words similar to our pattern. In addition to the naive string matching algorithm, we have analyzed Rabin-Karp, Knuth-Morris-Pratt and Boyer- Moore algorithm and suffix trie that has a great application on this issue. To solve the problem of approximate string matching we used algorithm for computing edit distance. At the end, we have covered three algorithms for text compression: Shannon-Fanoo, Huffman and Lempel-Ziv-Welsh algorithm.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:168:782950
Study programmeTitle: Computing
Study programme type: university
Study level: undergraduate
Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
Type of resourceText
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Public note
Created on2018-02-06 10:29:26