Liking cljdoc? Tell your friends :D

Prefix Matching with Levenshtein Automata

Version: 1.0 Date: 2025-10-26 Status: Implemented (Current System)

Executive Summary

This document describes the current implementation of liblevenshtein-rust's core functionality: approximate prefix matching using Universal Levenshtein Automata. This is the foundation upon which all proposed enhancements (suffix automata, WFST composition) build.

Dictionary traits: the Dictionary / DictionaryNode (and zipper) abstractions that let one Transducer drive prefix matching uniformly across every backend.

Key Capabilities

Prefix Matching - Find dictionary words within edit distance of a query
Three Algorithm Variants - Standard, Transposition, MergeAndSplit
Lazy Evaluation - Generate matches on-demand via iterators
Multiple Dictionary Backends - PathMap, DynamicDawg, DoubleArrayTrie, SuffixAutomaton
Thread-Safe - Lock-free concurrent access (ArcSwap)
Ordered Results - Distance-first, then lexicographic sorting

Theoretical Foundation
Architecture Overview
Core Components
Algorithm Variants
State Transitions
Query Processing
Performance Optimizations
Use Cases and Examples
Limitations and Trade-offs
References

Theoretical Foundation

Levenshtein Automaton

A Levenshtein automaton for string w and distance n is a finite-state automaton that accepts exactly the set of strings whose Levenshtein distance from w is at most n.

Formal Definition (Schulz & Mihov, 2002):

For query term w of length m and maximum distance n, the Levenshtein automaton A(w, n) is defined as:

States: Tuples (i, e) where:
- $i$ = position in query term ($0 \le i \le m$)
- $e$ = accumulated errors ($0 \le e \le n$)
Initial state: (0, 0) - start of term, no errors
Final states: $\{(m, e) \mid 0 \le e \le n\}$ - reached end of term within max distance
Transitions: Based on edit operations (insert, delete, substitute)

State Representation and Complexity

Naive Representation:

Store all reachable (i, e) tuples explicitly
State count: $\mathcal{O}((n+1) \times (m+1))$ = $\mathcal{O}(n \times m)$
For query length m=10, distance n=2: ~33 possible positions

Key Observation (Schulz & Mihov): At any point in dictionary traversal, all active positions lie within a characteristic vector of length 2n+1:

Given current offset k in query
Active positions: $\{(i, e) \mid k-n \le i \le k+n, e \le n\}$
This bounds the state space to $\mathcal{O}(n^2)$ per traversal step

Position Subsumption (Optimization):

Position p₁ = (i₁, e₁) subsumes p₂ = (i₂, e₂) if:

i₁ = i₂  AND  e₁ ≤ e₂

Rationale: If two positions are at the same query offset, the one with fewer errors dominates—any match reachable from the higher-error position is also reachable from the lower-error one (by simply accepting the string without additional errors).

Impact: Reduces typical state size by 30-60%

Example:

Query: "test"
Before subsumption: State = {(2,0), (2,1), (2,2), (3,1), (3,2)}
After subsumption:  State = {(2,0), (3,1)}
Reduction: 60% fewer positions

Characteristic Vector Optimization

Theory (from Schulz & Mihov, 2002):

Instead of storing explicit query string in states, pre-compute a characteristic vector for each incoming character:

CV(a) = vector indicating which query positions match character 'a'

Algorithm:

Pre-process query: For each alphabet symbol, compute bit vector of matches
During traversal: Use CV(dict_char) to determine which positions advance
Result: Transition function depends only on CV, not explicit query comparison

Complexity:

Without CV: $\mathcal{O}(m)$ comparisons per transition (check each query position)
With CV: $\mathcal{O}(1)$ lookup + $\mathcal{O}(\text{active positions})$ = $\mathcal{O}(n^2)$ per transition

Note: Our implementation uses direct query comparison for simplicity, but could be optimized with characteristic vectors for very large alphabets or long queries.

Universal Levenshtein Automaton

The Universal variant (Schulz & Mihov, 2002) parameterizes the automaton construction over:

Query term (dynamic input)
Maximum distance (user-specified)
Edit operations (algorithm-dependent)

