Linear-size CDAWG: new repetition-aware indexing and grammar compression

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

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.

Evolution from Suffix Trie to CDAWG via path compaction and minimization.

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.

Comparison between LSTrie and the proposed L-CDAWG + SLP structure, including the associated grammar rules.

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

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},
}
Figure