Abstract
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 e_T \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 \sigma + occ)$-time pattern matching. Here, $\tilde e_T$ 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, $\sigma$ is the alphabet size, and $occ$ is the number of occurrences of the pattern in $T$. For constant alphabets, our L-CDAWGs achieve $O(m + occ)$ pattern matching time with $O(e_T^r \log n)$ bits of space, improving upon previous run-length BWT-CDAWGs.
Introduction
In the era of "big data," massive datasets are often highly repetitive, such as genomic databases or version control systems. Standard text indexes like Suffix Trees or Suffix Arrays are linear in the text size ($n$), which becomes prohibitive for such data. While compressed indexes exist, they often face a trade-off between space efficiency and search speed. This paper introduces the Linear-size CDAWG (L-CDAWG), a self-indexing structure that bridges the gap between Compact Directed Acyclic Word Graphs (CDAWGs) and grammar-based compression (Straight-Line Programs).
Methodology
The L-CDAWG builds upon the standard CDAWG, which is a minimized version of a suffix tree where identical subtrees are merged. This process significantly reduces the number of nodes for repetitive strings.
The authors introduce several key innovations to make the CDAWG "linear-size" relative to repetitiveness measures rather than text length. Standard CDAWGs can be difficult to store because their edges represent long substrings. To solve this, the authors introduce Type-2 Nodes, which are non-branching nodes added to break down long edges into manageable pieces without increasing the overall complexity.
Furthermore, the graph is augmented with a Straight-Line Program (SLP)—a context-free grammar that generates a single string. This SLP is used to represent the labels on the edges of the graph efficiently. By combining this with Jump Links (a technique adapted from Linear-size Suffix Tries), the algorithm can "jump" across the graph to quickly reconstruct edge labels or find patterns without needing the original text. This makes the L-CDAWG a true self-index.
Key Results
The L-CDAWG achieves significant theoretical improvements for indexing highly repetitive text:
- Space Complexity: $O(\tilde{e}_T \log n)$ bits, where $\tilde{e}_T$ is the number of extensions of maximal repeats. This measure is typically much smaller than the text length $n$ in repetitive datasets.
- Pattern Matching: It can find all $occ$ occurrences of a pattern of length $m$ in $O(m \log \sigma + occ)$ time. For constant alphabets, this improves the pattern matching time of previous state-of-the-art structures by a factor of $\log \log n$.
- Self-Indexing: The structure supports extracting any substring of length $m$ in $O(m + \log n)$ time, meaning it contains enough information to reconstruct the original text.
Conclusion
The L-CDAWG represents a theoretical breakthrough in repetition-aware indexing. By showing that CDAWG topological properties can naturally induce an efficient grammar for edge labels, the authors provide a tiny yet fast index. While the paper is primarily theoretical, it sets the stage for future practical implementations and empirical evaluations against existing compressed indexes like the FM-index or LZ-based structures.
Summary updated