This allows on-the-fly construction during dictionary traversal without pre-computing the entire automaton.

Prefix Matching Modification

Key Insight: Standard Levenshtein automata match complete words at exactly the specified distance. For dictionary applications, we need prefix matching: accepting words that match a prefix of the query (or vice versa).

Standard Acceptance: Word accepted if:

All query characters consumed (term_index == query.len())
Final state distance $\le$ max_distance

Prefix Matching Acceptance: Word accepted if:

Dictionary node is final (marks complete word)
Any state position with $\text{term\_index} \in [0, \text{query.len()}]$ and $\text{num\_errors} \le \text{max\_distance}$
Remaining query characters can be deleted within budget

Modification:

// Standard: Must consume entire query
fn is_final_standard(state: &State, query_len: usize) -> bool {
    state.positions().iter().any(|p|
        p.term_index == query_len && p.num_errors <= max_distance
    )
}

// Prefix: Can stop early if remaining chars deletable
fn is_final_prefix(state: &State, query_len: usize, max_distance: usize) -> bool {
    state.positions().iter().any(|p| {
        let remaining = query_len - p.term_index;
        let deletions_needed = remaining;
        p.num_errors + deletions_needed <= max_distance
    })
}

Example:

Query: "testing" (length 7)
Dictionary: "test"
Max distance: 2

Standard Levenshtein:
  - Must consume all of "testing" → match at "testing" (not in dict)
  - Result: NO MATCH

Prefix Matching:
  - At "test", state has position (4, 0) - matched 4 chars, 0 errors
  - Remaining: "ing" (3 chars)
  - Can delete "ing" with 3 operations, but max_distance=2
  - Result: NO MATCH with distance 2, MATCH with distance 3+

Query: "tes" (length 3)
Dictionary: "test"
Max distance: 1

Prefix Matching:
  - At "test", state has position (3, 0)
  - Remaining: "" (0 chars) - no deletions needed
  - Or at "tes", state has position (3, 0)
  - Can insert "t" with 1 operation
  - Result: MATCH (either as prefix of "test" or with 1 insertion)

Implementation Note: Our implementation uses the prefix matching variant, allowing queries like:

query("test", 1) matches "test", "tests", "tested" (prefix with edits)
Dictionary traversal naturally stops at final nodes (complete words)

This is the standard behavior for spell-checking and autocomplete applications.

Edit Operations

Standard Algorithm

1. Match:      (i, e) --a--> (i+1, e)     if query[i] == a
2. Substitute: (i, e) --a--> (i+1, e+1)   if query[i] != a
3. Insert:     (i, e) --a--> (i, e+1)     consume dict char without advancing query
4. Delete:     (i, e) --ε--> (i+1, e+1)   advance query without consuming dict char

Transposition Algorithm

Adds:

5. Transpose:  (i, e) --b,a--> (i+2, e+1) if query[i:i+2] == "ab" and dict has "ba"

MergeAndSplit Algorithm

Adds:

6. Merge:      (i, e) --a--> (i+2, e+1)   query chars "ab" → dict char "c" (merge to ligature)
7. Split:      (i, e) --a,b--> (i+1, e+1) query char "c" → dict chars "ab" (split ligature)

Intersection with Dictionary

The key insight: compose the Levenshtein automaton with the dictionary automaton:

Dictionary DFA × Levenshtein NFA → Acceptance paths

Process:

Start at dictionary root and Levenshtein initial state
Simultaneously traverse both:
- Dictionary transitions on edge labels
- Levenshtein transitions on same labels + $\varepsilon$-transitions
Accept path when:
- Dictionary node is final (valid word)
- Levenshtein state is final (within max distance)

Architecture Overview

Component Diagram

┌─────────────────────────────────────────────────────────────┐
│                     User Application                         │
└───────────────────────────┬─────────────────────────────────┘
                            │
┌───────────────────────────▼─────────────────────────────────┐
│                   Transducer<D>                              │
│  - Combines dictionary + algorithm                          │
│  - Public API: query(), query_with_distance()               │
│  - Returns lazy iterators                                   │
└───────────────────────────┬─────────────────────────────────┘
                            │
        ┌───────────────────┼───────────────────┐
        │                   │                   │
