Algoritmi za podudaranje znakovnih nizova

završni rad

• Naslov (engleski): String Matching Algorithms
• Autor: Marin Maršić
• Mentor: Andrea Aglić-Aljinović (mentor)
• Član povjerenstva: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Član povjerenstva: Mario Krnić (član povjerenstva)
• Član povjerenstva: Ana Žgaljić Keko (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2016-07-11, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: egzaktno podudaranje znakovnih nizova; aproksimativno podudaranje znakovnih nizova; naivni algoritam; Rabin-Karp; Knuth-Morris-Pratt; Boyer-Moore; sufiksno stablo; edit udaljenost; kompresija teksta; Shanon-Fano; Huffman; Lempel-Ziv-Welsh
• Ključne riječi (engleski): exact string matching; approximate string matching; naive algorithm; Rabin-Karp; Knuth-Morris-Pratt; Boyer-Moore; suffix trie; edit distance; text compression; Shanon-Fano; Huffman; Lempel-Ziv-Welsh
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:782950
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 10:29:26