Dictionary Backend Guide

Version: 0.9.1 Last Updated: 2026-06-19

This guide explains the different dictionary backends available in liblevenshtein-rust and how to choose the right one for your use case.

Overview

The dictionary data structures live in the libdictenstein crate. liblevenshtein re-exports them (the liblevenshtein::prelude re-exports are deprecated since 0.9.1 for convenience; new code should use libdictenstein::<module>::<Type> directly). The *Char variants are the UTF-8 (char/u32) counterparts of the byte-level (u8) backends.

liblevenshtein uses a trait-based design that allows multiple dictionary implementations to share the same fuzzy-matching interface. Each backend has different trade-offs in terms of:

• Construction time: How long it takes to build the dictionary
• Query performance: How fast fuzzy searches are
• Memory usage: RAM footprint
• Update support: Whether the dictionary can be modified after construction
• Use case fit: What scenarios each backend excels at

The taxonomy below groups the available backends by their core data structure and intended workload.

Available Backends

1. DoubleArrayTrie (Recommended Default)

Type: Double-Array Trie with conflict resolution

Characteristics:

• Construction: Medium (conflict resolution)
• Query: Excellent ($\mathcal{O}(1)$ transitions, excellent cache locality)
• Memory: Minimal
• Updates: No (immutable after construction)
• Unicode: Use DoubleArrayTrieChar variant

When to use:

• Default choice for most static dictionaries
• Best overall query performance
• Memory-efficient
• Large dictionaries (100K+ terms)

Example:

use liblevenshtein::prelude::*;

let dict = DoubleArrayTrie::from_terms(vec![
    "test", "testing", "tested", "tester"
]);

let transducer = Transducer::new(dict, Algorithm::Standard);
for term in transducer.query("tset", 2) {
    println!("{}", term);
}

Feature flag: dat-backend (enabled by default)

2. DoubleArrayTrieChar (Unicode Support)

Type: Character-level Double-Array Trie

Characteristics:

• Construction: Medium
• Query: Very Good (~5% slower than byte-level)
• Memory: Moderate (4× edge label memory)
• Updates: No
• Unicode: ✅ Correct character-level distances

When to use:

• Unicode text with multi-byte characters (accented, CJK, emoji)
• Need correct character-level Levenshtein distances
• Internationalization requirements

Example:

use liblevenshtein::prelude::*;

// Multi-byte UTF-8 characters handled correctly
let dict = DoubleArrayTrieChar::from_terms(vec![
    "café", "naïve", "日本語", "emoji😀"
]);

let transducer = Transducer::new(dict, Algorithm::Standard);
for candidate in transducer.query_with_distance("cafe", 1) {
    println!("{}: {}", candidate.term, candidate.distance);
}

Trade-offs:

• ~5% performance overhead
• 4× memory for edge labels
• Correct Unicode Levenshtein distances

Feature flag: dat-backend (enabled by default)

3. PathMapDictionary (Dynamic Updates)

Type: Trie with structural sharing and interior mutability

Characteristics:

• Construction: Fast
• Query: Very Good
• Memory: Moderate
• Updates: ✅ Yes (thread-safe, lock-free reads via Arc<ArcSwap<…>>)
• Unicode: Use PathMapDictionaryChar variant

When to use:

• Need runtime dictionary updates
• Insert/remove terms dynamically
• Concurrent updates and queries
• Medium-sized dictionaries (10K-100K terms)

Example:

use liblevenshtein::prelude::*;

let dict = PathMapDictionary::from_terms(vec![
    "test", "testing"
]);

// Insert new terms at runtime
dict.insert("tested");
dict.insert("tester");

// Remove terms
dict.remove("testing");

let transducer = Transducer::new(dict, Algorithm::Standard);
for term in transducer.query("test", 1) {
    println!("{}", term);
}

Thread safety:

