In this paper we extend to two-dimensional data two recently introduced one-dimensional compressibility measures: the measure gamma defined in terms of the smallest string attractor, and the measure delta 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. Finally, we use the new measures 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].
Compressibility Measures for Two-Dimensional Data
Carfagna L.
;Manzini G.
2023-01-01
Abstract
In this paper we extend to two-dimensional data two recently introduced one-dimensional compressibility measures: the measure gamma defined in terms of the smallest string attractor, and the measure delta 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. Finally, we use the new measures 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].I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
