Comprehensive Documentation on Extending Levenshtein Automata to Support Weighted Operations
Date: 2025-11-06
Status: Research Complete - Implementation Recommendations Provided
Can a general algebra, calculus, or set of rules be derived to support:
For Weighted Transitions:
\mathcal{O}(|W| \times \max _\text{cost}/\text{precision})$ vs $\mathcal{O}(|W|)$ for uniform costsFor Extensible Operations:
Foundation: Wagner-Fischer Dynamic Programming → Finite Automata
Process:
Key Insight: Suffix independence (Lemma 2.0.2) justifies tracking only (position, errors).
The $\mathcal{O}(|W|)$ guarantee relies on:
Uniform cost → Bounded positions per state (≤ n+1)
→ Total states O(|W|) for fixed n
→ Linear construction time
With variable costs:
Variable costs → Infinite possible accumulated costs
→ Cannot enumerate all states
→ State explosion: O(|W| × (max_cost/min_cost)^n)
Critical dependencies:
|j-i| \le f-e$ assumes each move costs 1Key Idea: Round costs to fixed precision $\varepsilon$
struct WeightedPosition {
term_index: usize,
cost_units: u32, // actual_cost = cost_units × ε
}
Advantages:
\mathcal{O}(|W| \times \lceil \max _\text{cost}/\varepsilon \rceil)$Complexity:
\mathcal{O}(|W| \times \max _\text{cost}/\varepsilon)$\mathcal{O}(|D| \times \max _\text{cost}/\varepsilon)$\varepsilon$: Still $\mathcal{O}(|W|)$ and $\mathcal{O}(|D|)$ ✓Example - Keyboard Distance:
// Costs: adjacent=0.5, same_row=1.0, different_row=1.5
// Precision: ε=0.1
// Cost units: 5, 10, 15 respectively
// State count: O(|W| × 15) = O(|W|) ✓
This directory contains detailed analysis of:
Derivation Methodology (this document below)
Weighted Extension Analysis
General Framework
Starting Point: Wagner-Fischer DP computes matrix M[i,j] = d_L(W[1:i], V[1:j])
Key Observation:
During dictionary traversal:
- V revealed character-by-character
- Need to track: "where am I in W?" and "how many errors so far?"
- Don't need: specific path taken (all that matters is distance)
Mathematical Justification (Lemma 2.0.2):
If W = UW' and V = UV' (same prefix), then:
d_L(V, W) = d_L(V', W')
Implication: Distance depends only on remaining suffixes, not on how we got here!
Therefore:
Position π = (i, e)
i = index in W (how much consumed)
e = accumulated errors
Invariants Maintained:
|W|], V) \le n-e$0 \le i \le |W|, 0 \le e \le n$Formula: i#$e \sqsubseteq j$#f iff $(e < f) \land (|j-i| \le f-e)$
Geometric Reasoning (Edit Graph):
Edit graph: Horizontal axis = W, Vertical axis = V
Position (i,e) represents: matched i chars of W with e errors
From (i,e), reachable region:
R(i,e) = { (i',e') : |i'-i| + |e'-e| ≤ n-e }
(Manhattan ball of radius n-e)
For i#e to subsume j#f:
Must have: R(j,f) ⊆ R(i,e)
Condition 1: Radius check
n-f ≤ n-e → e < f (fewer errors = larger radius)
Condition 2: Center reachability
Can reach j from i within budget (f-e)?
Manhattan distance |j-i| ≤ (f-e) budget units
Example:
n=2, positions 3#0 and 4#1
Check: 3#0 ⊑ 4#1?
e < f: 0 < 1 ✓
|j-i| ≤ f-e: |4-3| = 1 ≤ 1-0 = 1 ✓
Result: YES, 3#0 subsumes 4#1
DP Recurrence (Wagner-Fischer):
M[i,j] = M[i-1,j-1] if W[i] = V[j]
M[i,j] = 1 + min(M[i-1,j-1], if W[i] ≠ V[j]
M[i-1,j],
M[i,j-1])
Key Insight: Decision depends ONLY on character match!
Generalization:
At position i in W, reading character x from dictionary:
Need to know: "Where does x match in W[i+1:i+k]?"
If matches at position j: Can skip to j with j-1 substitutions
Bit Vector Encoding:
χ(x, W[i:j]) = ⟨b₁, ..., b_k⟩
where b_k = 1 if W[i+k] = x, else 0
Example:
W = "hello", i=1, x='l'
W[2:5] = "ello"
χ('l', "ello") = ⟨0,1,1,0⟩
Position 2: 'e' ≠ 'l' → 0
Position 3: 'l' = 'l' → 1
Position 4: 'l' = 'l' → 1
Position 5: 'o' ≠ 'l' → 0
From DP to Transitions:
For position $\pi = i$#e reading character x:
Case 1: $\chi = \langle 1, \dots\rangle$ (immediate match)
W[i+1] = x
→ DP: M[i+1,j+1] = M[i,j] (no error)
→ Automaton: (i+1)#e
Case 2: $\chi = \langle 0,...,0,1,...\rangle$ at position j (match later)
Three DP operations possible:
1. Insert x: Stay at i, consume x from dict
→ i#(e+1)
2. Delete W[i+1]: Advance in W, add error
→ (i+1)#(e+1)
3. Multi-substitute then match: Skip to j
→ (i+j)#(e+j-1)
Optimization: Instead of creating intermediate positions for each substitution, jump directly to match point!
Case 3: $\chi = \langle 0,\dots,0\rangle$ (no match)
Only insert/delete:
→ {i#(e+1), (i+1)#(e+1)}
Note: Substitution would give (i+1)#(e+1), same as delete
Problem: "abc" → "bac" requires 2 standard operations but 1 transposition
Solution Strategy:
Add Flag: i#e_t where $t \in$ {0,1}
Extended Subsumption:
i#e_t ⊑ j#f_s iff:
(e < f) ∧ (|j-i| ≤ f-e) ∧ (t ≤ s)
Regular can subsume special, not vice versa
New Transition Cases:
From i#e_0 reading x:
If W[i+1] ≠ x AND W[i+2] = x:
→ Create i#(e+1)_1 (flag potential transposition)
From i#e_1 reading y:
If W[i+1] = y (the swapped character):
→ Complete: (i+1)#e_0
Why It Works: Flag tracks "seen first char, waiting for second"
Step 1: Define Semantics
Operation name: <operation>
Transformation: W → V (what changes?)
Cost: 1 (uniform) or c(op) (weighted)
Examples: concrete cases
Step 2: Determine Atomicity
Single-step operation? → No flag
Multi-step operation? → Add flag bit
Step 3: Extend Positions
Position = (i, e) or (i, e, flag)
Document flag states and meanings
Step 4: Define Transitions
For each case of characteristic vector:
Specify resulting positions
Justify why these positions
Step 5: Extend Subsumption
How do flagged positions compare?
Prove no false subsumptions
Step 6: Prove Complexity
Count positions per state:
Base: O(|W|)
Non-base: O(n) per base?
Total: O(|W|) for fixed n?
Step 7: Correctness
Prove: L(Automaton) = L_target
Via induction on word length
Property 1: Locality
\mathcal{O}(n)$ lookahead in WProperty 2: Bounded Cost
c_\text{min} \le c(\text{op}) \le c_\text{max}$ with bounded ratioProperty 3: Composability
Property 4: Subsumption-Compatible
Property 5: Deterministic
YES - with discretization:
// Current
struct Position {
term_index: usize,
num_errors: usize, // Integer count
}
// Weighted
struct WeightedPosition {
term_index: usize,
cost_units: u32, // Discretized cost
}
impl WeightedPosition {
fn from_cost(index: usize, cost: f64, precision: f64) -> Self {
Self {
term_index: index,
cost_units: (cost / precision).round() as u32,
}
}
fn actual_cost(&self, precision: f64) -> f64 {
self.cost_units as f64 * precision
}
}
State Space:
\mathcal{O}(|W| \times n)$\mathcal{O}(|W| \times \lceil \max _\text{cost}/\varepsilon \rceil)$\varepsilon$: Still $\mathcal{O}(|W|)$ ✓Modified Formula:
fn subsumes_weighted(
i: usize, c: u32, // Position 1
j: usize, d: u32, // Position 2
min_cost_per_op: u32,
) -> bool {
// Must have lower cost
if c >= d {
return false;
}
// Can we reach j from i within budget (d-c)?
let distance = (j - i) as u32;
let min_cost_needed = distance * min_cost_per_op;
let budget_available = d - c;
min_cost_needed <= budget_available
}
Issues:
fn transition_weighted(
pos: &WeightedPosition,
dict_char: char,
query: &[char],
costs: &CostFunction,
max_cost_units: u32,
precision: f64,
) -> Vec<WeightedPosition> {
let i = pos.term_index;
let c = pos.cost_units;
let mut result = vec![];
if i >= query.len() {
return result;
}
// Match (free)
if query[i] == dict_char {
result.push(WeightedPosition {
term_index: i + 1,
cost_units: c,
});
}
// Substitute
let sub_cost = discretize_cost(
costs.substitute(query[i], dict_char),
precision
);
if c + sub_cost <= max_cost_units {
result.push(WeightedPosition {
term_index: i + 1,
cost_units: c + sub_cost,
});
}
// Insert
let ins_cost = discretize_cost(costs.insert(dict_char), precision);
if c + ins_cost <= max_cost_units {
result.push(WeightedPosition {
term_index: i,
cost_units: c + ins_cost,
});
}
// Delete
let del_cost = discretize_cost(costs.delete(query[i]), precision);
if c + del_cost <= max_cost_units {
result.push(WeightedPosition {
term_index: i + 1,
cost_units: c + del_cost,
});
}
result
}
fn discretize_cost(cost: f64, precision: f64) -> u32 {
(cost / precision).round() as u32
}
Key Changes:
Cost-Characteristic Vectors:
fn cost_characteristic_vector(
x: char,
query: &[char],
offset: usize,
window_size: usize,
costs: &CostFunction,
) -> Vec<f64> {
(0..window_size)
.map(|k| {
let i = offset + k;
if i >= query.len() {
f64::INFINITY
} else if query[i] == x {
0.0 // Free match
} else {
costs.substitute(query[i], x)
}
})
.collect()
}
Usage: Determines minimum cost to match at each position
Problem: Standard Levenshtein treats 'a'→'s' same as 'a'→'z', but on QWERTY keyboard:
Solution: Variable substitution costs based on keyboard distance
Cost Function:
fn keyboard_distance_cost(c1: char, c2: char) -> f64 {
if c1 == c2 {
return 0.0; // Match
}
let pos1 = qwerty_position(c1); // (row, col)
let pos2 = qwerty_position(c2);
let row_diff = (pos1.row - pos2.row).abs();
let col_diff = (pos1.col - pos2.col).abs();
match (row_diff, col_diff) {
(0, 1) | (1, 1) => 0.5, // Adjacent (horizontal or diagonal)
(0, _) => 1.0, // Same row
_ => 1.5, // Different rows
}
}
Discretization $(\varepsilon = 0.1)$:
Costs: 0.5 1.0 1.5
Units (×10): 5 10 15
Position Structure:
struct KeyboardPosition {
term_index: usize,
cost_units: u32, // In units of 0.1
}
Transitions:
// Query: "tesy", Dictionary: "test"
// Starting position: (0, 0)
// Read 't': match query[0]='t' with dict='t'
// → (1, 0) cost=0.0
// Read 'e': match query[1]='e' with dict='e'
// → (2, 0) cost=0.0
// Read 's': mismatch query[2]='s' with dict='s'... wait, they match!
// → (3, 0) cost=0.0
// Read 't': match query[3]='y' with dict='t'
// Substitute 'y'→'t': adjacent on keyboard → cost=0.5 (5 units)
// → (4, 5) cost=0.5
// Reached end of query, cost = 0.5 ≤ threshold
// Result: MATCH with distance 0.5
Complexity:
States: O(|W| × max_cost/`$\varepsilon$`)
= O(|W| × 2.0/0.1)
= O(20|W|)
= O(|W|) for fixed ratio ✓
Phase 1: Universal LA (Restricted Substitutions)
/docs/research/universal-levenshtein/Phase 2: Research Discretized Weights
Phase 3: Full Weighted Automata
Precision vs Performance:
Precision $(\varepsilon )$ | State Multiplier | Use Case |
|---|---|---|
| 1.0 (integer) | 1-5× | Coarse costs, fast queries |
| 0.1 | 10-50× | Keyboard/OCR distances |
| 0.01 | 100-500× | High-precision scientific |
| 0.001 | 1000-5000× | Impractical |
Recommendation: Start with $\varepsilon =0.1,$ allow user configuration
Definition:
GLA_c,ε(W, θ) = (Q, Σ, Δ, q₀, F)
where:
W: query word
c: CostFunction (operations → costs)
ε: discretization precision
θ: cost threshold (max allowed)
Q: states (sets of weighted positions)
q₀: {(0, 0)} (start)
F: {M | ∃(i,c) ∈ M : i=|W| ∧ c·ε ≤ θ}
Δ: weighted state transition
Position Space:
P = {(i, c) | i ∈ [0,|W|], c ∈ [0, ⌈θ/ε⌉]}
Cardinality: O(|W| × θ/ε)
Subsumption:
(i, c) ⊑ (j, d) ⟺
c < d ∧
min_cost_path(i→j) ≤ (d-c)·ε
Complexity Theorem:
Theorem: For fixed ε > 0, θ, and c_min > 0:
|GLA_c,ε(W, θ)| = O(|W| × θ/ε)
Construction: O(|W| × θ/ε)
Query: O(|D| × θ/ε)
When θ/ε and c_max/c_min are O(1): Still O(|W|) and O(|D|)
\varepsilon > 0$ introduces approximation\mathcal{O}(n)$ window\mathcal{O}(|W|)$\varepsilon$ far from solution, finer near matchesSchulz, K. U., & Mihov, S. "Fast String Correction with Levenshtein-Automata"
/docs/research/levenshtein-automata/Mitankin, P., Mihov, S., & Schulz, K. U. (2009). "Universal Levenshtein Automata"
/docs/research/universal-levenshtein/Mohri, M. (2003). "Edit-Distance of Weighted Automata"
/docs/research/levenshtein-automata/PAPER_SUMMARY.md - Core algorithms/docs/research/universal-levenshtein/README.md - Restricted substitutions/docs/algorithms/02-levenshtein-automata/README.md - Current implementationCan general rules be derived for weighted transitions?
Answer: YES, via discretization
The Schulz/Mihov/Mitankin methodology CAN be extended to weighted costs by:
\varepsilon$The resulting complexity $\mathcal{O}(|W| \times \max _\text{cost}/\varepsilon)$ remains $\mathcal{O}(|W|)$ when cost range and precision are fixed.
The methodology is extensible but requires accepting precision-performance trade-offs. For most practical applications, Universal LA (binary restrictions) or coarse discretization $(\varepsilon =0.1-1.0)$ provides the best balance of expressiveness and performance.
Last Updated: 2025-11-06
Status: Research Complete
Next Steps: Implement Universal LA, then prototype discretized weights
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 |