┌───────▼────────┐  ┌──────▼───────┐  ┌───────▼────────┐
│ QueryIterator  │  │ Candidate    │  │ Ordered        │
│                │  │ Iterator     │  │ QueryIterator  │
│ Returns: str   │  │ Returns:     │  │ Returns:       │
│                │  │ {str, dist}  │  │ {str, dist}    │
│                │  │              │  │ (sorted)       │
└────────────────┘  └──────────────┘  └────────────────┘
        │                   │                   │
        └───────────────────┼───────────────────┘
                            │
┌───────────────────────────▼─────────────────────────────────┐
│                   Intersection                               │
│  - Simultaneous traversal of dictionary + automaton         │
│  - State management: StatePool for reuse                    │
│  - Path tracking: PathNode for term reconstruction          │
└───────────────────────────┬─────────────────────────────────┘
                            │
        ┌───────────────────┼───────────────────┐
        │                   │                   │
┌───────▼────────┐  ┌──────▼───────┐  ┌───────▼────────┐
│ Dictionary     │  │ State        │  │ Position       │
│ Backend        │  │              │  │                │
│ - PathMap      │  │ Collection   │  │ (term_index,   │
│ - DAWG         │  │ of Position  │  │  num_errors,   │
│ - DynamicDawg  │  │ objects      │  │  is_special)   │
└────────────────┘  └──────────────┘  └────────────────┘

Data Flow

Query Execution:

1. User: transducer.query("test", 2)
2. Create QueryIterator with:
   - Dictionary root node
   - Initial Levenshtein state: [(0, 0)]
   - Query term: "test"
   - Max distance: 2
3. Iterator yields matches lazily:
   - Explore dictionary edges
   - Update Levenshtein states
   - Yield when dictionary final & distance ≤ 2
4. User consumes: for term in iterator { ... }

Core Components

1. Position

Purpose: Represents a location in the Levenshtein automaton state space.

/// A position in the Levenshtein automaton.
///
/// Represents (term_index, num_errors) with optional special flag.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct Position {
    /// Index into query term (characters consumed)
    pub term_index: usize,

    /// Accumulated edit operations
    pub num_errors: usize,

    /// Special flag for extended algorithms
    /// - Transposition: transposition in progress
    /// - MergeAndSplit: merge/split operation
    pub is_special: bool,
}

impl Position {
    /// Create new position
    pub fn new(term_index: usize, num_errors: usize) -> Self;

    /// Check if this position subsumes another
    ///
    /// Position p1 subsumes p2 if:
    /// - Same term_index (same query position)
    /// - p1.num_errors ≤ p2.num_errors (fewer/equal errors)
    /// - Same is_special flag
    ///
    /// This enables state space pruning: if p1 subsumes p2,
    /// all paths reachable from p2 are also reachable from p1,
    /// so p2 can be discarded.
    pub fn subsumes(&self, other: &Position) -> bool {
        self.term_index == other.term_index
            && self.num_errors <= other.num_errors
            && self.is_special == other.is_special
    }
}

Key Properties:

Copy type (17 bytes) for efficient passing
Ordered by (term_index, num_errors, is_special) for deterministic traversal
Subsumption enables state space reduction

2. State

Purpose: Collection of positions forming a single Levenshtein automaton state.

/// Levenshtein automaton state.
///
/// Maintains sorted collection of positions with automatic
/// deduplication and subsumption pruning.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct State {
    /// Positions, sorted and deduplicated
    positions: Vec<Position>,
}

impl State {
    /// Create empty state
    pub fn new() -> Self;

    /// Insert position with subsumption pruning
    pub fn insert(&mut self, position: Position) {
        // 1. Check if subsumed by existing position → skip
        for existing in &self.positions {
            if existing.subsumes(&position) {
                return;
            }
        }

        // 2. Remove positions this subsumes
        self.positions.retain(|p| !position.subsumes(p));

        // 3. Insert in sorted order
        let insert_pos = self.positions.binary_search(&position)
            .unwrap_or_else(|pos| pos);
        self.positions.insert(insert_pos, position);
    }

