Dictionary Layer

Navigation: ↑ Documentation index · Theory → · Architecture → · Query half: liblevenshtein →

Overview

The Dictionary Layer is the family of dictionary backends provided by libdictenstein. It supplies pluggable implementations for storing and traversing collections of terms, optimized for the efficient character-by-character navigation a Levenshtein-automaton transducer (such as the companion liblevenshtein crate) performs. libdictenstein itself contains no fuzzy-matching code — it is the container half that such a transducer walks.

This layer abstracts over different data structures (tries, DAWGs, double-array tries) through common traits, allowing you to choose the best backend for your specific use case while maintaining a consistent API.

Architecture

Core Concepts

1. Dictionary Trait

The Dictionary trait defines the minimal interface for any dictionary backend:

pub trait Dictionary {
    type Node: DictionaryNode;

    fn root(&self) -> Self::Node;
    fn contains(&self, term: &str) -> bool;
    fn len(&self) -> Option<usize>;
    fn is_empty(&self) -> bool;
}

Key Features:

Graph-based traversal: Navigate character-by-character through nodes
Backend agnostic: Works with any underlying data structure
Lazy evaluation: Only explores paths needed for fuzzy matching

2. DictionaryNode Trait

Nodes represent positions in the dictionary graph:

pub trait DictionaryNode: Clone + Send + Sync {
    type Unit: CharUnit;  // u8 or char

    fn is_final(&self) -> bool;
    fn transition(&self, label: Self::Unit) -> Option<Self>;
    fn edges(&self) -> Box<dyn Iterator<Item = (Self::Unit, Self)> + '_>;
}

Key Features:

Unit abstraction: Supports both byte-level (u8) and character-level (char)
Lazy edge iteration: Only compute edges when needed
Thread-safe: Clone + Send + Sync for concurrent queries

3. MappedDictionary Trait

Extensions for dictionaries that associate values with terms:

pub trait MappedDictionary: Dictionary {
    type Value: DictionaryValue;

    fn get_value(&self, term: &str) -> Option<Self::Value>;
    fn contains_with_value<F>(&self, term: &str, predicate: F) -> bool
    where F: Fn(&Self::Value) -> bool;
}

Performance Impact: Filtering during traversal provides 10-100x speedup compared to post-filtering.

See Serialization & values for detailed documentation.

4. Character Units

The library supports two modes for handling text:

Mode	Type	Best For	Correctness
Byte-level	`u8`	ASCII/Latin-1, Speed	Edit distances on byte sequences
Character-level	`char`	Unicode text	Proper Unicode code point distances

Example:

// Byte-level: "café" = ['c', 'a', 'f', 0xC3, 0xA9] (5 bytes)
let dict_bytes = DoubleArrayTrie::from_terms(vec!["café"]);

// Character-level: "café" = ['c', 'a', 'f', 'é'] (4 chars)
let dict_chars = DoubleArrayTrieChar::from_terms(vec!["café"]);

// Different Levenshtein distances:
// "cafe" → "café": distance 1 (char-level), distance 2 (byte-level)

Available Implementations

Production Ready (Recommended)

1. DoubleArrayTrie (⭐ Default Choice)

Best for: General-purpose applications

use libdictenstein::double_array_trie::DoubleArrayTrie;

let mut dict = DoubleArrayTrie::from_terms(vec![
    "algorithm", "approximate", "automaton"
]);
dict.insert("analysis");  // Supports runtime insertions

Characteristics:

⚡ 3x faster queries than DAWG
💾 8 bytes/state memory footprint
🔧 Append-only dynamic updates
🎯 Cache-efficient BASE/CHECK arrays

→ Detailed Guide

2. DoubleArrayTrieChar (Unicode)

Best for: Multi-language applications with proper Unicode handling

use libdictenstein::double_array_trie::DoubleArrayTrieChar;

let mut dict = DoubleArrayTrieChar::from_terms(vec![
    "café", "naïve", "中文", "🎉"
]);
dict.insert("新しい");

Characteristics:

✅ Character-level distances
🌍 Full Unicode support (CJK, emoji, accents)
📊 ~5% overhead vs byte-level
💾 4x memory for edge labels (char vs u8)

→ Detailed Guide

3. DynamicDawg

Best for: Applications requiring both insert and remove operations

use libdictenstein::dynamic_dawg::DynamicDawg;

let dict = DynamicDawg::from_terms(vec!["initial", "terms"]);
dict.insert("new_term");  // ✅ Thread-safe
dict.remove("old_term");  // ✅ Supports removal

Characteristics:

