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

Povzetek

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.

Ključne besede

algoritmi;predponsko drevo;časovna zahtevnost;prostorska zahtevnost;diplomske naloge;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Založnik: A. Žuran
UDK: 004.922(043.2)
COBISS: 19509782 Povezava se bo odprla v novem oknu
Št. ogledov: 1037
Št. prenosov: 108
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: THE BURROWS-WHEELER TRANSFORM ALGORITHM
Sekundarni povzetek: 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.
Sekundarne ključne besede: algorithm;suffix tree;time complexity;memory complexity;
URN: URN:SI:UM:
Vrsta dela (COBISS): Diplomsko delo
Komentar na gradivo: Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informatika
Strani: 25 f.
ID: 9132835