This paper, published in 2017/2018 by researchers from Hokkaido, Kyushu, and Fujitsu Laboratories, introduces a new data structure for indexing highly repetitive text. It bridges the gap between two powerful concepts in string processing: Compact Directed Acyclic Word Graphs (CDAWGs) and grammar-based compression.
TL;DR
The authors introduce the Linear-size CDAWG (L-CDAWG), a self-indexing data structure that efficiently stores and searches highly repetitive text. By combining CDAWGs with grammar compression (Straight-Line Programs), they achieve optimal pattern matching speeds while keeping the index size proportional to the number of repeats rather than the total text length.
What Problem Does This Paper Address?
In the era of "big data," we often deal with massive datasets that are highly repetitive—think of genomic databases containing thousands of similar individual genomes or version control systems (like Git) storing many versions of the same source code.
Standard text indexes like Suffix Trees or Suffix Arrays are "linear" in the size of the text ($n$), which is far too large for these datasets. While "compressed" indexes exist, many suffer from a trade-off: they either use more space than necessary or they are slow, often taking time proportional to the square of the pattern length ($m^2$) to find a match. The challenge is to create an index that is both tiny (repetition-aware) and fast (linear or near-linear in pattern length $m$).
Methods
The authors propose the L-CDAWG, which builds upon the standard CDAWG. A CDAWG is essentially a "squashed" version of a suffix tree where identical subtrees are merged, making it very efficient for repetitive data.
The key innovations in the L-CDAWG are:
- Type-2 Nodes: Standard CDAWGs can be tricky because their edges represent long substrings of the original text. To avoid storing the original text, the authors introduce "type-2" nodes. These are non-branching nodes added to the graph to break down long edges into manageable pieces.
- SLP Integration: They augment the graph with a Straight-Line Program (SLP)—a type of context-free grammar that generates a single string. This SLP is used to represent the labels on the edges of the graph.
- Jump Links: They adapt a technique from "Linear-size Suffix Tries" (LSTries) called jump links. These links allow the algorithm to "jump" across the graph to quickly reconstruct edge labels or find patterns without needing the original text.
Datasets
This is a theoretical paper focused on algorithmic complexity and data structure design. As such, it does not perform empirical experiments on specific datasets. However, the authors cite biological sequences and versioned text as the primary real-world motivations for their work. They provide rigorous mathematical proofs for the space and time complexities of their structure.
Key Insights and Ideas
- Self-Indexing: The L-CDAWG is a "self-index," meaning it contains enough information to reconstruct any part of the original text without needing the text file itself.
- Repetitiveness Measures: The paper focuses on a measure called $\tilde{e}_T$ (the number of extensions of maximal repeats). This measure is much smaller than the text length $n$ for repetitive data, and the authors prove their index size is proportional to $\tilde{e}_T$.
- Bridging Two Worlds: The most significant "aha moment" is showing that the topological properties of a CDAWG can be used to naturally induce a grammar (SLP) that compresses the edge labels efficiently. This allows for $O(1)$ time sequential access to characters on an edge.
Key Results
The L-CDAWG achieves impressive theoretical bounds:
- Space: $O(\tilde{e}_T \log n)$ bits. For highly repetitive text, this is significantly smaller than the original text.
- Pattern Matching: It can find all $occ$ occurrences of a pattern of length $m$ in $O(m \log \sigma + occ)$ time (where $\sigma$ is the alphabet size).
- Improvement: For constant alphabets, it improves the pattern matching time of previous state-of-the-art structures (like run-length BWT-CDAWGs) by a factor of $\log \log n$.
- Random Access: It supports extracting any substring of length $m$ in $O(m + \log n)$ time.
Limitations and Future Work
- Implementation: The paper is purely theoretical. The authors acknowledge that a practical implementation and empirical evaluation against existing compressed indexes (like the FM-index or LZ-based indexes) is a necessary next step.
- Construction: While they provide an algorithm to build the L-CDAWG, it assumes the standard CDAWG is already constructed.
- Dynamic Data: The current structure is static. An open question is whether an L-CDAWG can be constructed in an "on-line" manner, allowing the index to grow as new data is added.
Summary updated