Comprehensive reference for implementation, performance, and user-facing terminology
Last Updated: 2026-08-01 · Version: 0.9.1
This glossary covers implementation details, performance optimizations, data structures, and user-facing features in liblevenshtein-rust.
For theoretical algorithm concepts (Position, Subsumption, Characteristic Vectors, etc.), see the Levenshtein Automata Glossary.
Crate-boundary note. Since v0.9.0 the dictionary backends were extracted to the sibling
libdictensteincrate and are re-exported here as#[deprecated]shims. Some entries below still reference historicalsrc/dictionary/…paths; those implementations now live inlibdictenstein. Terminology introduced after the 2025-01 revision — phonetics, time-series (MSM), the universal/generalized automaton variants, the.llev/.llreDSLs, and the formal-verification vocabulary — is collected in the Terminology added since 2025 section.
Categories: [Algorithm], [Edit Operations], [Mathematics]
Definition: A contiguous run of symbols consumed from only one input whose
cost is $G(r)=g_o+r g_e$ for run length $r>0$. The gap-open cost
$g_o$ is paid once per run; the gap-extension cost $g_e$ is paid for
each symbol, including the first. The lazy automaton remembers whether a query
gap or dictionary gap is already open, so extension does not pay $g_o$
again.
Implementation: AffineGapParams converts decimal costs to exact scaled
integers. AffineV maps Gotoh's $M$, $I_x$, and $I_y$ matrices to
Normal, AffineQueryGap, and AffineDictGap positions.
Code: src/transducer/variants/affine.rs
· Algorithm: Affine-gap dictionary automata
· See also: Automaton variant, CostScale, Subsumption
A compile-time policy that defines successor generation, epsilon closure,
subsumption, completion cost, and characteristic-vector windowing for one lazy
automaton family. The public Algorithm remains a runtime selector, but Phase 5
chooses its AutomatonVariant once per dictionary edge.
Categories: [Performance], [Memory]
Definition: Optimization technique using Arc<Vec<T>> to share path data between dictionary nodes without cloning, eliminating expensive allocation during tree traversal.
Benefits:
\mathcal{O}(\text{depth})$ cloning overheadUsed in: PathMapDictionary, DictZipper implementations
Code: src/dictionary/pathmap.rs (now in the libdictenstein crate)
See also: SmallVec, Lazy Edge Iteration
Categories: [Performance], [Memory], [Data Structure]
Definition: Memory allocation strategy where objects are allocated from a pre-allocated memory block (arena) and freed all at once when the arena is dropped, avoiding per-object deallocation overhead.
Benefits:
Trade-offs:
Used in: Transducer state/position pools
Code: src/transducer/pool.rs, src/transducer/pool_f64.rs
See also: State Pool, Memory Pressure
Categories: [Algorithm], [Data Structure], [Performance]
Definition: Automatic DAWG minimization triggered when the graph size exceeds a configured growth threshold, maintaining compact representation during bulk insertions.
Configuration: Set threshold ratio (e.g., 1.5 = minimize at 50% growth)
Benefits:
Trade-offs:
Used in: DynamicDawg
Code: src/dictionary/dynamic_dawg.rs (now in the libdictenstein crate)
See also: Suffix Sharing, Bloom Filter
Categories: [Performance], [SIMD]
Definition: Advanced Vector Extensions - Intel/AMD SIMD instruction sets enabling parallel operations on 256-bit (AVX2) or 512-bit (AVX-512) registers.
Usage in Project:
Detection: Runtime CPU feature detection via is_x86_feature_detected!
Performance: 30-64% speedup on supported CPUs
Code: src/transducer/simd/
See also: SSE4.1, Vectorization, Scalar Fallback
Categories: [Data Structure], [Algorithm]
Definition: Core arrays in double-array trie implementation. BASE stores the base index for state transitions, CHECK stores parent state for validity verification.
Algorithm:
transition(state, char) = BASE[state] + char
if CHECK[result] == state: valid transition
Benefits:
\mathcal{O}(1)$ state transitions via array indexingUsed in: DoubleArrayTrie, DoubleArrayTrieChar
Code: src/dictionary/double_array_trie.rs (now in the libdictenstein crate)
See also: Double-Array Trie, Cache Locality
Categories: [Data Structure], [Performance]
Definition: Probabilistic data structure for fast membership testing with no false negatives but possible false positives. Used to accelerate contains() operations in DynamicDawg.
Performance:
contains() operationsConfiguration: Set expected capacity (e.g., 10,000 terms)
Trade-offs:
Used in: DynamicDawg
Code: src/dictionary/dynamic_dawg.rs (now in the libdictenstein crate)
See also: Auto-Minimization, Contains Operations
Categories: [Unicode], [Algorithm]
Definition: Fundamental distinction in how strings are processed for distance calculations.
Byte-Level: Treats each UTF-8 byte as a unit
Character-Level: Treats each Unicode character as a unit
When to Use:
Performance: Character-level adds ~5% overhead for UTF-8 decoding
Code: src/dictionary/double_array_trie_char.rs (now in the libdictenstein crate)
See also: UTF-8 Decoding, CharUnit Trait, Monomorphization
Categories: [Performance], [Memory]
Definition: Property where data accessed together is stored close in memory, minimizing cache misses and improving CPU cache hit rates.
Impact in Project:
Performance Difference: 3-30x speedup for DAT vs PathMap queries
Measurement: Use perf stat -e cache-references,cache-misses to measure
Code: All dictionary implementations
See also: Double-Array Trie, Arena Allocation, BASE and CHECK Arrays
Categories: [API], [Unicode], [Data Structure]
Definition: Abstraction trait enabling generic implementations over both u8 (bytes) and char (Unicode characters), allowing byte-level and character-level dictionaries to share code.
Methods:
from_bytes() - Parse from UTF-8to_bytes() - Serialize to UTF-8Benefits:
Used in: All dictionary backends (generic over L: CharUnit)
Code: src/dictionary/char_unit.rs (now in the libdictenstein crate)
See also: Byte-Level vs Character-Level, Monomorphization
Categories: [API], [Algorithm], [Data Structure]
Definition: State snapshotting mechanism in ContextualCompletionEngine allowing undo/redo operations for draft text, enabling editor integrations with time-travel debugging.
Operations:
checkpoint() - Save current draft state (~116 ns)undo() - Restore to previous checkpointUse Cases:
Performance: Sub-microsecond checkpoint creation
Code: src/contextual/engine.rs
See also: Draft State, Contextual Completion, Incremental Typing
Categories: [API], [Algorithm]
Definition: Hierarchical scope-aware completion system providing fuzzy matching within lexical scopes (global → module → function → block), with separate draft and finalized term spaces.
Key Concepts:
Performance:
Use Cases:
Code: src/contextual/
See also: Hierarchical Visibility, Draft State, Scope-Aware Completion
Categories: [Caching], [Performance]
Definition: Cache eviction policy that considers both access frequency and computational cost of regenerating entries, prioritizing retention of expensive-to-recompute items.
Algorithm: Score = frequency × regeneration_cost
Benefits:
Trade-offs:
Used in: Planned for FuzzyMap caching
Code: src/cache/eviction/cost_aware.rs
See also: LRU, LFU, Memory Pressure Eviction
Categories: [Algorithm], [Edit Operations]
Definition: An unrestricted edit-script metric that includes adjacent transpositions in addition to insertion, deletion, and substitution. An edit may act on the output of an earlier edit. This is different from optimal string alignment (OSA), which forbids editing the same substring twice.
Example:
Use Cases:
Implementation: Algorithm::DamerauLevenshtein selects the unrestricted,
history-carrying unit-cost automaton;
damerau_levenshtein_distance is its full last-occurrence DP oracle.
Algorithm::Transposition remains OSA. The distinction is observable on
"CA" → "ABC": unrestricted Damerau–Levenshtein costs 2, whereas OSA costs
3. The compact pending delta supports budgets through 255; 1–3 is the
measured practical search range.
Reference: Lowrance and Wagner, “An Extension of the String-to-String Correction Problem,” Journal of the ACM 22(2), 1975. doi:10.1145/321879.321880
See also: Optimal String Alignment, Transposition, Edit Operations, Standard Algorithm
Categories: [Algorithm], [Dynamic Programming]
Definition: The map used by unrestricted Damerau–Levenshtein dynamic programming to remember the most recent row at which each alphabet symbol occurred. Together with the most recent matching target column, it identifies the opposite endpoints of a transposition macro.
The reference DP stores the complete table. The bounded dictionary automaton
does not: its joint budget bound permits one DamerauPending position to carry
only the currently owed positive endpoint delta.
See also: Damerau–Levenshtein Distance, Position kind
Categories: [Algorithm], [Edit Operations]
Definition: The restricted adjacent-transposition recurrence implemented
by Algorithm::Transposition and transposition_distance. Each substring may
be edited at most once. OSA is symmetric and non-negative, but it is not a
metric because the triangle inequality fails:
d_{\mathrm{OSA}}(\texttt{CA},\texttt{ABC}) = 3
> d_{\mathrm{OSA}}(\texttt{CA},\texttt{AC})
+ d_{\mathrm{OSA}}(\texttt{AC},\texttt{ABC}) = 2.
Indexing consequence: Do not use OSA with a BK-tree, VP-tree, or any other index whose pruning proof assumes the triangle inequality. A trie walker with an independently admissible lower bound may still be sound.
Code: src/distance/mod.rs and
src/transducer/transition.rs
See also: Damerau–Levenshtein Distance, Transposition, Metric
Categories: [Data Structure], [Performance]
Definition: Concurrent HashMap implementation providing lock-free reads and fine-grained write locking, used for thread-safe caching without global locks.
Benefits:
Used in: Fuzzy cache implementations, concurrent query caching
Code: External dependency, used in src/cache/
See also: Thread-Safe Interior Mutability, RwLock
Categories: [Data Structure], [Algorithm]
Definition: Space-efficient trie variant where common suffixes are shared through node merging, creating a directed acyclic graph structure.
Properties:
Variants in Project:
The classic static
DawgDictionaryand the arena-optimizedOptimizedDawgvariants were removed in the 0.9.x line; useDynamicDawgfor the DAWG structure orDoubleArrayTriefor a static, read-optimized dictionary.
Memory: ~24-48 bytes per state (depending on variant)
Code: src/dictionary/dawg.rs (now in the libdictenstein crate)
See also: Trie, Suffix Sharing, Auto-Minimization
Categories: [Data Structure], [Algorithm], [Performance]
Definition: Trie implementation using two parallel arrays (BASE and CHECK) for $\mathcal{O}(1)$ state transitions with excellent cache locality.
Structure:
Benefits:
\mathcal{O}(1)$ transitions: Array indexing, no pointer chasingVariants:
Trade-offs:
Code: src/dictionary/double_array_trie.rs (now in the libdictenstein crate)
See also: BASE and CHECK Arrays, Cache Locality, Dictionary Automaton
Categories: [API], [Algorithm]
Definition: Temporary, uncommitted text in ContextualCompletionEngine representing incremental typing (e.g., "local_var" while user is still typing) that exists separately from the finalized dictionary.
Properties:
finalize()Use Cases:
Performance: ~4 µs per character insertion
Code: src/contextual/draft.rs
See also: Finalized State, Checkpoint System, Incremental Typing
Categories: [Data Structure], [API]
Definition: DAWG variant supporting runtime insert, remove, and minimize operations with thread-safe access via RwLock.
Features:
Performance Optimizations:
Use Cases:
Code: src/dictionary/dynamic_dawg.rs (now in the libdictenstein crate)
See also: DAWG, Auto-Minimization, Bloom Filter, Thread-Safe Interior Mutability
Categories: [Performance], [SIMD]
Definition: SIMD-accelerated operation that scans dictionary edge labels in parallel to find matching characters, using vectorized comparisons.
Implementation:
Performance: 20-40% faster edge iteration for high-degree nodes
Threshold: Enabled for nodes with 16+ children (empirically tuned)
Code: src/dictionary/simd/edge_lookup.rs (now in the libdictenstein crate)
See also: AVX2, Vectorization, Threshold Tuning
Categories: [Algorithm]
Definition: Fundamental string transformation operations used to measure Levenshtein distance.
Standard Operations (Algorithm::Standard):
Extended Operations:
Code: src/transducer/transition.rs
See also: Levenshtein Distance, Damerau-Levenshtein Distance, Algorithm Variants
Categories: [Caching], [Performance]
Definition: Strategy for removing entries from a cache when capacity is reached, determining which entries to discard.
Policies Implemented:
Code: src/cache/eviction/
See also: LRU, LFU, TTL, Cost-Aware Eviction, Memory Pressure Eviction
Categories: [API], [Algorithm]
Definition: Committed, permanent terms in ContextualCompletionEngine that are visible across contexts according to hierarchical visibility rules, as opposed to draft state which is context-local.
Properties:
Creation: Call finalize() on a context with draft state
Code: src/contextual/engine.rs
See also: Draft State, Hierarchical Visibility, Contextual Completion
Categories: [API], [Data Structure]
Definition: Dictionary-like data structure supporting approximate key lookups using Levenshtein distance, returning values for keys within specified edit distance.
Example:
map.get("appl", 1) // Returns value for "apple"
Variants:
Performance: 10-100x faster with during-traversal value filtering vs post-filtering
Use Cases:
Code: src/cache/multimap.rs
See also: Value Filtering, Levenshtein Distance, Term-Value Mapping
Categories: [Algorithm], [API]
Definition: Scope visibility rules in ContextualCompletionEngine where child contexts can see parent terms but not sibling or descendant terms, modeling lexical scoping.
Example:
Global (terms: std::vector, std::string)
└─ Function (terms: parameter, result)
└─ Block (terms: local_var)
From Block: can see local_var, parameter, result, std::vector, std::string From Function: can see parameter, result, std::vector, std::string (NOT local_var)
Implementation: Context tree with upward traversal
Code: src/contextual/engine.rs
See also: Contextual Completion, Scope-Aware Completion, Context Tree
Categories: [Algorithm], [Performance]
Definition: Technique from Chapter 6 of Schulz & Mihov (2002) paper that simulates Levenshtein automaton LEV_n(W) without explicit construction, generating states on-demand during dictionary traversal.
Benefits:
\mathcal{O}(\lvert W\rvert)$ space instead of potentially $\mathcal{O}(4^{n})$ for materialized automatonImplementation: On-the-fly state generation in QueryIterator
Code: src/transducer/query.rs (Lines 86-188)
See also: Levenshtein Automaton, Lazy Evaluation, Parallel Traversal
Categories: [API], [Performance]
Definition: Character-by-character text input handling in ContextualCompletionEngine, updating draft state and providing real-time completion suggestions.
Performance:
Features:
Use Cases:
Code: src/contextual/engine.rs
See also: Draft State, Contextual Completion, Checkpoint System
Categories: [Performance], [Algorithm]
Definition: Zero-copy edge iteration strategy in PathMap that avoids allocating child vectors, instead providing iterators directly over internal data structures.
Benefits:
Implementation: Return impl Iterator over internal edge storage
Code: src/dictionary/pathmap.rs (now in the libdictenstein crate)
See also: Arc Path Sharing, Zero-Copy
Categories: [Algorithm], [Performance]
Definition: Evaluation strategy where query results are computed on-demand as the iterator is consumed, rather than materializing all results upfront.
Benefits:
\mathcal{O}(1)$ for iterator state)Implementation: QueryIterator and OrderedQueryIterator are lazy iterators
Code: src/transducer/query.rs
See also: Imitation Method, Iterator Pattern
Categories: [Algorithm]
Definition: Edit distance metric measuring the minimum number of single-character edits (insertions, deletions, substitutions) required to transform one string into another.
Example: distance("kitten", "sitting") = 3
Variants:
Code: Core algorithm spans src/transducer/
See also: Edit Operations, Damerau-Levenshtein Distance, Wagner-Fischer Algorithm
Categories: [Caching], [Performance]
Definition: Cache eviction policy that removes entries with the lowest access count when capacity is reached.
Benefits:
Trade-offs:
Implementation: Access counter per entry
Code: src/cache/eviction/lfu.rs
See also: LRU, Eviction Policy, Cost-Aware Eviction
Categories: [Caching], [Performance]
Definition: Cache eviction policy that removes the entry with the oldest last-access time when capacity is reached.
Benefits:
Trade-offs:
Implementation: Timestamp tracking per entry
Code: src/cache/eviction/lru.rs
See also: LFU, Eviction Policy, Temporal Locality
Categories: [Caching], [Performance], [Memory]
Definition: Adaptive cache eviction policy that monitors system memory availability and aggressively evicts entries when memory pressure is high.
Benefits:
Implementation:
Code: src/cache/eviction/memory_pressure.rs
See also: Eviction Policy, LRU, System Memory Monitoring
Categories: [Performance], [Unicode]
Definition: Rust compiler optimization that generates specialized code for each concrete type used with a generic function, enabling zero-cost abstractions.
Impact in Project:
u8 and char variantsTrade-off: Increased binary size (duplicate code for each type)
Code: All generic dictionary implementations over L: CharUnit
See also: CharUnit Trait, Byte-Level vs Character-Level, Zero-Cost Abstraction
Categories: [API], [Algorithm]
Definition: Query variant that returns results sorted by edit distance first, then lexicographically, using priority queue-based traversal.
Example Output:
Query: "aple", distance 2
Results (in order):
- "ape" (distance 1)
- "apple" (distance 1)
- "apply" (distance 2)
Implementation: query_ordered() returns OrderedQueryIterator
Performance: Slightly slower than unordered due to priority queue overhead
Code: src/transducer/query_ordered.rs
See also: Query Iterator, Lazy Evaluation
The one-byte PositionKind tag that identifies a frontier representative's
continuation language: normal, OSA transposition, split, affine gap, or pending
true-Damerau state. Together with the aux payload, it prevents distinct
unfinished operations from colliding in state ordering and subsumption.
For DamerauPending, aux is a positive endpoint delta. The macro has prepaid
the transposition and query-interior deletions; it may extend over dictionary
interior units and resolve only when the opposite endpoint matches.
Categories: [Algorithm], [Performance]
Definition: Simultaneous navigation of dictionary automaton A^D and Levenshtein automaton LEV_n(W), advancing through both in lockstep during query execution.
Algorithm:
dict_node = dictionary.root()
automaton_state = initial_state()
for each dict_edge in dictionary:
dict_node' = follow_edge(dict_node, char)
automaton_state' = transition(automaton_state, char)
if both_accepting(dict_node', automaton_state'):
yield current_word
Complexity: $\mathcal{O}(\lvert D\rvert)$ where $\lvert D\rvert$ is total dictionary edges
Code: src/transducer/query.rs
See also: Imitation Method, Dictionary Automaton, Levenshtein Automaton
Categories: [Data Structure], [API]
Definition: High-performance trie implementation with structural sharing and zero-copy path access, supporting dynamic updates through interior mutability.
Features:
Performance:
Variants:
Code: src/dictionary/pathmap.rs (now in the libdictenstein crate)
See also: Arc Path Sharing, Lazy Edge Iteration, Dynamic DAWG
Categories: [Performance]
Definition: Compiler optimization technique using runtime profiling data to guide code generation, optimizing hot paths and reducing cold path overhead.
Usage:
# Generate profile
RUSTFLAGS="-C profile-generate=/tmp/pgo" cargo build --release
./target/release/liblevenshtein benchmark
# Use profile
RUSTFLAGS="-C profile-use=/tmp/pgo -C llvm-args=-pgo-warn-missing-function" cargo build --release
Benefits: 10-15% performance improvement on hot query paths
Code: Build system only (no source changes)
See also: Performance Optimization, Benchmarking
Categories: [Algorithm], [SIMD]
Definition: SIMD-accelerated operation checking if one position subsumes another ($i\#e \sqsubseteq j\#f$), processing multiple positions in parallel.
Subsumption Rule: $i\#e \sqsubseteq j\#f \iff (e < f) \land (\lvert j-i\rvert \le f-e)$
Vectorization: Load 4-8 positions, perform parallel comparisons
Performance: 40-60% faster subsumption checking in state operations
Code: src/transducer/simd/subsumption.rs
See also: Subsumption (theory glossary), AVX2, State Operations
Categories: [Algorithm], [API]
Definition: Technique in ContextualCompletionEngine that searches both draft and finalized term spaces simultaneously in a single traversal, avoiding separate queries.
Benefits:
Implementation: Unified search with is_draft flag in results
Code: src/contextual/engine.rs
See also: Draft State, Finalized State, Contextual Completion
Categories: [API], [Algorithm]
Definition: Lazy iterator implementing the Imitation Method, generating fuzzy matching results on-demand through parallel traversal of dictionary and Levenshtein automaton.
Methods:
query(term, distance) → basic iteratorquery_with_distance(term, distance) → includes distance in resultsquery_ordered(term, distance) → sorted resultsPerformance: $\mathcal{O}(\lvert D\rvert)$ traversal, constant memory
Code: src/transducer/query.rs
See also: Lazy Evaluation, Parallel Traversal, Imitation Method
Categories: [Algorithm], [Navigation]
Definition: Property of zipper navigation where operations produce new zippers without modifying existing ones, enabling safe concurrent access and time-travel debugging.
Benefits:
Implementation: All zipper operations return new zipper instances
Code: src/dictionary/pathmap_zipper.rs (now in the libdictenstein crate)
See also: Zipper Pattern, Immutable Navigation
Categories: [Performance], [SIMD]
Definition: Technique for detecting available SIMD instruction sets at runtime, enabling adaptive code paths based on CPU capabilities.
Implementation:
if is_x86_feature_detected!("avx2") {
// Use AVX2 implementation
} else if is_x86_feature_detected!("sse4.1") {
// Use SSE4.1 implementation
} else {
// Use scalar fallback
}
Benefits:
Code: src/transducer/simd/mod.rs
See also: AVX2, SSE4.1, Scalar Fallback
Categories: [Performance], [API]
Definition: Synchronization primitive allowing multiple concurrent readers OR single writer, used for thread-safe dictionary access in dynamic backends.
Benefits:
Trade-offs:
Used in: DynamicDawg, SuffixAutomaton, Scdawg, PathMapDictionary, BijectiveMap (the ExternalSync backends)
Code: parking_lot::RwLock by default (via libdictenstein's sync_compat); std::sync::RwLock is the WASM / no-parking_lot fallback
See also: Thread-Safe Interior Mutability, DashMap, Dynamic DAWG
Categories: [Performance], [SIMD]
Definition: Non-vectorized implementation serving as fallback when SIMD instructions are unavailable or inappropriate (e.g., small data sizes).
Usage:
Performance: Typically 2-3x slower than SIMD, but still optimized scalar code
Code: All SIMD modules include scalar fallback paths
See also: Runtime CPU Feature Detection, AVX2, SSE4.1
Categories: [API], [Algorithm]
Definition: Completion system that respects lexical scoping rules, only suggesting terms visible in the current scope based on hierarchical visibility.
Example:
global scope: std::vector, std::string
function scope: parameter, result
block scope: local_var
Query in block: sees all three scopes
Query in function: sees function + global (NOT block)
Implementation: Context tree with upward traversal
Code: src/contextual/engine.rs
See also: Hierarchical Visibility, Contextual Completion, Context Tree
Categories: [Performance], [Memory]
Definition: Optimization data structure that stores small collections inline (on stack) and spills to heap only when size exceeds threshold, reducing allocations for common small sizes.
Configuration: SmallVec<[T; N]> where N is inline capacity
Benefits:
\le N$Used in: State storage, edge lists, position vectors
Code: External dependency, used throughout src/transducer/
See also: Arena Allocation, Memory Pressure
Categories: [Algorithm], [Performance]
Definition: Optimization in DynamicDawg where inserting pre-sorted terms enables efficient construction without repeated minimization.
Algorithm:
Performance: 30-50% faster for bulk inserts (1000+ terms)
Code: src/dictionary/dynamic_dawg.rs (now in the libdictenstein crate)
See also: Auto-Minimization, Dynamic DAWG
Categories: [Performance], [SIMD]
Definition: Streaming SIMD Extensions 4.1 - Intel/AMD instruction set enabling parallel operations on 128-bit registers (4x f32 or 4x i32).
Usage in Project:
Detection: Runtime CPU feature detection
Performance: 20-30% speedup vs scalar
Code: src/transducer/simd/
See also: AVX2, Vectorization, Scalar Fallback
Categories: [Performance], [Memory], [Data Structure]
Definition: Object pool pattern for reusing allocated state objects (Position sets) across queries, eliminating allocation overhead in hot paths.
Benefits:
Usage: Pass &mut StatePool to query operations
Code: src/transducer/state_pool.rs
See also: Arena Allocation, Memory Pressure
Categories: [Data Structure], [Algorithm]
Definition: Trie variant optimized for substring/infix matching, where any path through the automaton represents a valid substring.
Use Cases:
Variants:
Trade-offs:
.prefix() unavailable)Code: src/dictionary/suffix_automaton.rs (now in the libdictenstein crate)
See also: DAWG, Trie, Infix Matching
Categories: [Algorithm], [Data Structure]
Definition: DAWG optimization where nodes with identical right-languages (same set of possible continuations) are merged, reducing memory usage.
Example:
"cat" and "bat" share suffix "at"
"testing" and "resting" share suffix "esting"
Benefits:
Used in: All DAWG variants
Code: src/dictionary/dynamic_dawg.rs (now in the libdictenstein crate)
See also: DAWG, Auto-Minimization
Categories: [Performance], [Caching]
Definition: Property where recently accessed data is likely to be accessed again soon, exploited by LRU caching and CPU cache management.
Impact:
Measurement: Cache hit rate over time
See also: Cache Locality, LRU, Eviction Policy
Categories: [API], [Data Structure]
Definition: Association of values with dictionary terms, enabling fuzzy lookup of metadata alongside approximate string matching.
Example:
dict.insert_with_value("apple", 42);
dict.insert_with_value("application", vec![1, 2, 3]);
Supported Backends:
Common Value Types:
u32, u64HashSet<u32>Code: All dictionary implementations with generic V parameter
See also: Fuzzy Map, Value Filtering
Categories: [API], [Performance]
Definition: Pattern using RwLock or similar primitives to enable concurrent read access and exclusive write access to shared data structures.
Implementation:
Arc<RwLock<Dictionary>>
Benefits:
Used in: DynamicDawg, PathMapDictionary
Code: All dynamic dictionary backends
See also: RwLock, DashMap, Dynamic DAWG
Categories: [Performance], [SIMD]
Definition: Data-driven optimization technique where SIMD algorithms are enabled only above empirically determined data size thresholds, below which scalar code is faster due to setup overhead.
Example: Edge label scanning uses SIMD only for 16+ edges
Methodology:
Benefits:
Code: All SIMD implementations include threshold checks
See also: Runtime CPU Feature Detection, Scalar Fallback
Categories: [Algorithm], [Edit Operations]
Definition: Edit operation swapping two adjacent characters, implemented
by Algorithm::Transposition as optimal string alignment (restricted Damerau),
not unrestricted Damerau–Levenshtein distance.
Example: "teh" → "the" (transpose 'e' and 'h')
Cost: 1 edit operation
Implementation: Uses special t-position (i#e_t) to track transposition state
Code: src/transducer/transition.rs (Table 7.1, Lines 195-319)
See also: Optimal String Alignment, Damerau–Levenshtein Distance, Edit Operations, t-position (theory glossary)
Categories: [Caching], [Performance]
Definition: Cache eviction policy that removes entries after a fixed duration from insertion, regardless of access patterns.
Configuration: Set expiration duration (e.g., 5 minutes)
Use Cases:
Trade-offs:
Code: src/cache/eviction/ttl.rs
See also: LRU, Age-Based Eviction, Eviction Policy
Categories: [Unicode], [Performance]
Definition: Process of parsing multi-byte UTF-8 sequences into Unicode code points (char values) for character-level dictionary operations.
Performance Impact:
Implementation: Rust's built-in str::chars() iterator
Used in: All *Char dictionary variants
Code: src/dictionary/char_unit.rs (now in the libdictenstein crate)
See also: Byte-Level vs Character-Level, CharUnit Trait, Monomorphization
Categories: [API], [Performance]
Definition: Optimization technique filtering dictionary entries during traversal based on associated values, dramatically faster than post-filtering results.
Example:
// Filter by scope ID during traversal (10-100x faster)
transducer.query_by_value_set("var", 1, &visible_scopes)
// vs post-filtering (slow)
transducer.query("var", 1).filter(|t| visible_scopes.contains(&t.scope))
Performance: 10-100x speedup by pruning traversal early
Use Cases:
Code: src/transducer/query.rs
See also: Term-Value Mapping, Fuzzy Map, Scope-Aware Completion
Categories: [Performance], [SIMD]
Definition: Optimization technique using SIMD instructions to process multiple data elements in parallel with a single instruction.
Example: Compare 16 characters simultaneously with AVX2
Benefits:
Implementation: Manual SIMD intrinsics in hot paths
Code: src/transducer/simd/
See also: AVX2, SSE4.1, SIMD
Categories: [Algorithm]
Definition: Dynamic programming algorithm for computing Levenshtein distance using a $(\lvert W\rvert+1) \times (\lvert V\rvert+1)$ matrix where cell $[i,j]$ contains distance between $W[0..i]$ and $V[0..j]$.
Complexity: $\mathcal{O}(\lvert W\rvert \times \lvert V\rvert)$ time, $\mathcal{O}(\lvert W\rvert \times \lvert V\rvert)$ space ($\mathcal{O}(\min(\lvert W\rvert, \lvert V\rvert))$ with optimization)
Relation to Project: Levenshtein automata achieve $\mathcal{O}(\lvert D\rvert)$ by avoiding per-word distance computation
Code: Not directly implemented (automata approach avoids this)
See also: Levenshtein Distance, Parallel Traversal
Categories: [Performance], [API]
Definition: Programming language feature where high-level abstractions compile to the same machine code as hand-written low-level code, with no runtime overhead.
Examples in Project:
Rust Guarantee: Abstraction incurs no additional runtime cost vs manual implementation
Code: All generic code over L: CharUnit or V: DictionaryValue
See also: Monomorphization, CharUnit Trait
Categories: [Performance], [Memory]
Definition: Optimization avoiding data copying by using references, views, or sharing mechanisms.
Examples in Project:
Benefits:
Code: PathMap lazy edge iteration, Arc path sharing
See also: Lazy Edge Iteration, Arc Path Sharing
Categories: [Navigation], [Algorithm], [Data Structure]
Definition: Functional data structure pattern (from Huet 1997) providing efficient cursor-based tree navigation with context preservation, enabling immutable updates and backtracking.
Properties:
\mathcal{O}(1)$ navigation operationsVariants in Project:
Use Cases:
Code:
src/dictionary/pathmap_zipper.rs (now in the libdictenstein crate)src/transducer/intersection_zipper.rsSee also: Referential Transparency, Immutable Navigation, Context-Preserving Traversal
The terms below cover subsystems introduced or substantially expanded after the 2025-01 revision. Each is defined before use elsewhere in the documentation.
Categories: [Algorithm], [Time Series]
Definition: A sequence measure whose dynamic-programming path may advance through its two input axes at different rates. MSM, ERP, TWED, discrete Fréchet, and DTW are elastic measures, although they do not share all metric axioms or the same cost-combination operator.
Categories: [Algorithm], [Architecture], [Time Series]
Definition: The measure-specific policy behind the generic time-series trie walker. It defines relaxed column transitions, exact candidate scoring, candidate lower bounds, query plans, carry state, and empty-side semantics.
Code: src/time_series/elastic/ · Design:
Elastic kernels · See also: Kernel Obligations
K1–K4, Interval Relaxation, CostMonoid
Categories: [Algorithm], [Mathematics], [Time Series]
Definition: Evaluation of a recurrence over a quantization bin
$[\ell,h]$ by replacing each concrete step with its minimum over the bin. It
supports exact pruning only when K1 proves that every relaxed cell lower-bounds
every concrete cell represented by the trie prefix.
Categories: [Formal Verification], [Algorithm]
Definition: K1 is interval-column admissibility; K2 is cost inflation under lawful non-negative steps; K3 is exact survivor scoring; and K4 is candidate-level lower-bound coherence. Together they justify subtree pruning, leaf pruning, and exact emission without assuming the triangle inequality.
Categories: [Data Structure], [Time Series]
Definition: Immutable metadata computed once before an elastic trie walk
and borrowed by every column transition. A banded-DTW plan contains query
envelopes; MSM uses the unit type ().
Categories: [Data Structure], [Time Series]
Definition: Kernel-specific prefix information not encoded in a DP column. MSM carries the previous target bin because its Split recurrence depends on it; ERP and discrete Fréchet require no carry.
Categories: [Testing], [Mathematics], [Time Series]
Definition: The property that replacing every concrete sample $v$ by a
point interval $[v,v]$ reproduces the scalar DP exactly. It complements
admissibility by ruling out bounds that are sound but uselessly weak.
Categories: [Algorithm]
Definition: The default query engine. It simulates the Levenshtein automaton $A(W, k)$ whose states are reduced sets of positions $\langle i, e\rangle$, materialising each state on first visit during the dictionary walk — there is no precompiled DFA. Equivalent to the academic "parameterized automaton" / Schulz–Mihov imitation method.
Code: src/transducer/{query,state,transition,pool}.rs · See also: Imitation Method, Universal Levenshtein Automaton, Generalized Automaton, Characteristic Vector
Categories: [Algorithm]
Definition: A parameter-free deterministic automaton precomputed once for a fixed $k$ and reused for any query word (Mitankin 2005). The crate offers it as an eager alternative to the lazy engine when $k$ is fixed and queries are numerous.
Code: src/transducer/universal/ · See also: Parameterized Automaton, Subsumption
Categories: [Algorithm]
Definition: A runtime-configurable acceptance engine whose edit operations
are supplied as an OperationSet rather than a compile-time marker type. It
evaluates an exact sparse alignment graph: every edge consumes the operation's
declared source and target scalar counts, restricted pairs are checked, and
decimal weights accumulate as scaled integers. It is the differential oracle
for Hamming, indel, bounded-skip, phonetic, and other alignment-expressible
presets; it is not connected to dictionary traversal.
Code: src/transducer/generalized/ · Design: Generalized-automaton repair · See also: Alignment Cell, OperationSet, CostScale, Articulatory Distance
Categories: [Algorithm], [Metric]
Definition: The number of unequal positions in two equal-length sequences.
The string API counts Unicode scalars and returns None for unequal lengths.
Hamming is a metric separately on each fixed-length space; it is not Standard
Levenshtein followed by a length check.
Code: src/distance/hamming.rs · Design: Class-A presets · See also: Indel Distance, OperationSet
Categories: [Algorithm], [Metric]
Definition: Minimum insertion/deletion cost when substitution is absent.
Replacing one scalar costs two, and the value equals
$|x|+|y|-2\operatorname{LCS}(x,y)$, where LCS is longest common subsequence.indel_distance_bounded` returns the exact value only when it does
not exceed the supplied threshold.
Code: src/distance/indel.rs · Design: Class-A presets · See also: Hamming Distance, Bounded Skip
Categories: [Algorithm], [Relation]
Definition: Directional subsequence alignment using only match and source
deletion. For GeneralizedAutomaton::accepts(word, input), input must be a
subsequence of word; the cost is the number of skipped source scalars. This
does not include fzf-style gains, bonuses, or ranking.
Design: Class-A presets · See also: Indel Distance, Generalized Automaton, OperationSet
Categories: [Algorithm], [Data Structure]
Definition: Coordinate $(i,j)$ in the generalized-operation grid,
meaning that the first $i$ dictionary-word scalars and first $j$ input
scalars have been consumed. The sparse frontier stores the least exact scaled
cost for each reachable cell. Every non-empty operation moves to a
lexicographically later cell, giving a topological traversal order.
See also: Generalized Automaton, CostScale
Categories: [Algorithm], [API]
Definition: OperationSet enumerates the edit operations a generalized automaton may apply. SubstitutionSet restricts which character substitutions are permitted (presets: phonetic_basic, keyboard_qwerty, leet_speak, ocr_friendly); SubstitutionPolicy (Unrestricted — a zero-sized default — or Restricted) selects the policy at the type level.
OperationSet::validate() rejects non-progressing or invalid-cost rules,
zero-cost length changes, consumption overflow, and aggregate declared
consumption above 4,096 before generalized traversal.
Code: src/transducer/{algorithm,substitution_set,substitution_policy}.rs · See also: Edit Operations, Restricted Substitutions
Categories: [Algorithm], [Performance]
Definition: Myers' (1999) bit-vector dynamic-programming algorithm computing edit distance in $\mathcal{O}(\lceil m/w\rceil \cdot n)$ for machine word width $w$. standard_distance dispatches to it for short ($\le 64$-byte) ASCII inputs.
Code: src/distance/myers.rs · DOI: 10.1145/316542.316550 · See also: SIMD, Scalar Fallback
Categories: [Algorithm]
Definition: A strategy for large error bounds ($k \ge 5$): split the query into $k + 1$ pieces; by the pigeonhole principle at least one piece is error-free, so it can be located exactly via the SCDAWG and extended/verified. Avoids the state-space blow-up of large-$k$ automata.
Code: src/wallbreaker/ · See also: SCDAWG
Categories: [Data Structure]
Definition: A bidirectional compact DAWG indexing every substring, supporting forward extension and suffix links so a matched region can grow left and right. Backs WallBreaker piece location.
Code: Scdawg / ScdawgChar in libdictenstein · See also: WallBreaker, DAWG
Categories: [Algorithm], [API]
Definition: The ordered accumulation contract used by bounded dynamic
programs. It supplies an identity ZERO, absorbing TOP, associative
combine, total compare, inclusive within, and a non-overridable
minimum-valued select. Its seven laws make minimum-cost dominance and budget
pruning sound. It is intentionally not a semiring or WFST weight interface.
Code: src/cost/ · Design: Ordered cost monoid · See also: CostScale, Subsumption, WFST
Categories: [Algorithm], [API]
Definition: A checked fixed-point denominator that converts the shortest
round-tripping decimal representation of a non-negative finite f64 weight to
an exact usize numerator. A derived scale is the least common multiple of all
reduced operation denominators. Inexact conversion, invalid values, and every
arithmetic overflow are reported as ScaleError; no weight is silently rounded
or truncated.
Code: src/cost/scale.rs · See also: CostMonoid, Generalized Automaton
Categories: [Algorithm]
Definition: A minimax path cost whose accumulation operation is maximum.
The cost of a path is therefore its most expensive step, as in discrete
Fréchet-style dynamic programming. BottleneckCost uses non-negative finite
f64 values plus positive infinity and shares the fixed minimum selection rule
with the other cost monoids.
Code: src/cost/bottleneck.rs · See also: CostMonoid, Discrete Fréchet Distance
Categories: [Unicode], [API]
Definition: A standardized symbol set for the sounds of spoken language; the crate uses IPA for language-agnostic syllabification and articulatory-feature comparison.
Code: src/phonetic/ipa_syllable.rs · See also: Articulatory Feature Distance, Syllabification
Categories: [Algorithm]
Definition: A pronunciation-aware distance in which phonemes are vectors of articulatory features (place and manner of articulation, voicing), and the substitution cost between two phonemes is their feature-vector distance — so /p/↔/b/ (a voicing flip) costs less than /p/↔/k/.
Code: src/phonetic/feature_distance.rs, src/transducer/articulatory_costs.rs · See also: Generalized Automaton, IPA
Categories: [Algorithm], [API]
Definition: Rewriting a term to a canonical phonetic form (via the rule engine, in 53 languages) before fuzzy matching, so that orthographically different but sound-alike terms collide. Exposed as PhoneticNormalizedDictionary(Char).
Code: src/dictionary/phonetic_normalized.rs (now in the libdictenstein crate), src/phonetic/application.rs · See also: Soundex, NFA Product
Categories: [Algorithm]
Definition: Classical phonetic-encoding schemes that map a word to a code approximating its pronunciation, enabling sound-alike grouping. Each has a dedicated reference under docs/phonetic-extraction/.
See also: Phonetic Normalization
\cap$ Levenshtein)Categories: [Algorithm]
Definition: The product of a phonetic-pattern NFA (built by Thompson
construction) with unit-cost Levenshtein edits. For dictionary term $w$ and
the NFA language $L$, it computes $d(w,L)=\min_{v\in L}d(w,v)$. The generic
implementation stores one unioned NFA state set per exact cost.
Code: src/transducer/language/ · See also: Language Automaton, Cost-indexed Frontier, Thompson Construction, .llre
Categories: [Algorithm], [API]
Definition: A finite-state recognizer exposed through set-valued initial,
step, and arbitrary-symbol advance operations. Its transitions distribute
over state-set union. Implementations include SmallDfa<U>, the byte NFA, and
the Unicode-scalar NFA.
Code: src/transducer/language/mod.rs · See also: NFA Product, Relational Image
Categories: [Algorithm], [Data Structure], [Performance]
Definition: A fixed $k+1$-slot product state whose slot $e$ is the union
of all language states reachable at exact edit cost $e. The representation
merges equal-cost histories and bounds frontier storage independently of path
history.
Code: src/transducer/language/product.rs · See also: Frontier Canonicalization, NFA Product
Categories: [Algorithm], [Performance]
Definition: Minimum-cost dominance pass over a cost-indexed frontier. A
language state already present at cheaper level $e$ is removed from every
dearer level $f>e$ because non-negative future edit costs cannot make the
dearer copy improve a continuation.
See also: Cost-indexed Frontier, Subsumption
Categories: [Algorithm]
Definition: For relation $R$ and state set $S$, the target set
$R[S]=\{q'\mid\exists q\in S.\ R(q,q')\}$. Relational image distributes over
union; this is the formal basis for merging equal-cost language-product states.
See also: Language Automaton, Frontier Canonicalization
Categories: [Algorithm]
Definition: The classical construction of an $\varepsilon$-NFA from a
regular expression by structural induction (concatenation, alternation, Kleene
star). It avoids catastrophic backtracking, but NFA size and reachable subset
diversity remain resource surfaces; untrusted query_regex calls enforce a
4,096-state construction ceiling.
Code: src/phonetic/nfa/thompson.rs · See also: .llre, NFA Product
.llevCategories: [API], [Serialization]
Definition: The LibLevenshtein phonetic-rule file format: a source language for phonetic rewrite rule-sets, compiled (lexer → AST → ruleset → compiled) and applied via apply_rules_seq.
Code: src/phonetic/llev/ · grammar: docs/grammar/llev.ebnf · See also: Phonetic Normalization
.llre (LibLevenshtein Regex Expression)Categories: [API]
Definition: A regular-expression file format compiled (lexer → parser → AST → symbol expander → NFA compiler) to an NFA for phonetic/pattern matching. ReDoS-resistant via Thompson/Glushkov construction.
Code: src/phonetic/llre/ · grammar: docs/grammar/llre.ebnf · See also: Thompson Construction, NFA Product
Categories: [API]
Definition: The metasyntax used to specify the .llev, .llre, and regex grammars under docs/grammar/.
See also: .llev, .llre
Categories: [Algorithm], [Time Series], [Mathematics]
Definition: An elastic edit distance for real-valued sequences with one
fixed real gap value $g$. A match costs $\lvert x-y\rvert$; deleting
or inserting a sample $v$ costs $\lvert v-g\rvert$. ERP is a
pseudometric on raw sequences because occurrences of $g$ can be inserted
or removed at zero cost. It is a metric modulo the $g$-quotient, which
identifies sequences after all occurrences of $g$ are removed.
Code: src/time_series/kernels/erp.rs ·
Research: ERP paper analysis · DOI:
10.1016/B978-012088469-8.50070-X
Categories: [Algorithm], [Mathematics], [Time Series]
Definition: For ERP gap value $g$, the scalar
$\Phi_g(x)=\sum_i\lvert x_i-g\rvert$. The reverse triangle inequality
proves $\lvert\Phi_g(x)-\Phi_g(y)\rvert\le D_{\mathrm{ERP}}(x,y)$, so the
absolute potential difference is an admissible candidate lower bound.
Categories: [Algorithm], [Time Series], [Mathematics]
Definition: An elastic edit distance for timestamped numeric sequences that
compares adjacent sample segments. In the crate's unit-spaced specialization,
deleting a segment pays its absolute sample change plus temporal stiffness
$\nu$ and deletion penalty $\lambda$; matching pays current and previous
sample deviations plus $2\nu\lvert i-j\rvert$. The previous target
quantization interval is carried between trie edges so both segment terms have
exact interval-box minima.
The complete TwedConfig family permits $\nu=0$ and is not uniformly
metric. MetricTwedConfig validates the primary-source domain
$\nu>0,\lambda\ge0$ and alone implements MetricElasticKernel. At
$\nu=\lambda=0$, $D([0,1],[1])=0$ is an identity counterexample.
Code: src/time_series/kernels/twed.rs ·
Research: Marteau analysis · DOI:
10.1109/TPAMI.2008.76 ·
See also: ElasticKernel, MetricElasticKernel, Admissible Bound
Categories: [Algorithm], [Time Series], [Mathematics]
Definition: The non-negative coefficient $\nu$ multiplying timestamp
displacement in TWED. Larger values resist temporal warping. Strict positivity
is part of the metric proof's identity premise; non-negativity alone is enough
for additive inflation and exact lower-bound trie pruning.
See also: TWED, MetricElasticKernel
Categories: [Algorithm], [Time Series], [Mathematics]
Definition: The minimum, over all order-preserving couplings of two
nonempty sequences, of the coupling's largest point-to-point link. Its dynamic
program selects alternative predecessors with min and extends a path with
max, so the implementation uses BottleneckCost. On raw vectors it is a
pseudometric: consecutive duplicate samples are zero-cost stutters. Identity
holds modulo run-length collapse.
Code: src/time_series/kernels/frechet.rs ·
Research: Eiter–Mannila analysis ·
Source: Technical Report CD-TR 94/64
Categories: [Algorithm], [Mathematics], [Time Series]
Definition: For sequences $x$ and $y$, the quantity
$\max_i\min_j\lvert x_i-y_j\rvert$. Every discrete Fréchet coupling pairs
each $x_i$ with some $y_j$, so this value lower-bounds the coupling
bottleneck and the exact distance. “One-sided” matters: exchanging $x$ and
$y$ can change the value.
Categories: [Algorithm], [Mathematics], [Time Series]
Definition: The normal form that replaces each maximal consecutive run of
equal samples by one sample. For example, [1, 1, 2, 2, 2] collapses to
[1, 2]. Discrete Fréchet identity on raw vectors is equality of this normal
form rather than literal vector equality.
Categories: [Algorithm]
Definition: A metric for real-valued time series built from three unit-cost-parameterized edits — Move (change a value, cost $\lvert x_i - y\rvert$), Split (one value → two), and Merge (two adjacent values → one). MSM satisfies the triangle inequality, so metric-tree indexing is possible. The crate's trie search instead prunes with an admissible interval-relaxed dynamic-programming lower bound; that proof uses non-negative step costs and exact survivor re-scoring, not the triangle inequality.
Code: src/time_series/msm.rs · DOI: 10.1109/TKDE.2012.88 · See also: TimeSeriesIndex, DTW
Categories: [Algorithm]
Definition: An elastic time-series similarity measure whose monotone path
may advance either input or both inputs. This crate's exact variant requires a
symmetric Sakoe–Chiba half-width $w$, accumulates squared deviations inside
$\lvert i-j\rvert\le w$, and returns the square root publicly. DTW is not a
metric because it can violate the triangle inequality, so it is inadmissible
for BK-trees, VP-trees, cover trees, and other metric-ball pruning. It remains
admissible for this crate's quantized trie because interval columns and
LB_Keogh lower-bound every descendant and every survivor is re-scored exactly.
The code-level labels are DtwConfig::IS_METRIC = false and absence of a
MetricElasticKernel implementation.
Code: src/time_series/kernels/dtw.rs ·
Research: DTW and LB_Keogh analysis ·
DOIs: 10.1109/TASSP.1978.1163055,
10.1007/s10115-004-0154-9 ·
See also: Sakoe–Chiba Band, LB_Keogh, MetricElasticKernel, MSM
Categories: [Algorithm], [Security]
Definition: The symmetric DTW constraint $\lvert i-j\rvert\le w$,
where $w$ is an inclusive half-width. It makes cells outside the diagonal
strip unreachable, rejects endpoint length gaps larger than $w$, and caps
live work per DP column at $2w+1$ cells. The band changes the distance and
is therefore required in DtwConfig::new(w) rather than selected by a default.
See also: DTW, LB_Keogh
Categories: [Algorithm], [Data Structure]
Definition: An admissible lower bound for banded DTW. For each candidate
position, it measures squared deviation outside the minimum/maximum query
envelope reachable through the Sakoe–Chiba band, then sums those deviations.
KeoghPlan constructs all envelopes with monotonic deques. The trie also uses
an interval-valued prefix form as a constant-time first gate before computing
the banded DP column.
Code: src/time_series/kernels/keogh.rs ·
DOI: 10.1007/s10115-004-0154-9 ·
See also: DTW, Sakoe–Chiba Band, Admissible Bound
Categories: [API], [Formal Verification]
Definition: A compile-time marker for elastic kernels whose reviewed proof
establishes metricity on the documented domain or quotient. A future index
whose correctness uses the triangle inequality must require this marker rather
than merely inspect ElasticKernel::IS_METRIC. The generic lower-bound trie
does not require it. MetricTwedConfig implements the marker only after
validating strict stiffness; unchecked TwedConfig and DTW do not.
Code: src/time_series/elastic/mod.rs ·
See also: DTW, TWED, ElasticKernel, Kernel Obligations
Categories: [Data Structure], [API]
Definition: TimeSeriesIndex indexes quantized/encoded series in a DynamicDawg; HybridSearchIndex adds a two-stage search — a cheap lower-bound filter (length_lb, euclidean_lb, l1_lb, combined_lb) followed by exact MSM verification, optionally in parallel with rayon.
Code: src/time_series/{trie_index,hybrid_search,lower_bounds}.rs · See also: MSM, SAX Encoding
Categories: [Algorithm], [Data Structure]
Definition: Symbolic Aggregate approXimation — one of the QuantizationConfig encodings (alongside delta and float quantization) that turns a numeric series into a discrete symbol string so it can be stored in a trie/DAWG.
Code: src/time_series/encoding.rs · See also: TimeSeriesIndex
Categories: [API], [Data Structure]
Definition: The sibling crate (path dependency, v0.2) that owns all dictionary backends and the Dictionary/DictionaryNode/MappedDictionary traits, plus SIMD + bloom-filter pruning. Extracted from liblevenshtein in v0.9.0; the old types are re-exported here as deprecation shims.
See also: Deprecation Shim, Architecture Overview
Categories: [API]
Definition: An external, optional crate providing WFST (weighted finite-state transducer) / language-model composition. Referenced by liblevenshtein for WFST integration but not a build dependency of this crate.
See also: WFST
Categories: [API]
Definition: A #[deprecated] re-export in src/dictionary/ (and the prelude) that forwards a historical liblevenshtein dictionary type to its new home in libdictenstein, preserving source compatibility across the 0.9.0 extraction.
Code: src/dictionary/mod.rs (now in the libdictenstein crate) · See also: libdictenstein
Categories: [Algorithm]
Definition: The formal-verification toolchain. Rocq (formerly Coq) machine-checked .v theories prove metric and algorithmic properties; TLA+ specifications model-check concurrent and query behaviour. The verification profile (trusted / partial / legacy) recorded in FORMAL_VERIFICATION_MANIFEST.tsv is the declared source of truth for what is proved versus assumed.
See also: Verification
Algorithm: Imitation Method, Parallel Traversal, Query Fusion, Scope-Aware Completion, Wagner-Fischer Algorithm, Auto-Minimization, Suffix Sharing, Sorted Batch Insertion
Data Structure: Arena Allocation, BASE and CHECK Arrays, Bloom Filter, DAWG, Double-Array Trie, Dynamic DAWG, PathMap, SmallVec, State Pool, Suffix Automaton, Zipper Pattern
Performance: Arc Path Sharing, Cache Locality, Edge Label Scanning, Lazy Edge Iteration, Lazy Evaluation, Monomorphization, PGO, Runtime CPU Feature Detection, Scalar Fallback, Threshold Tuning, Vectorization, Zero-Copy
Memory: Arena Allocation, Memory Pressure Eviction, SmallVec, State Pool, Zero-Copy
API: CharUnit Trait, Checkpoint System, Contextual Completion, Draft State, Finalized State, Fuzzy Map, Ordered Query, Query Iterator, RwLock, Term-Value Mapping, Thread-Safe Interior Mutability, Value Filtering
Unicode: Byte-Level vs Character-Level, CharUnit Trait, UTF-8 Decoding, Monomorphization
Caching: Cost-Aware Eviction, DashMap, Eviction Policy, LFU, LRU, Memory Pressure Eviction, TTL, Temporal Locality
SIMD: AVX2, AVX-512, Edge Label Scanning, Position Subsumption, Runtime CPU Feature Detection, Scalar Fallback, SSE4.1, Threshold Tuning, Vectorization
Contributing: To add new terms, maintain alphabetical order and include all standard fields (definition, benefits, trade-offs, code references, see also).
Last Updated: 2026-08-01
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 |