• Lock-free reads (Arc<ArcSwap<PathMapState>>) — readers never block on a writer
• Writers publish a new state by an atomic pointer swap
• Queries see updates immediately

Feature flag: pathmap-backend (optional)

4. PathMapDictionaryChar (Dynamic Unicode)

Type: Character-level PathMap with dynamic updates

Characteristics:

• Construction: Fast
• Query: Good (~10% slower than byte-level)
• Memory: High (4× edge labels + structural overhead)
• Updates: ✅ Yes (thread-safe)
• Unicode: ✅ Correct character-level distances

When to use:

• Dynamic Unicode dictionaries
• Need both updates and correct Unicode distances
• Internationalized applications with runtime changes

Feature flag: pathmap-backend (optional)

5. DynamicDawg (Updates + Space Efficiency)

Type: DAWG with online insert/delete/minimize operations

Characteristics:

• Construction: Fast (incremental)
• Query: Good
• Memory: Low (maintains minimization)
• Updates: ✅ Yes (thread-safe, lock-free reads via the LockFreeDawg core)

When to use:

• Need both updates and space efficiency
• Incremental dictionary construction
• Memory-constrained dynamic dictionaries

Example:

use liblevenshtein::prelude::*;

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

// Online insertion with automatic minimization
dict.insert("testing");
dict.insert("tested");

// Online deletion
dict.remove("test");

println!("Nodes after minimization: {}", dict.node_count());

Feature flag: dawg-backend (optional)

Unicode: Use the DynamicDawgChar variant for correct character-level distances.

6. DynamicDawgU64 (Lock-Free Updates)

Type: 64-bit Dynamic DAWG with wait-free reads and 8-byte (u64) edge labels

Characteristics:

• Construction: Fast (incremental)
• Query: Good (wait-free reads, no blocking)
• Memory: Low (maintains minimization)
• Updates: ✅ Yes (lock-free reads; CAS writes)
• Concurrency: Reads are wait-free over one immutable root revision; writes path-copy the affected route and CAS-publish a replacement revision

When to use:

• High-concurrency workloads where updates and queries interleave heavily from many threads
• Alphabets or edge payloads that need the wider 8-byte (u64) edge label
• You prefer the u64-labelled variant of the shared lock-free DAWG core

Both DynamicDawg and DynamicDawgU64 are fully lock-free for reads — they share the same LockFreeDawg core (a reader retains one immutable root; writes use path-copying and a root compare_exchange loop). They differ only in the edge-label width: DynamicDawg uses a 1-byte u8 label, DynamicDawgU64 a wider u64 label (more label space at some extra memory). See Thread Safety for the concurrency model.

Feature flag: dawg-backend (optional)

7. SuffixAutomaton (Substring Matching)

Type: Suffix automaton for infix matching

Characteristics:

• Construction: Fast
• Query: Good (supports substring matching)
• Memory: Moderate
• Updates: No
• Special: Supports substring/infix matching

When to use:

• Need substring matching (not just prefix)
• Searching for patterns within words
• Text indexing applications

Example:

use liblevenshtein::prelude::*;

let dict = SuffixAutomaton::from_terms(vec![
    "testing", "fastest", "contest"
]);

// Can match substring "test" in any position
let transducer = Transducer::new(dict, Algorithm::Standard);
for term in transducer.query("test", 1) {
    println!("{}", term);
}

Feature flag: suffix-automaton-backend (optional)

8. Scdawg (Symmetric Compact DAWG)

Type: Symmetric Compact Directed Acyclic Word Graph with bidirectional traversal (Scdawg; ScdawgChar for UTF-8)

Characteristics:

• Construction: Medium (builds suffix automaton per term)
• Query: Excellent for substring ($\mathcal{O}(\lvert pattern\rvert)$)
• Memory: Moderate
• Updates: No (immutable after construction)
• Special: True suffix automaton indexing ALL substrings with bidirectional edges; backs the WallBreaker large-k query splitter

