Relating Left and Right Extensions of Maximal Repeats

Abstract

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 $\overleftarrow{T}=T[n]\cdots T[2]T[1]$ has size $O(\overleftarrow{\mathsf{e}})$, where $\overleftarrow{\mathsf{e}}$ is the number of left extensions of maximal repeats in $T$, and there are strings $T$ with $\frac{\overleftarrow{\mathsf{e}}}{\mathsf{e}}\in \Omega (\sqrt{n})$. In this note, we prove that this lower bound is tight: $\frac{\overleftarrow{\mathsf{e}}}{\mathsf{e}}\in O(\sqrt{n})$. Furthermore, given the alphabet size $\sigma$, we establish the alphabet-dependent bound $\frac{\overleftarrow{\mathsf{e}}}{\mathsf{e}}\le \min \{\frac{2n}{\sigma },\sigma \}$ and we show that it is asymptotically tight.

4 pages