Relating Left and Right Extensions of Maximal Repeats
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910658189066240 |
|---|---|
| author | Inenaga, Shunsuke Kosolobov, Dmitry |
| author_facet | Inenaga, Shunsuke Kosolobov, Dmitry |
| contents | The compact directed acyclic word graph (CDAWG) of a string $T$ is an index occupying $O(\mathsf{e})$ space, where $\mathsf{e}$ is the number of right extensions of maximal repeats in $T$. For highly repetitive datasets, the measure $\mathsf{e}$ typically is small compared to the length $n$ of $T$ and, thus, the CDAWG serves as a compressed index. Unlike other compressibility measures (as LZ77, string attractors, BWT runs, etc.), $\mathsf{e}$ is very unstable with respect to reversals: the CDAWG of the reversed string $\overset{{}_{\leftarrow}}{T} = T[n] \cdots T[2] T[1]$ has size $O(\overset{{}_{\leftarrow}}{\mathsf{e}})$, where $\overset{{}_{\leftarrow}}{\mathsf{e}}$ is the number of left extensions of maximal repeats in $T$, and there are strings $T$ with $\frac{\overset{{}_{\leftarrow}}{\mathsf{e}}}{\mathsf{e}} \in Ω(\sqrt{n})$. In this note, we prove that this lower bound is tight: $\frac{\overset{{}_{\leftarrow}}{\mathsf{e}}}{\mathsf{e}} \in O(\sqrt{n})$. Furthermore, given the alphabet size $σ$, we establish the alphabet-dependent bound $\frac{\overset{{}_{\leftarrow}}{\mathsf{e}}}{\mathsf{e}} \le \min\{\frac{2n}σ, σ\}$ and we show that it is asymptotically tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_15958 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Relating Left and Right Extensions of Maximal Repeats Inenaga, Shunsuke Kosolobov, Dmitry Data Structures and Algorithms The compact directed acyclic word graph (CDAWG) of a string $T$ is an index occupying $O(\mathsf{e})$ space, where $\mathsf{e}$ is the number of right extensions of maximal repeats in $T$. For highly repetitive datasets, the measure $\mathsf{e}$ typically is small compared to the length $n$ of $T$ and, thus, the CDAWG serves as a compressed index. Unlike other compressibility measures (as LZ77, string attractors, BWT runs, etc.), $\mathsf{e}$ is very unstable with respect to reversals: the CDAWG of the reversed string $\overset{{}_{\leftarrow}}{T} = T[n] \cdots T[2] T[1]$ has size $O(\overset{{}_{\leftarrow}}{\mathsf{e}})$, where $\overset{{}_{\leftarrow}}{\mathsf{e}}$ is the number of left extensions of maximal repeats in $T$, and there are strings $T$ with $\frac{\overset{{}_{\leftarrow}}{\mathsf{e}}}{\mathsf{e}} \in Ω(\sqrt{n})$. In this note, we prove that this lower bound is tight: $\frac{\overset{{}_{\leftarrow}}{\mathsf{e}}}{\mathsf{e}} \in O(\sqrt{n})$. Furthermore, given the alphabet size $σ$, we establish the alphabet-dependent bound $\frac{\overset{{}_{\leftarrow}}{\mathsf{e}}}{\mathsf{e}} \le \min\{\frac{2n}σ, σ\}$ and we show that it is asymptotically tight. |
| title | Relating Left and Right Extensions of Maximal Repeats |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.15958 |