When to use:

• Need $\mathcal{O}(\lvert pattern\rvert)$ substring search
• Bidirectional pattern traversal (left/right extensions)
• Text indexing with substring frequency queries
• WallBreaker pattern splitting algorithm

Example:

use liblevenshtein::prelude::*;

let scdawg = Scdawg::<()>::from_terms(["cathedral", "category", "catering"]);

// O(|pattern|) substring search
assert!(scdawg.contains_substring("cat"));
assert!(scdawg.contains_substring("thedr"));

// Find all occurrences
let matches = scdawg.find_exact_substring("cat");
assert_eq!(matches.len(), 3);  // Found in all three terms

Feature flag: scdawg-backend (optional)

9. PersistentARTrie (Disk-Based)

Type: Persistent Adaptive Radix Trie with memory-mapped storage (PersistentARTrie; PersistentARTrieChar for UTF-8)

Characteristics:

• Construction: Fast (incremental inserts)
• Query: Excellent (adaptive node sizes, SIMD acceleration)
• Memory: Disk-based (configurable buffer cache)
• Updates: ✅ Yes (with WAL for crash recovery)
• Special: Handles dictionaries larger than RAM

When to use:

• Dictionary too large to fit in memory
• Need persistence across application restarts
• Crash recovery required
• Memory-constrained environments with large dictionaries

Example:

use libdictenstein::persistent_artrie::PersistentARTrie;

// Create a new persistent dictionary
let dict = PersistentARTrie::create("words.part")?;

// Insert terms (persisted to disk)
dict.insert("hello", ())?;
dict.insert("world", ())?;

// Query with transducer
let transducer = Transducer::new(&dict, Algorithm::Standard);
for result in transducer.query("helo", 1) {
    println!("{}: distance {}", result.term, result.distance);
}

Architecture:

• Adaptive node sizes: Node4, Node16 (SIMD), Node48, Node256
• B-trie buckets for efficient leaf storage
• Pointer swizzling for lazy loading
• Write-ahead logging (WAL) for crash recovery

Feature flag: persistent-artrie (optional)

Backend Comparison

Performance Summary

Backend	Construction	Query	Memory	Updates	Unicode Variant
DoubleArrayTrie	●●●○○ Medium	●●●●● Excellent	●●●●● Minimal	✗ No	DoubleArrayTrieChar
PathMapDictionary	●●●●○ Fast	●●●●○ Very Good	●●●○○ Moderate	✅ Yes	PathMapDictionaryChar
DynamicDawg	●●●●○ Fast	●●●○○ Good	●●●●○ Low	✅ Yes (lock-free)	DynamicDawgChar
DynamicDawgU64	●●●●○ Fast	●●●○○ Good	●●●●○ Low	✅ Yes (lock-free)	— (u64 labels)
SuffixAutomaton	●●●●○ Fast	●●●○○ Good	●●●○○ Moderate	✗ No	SuffixAutomatonChar
Scdawg	●●●○○ Medium	●●●●● Excellent (substring)	●●●○○ Moderate	✗ No	ScdawgChar
PersistentARTrie	●●●●○ Fast	●●●●● Excellent	Disk-based	✅ Yes	PersistentARTrieChar

Benchmark Results

Query performance relative to DoubleArrayTrie (100K terms, distance 2):

Backend	Relative Speed	Memory (MB)
DoubleArrayTrie	1.0× (baseline)	8.5
DoubleArrayTrieChar	0.95×	11.2
PathMapDictionary	0.92×	12.3
PathMapDictionaryChar	0.87×	16.8
DynamicDawg	0.85×	7.8
DynamicDawgU64	0.84×	9.1
SuffixAutomaton	0.82×	10.5
Scdawg	0.90× (substring: 1.2×)	14.2
PersistentARTrie	0.88×	Disk + cache

Note: All backends benefit from SIMD acceleration (20-64% faster, automatic on x86_64 with AVX2/SSE4.1).

