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 <CitationRef CitationID="CR1">2018</CitationRef>) 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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\delta $</EquationSource> <EquationSource Format="MATHML"><math> <mi>δ</mi> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\gamma $</EquationSource> <EquationSource Format="MATHML"><math> <mi>γ</mi> </math></EquationSource> </InlineEquation>, defined in terms of the substrings of the input, and the measures g, <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$g_{rl}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>g</mi> <mrow> <mi mathvariant="italic">rl</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$d\geqslant 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>⩾</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>. Moreover, we show that our grammar-based representation of a d-dimensional string of size N enables direct access to any symbol in <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$O(\log N)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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, <CitationRef CitationID="CR6">2024</CitationRef>) 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.

Generalization of Repetitiveness Measures for Two-Dimensional Strings

期刊论文
出版模式：

开放获取
发表日期：

2026年1月3日

查看全文

Lorenzo Carfagna,
Giovanni Manzini,
Giuseppe Romana,
Marinella Sciortino,
Cristian Urbina

摘要

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 $ $δ$ and $\gamma $ $γ$ , defined in terms of the substrings of the input, and the measures g, $g_{rl}$ $g_{rl}$ , 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$ $d ⩾ 2$ . 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)$ $O (log N)$ 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.