    /// Merge another state
    pub fn merge(&mut self, other: &State);

    /// Get positions
    pub fn positions(&self) -> &[Position];

    /// Check if final (any position reached query end)
    pub fn is_final(&self, query_len: usize) -> bool {
        self.positions.iter().any(|p| p.term_index == query_len)
    }
}

Optimizations:

Subsumption pruning reduces state count by ~30-60%
Sorted storage enables binary search insertion
Reuse via StatePool (object pooling pattern)

3. StatePool

Purpose: Object pool for state reuse to eliminate allocations.

/// Object pool for State instances.
///
/// Dramatically reduces allocation overhead by reusing State objects.
/// Measured improvements:
/// - 40-60% faster for PathMap queries
/// - 3.3x faster for DAWG queries
pub struct StatePool {
    /// Available states for reuse
    pool: Vec<State>,
}

impl StatePool {
    /// Acquire a state (reuse from pool or allocate new)
    pub fn acquire(&mut self) -> State {
        self.pool.pop().unwrap_or_else(State::new)
    }

    /// Return state to pool (clears and stores for reuse)
    pub fn release(&mut self, mut state: State) {
        state.clear();
        self.pool.push(state);
    }
}

Performance Impact:

Before: Allocate new State for every transition
After: Reuse States from pool
Result: 40-60% speedup (PathMap), 3.3x speedup (DAWG)

4. Intersection

Purpose: Traversal state combining dictionary node + Levenshtein state.

/// Intersection of dictionary and Levenshtein automaton.
///
/// Represents current position in simultaneous traversal.
pub struct Intersection<N: DictionaryNode> {
    /// Edge label from parent (for term reconstruction)
    pub label: Option<u8>,

    /// Current dictionary node
    pub node: N,

    /// Current Levenshtein state (collection of positions)
    pub state: State,

    /// Parent path for backtracking (lightweight)
    pub parent: Option<Box<PathNode>>,
}

Path Reconstruction:

PathNode: Lightweight (16 bytes) vs. full Intersection (50+ bytes)
Stores only label + parent pointer
Eliminates Arc cloning overhead (15-25% improvement)

5. Transducer

Purpose: Main user-facing API combining dictionary + algorithm.

/// Main transducer for approximate string matching.
#[derive(Clone, Debug)]
pub struct Transducer<D: Dictionary> {
    dictionary: D,
    algorithm: Algorithm,
}

impl<D: Dictionary> Transducer<D> {
    /// Create transducer
    pub fn new(dictionary: D, algorithm: Algorithm) -> Self;

    /// Query for terms (strings only)
    pub fn query(&self, term: &str, max_distance: usize)
        -> QueryIterator<D::Node>;

    /// Query with distances
    pub fn query_with_distance(&self, term: &str, max_distance: usize)
        -> CandidateIterator<D::Node>;

    /// Query with ordered results (distance-first, lexicographic)
    pub fn query_ordered(&self, term: &str, max_distance: usize)
        -> OrderedQueryIterator<D::Node>;
}

Algorithm Variants

Standard Algorithm

Edit Operations:

Match: Consume matching character (no error)
Substitute: Replace character (1 error)
Insert: Add character to query (1 error)
Delete: Remove character from query (1 error)

Transition Function:

fn transition_standard(
    state: &State,
    dict_char: u8,
    query: &[u8],
    max_distance: usize,
) -> State {
    let mut next_state = State::new();

    for pos in state.positions() {
        // 1. Match
        if pos.term_index < query.len() && query[pos.term_index] == dict_char {
            next_state.insert(Position::new(pos.term_index + 1, pos.num_errors));
        }

        // 2. Substitute
        if pos.term_index < query.len() && pos.num_errors < max_distance {
            next_state.insert(Position::new(pos.term_index + 1, pos.num_errors + 1));
        }

        // 3. Insert (ε-transition already processed)

        // 4. Delete (ε-transition already processed)
    }

    next_state
}

$\varepsilon$-Transitions (processed before consuming dict char):

