liblevenshtein-rust Architecture

Version: 0.10.0 Last Updated: 2026-08-03

This document describes the intra-crate architecture and design principles of liblevenshtein-rust — how the modules inside this crate fit together. For the inter-crate view (how liblevenshtein relates to libdictenstein, duallity, and the DSL layer) see the Architecture Overview.

---

Table of Contents

• Overview
• Module Organization
• Core Components
• Design Principles
• Performance Architecture
• Thread Safety
• Future Directions

---

Overview

liblevenshtein-rust is a high-performance library for approximate string matching using Levenshtein automata. Since v0.9.0 it is layered over a sibling crate:

1. Dictionary backends live in libdictenstein — the trie/DAWG implementations (DoubleArrayTrie, DynamicDawg/DynamicDawgU64, SuffixAutomaton, Scdawg, PersistentARTrie, PathMapDictionary) and the Dictionary / DictionaryNode / MappedDictionary traits. They are re-exported here as #[deprecated] shims for source compatibility.
2. The Levenshtein transducer & automata live in this crate (src/transducer/): the lazy/parameterized engine (default), plus eager universal/ and runtime-configurable generalized/ implementations.
3. Higher-level engines are built on the core: phonetic matching, time-series measures, WallBreaker, contextual completion, and fuzzy caching.

Key Characteristics

• Type-safe — extensive use of Rust's type system for correctness.
• Zero-cost abstractions — trait-based design, monomorphized; the SubstitutionPolicy default (Unrestricted) is a zero-sized type.
• Memory-efficient — structural sharing via Arc, position-set pooling, SmallVec stack allocation.
• Concurrent-safe — lock-free reads on every backend (immutable arrays on the static dict, ArcSwap snapshots on the dynamic ones); every backend is Send + Sync with cheap Arc clones.
• Feature-gated — modular compilation (phonetic, serialization, WASM, FFI, caching …).

---

Module Organization

src/
├── lib.rs              # Public API, prelude, feature gates
│
├── transducer/         # THE CORE — Levenshtein automata & query iterators
│   ├── mod.rs          #   Transducer<D, P> struct, public API
│   ├── algorithm.rs    #   Algorithm enum (Standard, Transposition, MergeAndSplit)
│   ├── state.rs        #   Automaton state = set of positions ⟨i,e⟩
│   ├── position.rs     #   Position ⟨i,e⟩
│   ├── transition.rs   #   χ-driven transition rule
│   ├── pool.rs         #   StatePool — position-set reuse (no steady-state alloc)
│   ├── intersection.rs #   Dictionary ∩ automaton lock-step walk
│   ├── query.rs        #   QueryIterator (+ ordered_query, priority_query,
│   │                   #     value_filtered_query, zipper iterators)
│   ├── universal/      #   Eager parameter-free DFA (Mitankin 2005)
│   ├── generalized/    #   Runtime OperationSet (drives weighted/phonetic edits)
│   ├── *_f64.rs        #   Real-valued (weighted) shadow of the integer path
│   ├── substitution_set.rs / substitution_policy.rs
│   └── simd.rs         #   x86_64 SIMD helpers
│
├── distance/           # Direct edit-distance functions
│   ├── mod.rs          #   standard_distance (auto-dispatch), affix stripping
│   ├── myers.rs        #   Myers bit-parallel
│   └── simd.rs         #   AVX2 / SSE4.1 distance (runtime-detected)
│
├── filter/             # n-gram / Jaro-Winkler / hybrid pre-filters
├── dictionary/         # #[deprecated] re-export shims over libdictenstein
│                       #   (+ phonetic_normalized, the one backend still local)
│
├── phonetic/           # Phonetic engine (feature: phonetic-rules)
│   ├── rules/          #   53-language rewrite rules
│   ├── nfa/            #   Thompson construction, product automaton, lazy DFA
│   ├── llev/ · llre/ · regex/   # the .llev / .llre DSLs
│   └── features.rs · feature_distance.rs   # articulatory features
│
├── time_series/        # Move-Split-Merge (MSM) metric, automaton, indexing
├── wallbreaker/        # Large-k strategy (SCDAWG + pigeonhole)
├── contextual/         # Hierarchical scopes, draft buffers, checkpoints
├── cache/              # FuzzyMultiMap + composable eviction wrappers
│
├── serialization/      # bincode / protobuf binary persistence (+ gzip wrapper)
└── wasm/ · ffi/        # JavaScript & C-ABI boundaries

---

Core Components

For the container-level view of these components and how they relate to the external crates, see the C4 container diagram:

1 · Dictionary abstraction (libdictenstein)

The Dictionary trait — now defined in libdictenstein — is the seam between the automata and the backends:

pub trait Dictionary: Send + Sync {
    type Node: DictionaryNode;
    fn root(&self) -> Self::Node;
    fn len(&self) -> Option<usize>;
    fn sync_strategy(&self) -> SyncStrategy;
}

SyncStrategy (defined below in Thread Safety) communicates a backend's concurrency model to callers. The concrete backends and a decision tree for choosing one are documented in the dictionary structures diagrams and the user-guide backends page. New code should import them directly from libdictenstein.

2 · Transducer (Levenshtein automaton)

Transducer<D, P = Unrestricted> wraps a dictionary and is parameterized by an Algorithm and a SubstitutionPolicy:

pub struct Transducer<D: Dictionary, P: SubstitutionPolicy = Unrestricted> {
    dictionary: D,
    algorithm: Algorithm,
    policy: P,
}

A query lazily simulates the Levenshtein automaton $A(W, k)$ and intersects it with the dictionary in one depth-first walk — see Lazy vs. Eager Automata. Key methods: query, query_with_distance, query_ordered/query_ranked, and the value-aware query_filtered / query_values / query_by_value_set (which require a MappedDictionary).