🔒 Thread-safe insert AND remove
🔄 Active queries see updates immediately
📉 Good performance for fully dynamic use
💾 Moderate memory overhead

→ Detailed Guide

4. DynamicDawgChar (Unicode + Dynamic)

Best for: Unicode applications with full dynamic updates

use libdictenstein::dynamic_dawg::DynamicDawgChar;

let dict = DynamicDawgChar::from_terms(vec!["café", "中文"]);
dict.insert("新しい");  // ✅ Unicode + thread-safe
dict.remove("café");    // ✅ Full removal support

Characteristics:

✅ Character-level Unicode distances
🔒 Thread-safe insert and remove
📊 ~5% overhead vs byte-level
🌍 Full Unicode support

→ Detailed Guide

Specialized Use Cases

5. SuffixAutomaton

Best for: Substring/infix search within text

use libdictenstein::suffix_automaton::SuffixAutomaton;

let dict = SuffixAutomaton::from_source_text("the quick brown fox");
// Finds "quick" even though it's not a prefix

Characteristics:

🔍 Substring matching (not just prefixes)
📝 Text indexing use cases
💾 2x memory vs standard tries

→ Detailed Guide

6. PathMapDictionary (Feature: `pathmap-backend`)

Best for: Frequent updates with simpler structure

#[cfg(feature = "pathmap-backend")]
use libdictenstein::pathmap::PathMapDictionary;

let dict = PathMapDictionary::from_terms(vec!["test"]);
dict.insert("new");  // Simpler internal structure

Characteristics:

📦 Simple structure for updates
🔒 Thread-safe
📉 2-3x slower than DoubleArrayTrie
💾 Higher memory usage

Substring & static-compact

7. SuffixAutomatonChar / Scdawg / ScdawgChar

Unicode substring search (SuffixAutomatonChar) and the static, compact symmetric DAWG (Scdawg / ScdawgChar) for bidirectional substring indexing at ~20–30% fewer states than a plain suffix automaton. See suffix-automaton.md and scdawg.md.

Token / time-series labels

8. DynamicDawgU64

A DynamicDawg whose edge labels are 64-bit units — for token sequences and time-series keys:

use libdictenstein::dynamic_dawg::DynamicDawgU64;

let dict = DynamicDawgU64::new();   // thread-safe insert + remove over u64 labels

Disk-backed (feature `persistent-artrie`)

9. Persistent ARTrie family

Crash-durable Adaptive Radix Tries: PersistentARTrie / PersistentARTrieChar (key -> value), PersistentARTrieU64Compact (native u64 sequence keys), and PersistentVocabARTrie (term <-> u64 vocabulary ids). These are built on a lock-free overlay, write-ahead logging, and CX (compact-snapshot) checkpoint images over mmap (or io_uring) block storage. See the crate README and mmap-architecture.md.

10. Persistent suffix graph family

Durable substring indexes: PersistentSuffixAutomaton, PersistentSuffixTree, and PersistentScdawg, each with byte and Char variants. These persist native suffix graph snapshots plus operation-segment WALs. Reads traverse immutable snapshots without taking a writer lock; writes rebuild a candidate graph revision and CAS-publish the winning copy.

Decision Guide

Quick Selection Flowchart

Detailed Comparison Table

Feature	DAT	DAT-Char	DynDAWG	DynDAWG-Char	PathMap	SuffixAuto
Query Speed	⭐⭐⭐⭐⭐	⭐⭐⭐⭐	⭐⭐⭐	⭐⭐⭐	⭐⭐	⭐⭐⭐
Memory	⭐⭐⭐⭐⭐	⭐⭐⭐⭐	⭐⭐⭐	⭐⭐⭐	⭐⭐	⭐⭐
Construction	⭐⭐⭐⭐	⭐⭐⭐⭐	⭐⭐⭐	⭐⭐⭐	⭐⭐⭐⭐	⭐⭐⭐
Insert	✅ Append	✅ Append	✅ Full	✅ Full	✅ Full	✅ Full
Remove	❌	❌	✅	✅	✅	✅
Union	❌	❌	✅	✅	✅	❌
Clone Cost	$O(n)$	$O(n)$	$O(1)$	$O(1)$	$O(1)$	N/A
Clone Sharing	❌ Deep	❌ Deep	✅ Arc	✅ Arc	✅ Arc $\times$ 2	N/A
Unicode	Byte	✅ Char	Byte	✅ Char	Byte	Byte
Thread-Safe	✅	✅	✅	✅	✅	✅
Use Case	General	Unicode	Dynamic	Dyn+Unicode	Simple	Substring