Decision Guide

The flowchart below distills the prose decision criteria into a single path from your requirements to a recommended backend.

Choose DoubleArrayTrie when:

• ✅ You need the best query performance
• ✅ Dictionary is static (no updates needed)
• ✅ Memory efficiency matters
• ✅ Default choice for most use cases

Choose DoubleArrayTrieChar when:

• ✅ Working with Unicode text
• ✅ Need correct character-level distances
• ✅ Internationalization is required
• ✅ Can accept ~5% performance overhead

Choose PathMapDictionary when:

• ✅ Need runtime dictionary updates
• ✅ Insert/remove operations required
• ✅ Thread-safe concurrent access needed
• ✅ Dictionary changes frequently

Choose PathMapDictionaryChar when:

• ✅ Need both Unicode and dynamic updates
• ✅ Internationalized app with runtime changes
• ✅ Can accept higher memory usage

Choose DynamicDawg when:

• ✅ Need both updates and space efficiency
• ✅ Memory constrained but need updates
• ✅ Can accept slightly slower queries
• ✅ Want lock-free reads with compact single-byte (u8) edge labels

Choose DynamicDawgU64 when:

• ✅ Need updates with lock-free reads (readers never block on a writer)
• ✅ High-concurrency, read-write-interleaved workloads
• ✅ Can accept u64 (8-byte) edge labels for wait-free reads

Choose SuffixAutomaton when:

• ✅ Need substring/infix matching
• ✅ Pattern matching within words
• ✅ Text indexing applications

Choose Scdawg when:

• ✅ Need $\mathcal{O}(\lvert pattern\rvert)$ substring search
• ✅ Bidirectional pattern traversal required
• ✅ Pattern splitting (WallBreaker algorithm)
• ✅ Substring frequency queries

Choose PersistentARTrie when:

• ✅ Dictionary larger than available RAM
• ✅ Need persistence across restarts
• ✅ Crash recovery is required
• ✅ Building dictionary incrementally over time

Feature Flags

Enable backends via Cargo features:

[dependencies]
liblevenshtein = {
    git = "https://github.com/vinary-tree/liblevenshtein-rust",
    tag = "v0.9.1",
    features = [
        "dat-backend",              # DoubleArrayTrie (default)
        "pathmap-backend",          # PathMapDictionary
        "dawg-backend",             # DynamicDawg / DynamicDawgU64
        "suffix-automaton-backend", # SuffixAutomaton
        "scdawg-backend",           # Scdawg
        "persistent-artrie"         # PersistentARTrie
    ]
}

Custom Backends

You can implement your own dictionary backend by implementing the Dictionary trait (defined in libdictenstein):

use libdictenstein::{Dictionary, DictionaryNode};

pub struct MyCustomDictionary {
    // Your implementation
}

impl Dictionary for MyCustomDictionary {
    type Node = MyNode;

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

    fn len(&self) -> Option<usize> {
        // Return number of terms
    }

    fn contains(&self, term: &str) -> bool {
        // Check if term exists
    }

    // ... other required methods
}

See Developer Guide for more details on custom backends.

Related Documentation

• Getting Started - Basic usage
• Algorithms - Levenshtein algorithm variants
• Thread Safety - Concurrent access patterns
• Serialization - Save and load dictionaries
• Glossary - Definitions of terms used throughout the docs
• Architecture Overview - How libdictenstein and liblevenshtein fit together
• Benchmarks - Detailed performance measurements

References

• Trie (Wikipedia)
• Directed Acyclic Word Graph (Wikipedia)
• Double-Array Trie
• Suffix Automaton
• Morrison, D. R. (1968). "PATRICIA — Practical Algorithm To Retrieve Information Coded in Alphanumeric." Journal of the ACM, 15(4), 514–534. DOI: 10.1145/321479.321481

---

← Documentation Index