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

arXiv: https://arxiv.org/abs/1705.09779 · HTML: https://mlsanity.com/paper/1705.09779/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2017.

## Built on by (most cited first, 1 of 1)

- [Evaluating n-Gram Novelty of Language Models Using Rusty-DAWG](https://mlsanity.com/paper/2406.13069/) (2024)

## Abstract (arXiv)

In this paper, we propose a novel approach to combine 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 eT log n) bits of space allowing for O(log n)-time random and O(1)-time sequential accesses to edge labels, and O(m log σ + occ)-time pattern matching. Here, tilde eT 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, σ is the alphabet size, and occ is the number of occurrences of the pattern in T. The repetitiveness measure tilde eT 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) pattern matching time with O(eTr 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, eTr 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 eT) for a given text T in O(n + tilde eT log σ) time.