Persistent backends are excluded from this in-memory comparison table because they require file paths, durability policy, and checkpoint/recovery costs. For durable prefix/key-value dictionaries choose PersistentARTrie/Char/U64; for durable substring search choose the persistent suffix graph family.

Performance Benchmarks

Provenance. The figures below are indicative relative orderings on a 10,000-word dictionary — not a current measurement. For reproducible numbers, see the benchmarking ledgers under ../benchmarks/ and ../experiments/, produced by the benches/ suite. The qualitative ranking — DoubleArrayTrie fastest and most compact; DynamicDawg trades raw speed for runtime mutability and suffix-sharing — is stable and well-supported.

Construction Time

DoubleArrayTrie:     3.2ms
DoubleArrayTrieChar: 3.4ms   (+6%)
PathMapDictionary:   3.5ms   (+9%)
DynamicDawg:         4.1ms   (+28%)
DynamicDawgChar:     7.2ms   (+125%)

Exact Match (single term)

DoubleArrayTrie:     6.6µs
DoubleArrayTrieChar: 6.9µs  (+5%)
DynamicDawg:         19.8µs (+200%)
PathMapDictionary:   71.1µs (+977%)

Contains Check (100 terms)

DoubleArrayTrie:     0.22µs per check
DoubleArrayTrieChar: 0.23µs (+5%)
DynamicDawg:         6.7µs  (+2945%)
PathMapDictionary:   132µs  (+59900%)

Fuzzy Search (max distance 2)

DoubleArrayTrie:     16.3µs
DoubleArrayTrieChar: 17.1µs  (+5%)
DynamicDawg:         2,150µs (+13100%)
PathMapDictionary:   5,919µs (+36200%)

Key Takeaway: DoubleArrayTrie variants are consistently 3-30x faster than alternatives for fuzzy matching workloads.

Memory Characteristics

Per-State Memory (approximate)

DoubleArrayTrie:     8 bytes/state
DoubleArrayTrieChar: 12 bytes/state (char labels = 4x u8)
DynamicDawg:         16 bytes/state
DynamicDawgChar:     24 bytes/state (char labels + Arc)
PathMapDictionary:   32 bytes/state (HashMap overhead)
SuffixAutomaton:     48 bytes/state (suffix links)

Example: 50,000 terms

DoubleArrayTrie:     ~800 KB
DoubleArrayTrieChar: ~1.2 MB
DynamicDawg:         ~2.4 MB
PathMapDictionary:   ~3.2 MB

Common Use Cases

1. Web Application Autocomplete

Recommendation: DoubleArrayTrie or DoubleArrayTrieChar

use libdictenstein::double_array_trie::DoubleArrayTrie;
use liblevenshtein::levenshtein::Algorithm;
use liblevenshtein::levenshtein_automaton::LevenshteinAutomaton;

// Initialize once at startup
let dict = DoubleArrayTrie::from_terms(load_product_names());

// Per-request fuzzy search
fn autocomplete(query: &str, max_distance: usize) -> Vec<String> {
    let automaton = LevenshteinAutomaton::new(query, max_distance, Algorithm::Standard);
    automaton.query(&dict).collect()
}

Why: Fast queries (microseconds), low memory, append-only updates for new products.

2. Multi-Language Spell Checker

Recommendation: DoubleArrayTrieChar

use libdictenstein::double_array_trie::DoubleArrayTrieChar;

let dict = DoubleArrayTrieChar::from_terms(vec![
    // English
    "color", "colour",
    // Spanish
    "niño", "año",
    // Chinese
    "你好", "世界",
    // Emoji
    "😀", "🎉"
]);

// Correct Levenshtein distances for all languages

Why: Character-level distances handle accents, CJK, emoji correctly.

3. Real-Time Collaborative Editor

Recommendation: DynamicDawg or DynamicDawgChar

use libdictenstein::dynamic_dawg::DynamicDawg;

let dict = DynamicDawg::new();

// User adds word to personal dictionary
dict.insert("refactoring");

// User removes word
dict.remove("typo");

// Active autocomplete queries see changes immediately

Why: Thread-safe insert/remove, queries reflect updates instantly.

4. Code Completion with Scope Filtering

Recommendation: DoubleArrayTrie<u32> with values

use libdictenstein::double_array_trie::DoubleArrayTrie;

let dict = DoubleArrayTrie::from_terms_with_values(vec![
    ("println", 1),   // Global scope
    ("format", 1),    // Global scope
    ("my_var", 42),   // Local scope 42
    ("temp", 42),     // Local scope 42
]);