fn epsilon_transitions_standard(
    state: &State,
    query: &[u8],
    max_distance: usize,
) -> State {
    let mut next_state = state.clone();
    let mut changed = true;

    while changed {
        changed = false;
        let current = next_state.clone();

        for pos in current.positions() {
            // Delete: advance query without consuming dict char
            if pos.term_index < query.len() && pos.num_errors < max_distance {
                let new_pos = Position::new(pos.term_index + 1, pos.num_errors + 1);
                if !current.positions().contains(&new_pos) {
                    next_state.insert(new_pos);
                    changed = true;
                }
            }

            // Insert: stay at same query position (handled during dict transition)
        }
    }

    next_state
}

Transposition Algorithm

Additional Operation:

Transpose: Swap adjacent characters (1 error)

Example:

Query: "tset"
Dictionary: "test"
Distance: 1

Standard: NO MATCH (requires 2 edits: substitute 's'→'e', substitute 'e'→'s')
Transposition: MATCH (1 transposition: "ts" ↔ "st")

Implementation:

Uses is_special flag to track transposition state:

// Detect potential transposition
if pos.term_index + 1 < query.len()
    && query[pos.term_index] == dict_char_next
    && query[pos.term_index + 1] == dict_char
    && pos.num_errors < max_distance
{
    // Mark special position for transposition
    next_state.insert(Position::new_special(
        pos.term_index + 2,
        pos.num_errors + 1,
    ));
}

MergeAndSplit Algorithm

Additional Operations:

Merge: Two query chars → one dict char (e.g., "ae" → "æ")
Split: One query char → two dict chars (e.g., "æ" → "ae")

Use Case: OCR errors, ligatures, character decomposition

Implementation:

Similar to transposition but handles 2-to-1 and 1-to-2 character mappings.

State Transitions

Transition Diagram

Standard Algorithm:

Initial: (0, 0)
Query: "test" (length 4)
Max Distance: 2

States reachable after consuming 't' from dictionary:

(0, 0) --t--> (1, 0)  [match]
(0, 0) --t--> (0, 1)  [insert]
(0, 0) --ε--> (1, 1)  [delete] --t--> (2, 1) [substitute]
(0, 0) --ε--> (1, 1)  [delete] --t--> (1, 1) [insert]

After ε-closure and subsumption:
- (1, 0): matched 't', 0 errors
- (1, 1): matched 't', 1 error (substitute or insert)
- (2, 1): matched 'te' via delete, 1 error

Example Trace

Query: "tset" with distance 2 Dictionary word: "test" Algorithm: Standard

Step 0: Initial state
  State: [(0,0)]
  Query position: 0
  Dict position: root

Step 1: Consume 't' from dictionary
  ε-closure: [(0,0), (1,1)]  [delete]
  Transition 't':
    (0,0) + 't': (1,0) [match t]
    (0,0) + 't': (0,1) [insert]
    (1,1) + 't': (2,1) [substitute e→t]
  State: [(0,1), (1,0), (2,1)]

Step 2: Consume 'e' from dictionary
  ε-closure: [(0,1), (1,0), (1,1), (2,1), (2,2), (3,2)]
  Transition 'e':
    (1,0) + 'e': (2,1) [substitute s→e]
    (1,1) + 'e': (2,1) [substitute s→e]
    (2,1) + 'e': (3,1) [substitute e→e, effectively match]
    (2,2) + 'e': (3,2) [substitute e→e]
  State: [(2,1), (3,1), (3,2)]

Step 3: Consume 's' from dictionary
  Transition 's':
    (2,1) + 's': (3,1) [match s]
    (3,1) + 's': (4,2) [insert]
  State: [(3,1), (4,2)]

Step 4: Consume 't' from dictionary
  Transition 't':
    (3,1) + 't': (4,1) [match t]
    (4,2) + 't': (4,2) [insert, already at end]
  Final State: [(4,1), (4,2)]

✅ ACCEPT: Position (4,1) reached end with distance 1
   Path: t-e-s-t matches "tset" with 1 edit (substitute s→e)

Query Processing

QueryIterator (Lazy Evaluation)

Design: Iterator pattern with depth-first traversal

