Auxiliary data structures for improved suffix array query performance

Näytä kaikki kuvailutiedot



Pysyväisosoite

http://urn.fi/URN:NBN:fi:hulib-202012084732
Julkaisun nimi: Auxiliary data structures for improved suffix array query performance
Tekijä: Heino, Lauri
Muu tekijä: Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta
Julkaisija: Helsingin yliopisto
Päiväys: 2020
Kieli: eng
URI: http://urn.fi/URN:NBN:fi:hulib-202012084732
http://hdl.handle.net/10138/322476
Opinnäytteen taso: pro gradu -tutkielmat
Oppiaine: Tietojenkäsittelytiede
Tiivistelmä: The suffix array is a space-efficient data structure that provides fast access to all occurrences of a search pattern in a text. Typically suffix arrays are queried with algorithms based on binary search. With a pre-computed index data structure that provides fast access to the relevant suffix array interval, querying can be sped-up, because the binary search process operates over a smaller interval. In this thesis a number different ways of implementing such an index data structure are studied, and the performance of each implementation is measured. Our experiments show that with relatively small data structures, one can reduce suffix array query times by almost 50%. There is a trade-off between the size of the data structure and the speed-up potential it offers.
Avainsanat: suffix arrays
data structures


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
Heino_Lauri_tutkielma_2020.pdf 560.7KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot