logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-01212023-182457


Tipo di tesi
Tesi di laurea magistrale
Autore
CEREGINI, MATTEO
URN
etd-01212023-182457
Titolo
Faster Wavelet Trees with Quad Vectors
Dipartimento
INFORMATICA
Corso di studi
INFORMATICA
Relatori
relatore Prof. Venturini, Rossano
Parole chiave
  • bit vectors
  • quad vectors
  • Wavelet matrices
  • Wavelet trees
Data inizio appello
24/02/2023
Consultabilità
Non consultabile
Data di rilascio
24/02/2063
Riassunto
Given a text, rank and select queries return the number of occurrences of a character up to a position (rank) or the position of a character with a given rank (select). These queries find application in compression, computational geometry, pattern matching, and are the basic building blocks of compressed full-text indexes. A Wavelet tree is a compact data structure that, for a text of length 'n' over an alphabet of size 'sigma', can answer rank and select queries in O(log 'sigma') time.
In this thesis, we show how to improve the latency of queries in Wavelet trees by using a 4-ary tree instead of a binary tree as the layout of the Wavelet tree. To this end, we present a space-efficient rank and select data structure for quad vectors.Query latency is an important measure when queries depend on others.
File