Nalazite se na CroRIS probnoj okolini. Ovdje evidentirani podaci neće biti pohranjeni u Informacijskom sustavu znanosti RH. Ako je ovo greška, CroRIS produkcijskoj okolini moguće je pristupi putem poveznice www.croris.hr
izvor podataka: crosbi !

Sufiksno stablo (CROSBI ID 407817)

Ocjenski rad | sveučilišni preddiplomski završni rad

Šebrek, Tomislav Sufiksno stablo / Šikić, Mile (mentor); Zagreb, Fakultet elektrotehnike i računarstva, . 2015

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

Povezanost rada

Računarstvo