Decision: ❌ NOT APPLICABLE - Bimachines should NOT be integrated into liblevenshtein-rust
Date: 2025-01-06 Paper: "Space-Efficient Bimachine Construction Based on the Equalizer Accumulation Principle" (Gerdjikov, Mihov, Schulz; TCS 790:80–95, 2019; doi:10.1016/j.tcs.2019.04.027; preprint arXiv:1803.04312, 2018) Status: Analysis complete, implementation NOT recommended
Clear Answer: NO - Bimachines are fundamentally incompatible with liblevenshtein-rust's architecture and goals.
| Aspect | Finding | Impact |
|---|---|---|
| Problem Domain | Bimachines solve transduction; we solve matching | ❌ Incompatible |
| Performance | 𝒪(2^∣Q∣) states vs our 𝒪(∣W∣) | ❌ Worse |
| Determinism | Converts non-det → det; we're already det | ❌ Unnecessary |
| Output Type | String → String vs String → Set | ❌ Mismatch |
| Integration Cost | Major architectural overhaul | ❌ High cost, no benefit |
DO NOT IMPLEMENT bimachines. Instead:
A bimachine is a deterministic computational model for rational string functions:
Bimachine = (AL, AR, ψ)
Where:
- AL: Left deterministic automaton (processes input left-to-right)
- AR: Right deterministic automaton (processes input right-to-left)
- ψ: Output function ψ(qL, σ, qR) → M
Primary Goal: Convert non-deterministic functional finite-state transducers into equivalent fully deterministic devices.
Key Innovation: "Equalizer accumulation principle" reduces state count from Θ(n!) to 𝒪(2^∣Q∣).
Input: "hello"
Output: "HELLO" // String transformation
Transducer: Non-deterministic string-to-string function
Bimachine: Deterministic equivalent
✅ SAME RESEARCH GROUP:
Important: These authors understand BOTH approaches deeply and chose Levenshtein automata for edit distance matching.
liblevenshtein-rust implements Levenshtein Automata (not transducers):
Problem: Find all dictionary words within distance n from query W
Solution: Levenshtein Automaton LEV_n(W)
- Deterministic finite automaton
- Accepts exactly L_Lev(n,W) = {V | d_L(W,V) ≤ n}
- Construction: O(|W|) for fixed n
- Query: O(|D|) dictionary traversal
Key Insight: Already deterministic, already optimal for this problem.
use liblevenshtein::prelude::*;
let dict = DoubleArrayTrie::from_terms(vec!["test", "text", "best"]);
let transducer = Transducer::new(dict, Algorithm::Standard);
// Query: Find words within distance 1 of "tset"
for term in transducer.query("tset", 1) {
println!("{}", term);
}
// Output: "test" (NOT a transformation, a SET of matches)
| Aspect | Bimachines | Levenshtein Automata |
|---|---|---|
| Function Type | f : Σ* → Ω* | Match(W,n) : D → P(Σ*) |
| Input | Single string | Query + Dictionary |
| Output | Transformed string | Set of matching words |
| Purpose | General transduction | Edit distance matching |
| Determinism | Converts non-det → det | Already deterministic |
| Primary Use | NLP transformations | Fuzzy search, spell check |
Bimachine Output:
Input: "hello"
Output: "HELLO" // Single transformed string
Levenshtein Automaton Output:
Query: "tset"
Distance: 1
Output: {"test", "best", ...} // Set of matches
Fundamental problem: Bimachines produce ONE output string; we produce MANY matching strings.
Standard construction: Θ(n!) states (worst case, Section 6.2)
Equalizer accumulation: O(2^|Q|) states (Theorem 5, improvement)
Example (n+2 states):
- Standard: n! + 2^n + n states
- Optimized: 2n + n + 3 states
Innovation: Massive improvement from factorial to exponential!
Construction: O(|W|) for fixed n (Theorem 5.2.1)
Query: O(|D|) dictionary traversal
States: O(|W|) positions (Corollary 5.2.2)
Example (word length 10, distance 2):
- States: ~10 positions
- No exponential growth
- No factorial complexity
Comparison:
𝒪(2^∣Q∣) → exponential (but better than factorial)𝒪(∣W∣) → linear (optimal for edit distance)Conclusion: Levenshtein automata are MORE EFFICIENT than bimachines for this problem.
Note: Module is named "transducer" but implements Levenshtein automata, NOT finite-state transducers:
// From src/transducer/mod.rs
pub struct Transducer<D: Dictionary> {
dictionary: D,
algorithm: Algorithm, // Standard, Transposition, MergeAndSplit
}
impl<D: Dictionary> Transducer<D> {
pub fn query(&self, term: &str, max_distance: usize)
-> impl Iterator<Item = String>
{
// Parallel traversal of dictionary + Levenshtein automaton
// NOT a transducer in the formal sense!
QueryIterator::new(...)
}
}
Naming Historical Context: "Transducer" here means "edit distance calculator," not "finite-state transducer." The implementation uses the imitation method (Schulz & Mihov 2002, Chapter 6).
All backends (DoubleArrayTrie, DAWG, PathMap) implement Dictionary trait:
pub trait Dictionary {
fn root(&self) -> NodeRef;
fn transition(&self, node: NodeRef, ch: char) -> Option<NodeRef>;
fn is_final(&self, node: NodeRef) -> bool;
}
Key Point: Dictionaries accept/reject words, they DON'T transform them.
Levenshtein Automata Property (Theorem 4.0.32):
LEV_n(W) is a deterministic, acyclic finite automaton.
Implication: No need for bimachine determinization - already deterministic!
Bimachine Processing:
1. Process input left-to-right (AL)
2. Process input right-to-left (AR)
3. Combine states via output function ψ(qL, σ, qR)
4. Produce transformed output
Levenshtein Automaton Processing:
1. Parallel traversal of dictionary automaton A^D
2. Parallel simulation of LEV_n(W) states
3. Accept when both automata in accepting state
4. Yield matching dictionary word (NOT transformed)
Fundamentally different: Bidirectional transformation vs parallel acceptance.
What bimachines solve:
Problem: Convert non-deterministic transducer to deterministic
Example: "hello" → {"HELLO", "Hello"} becomes "hello" → "HELLO"
What liblevenshtein does:
Problem: Find all words within edit distance
Example: Query("tset", 1) → {"test", "best", ...}
No transduction needed, no non-determinism to eliminate!
Bimachine output: Single string (from monoid M) Our output: Set of strings (from powerset P(Σ*))
Can't map set-valued function to monoid-valued function without losing information.
| Criterion | Bimachines | Current (LA) | Winner |
|---|---|---|---|
| Problem Fit | String transformation | Edit distance matching | Current ✓ |
| Construction | 𝒪(2^∣Q∣) states | 𝒪(∣W∣) construction | Current ✓ |
| Query Speed | N/A (different problem) | 𝒪(∣D∣) traversal | Current ✓ |
| Memory | 𝒪(2^∣Q∣) space | 𝒪(∣W∣) space | Current ✓ |
| Determinism | Enforced | Already guaranteed | Tie |
| Simplicity | 2 automata + output fn | Single automaton | Current ✓ |
| Extensibility | Limited to transduction | Multiple algorithms | Current ✓ |
| Production Use | Theoretical | Millions of queries | Current ✓ |
| Implementation | Complete rewrite | Working, optimized | Current ✓ |
Score: Current implementation wins 8/9 categories
Goal: "teh" → "The" (correct + capitalize)
Option 1: Post-Processing (RECOMMENDED)
// Step 1: Find candidates
let candidates: Vec<String> = transducer.query("teh", 1).collect();
// Step 2: Apply transformations
let corrected: Vec<String> = candidates
.into_iter()
.map(|s| capitalize(&s))
.collect();
Advantages:
Option 2: Callback-Based API
transducer.query_with_callback("teh", 1, |term: &str, distance: usize| {
let transformed = transform(term);
process(transformed);
});
Advantages:
Option 3: Bimachine Integration (NOT RECOMMENDED)
Would require:
𝒪(2^∣Q∣) state explosion𝒪(∣W∣) → 𝒪(2^∣Q∣))Conclusion: Options 1 or 2 provide transformation capability without architectural overhead.
Paper: Mitankin, Mihov, Schulz (2005)
Status: Documented in /docs/research/universal-levenshtein/
Problem: Restricted substitutions (only specific character pairs allowed)
Examples:
Relationship to Bimachines: NONE - completely different approach Recommendation: ✅ IMPLEMENT THIS INSTEAD (2-4 weeks, clear benefits)
Status: Documented in /docs/research/weighted-levenshtein-automata/
Problem: Variable operation costs (keyboard distance, frequency-based)
Solution: Discretization approach
WeightedPosition = (term_index, cost_units)
Complexity: O(|W| × max_cost/precision)
Relationship to Bimachines: NONE - bimachines don't handle weighted operations Recommendation: ✅ PROTOTYPE IF NEEDED (4-6 weeks research + 4-6 weeks implementation)
Status: Documented in /docs/research/wallbreaker/
Problem: Efficiency for large error bounds (n > 2)
Solution: Split query into patterns, merge results
Relationship to Bimachines: NONE - orthogonal optimization Recommendation: ✅ CONSIDER FOR SCIENTIFIC APPLICATIONS
Bulgarian lexicon (870K words):
- Distance 1: < 1ms
- Distance 2: 1-2ms
German lexicon (6M words):
- Distance 1: ~2-5ms
- Distance 2: ~5-10ms
With SIMD optimization:
- 20-64% faster across all workloads
These are EXCELLENT numbers achieving:
𝒪(∣W∣) construction as proven𝒪(∣D∣) query as provenBest case (with equalizer accumulation):
- O(2^|Q|) states (exponential growth)
- NOT applicable to edit distance matching
- Solves wrong problem (transduction)
Conclusion: Current architecture is already optimal. Bimachines would make it WORSE.
Paper Achievement: 𝒪(2^∣Q∣) vs Θ(n!)
Applicability to us: ❌ We use 𝒪(∣W∣) - better than both
Paper Feature: Free monoids, groups, tropical semiring Applicability to us: ❌ Our output is sets, not monoid elements
Paper Goal: Convert non-deterministic → deterministic Applicability to us: ❌ Already deterministic (Theorem 4.0.32)
Paper Innovation: Find common continuations in transducers Applicability to us: ❌ We use subsumption (Position π₁ ⊑ π₂), not equalizers
Summary: Excellent paper solving real problems, but wrong problems for us.
Phase 1: Research & Design (2-3 weeks)
Phase 2: Core Implementation (4-6 weeks)
Phase 3: Backend Integration (2-3 weeks)
Phase 4: Testing & Optimization (2-3 weeks)
Total Effort: 10-15 weeks (2.5-3.5 months)
𝒪(2^∣Q∣) vs current 𝒪(∣W∣))Cost/Benefit: All cost, no benefit.
Reasons:
𝒪(2^∣Q∣) vs 𝒪(∣W∣))Reasons:
Implementation Guide: See /docs/research/universal-levenshtein/implementation-plan.md
Reasons:
Caution:
Research Guide: See /docs/research/weighted-levenshtein-automata/README.md
Reasons:
Optimization Opportunities:
The bimachine paper is excellent theoretical work solving real problems in finite-state transducer determinization. However, liblevenshtein-rust doesn't use finite-state transducers - it uses Levenshtein automata, which are a superior, purpose-built solution for edit distance matching.
This is precisely why Schulz & Mihov published BOTH papers:
Different tools for different jobs.
The fact that the same authors developed both approaches and chose Levenshtein automata for liblevenshtein is strong validation that bimachines aren't needed here.
Bimachine Paper (Subject of Analysis):
Levenshtein Automata (Current Implementation):
Universal Levenshtein Automata (Recommended Next Step):
CLEAR DECISION: ❌ DO NOT IMPLEMENT BIMACHINES
Bimachines are an impressive theoretical achievement for transducer determinization, but they solve a problem liblevenshtein-rust doesn't have. The current Levenshtein automata architecture is:
𝒪(∣W∣) vs 𝒪(2^∣Q∣))Next Steps:
Confidence Level: VERY HIGH Analysis Date: 2025-01-06 Decision: FINAL - Do not revisit unless project goals fundamentally change
Document Purpose: This analysis serves as a decision record, preventing repeated investigation of this approach and guiding contributors toward applicable research directions (Universal LA, weighted distances, GPU acceleration).
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 |