diplomsko delo
Povzetek
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.
Ključne besede
algoritmi;podatkovne strukture;priponsko polje;diplomske naloge;
Podatki
Jezik: |
Slovenski jezik |
Leto izida: |
2016 |
Tipologija: |
2.11 - Diplomsko delo |
Organizacija: |
UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko |
Založnik: |
A. Jeromel |
UDK: |
004.422.63(043.2) |
COBISS: |
20080662
|
Št. ogledov: |
823 |
Št. prenosov: |
87 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Angleški jezik |
Sekundarni naslov: |
Burrows-Wheeler transform construction using suffix array |
Sekundarni povzetek: |
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. |
Sekundarne ključne besede: |
algorithm;data structure;suffix array; |
URN: |
URN:SI:UM: |
Vrsta dela (COBISS): |
Diplomsko delo/naloga |
Komentar na gradivo: |
Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije |
Strani: |
V, 21 str. |
ID: |
9166385 |