3 · Query-iterator family

All iterators perform the same lock-step walk and yield Candidate { term, distance }, differing in ordering and value filtering:

OrderedQueryIterator returns results distance-first then lexicographically via a binary heap; ValueFilteredQueryIterator prunes whole subtrees by a value predicate — the 10–100× speedup behind scope-aware completion.

4 · State pool (object-pool pattern)

Automaton states are sets of positions reused across query steps through a StatePool (src/transducer/pool.rs), so steady-state querying performs no heap allocation. See the position-set state diagram.

5 · Serialization system

A trait-based format family (feature: serialization):

pub trait DictionarySerializer {
    fn serialize<D: Dictionary, W: Write>(&self, dict: &D, w: W) -> Result<()>;
    fn deserialize<D: DictionaryFromTerms, R: Read>(&self, r: R) -> Result<D>;
}

Implementations: BincodeSerializer, ProtobufSerializer (feature: protobuf), and GzipSerializer<S> which wraps either binary serializer to add compression (feature: compression). JSON, TOML, and newline text are not dictionary persistence formats. See the serialization formats diagram. The separate liblevenshtein-cli application crate owns file-extension and magic-byte auto-detection.

6 · Application boundary

The CLI, REPL, filesystem traversal, compression/archive handling, and document extractors live in the sibling liblevenshtein-rust-cli repository. That crate depends on this one; this library has no reverse dependency and no application feature flag. Reusable in-memory phonetic grep engines remain under phonetic::{grep,grep_online,token_grep}.

---

Design Principles

1 · Trait-based polymorphism

Traits for abstraction (Dictionary, SubstitutionPolicy), concrete types for performance — monomorphized to zero-cost specializations.

2 · Wait-free-where-possible concurrency

Backends expose their model via SyncStrategy; readers never block on DoubleArrayTrie or DynamicDawgU64 (atomic ArcSwap), and take a parking_lot read guard on the mutable DAWG/automaton backends. Arc makes every clone cheap.

3 · Arc sharing & SmallVec stack allocation

Paths and position-sets are shared via Arc rather than deep-cloned; small collections (edge lists, position vectors) live inline in a SmallVec and spill to the heap only when they outgrow their inline capacity.

4 · Lazy evaluation

Queries are iterators that generate results on demand, enabling early termination and composition with iterator adapters with $\mathcal{O}(1)$ iterator state.

5 · Feature gates

Modular compilation keeps the default dependency set minimal:

[features]
default          = ["parking_lot"]
phonetic-rules   = ["unicode-normalization"]
serialization    = ["serde", "bincode", "libdictenstein/serialization"]
compression      = ["flate2", "serialization", "libdictenstein/compression"]
parallel-grep    = ["rayon", "phonetic-rules"]
# … wasm, ffi, persistent-artrie, eviction-opt-* …

The full graph is shown in the feature-flag DAG.

---

Performance Architecture

Optimizations are layered from the algorithm down to the compiler:

• Algorithm — lazy simulation (only $\mathcal{O}(\lvert W\rvert)$ distinct states for fixed $k$), subsumption pruning, ordered/priority iteration, value-scope pruning.
• Distance — standard_distance dispatches to Myers bit-parallel for short ASCII inputs and AVX2/SSE4.1 SIMD otherwise, with a scalar fallback. See the distance dispatch diagram.
• Data structures — Arc sharing, SmallVec, the StatePool, and (in libdictenstein) SIMD + bloom-filter edge pruning.
• Compiler — aggressive inlining, target features, LTO.

Measured backend numbers are in the main README's Performance section and the performance guide. Benchmarking uses Criterion.rs with perf/flamegraph profiling.

---

Thread Safety

Every dictionary is Send + Sync and cheap to clone (Arc). The read path depends on the backend:

SyncStrategy communicates the model to callers:

pub enum SyncStrategy {
    Persistent,    // Immutable / copy-on-write snapshot — always safe (e.g. PersistentARTrie, PathMap snapshots)
    InternalSync,  // Lock-free internal synchronization (ArcSwap / CAS) — every in-memory dynamic backend
    ExternalSync,  // Trait default (interior mutability behind a lock); reported by the immutable DoubleArrayTrie
}

Multiple threads may query a shared transducer concurrently; on every backend a writer publishes new state by an atomic ArcSwap / compare_exchange swap without ever excluding readers, so queries observe the update as soon as the swap completes. No dictionary read blocks on a writer — the static DoubleArrayTrie reads immutable arrays, and every dynamic backend loads a lock-free ArcSwap snapshot.

---

Future Directions

SIMD distance and edge-pruning shipped (v0.8+) and are no longer future work. Remaining exploratory directions:

1. Async/streaming query surface — a Stream-returning query for non-blocking integration.
2. Custom allocators — arena allocators scoped to a query session.
3. GPU acceleration (research) — large-scale parallel queries over very large dictionaries.

Recorded design explorations live under docs/research/ (an append-only record) and docs/design/.

---

References

• Performance guide
• Features overview
• Contributing
• Build guide
• Architecture Overview (inter-crate)

---

Summary

liblevenshtein-rust achieves high performance through efficient data structures (tries/DAWGs in libdictenstein with structural sharing), smart memory management (position-set pooling, Arc sharing, SmallVec), zero-cost abstractions (monomorphized traits, ZST policies), profiling-driven optimization of hot paths, and a wait-free-where-possible concurrency design. The architecture is extensible (new backends, formats, algorithms, engines) while keeping the core small and the crate boundary with libdictenstein clean.

---

← Documentation Index