pub struct QueryIterator<N: DictionaryNode> {
    /// Stack of unexplored intersections
    stack: Vec<Intersection<N>>,

    /// Query term as bytes
    term_bytes: Vec<u8>,

    /// Maximum allowed distance
    max_distance: usize,

    /// Algorithm for state transitions
    algorithm: Algorithm,

    /// State pool for reuse
    state_pool: StatePool,
}

impl<N: DictionaryNode> Iterator for QueryIterator<N> {
    type Item = String;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some(intersection) = self.stack.pop() {
            // Check if final (dictionary final + distance OK)
            if intersection.node.is_final()
                && self.is_acceptable(&intersection.state)
            {
                return Some(self.reconstruct_term(&intersection));
            }

            // Expand children
            for (label, child_node) in intersection.node.edges() {
                // Apply ε-transitions
                let mut state = self.apply_epsilon_transitions(&intersection.state);

                // Apply labeled transition
                state = self.apply_transition(&state, label);

                // Prune if no positions remain
                if state.is_empty() {
                    continue;
                }

                // Push new intersection
                self.stack.push(Intersection {
                    label: Some(label),
                    node: child_node,
                    state,
                    parent: Some(Box::new(PathNode::new(
                        label,
                        intersection.parent.clone(),
                    ))),
                });
            }
        }

        None
    }
}

Advantages:

Memory efficient: Only stores active paths, not entire search tree
Early termination: Stop as soon as sufficient results found
Composable: Works with .filter(), .take(), etc.

OrderedQueryIterator

Purpose: Return results ordered by distance first, then lexicographically.

Algorithm:

Collect all results into BTreeMap<(distance, term)>
Iterator returns entries in sorted order

Use Case: "Top-k closest matches"

let results: Vec<_> = transducer
    .query_ordered("tset", 2)
    .take(5)  // Only top 5
    .collect();

// Results guaranteed sorted:
// test: 1
// tests: 2
// tested: 2
// ... (alphabetical within same distance)

Performance Optimizations

1. Arc Path Sharing

Problem: Deep cloning of parent chains was expensive (7-15% overhead)

Solution: Use Arc for shared immutable paths

Impact: Eliminated cloning overhead, 15-25% speedup

2. StatePool (Object Pooling)

Problem: Allocating new State for every transition

Solution: Reuse States from object pool

Impact:

PathMap: 40-60% faster
DAWG: 3.3x faster

3. SmallVec Integration

Problem: Small Vec allocations for positions

Solution: Stack-allocated SmallVec for typical sizes

Impact: 5-18% speedup for filtering/prefix scenarios

4. Lazy Edge Iteration

Problem: Eager Vec allocation for edges

Solution: Zero-copy iterator over PathMap edges

Impact: 15-50% faster edge iteration

5. Aggressive Inlining

Hot path functions marked #[inline(always)]:

Position::new()
State::positions()
DictionaryNode::transition()

Impact: 5-10% overall speedup

6. Position Subsumption

Problem: Exponential state space growth

Solution: Prune subsumed positions

Example:

Before: State with positions [(3,1), (3,2), (3,3)]
After:  State with positions [(3,1)]  [subsumes others]
Reduction: 66% fewer positions

Impact: 30-60% state space reduction

Use Cases and Examples

Example 1: Basic Spell Checking

use liblevenshtein::prelude::*;

let dict = PathMapDictionary::from_terms(vec![
    "test", "testing", "tested", "tester", "best"
]);
let transducer = Transducer::new(dict, Algorithm::Standard);

// Find corrections for typo
for correction in transducer.query("tset", 1) {
    println!("{}", correction);
}
// Output: "test" (distance 1: transpose)

Example 2: Code Completion

// Complete function names
let functions = vec!["calculate", "calculator", "calibrate"];
let dict = PathMapDictionary::from_terms(functions);
let transducer = Transducer::new(dict, Algorithm::Standard);

// User types "calcul" with potential typo
for suggestion in transducer.query("caclul", 2) {
    println!("{}", suggestion);
}
// Output: "calculate", "calculator" (distance 2)

Example 3: Fuzzy Search with Filtering

