Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression

Takuya Takagi, Keisuke Goto, Yuta Fujishige, Shunsuke Inenaga, Hiroki Arimura

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:

  1. 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.
  2. 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.
  3. 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

Abstract

In this paper, we propose a novel approach to combine \emph{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$. The repetitiveness measure $\tilde e_T$ is known to be much smaller than the text length $n$ for highly repetitive text. For constant alphabets, our L-CDAWGs achieve $O(m + occ)$ pattern matching time with $O(e_T^r \log n)$ bits of space, which improves the pattern matching time of Belazzougui et al.'s run-length BWT-CDAWGs by a factor of $\log \log n$, with the same space complexity. Here, $e_T^r$ is the number of right extensions of maximal repeats in $T$. As a byproduct, our result gives a way of constructing an SLP of size $O(\tilde e_T)$ for a given text $T$ in $O(n + \tilde e_T \log \sigma)$ time.
BibTeX
@inproceedings{takagi2017linear,
  author = {Takuya Takagi and Keisuke Goto and Yuta Fujishige and Shunsuke Inenaga and Hiroki Arimura},
  title = {{Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression}},
  booktitle = {SPIRE},
  year = {2017},
  doi = {10.1007/978-3-319-67428-5\_26},
}

Loading related content...

Figure