The landscape of compressibility measures for two-dimensional data
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910451795755008 |
|---|---|
| author | Carfagna, Lorenzo Manzini, Giovanni |
| author_facet | Carfagna, Lorenzo Manzini, Giovanni |
| contents | In this paper we extend to two-dimensional data two recently introduced one-dimensional compressibility measures: the $γ$ measure defined in terms of the smallest string attractor, and the $δ$ measure defined in terms of the number of distinct substrings of the input string. Concretely, we introduce the two-dimensional measures $γ_{2D}$ and $δ_{2D}$, as natural generalizations of $γ$ and $δ$, and we initiate the study of their properties. Among other things, we prove that $δ_{2D}$ is monotone and can be computed in linear time, and we show that, although it is still true that $δ_{2D} \leq γ_{2D}$, the gap between the two measures can be $Ω(\sqrt{n})$ and therefore asymptotically larger than the gap between $γ$ and $δ$. To complete the scenario of two-dimensional compressibility measures, we introduce the measure $b_{2D}$ which generalizes to two dimensions the notion of optimal parsing. We prove that, somewhat surprisingly, the relationship between $b_{2D}$ and $γ_{2D}$ is significantly different than in the one-dimensional case. As an application of our results we 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, 2024]. Our analysis shows that the space usage can be bounded in terms of both $γ_{2D}$ and $δ_{2D}$. Finally, using insights from our analysis, we design the first linear time and space algorithm for constructing the two-dimensional block tree for arbitrary matrices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_02629 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The landscape of compressibility measures for two-dimensional data Carfagna, Lorenzo Manzini, Giovanni Data Structures and Algorithms Combinatorics In this paper we extend to two-dimensional data two recently introduced one-dimensional compressibility measures: the $γ$ measure defined in terms of the smallest string attractor, and the $δ$ measure defined in terms of the number of distinct substrings of the input string. Concretely, we introduce the two-dimensional measures $γ_{2D}$ and $δ_{2D}$, as natural generalizations of $γ$ and $δ$, and we initiate the study of their properties. Among other things, we prove that $δ_{2D}$ is monotone and can be computed in linear time, and we show that, although it is still true that $δ_{2D} \leq γ_{2D}$, the gap between the two measures can be $Ω(\sqrt{n})$ and therefore asymptotically larger than the gap between $γ$ and $δ$. To complete the scenario of two-dimensional compressibility measures, we introduce the measure $b_{2D}$ which generalizes to two dimensions the notion of optimal parsing. We prove that, somewhat surprisingly, the relationship between $b_{2D}$ and $γ_{2D}$ is significantly different than in the one-dimensional case. As an application of our results we 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, 2024]. Our analysis shows that the space usage can be bounded in terms of both $γ_{2D}$ and $δ_{2D}$. Finally, using insights from our analysis, we design the first linear time and space algorithm for constructing the two-dimensional block tree for arbitrary matrices. |
| title | The landscape of compressibility measures for two-dimensional data |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2307.02629 |