logo SBA

ETD

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

Tesi etd-07052023-185441


Tipo di tesi
Tesi di laurea magistrale
Autore
CARFAGNA, LORENZO
URN
etd-07052023-185441
Titolo
Compressibility measures for two-dimensional data
Dipartimento
INFORMATICA
Corso di studi
INFORMATICA
Relatori
relatore Prof. Manzini, Giovanni
Parole chiave
  • block tree
  • data compression
  • repetitiveness measures
Data inizio appello
21/07/2023
Consultabilità
Non consultabile
Data di rilascio
21/07/2026
Riassunto
In this thesis we extend to two-dimensional data two recently introduced one-dimensional compressibility measures: the $\gamma$ measure defined in terms of the smallest {string attractor}, and the $\delta$ measure defined in terms of the number of distinct substrings of the input string. Concretely, we introduce the two-dimensional measures $\gamma_{2D}$ and $\delta_{2D}$ as natural generalizations of $\gamma$ and $\delta$ and study some of their properties. Among other things, we prove that $\delta_{2D}$ is monotone and can be computed in {linear time}, and we show that although it is still true that $\delta_{2D} \leq \gamma_{2D}$ the gap between the two measures can be $\Omega(\sqrt{n})$ for families of $n\times n$ matrices and therefore asymptotically larger than the gap in one-dimension. As an application of the measures $\gamma_{2D}$ and $\delta_{2D}$ we provide the first analysis of the space usage of the two-dimensional block tree introduced in [Brisaboa {\em et al.}, Two-dimensional block trees, {\em The computer Journal}, 2023]. Finally we present a linear time algorithm for constructing the two-dimensional block tree for arbitrary matrices, that is asymptotically faster than the (probabilistic) known solution which can only be used for binary matrices.
File