// Query only local scope (10-100x faster than post-filtering)
let results = query_with_filter(&dict, "temp", 2, |scope| *scope == 42);

Why: Value filtering during traversal is dramatically faster. See Serialization & values.

5. Document Search (Substring Matching)

Recommendation: SuffixAutomaton

use libdictenstein::suffix_automaton::SuffixAutomaton;

let doc = "The quick brown fox jumps over the lazy dog";
let dict = SuffixAutomaton::from_source_text(doc);

// Find "quick" even though it's not at the beginning
let results = fuzzy_search(&dict, "quik", 1);  // Finds "quick"

Why: Matches substrings anywhere in text, not just prefixes.

6. Merging User and System Dictionaries

Recommendation: DynamicDawg or PathMapDictionary with values

use libdictenstein::dynamic_dawg::DynamicDawg;
use libdictenstein::MutableMappedDictionary;

// System-wide default frequencies
let system_dict: DynamicDawg<u32> = DynamicDawg::new();
system_dict.insert_with_value("algorithm", 1000);
system_dict.insert_with_value("database", 800);

// User-specific word frequencies
let user_dict: DynamicDawg<u32> = DynamicDawg::new();
user_dict.insert_with_value("algorithm", 50);  // User types this often
user_dict.insert_with_value("refactoring", 30); // User-specific term

// Merge: prioritize user frequencies but include system terms
system_dict.union_with(&user_dict, |system_freq, user_freq| {
    // Boost user terms by 10x for better autocomplete ranking
    user_freq * 10 + system_freq
});

// Result: "algorithm" = 1500 (50*10 + 1000)
//         "refactoring" = 300 (30*10 + 0)
//         "database" = 800 (unchanged)

Why: Union operations enable personalized autocomplete by combining user patterns with system defaults, custom merge logic for ranking.

Alternative with Configuration Layers:

use libdictenstein::pathmap::PathMapDictionary;
use libdictenstein::MutableMappedDictionary;

// Default application settings
let defaults: PathMapDictionary<String> = PathMapDictionary::new();
defaults.insert_with_value("theme", "light".to_string());
defaults.insert_with_value("language", "en".to_string());

// User preferences
let user_prefs: PathMapDictionary<String> = PathMapDictionary::new();
user_prefs.insert_with_value("theme", "dark".to_string()); // Override

// Merge: user preferences override defaults (last-writer-wins)
defaults.union_replace(&user_prefs);

// Effective config: theme=dark, language=en

Why: PathMapDictionary's structural sharing makes it ideal for configuration layers with frequent snapshots.

Integration with Levenshtein Automata

The Dictionary Layer is designed to work seamlessly with Layer 2 (Automata):

use libdictenstein::double_array_trie::DoubleArrayTrie;
use liblevenshtein::levenshtein::Algorithm;
use liblevenshtein::levenshtein_automaton::LevenshteinAutomaton;

// Step 1: Create dictionary
let dict = DoubleArrayTrie::from_terms(vec!["test", "testing", "tested"]);

// Step 2: Create automaton for query
let automaton = LevenshteinAutomaton::new("tset", 1, Algorithm::Standard);

// Step 3: Query dictionary with automaton
let results: Vec<String> = automaton.query(&dict).collect();
// Results: ["test"] (distance 1: swap 's' and 'e')

The automaton traverses the dictionary graph using DictionaryNode::transition() to explore only paths within the distance threshold.

See Automata Layer for details.

Thread Safety

All dictionary implementations in this library are thread-safe for concurrent reads:

use std::sync::Arc;
use std::thread;

let dict = Arc::new(DoubleArrayTrie::from_terms(vec!["test"]));

// Multiple threads can query simultaneously
let handles: Vec<_> = (0..4).map(|_| {
    let dict = Arc::clone(&dict);
    thread::spawn(move || {
        dict.contains("test")  // ✅ Safe
    })
}).collect();

For concurrent writes, dictionaries have different strategies:

Dictionary	Strategy	Writes	Notes
DoubleArrayTrie	`Persistent`	Rebuild + atomic swap	Append-only via builder
DynamicDawg	`InternalSync`	Direct mutation	Internal RwLock
PathMapDictionary	`InternalSync`	Direct mutation	Internal RwLock

Advanced Topics

Custom Dictionary Implementation

To implement a custom backend:

use libdictenstein::{Dictionary, DictionaryNode, CharUnit};

#[derive(Clone)]
struct MyNode {
    // Your node structure
}

impl DictionaryNode for MyNode {
    type Unit = u8;

    fn is_final(&self) -> bool {
        // Check if this node marks end of term
    }

