Compressibility Measures for Two-Dimensional Data

Abstract

In this paper 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}\le {\gamma }_{2D}$ the gap between the two measures can be $\mathrm{\Omega }(\sqrt{n})$ for families of $n\times n$ matrices and therefore asymptotically larger than the gap in one-dimension. Finally, we use the measures ${\gamma }_{2D}$ and ${\delta }_{2D}$ to provide the first analysis of the space usage of the two-dimensional block tree introduced in [Brisaboa et al., Two-dimensional block trees, The computer Journal, 2023].