prikaz prve stranice dokumenta Sufiksno stablo
No public access
undergraduate thesis
Sufiksno stablo
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2015. urn:nbn:hr:168:444680
Šebrek, Tomislav
University of Zagreb
Faculty of Electrical Engineering and Computing

Cite this document

Šebrek, T. (2015). Sufiksno stablo (Undergraduate thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:444680

Šebrek, Tomislav. "Sufiksno stablo." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2015. https://urn.nsk.hr/urn:nbn:hr:168:444680

Šebrek, Tomislav. "Sufiksno stablo." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2015. https://urn.nsk.hr/urn:nbn:hr:168:444680

Šebrek, T. (2015). 'Sufiksno stablo', Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 19 April 2024, https://urn.nsk.hr/urn:nbn:hr:168:444680

Šebrek T. Sufiksno stablo [Undergraduate thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2015 [cited 2024 April 19] Available at: https://urn.nsk.hr/urn:nbn:hr:168:444680

T. Šebrek, "Sufiksno stablo", Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2015. Available at: https://urn.nsk.hr/urn:nbn:hr:168:444680

Please login to the repository to save this object to your list.
Metadata
TitleSufiksno stablo
Title (english)Suffix tree
AuthorTomislav Šebrek
MentorMile Šikić (mentor)
Committee memberMile Šikić (predsjednik povjerenstva)
Committee memberKrešimir Križanović (član povjerenstva)
Committee memberAndrej Novak (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2015-07-13, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Abstract
Sufiksno stablo je struktura podataka koja omogućuje razne manipulacije nad znakovnim nizom u linearnom vremenu ovisnom samo o duljini podniza nad kojima se ostvaruje upit, a moguće ga je izgraditi u linearnom vremenu. U ovom radu opisana je izgradnja stabla Ukkonenovim algoritmom koji se temelji na izgradnji implicitnih sufiksnih stabala za svaki prefiks znakovnog niza kroz implicitna i eksplicitna proširenja, a svoju linearnost postiže kroz eliminaciju implicitnih proširenja, uvođena strukture aktivne pozicije te sufiksnim vezama. U ovom radu opisana je implementacija Ukkonenovog algoritma za izgradnju poopćenog sufiksnog stabla, što je zapravo generalizacija algoritma za skup znakovnih nizova. Kao primjena poopćenog stabla, prikazan je implementacija pronalaska svih sufiks-prefiks preklapanja između znakovnih nizova nad kojima je stablo izgrađeno. Rezultati testiranja složenosti programskog rješenja nad znakovnim nizovima različitih duljina podudaraju se s teorijskom analizom složenosti.
Abstract (english)
Suffix tree is a data structure that allows various string operations to be executed in linear time dependent only on the length of the substring for which the operation is executed, and its construction is possible in linear time. Ukkonen's algorithm for suffix tree construction is based on construction of implicit suffix trees for each string prefix through implicit and explicit extensions. Linearity of Ukkonen's algorithm is achieved through elimination of implicit extension check, active position structure and suffix links. In this thesis implementation of Ukkonen's algorithm for construction of generalised suffix tree, which in fact is generalisation of algorithm over set of strings, is shown. As an example of suffix tree, implementation of finding all suffix-prefix matches between strings over which the tree was built is demonstrated. Complexity calculated by running several tests over different sized strings matches the complexity obtained by theoretical analysis of the algorithm.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:168:444680
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
RepositoryFER Repository
Created on2018-02-06 12:13:57

(©) Nacionalna i sveučilišna knjižnica u Zagrebu 2015. Sva prava pridržana. | Hrvatske bratske zajednice 4 p.p. 550, 10000 Zagreb, Hrvatska Tel. ++ 385 1 616-4040
OIB: 84838770814 | IBAN: HR66 2340 0091 1000 1008 1, Porezni broj (PDV identifikacijski broj) - VAT Number: HR84838770814
Prijava u repozitorij