Navigation: ← Dictionary Layer | DoubleArrayTrie | Algorithms Home
SuffixAutomaton is a specialized dictionary for substring matching (finding patterns anywhere in text), unlike traditional tries which only match prefixes. It's the go-to choice for full-text search, code search, and document indexing where patterns can appear at any position.
\le 2n-1$ states for $n$ characters\mathcal{O}(n)$ online construction✅ Use SuffixAutomaton when:
⚠️ Use standard dictionaries when:
DoubleArrayTrie (3x faster)DoubleArrayTrie or DynamicDawgA suffix automaton is a minimal deterministic finite automaton (DFA) that recognizes all suffixes of indexed text.
Example: Text "banana"
Suffixes:
Key Property: Any path from root = some substring of the text
Traditional Trie (prefix matching):
Dictionary: ["test", "testing", "tested"]
Trie structure:
(root)
|
t
|
e
|
s
|
t (final "test")
/ \
i e
| |
n d (final "tested")
|
g (final "testing")
Query "tes": ✅ Prefix match
Query "test": ✅ Complete match
Query "est": ❌ Not a prefix
Query "sting": ❌ Not a prefix
Suffix Automaton (substring matching):
Text: "testing"
Suffix Automaton recognizes ALL substrings:
"t", "te", "tes", "test", "testi", "testin", "testing"
"e", "es", "est", "esti", "estin", "esting"
"s", "st", "sti", "stin", "sting"
"t", "ti", "tin", "ting"
"i", "in", "ing"
"n", "ng"
"g"
Query "test": ✅ Substring match
Query "sting": ✅ Substring match
Query "tin": ✅ Substring match
Query "xyz": ❌ Not in text
States group substrings by their ending positions (endpos):
Text: "banana" (positions 0-5)
Substrings ending at position 5 (all suffixes):
"banana" (0-5)
"anana" (1-5)
"nana" (2-5)
"ana" (3-5)
"na" (4-5)
"a" (5-5)
States in suffix automaton ≈ equivalence classes of endpos sets
Minimality: This grouping ensures $\le 2n-1$ states for $n$ characters.
Each state has a suffix link pointing to the longest proper suffix in a different endpos class:
State representing "ana" → suffix link → state representing "na"
State representing "banana" → suffix link → state representing "anana"
Suffix links form a tree structure used during construction and navigation.
| Scenario | Prefix Dictionary | SuffixAutomaton |
|---|---|---|
| Autocomplete | ✅ "test" → "testing" | ⚠️ Overkill |
| Spell checking | ✅ Check whole words | ⚠️ Overkill |
| Code search | ❌ Misses "recalculate" | ✅ Finds "calculate" |
| Log search | ❌ Misses "ERROR_123" mid-line | ✅ Finds "ERROR_123" |
| Document search | ❌ Only finds start of words | ✅ Finds anywhere |
| DNA/protein search | ❌ Only finds prefixes | ✅ Finds patterns anywhere |
Problem: Find all occurrences of "calculate" in source code
let code = r#"
fn recalculate_total(items: &[Item]) -> f64 {
items.iter().map(|i| i.price * calculate_tax(i)).sum()
}
fn calculate_tax(item: &Item) -> f64 {
item.tax_rate * item.price
}
"#;
With Prefix Dictionary (DoubleArrayTrie):
let dict = DoubleArrayTrie::from_terms(vec!["calculate", "recalculate"]);
// Query "calculate"
assert!(dict.contains("calculate")); // ✅
// But won't find "calculate" inside "recalculate"!
With SuffixAutomaton:
let dict = SuffixAutomaton::from_text(code);
// Query "calculate"
// Finds BOTH occurrences:
// 1. Inside "recalculate" at position X
// 2. In "calculate_tax" at position Y
let positions = dict.match_positions("calculate");
println!("Found at positions: {:?}", positions);
// Output: [(0, X), (0, Y)] // (doc_id, position)
pub struct SuffixAutomaton {
// Lock-free: the whole automaton lives behind one atomic pointer.
// (Shipped as the `LockFreeSuffixAutomaton<u8, V>` newtype, which wraps
// `Arc<ArcSwap<SuffixAutomatonInner>>`.)
inner: Arc<ArcSwap<SuffixAutomatonInner>>,
}
struct SuffixAutomatonInner {
nodes: Vec<SuffixNode>, // State storage
last_state: usize, // Current state during construction
text_count: usize, // Number of indexed texts
needs_compaction: bool, // Deletion flag
}
struct SuffixNode {
edges: Vec<(u8, usize)>, // Label → child state
suffix_link: Option<usize>, // Longest proper suffix link
max_length: usize, // Longest string in this class
is_final: bool, // End-of-string marker
ref_count: usize, // For garbage collection
}
┌─────────────────┬─────────────┬────────────────┐
│ Component │ Size │ Per State │
├─────────────────┼─────────────┼────────────────┤
│ edges (Vec) │ ~24 bytes │ ~24 bytes │
│ suffix_link │ 16 bytes │ 16 bytes │
│ max_length │ 8 bytes │ 8 bytes │
│ is_final │ 1 byte │ 1 byte │
│ ref_count │ 8 bytes │ 8 bytes │
├─────────────────┼─────────────┼────────────────┤
│ Total per state │ ~57 bytes │ ~57 bytes │
└─────────────────┴─────────────┴────────────────┘
For text of n characters:
\le 2n-1$ (typically $\approx 1.5n$)Example: 10,000-character document $\approx$ 850 KB
Suffix automaton is built character by character:
fn extend(&mut self, byte: u8) {
let new_state = self.nodes.len();
self.nodes.push(SuffixNode {
edges: Vec::new(),
suffix_link: None,
max_length: self.nodes[self.last_state].max_length + 1,
is_final: false,
ref_count: 0,
});
// Add edge from previous states
let mut current = self.last_state;
while let Some(curr) = current {
if self.nodes[curr].has_edge(byte) {
break;
}
self.nodes[curr].add_edge(byte, new_state);
current = self.nodes[curr].suffix_link;
}
// Set suffix link for new state
if current.is_none() {
// All states now have edge to new_state
self.nodes[new_state].suffix_link = Some(0); // Root
} else {
let curr = current.unwrap();
let target = self.nodes[curr].get_edge(byte).unwrap();
if self.nodes[target].max_length == self.nodes[curr].max_length + 1 {
// No split needed
self.nodes[new_state].suffix_link = Some(target);
} else {
// Split state (complex case)
let clone = self.clone_state(target);
self.nodes[new_state].suffix_link = Some(clone);
self.nodes[target].suffix_link = Some(clone);
// Redirect edges
self.redirect_edges(curr, byte, clone);
}
}
self.last_state = new_state;
}
Complexity: $\mathcal{O}(1)$ amortized per character
Build generalized suffix automaton:
fn from_texts<I, S>(texts: I) -> Self
where
I: IntoIterator<Item = S>,
S: AsRef<str>,
{
let mut automaton = SuffixAutomaton::new();
for text in texts {
automaton.insert(text.as_ref());
}
automaton
}
fn insert(&self, text: &str) {
// Lock-free: mutate a clone of the current snapshot, then publish it with
// an atomic swap (the shipped code retries the publish with compare-and-swap).
let mut next = (**self.inner.load()).clone();
// Reset to root for new text
next.last_state = 0;
// Extend with each character
for byte in text.bytes() {
next.extend(byte);
}
// Mark final states
let mut state = next.last_state;
while let Some(s) = state {
next.nodes[s].is_final = true;
state = next.nodes[s].suffix_link;
}
next.text_count += 1;
self.inner.store(Arc::new(next));
}
use libdictenstein::suffix_automaton::SuffixAutomaton;
let text = "the quick brown fox jumps over the lazy dog";
let dict = SuffixAutomaton::from_text(text);
// Find substrings
assert!(dict.contains("quick")); // ✅ Found
assert!(dict.contains("brown fox")); // ✅ Found
assert!(dict.contains("fox jumps")); // ✅ Found
assert!(dict.contains("lazy")); // ✅ Found
assert!(!dict.contains("fast")); // ❌ Not in text
use libdictenstein::suffix_automaton::SuffixAutomaton;
use liblevenshtein::levenshtein::Algorithm;
use liblevenshtein::levenshtein_automaton::LevenshteinAutomaton;
let code = r#"
fn calculate_total(items: &[Item]) -> f64 {
items.iter().map(|i| i.price).sum()
}
fn recalculate() {
let total = calculate_total(&items);
}
"#;
let dict = SuffixAutomaton::from_text(code);
// Fuzzy search for "calculate" with typos
let automaton = LevenshteinAutomaton::new("calculat", 1, Algorithm::Standard);
let results: Vec<String> = automaton.query(&dict).collect();
println!("{:?}", results);
// Finds: "calculate" (appears in both functions)
use libdictenstein::suffix_automaton::SuffixAutomaton;
let documents = vec![
"Levenshtein automata for approximate matching",
"Suffix trees and suffix arrays for pattern search",
"Double array tries for efficient dictionaries",
];
let dict = SuffixAutomaton::from_texts(documents);
// Search across all documents
assert!(dict.contains("automata")); // Doc 0
assert!(dict.contains("suffix")); // Doc 1
assert!(dict.contains("array")); // Doc 2
assert!(dict.contains("for")); // All docs (common word)
use libdictenstein::suffix_automaton::SuffixAutomaton;
let text = "banana";
let dict = SuffixAutomaton::from_text(text);
// Find where "ana" appears
let positions = dict.match_positions("ana");
println!("'ana' appears at positions: {:?}", positions);
// Output: [(0, 1), (0, 3)]
// ↑ ↑
// Doc 0, Doc 0,
// pos 1 pos 3
// b[ana]na ban[ana]
use libdictenstein::suffix_automaton::SuffixAutomaton;
let dict = SuffixAutomaton::new();
// Add texts dynamically
dict.insert("testing the suffix automaton");
dict.insert("another test string");
assert!(dict.contains("test"));
assert!(dict.contains("suffix"));
// Remove text
dict.remove("another test string");
// Compact to reclaim space
if dict.needs_compaction() {
dict.compact();
}
use libdictenstein::suffix_automaton::SuffixAutomaton;
use liblevenshtein::levenshtein::Algorithm;
use liblevenshtein::levenshtein_automaton::LevenshteinAutomaton;
let logs = vec![
"[2024-01-01] INFO: Server started",
"[2024-01-01] ERROR_CODE_123: Connection failed",
"[2024-01-01] WARN: High memory usage",
"[2024-01-01] ERROR_CODE_456: Timeout",
];
let dict = SuffixAutomaton::from_texts(logs);
// Find all error codes
let automaton = LevenshteinAutomaton::new("ERROR_CODE", 0, Algorithm::Standard);
let results: Vec<String> = automaton.query(&dict).collect();
println!("Error codes found: {:?}", results);
// Finds: "ERROR_CODE_123", "ERROR_CODE_456"
use libdictenstein::suffix_automaton::SuffixAutomaton;
let dna_sequence = "ATCGATCGATCGATCGTAGCTAGCTAGCT";
let dict = SuffixAutomaton::from_text(dna_sequence);
// Find motif
assert!(dict.contains("ATCG"));
assert!(dict.contains("TAGC"));
// Find with mismatches (fuzzy)
let automaton = LevenshteinAutomaton::new("ATCG", 1, Algorithm::Standard);
let results: Vec<String> = automaton.query(&dict).collect();
println!("Motifs (distance ≤1): {:?}", results);
// Finds patterns similar to "ATCG"
use libdictenstein::suffix_automaton::SuffixAutomaton;
let dict = SuffixAutomaton::new();
// Build index incrementally as data arrives
for line in read_stream() {
dict.insert(&line);
// Query immediately available
if dict.contains("ERROR") {
alert("Error detected!");
}
}
// Periodic maintenance
if dict.text_count() > 1000 && dict.needs_compaction() {
dict.compact();
}
| Operation | Complexity | Notes |
|---|---|---|
| Construction | $\mathcal{O}(n)$ | n = text length |
| Insert character | $\mathcal{O}(1)$ amortized | Online construction |
| Contains (exact) | $\mathcal{O}(m)$ | m = query length |
| Fuzzy search | $\mathcal{O}(m \times d^{2} \times b)$ | d = distance, b = branching |
| Compact | $\mathcal{O}(s)$ | s = number of states |
Index 10,000-character text:
SuffixAutomaton: ~8ms
DoubleArrayTrie: ~3ms (but only prefixes)
Index 100,000-character text:
SuffixAutomaton: ~85ms
Exact substring search (10K-char text):
Query "test": ~450ns
Query "algorithm": ~680ns
Fuzzy substring search (distance 2):
Query "test": ~38µs
Query "algorithm": ~91µs
Text size: 10,000 characters
States: ~15,000 (1.5× text length)
Memory: ~850 KB
Text size: 100,000 characters
States: ~150,000
Memory: ~8.5 MB
Task: Index 10,000 words (avg 8 chars = 80K chars total)
Construction Memory Contains Fuzzy (d=2)
────────────────────────────────────────────────────────────────────────
DoubleArrayTrie 3.2ms 800 KB 6.6µs 16.3µs
SuffixAutomaton 68ms 6.8 MB 450ns 82µs
Substring matching? ❌ ✅ ❌ ✅
Trade-off: SuffixAutomaton uses more memory and construction time, but enables substring matching not possible with prefix dictionaries.
| Use Case | Recommended | Reason |
|---|---|---|
| Full-text search | ✅ SuffixAutomaton | Need substring matching |
| Code search | ✅ SuffixAutomaton | Find identifiers anywhere |
| Log analysis | ✅ SuffixAutomaton | Error codes mid-line |
| Bioinformatics | ✅ SuffixAutomaton | DNA/protein motifs |
| Autocomplete | ⚠️ DoubleArrayTrie | Only need prefixes |
| Spell checking | ⚠️ DoubleArrayTrie | Whole words only |
| Dictionary lookup | ⚠️ DoubleArrayTrie | Much faster |
Code Search Engines
Document Search
Log Monitoring
Bioinformatics
Data Mining
Blumer, A., Blumer, J., Ehrenfeucht, A., Haussler, D., & McConnell, R. M. (1985). "The smallest automaton recognizing the subwords of a text"
Crochemore, M. (1986). "Transducers and repetitions"
Inenaga, S., Hoshino, H., Shinohara, A., Takeda, M., & Arikawa, S. (2005). "On-line construction of symmetric compact directed acyclic word graphs"
Crochemore, M., & Rytter, W. (2002). Jewels of Stringology
Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences
Navigation: ← Dictionary Layer | DoubleArrayTrie | Algorithms Home
Can you improve this documentation?Edit on GitHub
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |