|
|
|
|
| LEADER |
03240na a2200241 4500 |
| 003 |
HR-ZaFER |
| 005 |
20160613113222.0 |
| 008 |
160221s2015 ci ||||| m||| 00| 0 hr d |
| 035 |
|
|
|a (HR-ZaFER)ferid2216
|
| 040 |
|
|
|a HR-ZaFER
|b hrv
|c HR-ZaFER
|e ppiak
|
| 100 |
1 |
|
|a Šebrek, Tomislav
|9 37041
|
| 245 |
1 |
0 |
|a Sufiksno stablo :
|b završni rad /
|c Tomislav Šebrek ; [mentor Mile Šikić].
|
| 246 |
1 |
|
|a Suffix tree
|i Naslov na engleskom:
|
| 260 |
|
|
|a Zagreb,
|b T. Šebrek,
|c 2015.
|
| 300 |
|
|
|a 35 str. ;
|c 30 cm +
|e CD-ROM
|
| 502 |
|
|
|b preddiplomski studij
|c Fakultet elektrotehnike i računarstva u Zagrebu
|g smjer: Računarska znanost, šifra smjera: 41, datum predaje: 2015-06-12, datum završetka: 2015-07-13
|
| 520 |
3 |
|
|a Sažetak na hrvatskom: 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.
|
| 520 |
3 |
|
|a Sažetak na engleskom: 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.
|
| 653 |
|
1 |
|a eksplicitno proširenje
|a implicitno proširenje
|a implicitno sufiksno stablo
|a poopćeno sufiksno stablo
|a sufiks-prefiks preklapanje
|a sufiksna veza
|a sufiksno stablo
|a Ukkonenov algoritam
|
| 653 |
|
1 |
|a explicit extension
|a implicit extension
|a implicit suffix tree
|a generalised suffix tree
|a suffix-prefix match
|a suffix link
|a suffix tree
|a Ukkonen's algorithm
|
| 700 |
1 |
|
|a Šikić, Mile
|4 ths
|9 29535
|
| 942 |
|
|
|c Z
|2 udc
|
| 999 |
|
|
|c 45903
|d 45903
|