Ukkonenov algoritem konstrukcije priponskega drevesa

diplomsko delo

Štefan Horvat (Avtor), Borut Žalik (Mentor), Marko Bizjak (Komentor)

Povzetek

S pomočjo priponskih dreves lahko zelo preprosto in hitro izvajamo različne operacije nad nizi. Za gradnjo priponskih dreves obstajajo različni algoritmi. V diplomskem delu opi-šemo in implementiramo Ukkonenov algoritem, ki priponsko drevo zgradi v linearnem času. Najprej preučimo delovanje algoritma in tvorimo ustrezne podatkovne strukture. Sledi implementacija in preizkušanje. Z eksperimenti pokažemo karakteristike algoritma ob različnem številu znakov ter preverimo njegovo časovno in prostorsko zahtevnost.

Ključne besede

algoritmi;podatkovne strukture;analiza algoritmov;časovna in prostorska zahtevnost;diplomske naloge;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2020
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Založnik:	[Š. Horvat]
UDK:	004.422.63(043.2)
COBISS:	37249027
Št. ogledov:	480
Št. prenosov:	117
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Ukkonen's algorithm for suffix tree construction
Sekundarni povzetek:	Different operations on strings can be executed efficiently using a suffix tree. Various algorithms exist for the suffix tree construction. Ukkonen’s algorithm is one of them andis considered in this thesis. The idea of the algorithm is presentedfirst. The used data structuresare described next,followed by implementation details. Our implementation of the Ukkonen’s algorithm is evaluated in regard to the spent CPU time and computer memory usage. The obtained implementation turns out stable and efficient.
Sekundarne ključne besede:	algorithms;data structures;algorithm analysis;space and time complexity;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Komentar na gradivo:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije
Strani:	V, 43 f.
ID:	11972770