Sufiksno stablo

završni rad

• Naslov (engleski): Suffix tree
• Autor: Tomislav Šebrek
• Mentor: Mile Šikić (mentor)
• Član povjerenstva: Mile Šikić (predsjednik povjerenstva)
• Član povjerenstva: Krešimir Križanović (član povjerenstva)
• Član povjerenstva: Andrej Novak (č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: 2015-07-13, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: eksplicitno proširenje; implicitno proširenje; implicitno sufiksno stablo; poopćeno sufiksno stablo; sufiks-prefiks preklapanje; sufiksna veza; sufiksno stablo; Ukkonenov algoritam
• Ključne riječi (engleski): explicit extension; implicit extension; implicit suffix tree; generalised suffix tree; suffix-prefix match; suffix link; suffix tree; Ukkonen's algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:444680
• 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 12:13:57