Symmetric Compact Directed Acyclic Word Graph (SCDAWG)

This documentation provides a comprehensive, pedagogical treatment of the Symmetric Compact DAWG (SCDAWG), a data structure that enables $O(\lvert \text{pattern}\rvert )$ substring searching with bidirectional navigation capabilities.

Overview

The SCDAWG, also known as C2S (Compact Symmetric), is the most space-efficient index structure that supports:

1. Substring search in $O(\lvert \text{pattern}\rvert )$ time
2. Right extension: given a pattern V, navigate to V followed by character $\sigma$
3. Left extension: given a pattern V, navigate to character $\sigma$ followed by V
4. Occurrence enumeration: find all positions where a pattern occurs

These capabilities make the SCDAWG ideal for applications like the WallBreaker algorithm (Gerdjikov et al. 2013; see 07-references), which requires bidirectional pattern growth during dictionary-based fuzzy string matching.

Document Structure

This documentation builds concepts progressively from fundamental to advanced:

Document	Topic
01-introduction	Problem motivation: why we need substring indices
02-suffix-automaton	Foundation: equivalence classes, suffix links, end-positions
03-cdawg	Compact DAWG: compaction and primary/secondary edges
04-scdawg	Symmetric Compact DAWG: left extensions and prime subwords
05-construction	On-line construction algorithm with sext links
06-operations	Substring search, bidirectional extension, IS features
07-references	Annotated bibliography of source papers

Running Example

Throughout this documentation, we use the string w = "abcabcab" as a running example. This string is traced through each data structure:

String: a b c a b c a b
Index:  0 1 2 3 4 5 6 7

Key properties of this example:

• Length $\lvert w\rvert = 8$
• Alphabet $\Sigma = {a, b, c}$
• Contains repeated patterns: "ab" (3$\times$), "abc" (2$\times$), "bc" (2$\times$), "cab" (2$\times$)
• No unique end marker in raw form (added during construction)

Complexity Summary

Structure	States	Transitions	Space	Query Time
Suffix Trie	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(m)$
Suffix Tree	$O(n)$	$O(n)$	$O(n)$	$O(m)$
Suffix Automaton (DAWG)	$\le 2n - 1$	$\le 3n - 4$	$O(n)$	$O(m)$
CDAWG	$\le n + 1$	$\le 2n - 2$	$O(n)$	$O(m)$
SCDAWG	$\le n + 1$	$\le 4n - 4$	$O(n)$	$O(m)$

Where $n = \lvert w\rvert$ (text length) and $m = \lvert \text{pattern}\rvert$ (query length).

Key Concepts at a Glance

Equivalence Classes

Strings belong to the same equivalence class if they share the same end-position set (endpos) — the set of positions at which the factor ends in w:

end-pos("ab") = {2, 5, 8}  (positions after "ab")
end-pos("cab") = {5, 8}    (positions after "cab")

Since "ab" and "cab" have different end-positions, they are in different classes.

Suffix Links

A suffix link connects each state to its longest proper suffix that forms a distinct equivalence class (one endpos-level up):

\text{abc} \xrightarrow{\text{slink}} \text{bc} \xrightarrow{\text{slink}} \text{c}

Left Extension Edges (SCDAWG-specific)

While right extension edges (standard edges) navigate by appending characters:

\text{ab} \xrightarrow{c} \text{abc} \quad (\text{append } c \text{ to } \text{ab})

Left extension edges navigate by prepending characters:

\text{ab} \xrightarrow{c} \text{cab} \quad (\text{prepend } c \text{ to } \text{ab})

This bidirectional capability is what makes the SCDAWG "symmetric."

Prime Subwords

A prime subword is a maximal representative of an equivalence class:

If every occurrence of "ab" is preceded by 'c' and followed by 'c',
then "cabcc" is the implication (prime subword) of "ab".

The SCDAWG contains only prime subwords as nodes, making it maximally compact.

Prerequisites

This documentation assumes familiarity with:

• Basic automata theory (states, transitions, acceptance)
• Graph terminology (nodes, edges, DAG)
• Asymptotic complexity notation (O-notation)

No prior knowledge of suffix structures is required.

References

The key papers that define and construct the SCDAWG are:

1. Blumer et al. (1987) — "Complete Inverted Files for Efficient Text Retrieval and Analysis." DOI: 10.1145/28869.28873

   • Defines the SCDAWG structure (C2S)
   • Introduces IS (Inverted File) features: freq(), locations()

2. Inenaga et al. (2001) — "On-Line Construction of Symmetric Compact Directed Acyclic Word Graphs." DOI: 10.1109/SPIRE.2001.989743

   • On-line $O(n)$ construction algorithm
   • Key insight: sext links = edges of CDAWG(wʳᵉᵛ)

3. Inenaga et al. (2005) — "On-line construction of compact directed acyclic word graphs." DOI: 10.1016/j.dam.2004.04.012

   • On-line $O(n)$ CDAWG construction
   • Multi-string support with unique end markers

See 07-references for the complete annotated bibliography.