Linear-size CDAWG: new repetition-aware indexing and grammar compression

In this paper, we propose a novel approach to combine \emph{compact directed acyclic word graphs} (CDAWGs) and grammar-based compression. This leads us to an efficient self-index, called Linear-size CDAWGs (L-CDAWGs), which can be represented with $O({\tilde{e}}_T\log n)$ bits of space allowing for $O(\log n)$-timerandomand$O(1)$-timesequentialaccessestoedgelabels,and$O(m \log \sigma + occ)$-timepatternmatching\mathrm{.}Here,$\tilde e_T$ is the number of all extensions of maximal repeats in $T$, $n$ and $m$ are respectively the lengths of the text $T$ and a given pattern, $\sigma$ is the alphabet size, and $occ$ is the number of occurrences of the pattern in $T$. The repetitiveness measure ${\tilde{e}}_T$ is known to be much smaller than the text length $n$ for highly repetitive text. For constant alphabets, our L-CDAWGs achieve $O(m + occ)$patternmatchingtimewith$O(e_T^r \log n)$ bits of space, which improves the pattern matching time of Belazzougui et al.'s run-length BWT-CDAWGs by a factor of $\log \log n$, with the same space complexity. Here, $e_T^r$ is the number of right extensions of maximal repeats in $T$. As a byproduct, our result gives a way of constructing an SLP of size $O(\tilde e_T)$foragiventext$T$in$O(n + \tilde e_T \log \sigma)$ time.