diplomsko delo
Anže Jeromel (Author), Borut Žalik (Mentor)

Abstract

V diplomski nalogi smo obravnavali dva različna načina konstrukcije Burrows-Wheelerjeve transformacije in ju primerjali glede na čas izvajanja. Razložili smo idejo in postopek transformacije in njenega inverza ter ju prikazali na primeru. Implementirali smo dva različna algoritma – izboljšan osnovni algoritem ter algoritem s priponskim poljem. Izbrana algoritma smo preizkusili na različnih datotekah in rezultate primerjali. Ugotovili smo, da se izboljšan osnovni algoritem bolje izkaže pri krajših nizih naključno porazdeljenih znakov, pri vseh ostalih pa je bolje uporabiti algoritem s priponskim poljem.

Keywords

algoritmi;podatkovne strukture;priponsko polje;diplomske naloge;

Data

Language: Slovenian
Year of publishing:
Typology: 2.11 - Undergraduate Thesis
Organization: UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher: A. Jeromel
UDC: 004.422.63(043.2)
COBISS: 20080662 Link will open in a new window
Views: 823
Downloads: 87
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Burrows-Wheeler transform construction using suffix array
Secondary abstract: In our thesis, we explored two different approaches to constructing the Burrows-Wheeler transform and compared their execution time. We explained the basic idea and process of the transform and its inverse transform and presented examples of both. We implemented two different algorithms – an improved basic algorithm and an algorithm, which utilises a suffix array. Both approaches were then tested on different files and the results compared. Results show that the improved basic algorithm works better with shorter strings of randomly distributed characters. With all other test strings, however, the suffix array algorithm achieved better results.
Secondary keywords: algorithm;data structure;suffix array;
URN: URN:SI:UM:
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, 21 str.
ID: 9166385