2 papers
cs.DS2024
The CDAWG Index and Pattern Matching on Grammar-Compressed Strings
Alan M. Cleary, Joseph Winjum, Jordan Dood +1
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 inde…
cs.DS2024
Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings
Alan M. Cleary, Joseph Winjum, Jordan Dood +1
Grammar-based compression is a widely-accepted model of string compression that allows for efficient and direct manipulations on the compressed data. Most, if not all, such manipul…