Comprehensive guide to the algorithms, data structures, and optimizations in liblevenshtein-rust.
This documentation provides in-depth coverage of all algorithmic layers, complete with theory, diagrams, usage examples, performance analysis, and references to academic literature.
liblevenshtein-rust is a high-performance fuzzy string matching library based on Levenshtein automata. It combines multiple algorithmic layers to provide fast approximate string matching against large dictionaries.
The library is organized into 9 distinct algorithmic layers:
┌─────────────────────────────────────────────────────────┐
│ Application Layer (Your Code) │
├─────────────────────────────────────────────────────────┤
│ 8. Caching Layer (LRU, LFU, TTL, etc.) │
├─────────────────────────────────────────────────────────┤
│ 7. Contextual Completion (Scope-aware, Hierarchical) │
├─────────────────────────────────────────────────────────┤
│ 6. Zipper Navigation (Functional Traversal) │
├─────────────────────────────────────────────────────────┤
│ 3. Intersection/Traversal (Query Iterators) │
├─────────────────────────────────────────────────────────┤
│ 2. Levenshtein Automata (Finite State Machines) │
├─────────────────────────────────────────────────────────┤
│ 1. Dictionary Layer (Tries, DAWGs, Suffix Automata) │
├─────────────────────────────────────────────────────────┤
│ 9. Value Storage (Term → Value Mappings) │
├─────────────────────────────────────────────────────────┤
│ 5. SIMD Optimization (Vectorized Hot Paths) │
├─────────────────────────────────────────────────────────┤
│ 4. Distance Calculation (Direct DP Algorithms) │
└─────────────────────────────────────────────────────────┘
use liblevenshtein::prelude::*;
// Create dictionary
let dict = DoubleArrayTrie::from_terms(vec![
"apple", "application", "apply", "apricot"
]);
// Fuzzy search with max distance 2
let results: Vec<String> = dict
.fuzzy_search("aple", 2)
.collect();
// Results: ["apple", "apply"]
// Dictionary with associated values
let dict = DoubleArrayTrie::from_terms_with_values(vec![
("apple", 1),
("banana", 2),
("cherry", 3),
]);
// Search with value filtering (10-100x faster!)
let results: Vec<(String, i32)> = dict
.fuzzy_search_filtered("aple", 2, |v| *v < 3)
.collect();
// Results: [("apple", 1)]
// Character-level for proper Unicode
let dict = DoubleArrayTrieChar::from_terms(vec![
"café", "naïve", "中文", "🎉"
]);
// Correct character-level distance
let results: Vec<String> = dict
.fuzzy_search("cafe", 1) // Missing accent = 1 character edit
.collect();
// Results: ["café"]
Purpose: Efficient storage and traversal of term collections
Implementations:
Key Topics:
Purpose: Finite state machines for approximate string matching
Algorithms:
Core Concepts:
(term_index, accumulated_cost, kind, auxiliary_payload)Purpose: Exact trie search when a contiguous query or dictionary gap pays one opening cost plus a per-symbol extension cost.
Coverage: Gotoh recurrence, exact fixed-point costs, three position layers, B-4 subsumption, layer-aware completion, operation-derived windows, Rust API, security guidance, independent formal models, generated properties, and benchmark protocol.
Purpose: Exact trie search under history-composing adjacent transpositions.
Coverage: Lowrance–Wagner recurrence, bounded streaming macro, kind-aware subsumption, literate pseudocode, resource policy, Rust usage, formal invariants, generated properties, and corpus evidence.
Performance:
\mathcal{O}(kn)$ vs $\mathcal{O}(n^{2})$ batchPurpose: Operation-driven acceptance for runtime weighted and multi-scalar operation sets
Core properties:
Purpose: Independent reference algorithms and conformance harnesses for alignment-expressible presets
Core properties:
Purpose: Execute queries by traversing Dictionary × Automaton
Query Types:
Key Topics:
Purpose: Exact bounded Levenshtein distance from a dictionary term to a regular language
Key Topics:
LanguageAutomaton<U>k+1$ cost frontierPurpose: Direct string distance computation (non-automaton approach)
Algorithms:
\mathcal{O}(mn)$ time, $\mathcal{O}(\min(m,n))$ spaceUse Cases:
Purpose: Vectorize hot paths for 20-64% performance gains
Optimized Operations:
\ge 16$ charsKey Topics:
Purpose: Functional, context-preserving traversal of data structures
Pattern: Huet's Zipper (1997) - functional navigation with context
Implementations:
DictZipper: Navigate dictionariesValuedDictZipper: Access values during navigationAutomatonZipper: Track automaton stateIntersectionZipper: Compose dictionary + automatonUse Cases:
Purpose: Scope-aware, hierarchical code completion
Components:
Use Cases:
Purpose: Query result caching with configurable eviction
Eviction Policies:
Features:
Purpose: Associate arbitrary data with dictionary terms (fuzzy maps)
Architecture:
Terms → States (via transitions) → Values (via state index)
Example:
"apple" → state 5 → value: Some(1)
"app" → state 3 → value: None (not final)
Implementation:
values: Arc<Vec<Option<V>>> indexed by state numberSome(value)Use Cases:
Key Topics:
| Backend | Construction | Exact Match | Distance 1 | Distance 2 | Memory |
|---|---|---|---|---|---|
| DoubleArrayTrie | 3.2ms | 6.6µs | 12.9µs | 16.3µs | 8 bytes/char |
| DynamicDawg | 4.1ms | 19.8µs | 319µs | 2,150µs | ~12 bytes/char |
| PathMap | 3.5ms | 71.1µs | 888µs | 5,919µs | Variable |
| Component | Scalar | AVX2 | Speedup |
|---|---|---|---|
| Characteristic Vector | 100% | 3-4x | 300-400% |
Distance Matrix ($\ge 16$ chars) | 100% | 1.2-1.3x | 20-30% |
| Overall Workload | 100% | 1.2-1.64x | 20-64% |
| Selectivity | Post-Filter | During-Traversal | Speedup |
|---|---|---|---|
| 10% | 100ms | 10ms | 10x |
| 1% | 100ms | 1ms | 100x |
Need to remove terms?
├─ YES → DynamicDawg (thread-safe insert/remove)
└─ NO
├─ Unicode text?
│ ├─ YES → DoubleArrayTrieChar (character-level)
│ └─ NO → DoubleArrayTrie ⭐ (recommended)
│
└─ Substring search?
└─ YES → SuffixAutomaton (infix matching)
Autocomplete / Spell Checking
DoubleArrayTrieStandard (distance 1-2)OrderedQueryIterator (top-10 results)Typo Tolerance
DoubleArrayTrieTransposition (keyboard errors)QueryIterator (all matches)International Text
DoubleArrayTrieCharStandard or TranspositionCode Completion (Scope-aware)
DoubleArrayTrie with scope IDsStandardValueFilteredQueryIterator (10-100x faster)Full-Text Search
SuffixAutomatonStandardQueryIteratorLive Dictionary Updates
DynamicDawg (thread-safe)Schulz & Mihov (2002) - "Fast string correction with Levenshtein automata"
Blumer et al. (1985) - "The smallest automaton recognizing the subwords of a text"
Aoe (1989) - "An Efficient Digital Search Algorithm by Using a Double-Array Structure"
Damerau (1964) - "A technique for computer detection and correction of spelling errors"
Wagner & Fischer (1974) - "The String-to-String Correction Problem"
Huet (1997) - "The Zipper"
Gotoh (1982) - "An improved algorithm for matching biological sequences"
See the complete reference list for more papers and resources.
By Layer:
By Topic:
Quick Links:
Found an issue or have suggestions? See CONTRIBUTING.md for guidelines on improving this documentation.
Documentation is licensed under CC BY 4.0. Code examples are licensed under the same license as the library (MIT or Apache 2.0).
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 |