    fn transition(&self, label: Self::Unit) -> Option<Self> {
        // Follow edge labeled with 'label'
    }

    fn edges(&self) -> Box<dyn Iterator<Item = (Self::Unit, Self)> + '_> {
        // Return all outgoing edges
    }
}

struct MyDictionary {
    // Your dictionary structure
}

impl Dictionary for MyDictionary {
    type Node = MyNode;

    fn root(&self) -> Self::Node {
        // Return root node
    }

    fn len(&self) -> Option<usize> {
        Some(/* term count */)
    }
}

Serialization

Dictionaries can be serialized for persistence:

use libdictenstein::double_array_trie::DoubleArrayTrie;

let dict = DoubleArrayTrie::from_terms(vec!["test"]);

// Serialize
let bytes = bincode::serialize(&dict)?;
std::fs::write("dict.bin", bytes)?;

// Deserialize
let bytes = std::fs::read("dict.bin")?;
let dict: DoubleArrayTrie = bincode::deserialize(&bytes)?;

See Serialization Guide for details.

Academic References

Foundational Papers

Aoe, J. (1989). "An Efficient Digital Search Algorithm by Using a Double-Array Structure"
- IEEE Transactions on Software Engineering, 15(9), 1066-1077
- DOI: 10.1109/32.31365
- 📄 Original double-array trie algorithm
Yata, S., Oono, M., Morita, K., Fuketa, M., Sumitomo, T., & Aoe, J. (2007). "A compact static double-array keeping character codes"
- Information Processing & Management, 43(1), 237-247
- DOI: 10.1016/j.ipm.2006.04.004
- 📄 Optimization techniques for DATs
Blumer, A., Blumer, J., Haussler, D., McConnell, R., & Ehrenfeucht, A. (1987). "Complete inverted files for efficient text retrieval and analysis"
- Journal of the ACM, 34(3), 578-595
- DOI: 10.1145/28869.28873
- 📄 DAWG construction algorithms

Textbooks

Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology
- Cambridge University Press
- ISBN: 978-0521585194
- 📚 Comprehensive coverage of string algorithms and suffix structures

Open Access Resources

Schulz, K. U., & Mihov, S. (2002). "Fast String Correction with Levenshtein Automata"
- International Journal on Document Analysis and Recognition, 5(1), 67-85
- DOI: 10.1007/s10032-002-0082-8
- Core algorithm for fuzzy matching with tries

Next Steps

Deep Dive: Read the DoubleArrayTrie Implementation Guide
Unicode: Learn about DoubleArrayTrieChar
Values: Explore Serialization & values
Query: Understand Levenshtein Automata

Navigation: ↑ Documentation index · Theory → · Architecture → · Query half: liblevenshtein →

Uh oh!

FilesExpand file tree

README.md

Latest commit

History

README.md

File metadata and controls

Dictionary Layer

Overview

Architecture

Core Concepts

1. Dictionary Trait

2. DictionaryNode Trait

3. MappedDictionary Trait

4. Character Units

Available Implementations

Production Ready (Recommended)

1. DoubleArrayTrie (⭐ Default Choice)

2. DoubleArrayTrieChar (Unicode)

3. DynamicDawg

4. DynamicDawgChar (Unicode + Dynamic)

Specialized Use Cases

5. SuffixAutomaton

6. PathMapDictionary (Feature: pathmap-backend)

Substring & static-compact

7. SuffixAutomatonChar / Scdawg / ScdawgChar

Token / time-series labels

8. DynamicDawgU64

Disk-backed (feature persistent-artrie)

9. Persistent ARTrie family

10. Persistent suffix graph family

Decision Guide

Quick Selection Flowchart

Detailed Comparison Table

Performance Benchmarks

Construction Time

Exact Match (single term)

Contains Check (100 terms)

Fuzzy Search (max distance 2)

Memory Characteristics

Per-State Memory (approximate)

Example: 50,000 terms

Common Use Cases

1. Web Application Autocomplete

2. Multi-Language Spell Checker

3. Real-Time Collaborative Editor

4. Code Completion with Scope Filtering

5. Document Search (Substring Matching)

6. Merging User and System Dictionaries

Integration with Levenshtein Automata

Thread Safety

Advanced Topics

Custom Dictionary Implementation

Serialization

Related Documentation

Conceptual deep-dives (this layer)

Cross-cutting (other sections)

Academic References

Foundational Papers

Textbooks

Open Access Resources

Next Steps

6. PathMapDictionary (Feature: `pathmap-backend`)

Disk-backed (feature `persistent-artrie`)