diplomsko delo
Andrej Žuran (Author), Borut Žalik (Mentor)

Abstract

V diplomski nalogi smo obravnavali algoritem Burrows-Wheelerjeve transformacije. Spoznali smo idejo transformacije in njen zgodovinski razvoj. Opisali smo najpogosteje uporabljene algoritme in inverz transformacije. Implementirali smo dva izbrana algoritma BWT. Prvi, tako imenovani izboljšan osnovni algoritem transformacije BWT nadgradi osnovno idejo BWT z izboljšanjem prostorske zahtevnosti. Drugi, algoritem, temelječ na predponskem drevesu, si pri gradnji transformacije pomaga s predponskim drevesom, ki smo ga zgradili z Ukkonenovim algoritmom. Implementirana algoritma smo nato primerjali glede na porabo časa CPU in porabo pomnilniškega prostora.

Keywords

algoritmi;predponsko drevo;časovna zahtevnost;prostorska zahtevnost;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. Žuran
UDC: 004.922(043.2)
COBISS: 19509782 Link will open in a new window
Views: 1037
Downloads: 108
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: THE BURROWS-WHEELER TRANSFORM ALGORITHM
Secondary abstract: In diploma thesis we have considered the Burrows-Wheeler transform (BWT). Firstly, the historical backround and the basic idea of BWT have been discussed. Two algorithms for BWT construction have been implemented. The first one, so-called enhanced base algorithm, extends the basic idea of BWT with improvements in space complexity. The second one, the algorithm based on the suffix trees performs BWT via the suffix tree, which was obtained by Ukkonen’s algorithm. Finally, both implemented algorithms have been compared according to spent CPU time and memory consumption.
Secondary keywords: algorithm;suffix tree;time complexity;memory complexity;
URN: URN:SI:UM:
Type (COBISS): Undergraduate thesis
Thesis comment: Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informatika
Pages: 25 f.
ID: 9132835