Naslov
Sufiksno stablo
(Suffix Tree)

Autori
Šebrek, Tomislav

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, preddiplomski

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
02.05

Godina
2015

Stranica
40

Mentor
Šikić, Mile

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
(explicit extension; implicit extension; implicit suffix tree; generalised suffix tree; suffix-prefix match; suffix link; suffix tree; Ukkonen's algorithm)

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.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA