Generalization of Repetitiveness Measures for Two-Dimensional Strings

Abstract The problem of detecting and measuring the repetitiveness of one-dimensional strings has been extensively studied in data compression and text indexing. Our understanding of these issues has been significantly improved by the introduction of the notion of string attractor (Kempa and Prezza 2018) and by the results showing the relationship between attractors and other measures of compressibility. When the input data are structured in a non-linear way, as in two-dimensional strings, inherent redundancy often offers an even richer source for compression. However, systematic studies on repetitiveness measures for two-dimensional strings are still scarce. In this paper, we extend to two or more dimensions the main measures of complexity introduced for one-dimensional strings. We distinguish between the measures $$\delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>δ</mml:mi> </mml:math> and $$\gamma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>γ</mml:mi> </mml:math> , defined in terms of the substrings of the input, and the measures g , $$g_{rl}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>g</mml:mi> <mml:mrow> <mml:mi>rl</mml:mi> </mml:mrow> </mml:msub> </mml:math> , and b , which are based on copy-paste mechanisms. We study the properties and mutual relationships between these two classes and we show that the two classes become incomparable for d -dimensional inputs as soon as $$d\geqslant 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>⩾</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> . Moreover, we show that our grammar-based representation of a d -dimensional string of size N enables direct access to any symbol in $$O(\log N)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> time. We also compare our measures for two-dimensional strings with the 2D Block Tree data structure (Brisaboa et al., Comput. J. 67 (1), 391–406, 2024) and provide some insights for the design of future effective two-dimensional compressors. A preliminary version of this paper appeared in the proceedings of the conference SPIRE 2024.