The landscape of compressibility measures for two-dimensional data

Authors Lorenzo Carfagna, Giovanni Manzini

Abstract: In this paper we extend to two-dimensional data two recently introduced one-dimensional compressibility measures: the

g a m m a

measure defined in terms of the smallest string attractor, and the

d e l t a

measure defined in terms of the number of distinct substrings of the input string. Concretely, we introduce the two-dimensional measures

g a m m a_{2 D}

and

d e l t a_{2 D}

as natural generalizations of

g a m m a

and

d e l t a

and study some of their properties. Among other things, we prove that

d e l t a_{2 D}

is monotone and can be computed in linear time, and we show that although it is still true that

d e l t a_{2 D} l e q g a m m a_{2 D}

the gap between the two measures can be

O m e g a (s q r t n)

for families of

n i m e s n

matrices and therefore asymptotically larger than the gap in one-dimension. Finally, we use the measures

g a m m a_{2 D}

and

d e l t a_{2 D}

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].

This page was built for publication: The landscape of compressibility measures for two-dimensional data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6510935)