Ukkonenov algoritem konstrukcije priponskega drevesa

diplomsko delo

Štefan Horvat (Author), Borut Žalik (Mentor), Marko Bizjak (Co-mentor)

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2020
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher:	[Š. Horvat]
UDC:	004.422.63(043.2)
COBISS:	37249027
Views:	480
Downloads:	117
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Ukkonen's algorithm for suffix tree construction
Secondary abstract:	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.
Secondary keywords:	algorithms;data structures;algorithm analysis;space and time complexity;
Type (COBISS):	Bachelor thesis/paper
Thesis comment:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije
Pages:	V, 43 f.
ID:	11972770