Sufiksno stablo (CROSBI ID 407817)
Ocjenski rad | sveučilišni preddiplomski završni rad
Podaci o odgovornosti
Šebrek, Tomislav
Šikić, Mile
hrvatski
Sufiksno stablo
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.
eksplicitno proširenje; implicitno proširenje; implicitno sufiksno stablo; poopćeno sufiksno stablo; sufiks-prefiks preklapanje; sufiksna veza; sufiksno stablo; Ukkonenov algoritam
nije evidentirano
engleski
Suffix Tree
nije evidentirano
explicit extension; implicit extension; implicit suffix tree; generalised suffix tree; suffix-prefix match; suffix link; suffix tree; Ukkonen's algorithm
nije evidentirano
Podaci o izdanju
40
02.05.2015.
obranjeno
Podaci o ustanovi koja je dodijelila akademski stupanj
Fakultet elektrotehnike i računarstva
Zagreb