Output-Sensitive Construction of CDAWGs from BWT-Runs
This work provides a more space-efficient construction of CDAWGs for highly repetitive strings, benefiting applications in string processing and compression.
The paper presents an algorithm to construct the compact directed acyclic word graph (CDAWG) of a string in time O(e_L log n log(n/r)) and space O(r log(n/r) + e_L), where e_L is the number of CDAWG edges and r is the number of BWT-runs, assuming a compressed suffix tree of size O(r log(n/r)) is available.
The compact directed acyclic word graph (CDAWG) of a string can be viewed in two equivalent ways: as the edge-compacted DAWG of the string, and as the DAG obtained from the suffix tree by merging the nodes whose subtrees are isomorphic. By exploiting these two views in opposite directions, we show how to build, for the (reversed) input string of length $n$, the CDAWG with $e_L$ edges in $O(e_L\log n\log(n/r))$ time with $O(r\log(n/r)+e_L)$ words of working space, provided that the fully functional compressed suffix tree of Gagie, Navarro, and Prezza of size $O(r\log(n/r))$ is available. Here, $r$ denotes the number of BWT-runs of the input string.