let words = vec!["apple", "application", "apply", "ape"];
let dict = PathMapDictionary::from_terms(words);
let transducer = Transducer::new(dict, Algorithm::Standard);

// Search with prefix filter
let results: Vec<_> = transducer
    .query_ordered("aple", 1)
    .prefix()  // Only words starting with "aple" ± 1 edit
    .filter(|c| c.term.len() >= 4)  // Minimum length 4
    .take(3)
    .collect();

for candidate in results {
    println!("{}: {}", candidate.term, candidate.distance);
}
// Output:
// apple: 1
// apply: 1

Example 4: Transposition for Typos

// Common typo: adjacent letter swap
let dict = PathMapDictionary::from_terms(vec!["form", "from", "format"]);
let transducer = Transducer::new(dict, Algorithm::Transposition);

// "form" typed as "from" (transposition)
for match_ in transducer.query("from", 1) {
    println!("{}", match_);
}
// Output: "form", "from" (both within distance 1)

Example 5: Ordered Results for Top-K

let dict = PathMapDictionary::from_terms(vec![
    "test", "tests", "tested", "testing", "tester", "best", "fest"
]);
let transducer = Transducer::new(dict, Algorithm::Standard);

// Get top 3 closest matches
for candidate in transducer.query_ordered("tset", 2).take(3) {
    println!("{}: {}", candidate.term, candidate.distance);
}
// Output (sorted by distance, then alphabetically):
// test: 1
// best: 2
// fest: 2

Limitations and Trade-offs

1. Prefix Matching Only

Limitation: Cannot find substring matches

Example:

// Query: "test"
// Dictionary: "contest"
// Result: NO MATCH (doesn't start with "test")

Solution: Suffix automaton (see suffix-automaton.md)

2. No Context Awareness

Limitation: Cannot use grammatical context

Example:

// Query: "I saw too movies"
// Candidates: "to", "too", "two"
// Result: All returned, cannot distinguish which is grammatically correct

Solution: WFST composition (see hierarchical-correction.md)

3. State Space Growth

Challenge: State count grows with distance

Mitigation:

Position subsumption (30-60% reduction)
Early pruning of unreachable states
Maximum distance limits

Performance:

Distance 1: Typically < 10 positions per state
Distance 2: Typically < 50 positions per state
Distance 3+: Can exceed 100 positions (slower)

4. Memory Usage

Per-Query Overhead:

StatePool: ~1-5 MB (reusable)
Active stack: ~10-100 KB (depends on dictionary branching)
Path reconstruction: ~1 KB per result

Dictionary Overhead:

PathMap: ~24 bytes per node
DAWG: ~32 bytes per node
DynamicDawg: ~48 bytes per node (with metadata)

5. Unicode Handling

Current: Byte-based (UTF-8 bytes)

Limitation: Grapheme clusters (é, emoji) treated as multiple units

Workaround: Pre-normalize text to NFD or NFC

Future: Grapheme-aware variant (see suffix-automaton.md Future Enhancements)

References

Academic Papers (with DOIs)

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
- Primary theoretical basis for this implementation
- Universal Levenshtein automaton construction
- Intersection with dictionary automata
- Parametric algorithm (Standard, Transposition)
Levenshtein, V. I. (1966) "Binary codes capable of correcting deletions, insertions, and reversals" Soviet Physics Doklady, 10(8), 707-710.
- Original definition of edit distance
- Insert, delete, substitute operations
Damerau, F. J. (1964) "A technique for computer detection and correction of spelling errors" Communications of the ACM, 7(3), 171-176. DOI: 10.1145/363958.363994
- Damerau-Levenshtein distance (adds transposition)
- Basis for Transposition algorithm
Wagner, R. A., & Fischer, M. J. (1974) "The string-to-string correction problem" Journal of the ACM, 21(1), 168-173. DOI: 10.1145/321796.321811
- Dynamic programming algorithm for edit distance
- $\mathcal{O}(mn)$ time complexity
Mihov, S., & Schulz, K. U. (2004) "Fast approximate search in large dictionaries" Computational Linguistics, 30(4), 451-477. DOI: 10.1162/0891201042544938
- Extended automaton algorithms
- Merge and split operations
- Practical optimizations

