Papers › The CDAWG Index and Pattern Matching on Grammar-Compressed Strings
The CDAWG Index and Pattern Matching on Grammar-Compressed Strings
Alan M. Cleary, Joseph Winjum, Jordan Dood, Shunsuke Inenaga
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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 𝒪(ra(m)+occ) time while requiring only 𝒪(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 𝒪(er(T)) space asymptotic bound.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections