The CDAWG Index and Pattern Matching on Grammar-Compressed Strings

The compact directed acyclic word graph (CDAWG) is the minimal compact automaton that recognizes all the suffixes of a string. Classically the CDAWG has been implemented as an index of the string it recognizes, requiring o (n) space for a copy of the string T being indexed, where n=|T|. In this work, we propose using the CDAWG as an index for grammar-compressed strings. While this enables all analyses supported by the CDAWG on any grammar-compressed string, in this work we specifically consider pattern matching. Using the CDAWG index, pattern matching can be performed on any grammar-compressed string in O (ra (m) +occ) time while requiring only O (er (T) ) additional space, where m is the length of the pattern, ra (m) is the grammar random access time, occ is the number of occurrences of the pattern in T, and er (T) is the number of right-extensions of the maximal repeats in T. Our experiments show that even when using a na\"ive random access algorithm, the CDAWG index achieves state of the art run-time performance for pattern matching on grammar-compressed strings. Additionally, we find that all of the grammars computed for our experiments are smaller than the number of right-extensions in the string they produce and, thus, their CDAWGs are within the best known O (er (T) ) space asymptotic bound.