Implementation References

Ofek, N. (2010) "Damn Cool Algorithms: Levenshtein Automata" Blog post: http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata
- Practical implementation guide
- Parametric construction
- Python code examples
Jacobs, J. (2015) "Levenshtein automata can be simple and fast" Blog post: https://julesjacobs.com/2015/06/17/disqus-levenshtein-simple-and-fast.html
- Simplified implementation
- Characteristic vector optimization
- Complexity analysis: $\mathcal{O}(D^2 N)$ where $D$ = distance, $N$ = query length
Bergroth, L., Hakonen, H., & Raita, T. (2000) "A survey of longest common subsequence algorithms" Proceedings of SPIRE, 39-48. DOI: 10.1109/SPIRE.2000.878178
- Edit distance computation algorithms
- DP matrix optimization techniques
Lucene Project "LevenshteinAutomata Implementation" Apache Lucene Source Code
- Production implementation based on Schulz & Mihov
- Parametric automaton construction
- DFA minimization techniques
Kabir, I. (2021) "Universal Levenshtein Automata: An Implementer's Perspective" Blog post: https://www.ifazk.com/blog/2021-06-20-Universal-Levenshtein-Automata-An-Implementers-Perspective.html
- Detailed implementation walkthrough
- State management strategies
- Performance considerations
Cotumaccio, N. (2019) "Of Levenshtein automata implementations" Blog post: https://fulmicoton.com/posts/levenshtein/
- State representation optimizations
- Offset and edit distance tracking
- Complexity analysis with characteristic vectors

Related Work in This Project

src/transducer/ - Current implementation
src/dictionary/ - Dictionary backends
suffix-automaton.md - Substring matching extension
hierarchical-correction.md - Context-aware correction
docs/developer-guide/performance.md - Optimization details
dynamic-dawg.md - Runtime dictionary updates

Appendix A: Complexity Analysis

Time Complexity

Operation	Complexity	Notes
Construction	$`\mathcal{O}(1)`$	Lazy construction during traversal
Query (worst case)	$`\mathcal{O}(m \times n^d \times \lvert\Sigma\rvert^d)`$	$`m`$ = query length, $`n`$ = max distance, $`\Sigma`$ = alphabet, $`d`$ = dictionary depth
Query (typical)	$`\mathcal{O}(m \times k)`$	$`k`$ = result count (with pruning)
Per-transition	$`\mathcal{O}(\text{positions})`$	Typically 10-50 positions for distance 2
Subsumption check	$`\mathcal{O}(\text{positions}^2)`$	~$`\mathcal{O}(p)`$ amortized with sorted positions

Space Complexity

Component	Complexity	Typical Size
Position	17 bytes	Fixed
State	$`\mathcal{O}(\text{positions})`$	Vec
StatePool	$`\mathcal{O}(\text{states})`$	~1-5 MB (reusable)
Active stack	$`\mathcal{O}(\text{depth} \times \text{branching})`$	~10-100 KB
Path nodes	$`\mathcal{O}(\text{depth} \times \text{results})`$	~16 bytes each

State Space Bounds

Without pruning:

Standard (distance $n$): $\mathcal{O}((n+1)^{(m+1)})$ states
Example: query length 10, distance 2 → ~60K states

With subsumption pruning:

Reduction: 30-60% fewer states
Example: 60K → 24K-42K states

Empirical measurements:

Distance 1: ~100-500 states explored
Distance 2: ~1K-5K states explored
Distance 3: ~10K-50K states explored

Appendix B: Algorithm Comparison

Feature	Standard	Transposition	MergeAndSplit
Operations	Insert, Delete, Substitute	+ Transpose	+ Merge, Split
Typical Use	General spell check	Typo correction	OCR errors, ligatures
State complexity	$`\mathcal{O}(n \times m)`$	$`\mathcal{O}(n \times m)`$	$`\mathcal{O}(n \times m^2)`$
Example	"tset" → "test" (2 edits)	"tset" → "test" (1 edit)	"æ" ↔ "ae" (1 edit)
Performance	Baseline	+10-20% overhead	+30-50% overhead