20.500.12556/DKUM-57934 ALGORITEM BURROWS-WHEELERJEVE TRANSFORMACIJE THE BURROWS-WHEELER TRANSFORM ALGORITHM 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. 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. algoritmi predponsko drevo časovna zahtevnost prostorska zahtevnost algorithms suffix tree time complexity memory complexity true true false A. Žuran Slovenski jezik Angleški jezik Diplomsko delo 2016-03-30 06:43:45 2016-04-13 14:25:15 2022-06-15 03:09:43 2019-07-11 10:23:01 2016 0 [Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.922(043.2) 19509782 URN:SI:UM:DK:LKP1UUMP VS_Zuran_Andrej_2016.pdf VS_Zuran_Andrej_2016.pdf 1 00294986C217FB31ED981F7A1BE28569 6c01bfbc156908363f257ced0c8ef4b6dfbb212ede5cc515b44b2a4a320abbb5 03cbb496-7c0c-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=87797 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0