Date: 2025-11-12 Paper: "Deciding Word Neighborhood with Universal Neighborhood Automata" (TCS 2011) Authors: Petar Mitankin, Stoyan Mihov, Klaus U. Schulz Related Documents:
This document provides a concrete mapping between theoretical concepts from the TCS 2011 paper and their implementation in both the lazy and universal Levenshtein automata codebases. Use this as a reference for understanding how theory translates to code.
| Paper Concept | Section | Lazy Code | Universal Code |
|---|---|---|---|
| Bounded Diagonal Property | §1 | ✅ Applied | ✅ Applied |
Operation Types ($t^x$, $t^y$, $t^w$) | §2 | ⚠️ Hardcoded | ⚠️ Hardcoded |
Subsumption $(<^\chi _s)$ | §3 | ✅ Implemented | ✅ Implemented |
State Anti-chain $(\sqcup )$ | §4 | ✅ Implemented | ✅ Implemented |
| Matrix-State Construction | §5 | ❌ N/A | ✅ Implemented |
Preprocessing $\chi[\text{Op},r]$ | §6 | ❌ N/A | ✅ Implemented |
Restricted Substitutions ($\text{op}^r$) | §7 | 🚧 In Progress | 🚧 In Progress |
| Diagonal Crossing (f_n, m_n) | §8 | ❌ N/A | ✅ Consumption-aware |
Characteristic Vector $\beta$ | §9 | ❌ N/A | ✅ Implemented |
Legend:
Theorem 8.2: The following are equivalent:
\Upsilon$ is length preservingFor Standard Levenshtein (n=2):
\le 8$ positions (with subsumption)File: src/transducer/state.rs:8-48
/// # SmallVec Optimization
///
/// Uses SmallVec with inline size of 8 to avoid heap allocations for typical states.
/// This optimization is theoretically justified by the **bounded diagonal property**
/// (Theorem 8.2, Mitankin et al., TCS 2011).
///
/// For Standard Levenshtein with error bound n=2:
/// - Diagonal bound c = 2
/// - Band width = 2c + 1 = 5 diagonals
/// - Typical state size ≤ 8 positions (with subsumption)
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct State {
positions: SmallVec<[Position; 8]>, // ← Justified by bounded diagonal
}
Why It Applies: Lazy automata use word-specific positions (term_index, num_errors) which still cluster around the diagonal in the DP matrix. The bounded diagonal property is a property of Levenshtein distance, not automaton architecture.
File: src/transducer/universal/state.rs:59-122
/// # SmallVec Optimization
///
/// Uses SmallVec with inline size of 8 to avoid heap allocations for typical states.
/// This optimization is theoretically justified by the **bounded diagonal property**
/// (Theorem 8.2, Mitankin et al., TCS 2011).
///
/// For Standard Levenshtein with error bound n=2:
/// - Diagonal bound c = 2
/// - Band width = 2c + 1 = 5 diagonals
/// - Typical state size ≤ 8 positions (with subsumption)
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct UniversalState<V: PositionVariant> {
positions: SmallVec<[UniversalPosition<V>; 8]>, // ← Justified by bounded diagonal
max_distance: u8,
}
Why It Applies: Universal automata use abstract positions I + offset#errors which also satisfy the bounded diagonal property, yielding $\mathcal{O}(n^{2})$ state space independent of word length.
Operation Type: $t = \langle t^x, t^y, t^w\rangle$
Where:
t^x: Characters consumed from first word (|u|)t^y: Characters consumed from second word (|v|)t^w: Operation weight/costStandard Levenshtein Operations:
Match: ⟨1, 1, 0⟩ (consume both, no cost)
Substitution: ⟨1, 1, 1⟩ (consume both, cost 1)
Insertion: ⟨0, 1, 1⟩ (consume v only, cost 1)
Deletion: ⟨1, 0, 1⟩ (consume u only, cost 1)
File: src/transducer/algorithm.rs:1-23
/// Algorithm for computing edit distance
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Algorithm {
/// Standard Levenshtein distance (operations: match, substitute, insert, delete)
Standard,
/// Levenshtein with transposition
Transposition,
/// Levenshtein with merge and split
MergeAndSplit,
}
Status: ⚠️ Hardcoded variants - not generalized to support arbitrary operation types
Gap: No representation of $\langle t^x, t^y, t^w\rangle$ triples. Operations are implicit in the transition logic rather than data-driven.
Transition Logic (implicit operations): src/transducer/lazy.rs:200-350
// Match: ⟨1, 1, 0⟩
if query_char == dict_char {
successor.insert(Position::new(term_index + 1, num_errors), algorithm, query_length);
}
// Operations: ⟨1, 1, 1⟩, ⟨0, 1, 1⟩, ⟨1, 0, 1⟩
if num_errors < max_distance {
successor.insert(Position::new(term_index + 1, num_errors + 1), algorithm, query_length); // Substitution or Deletion
successor.insert(Position::new(term_index, num_errors + 1), algorithm, query_length); // Insertion
// ... etc
}
File: src/transducer/universal/position.rs:1-50
pub trait PositionVariant: Clone + Debug + PartialEq + Eq + PartialOrd + Ord {
// Marker trait for position variants
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct Standard;
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct Transposition;
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct MergeAndSplit;
Status: ⚠️ Hardcoded variants via phantom types
Gap: No explicit $\langle t^x, t^y, t^w\rangle$ representation. Operations encoded implicitly in successor generation logic.
Successor Logic (implicit operations): src/transducer/universal/position.rs:200-400
impl<V: PositionVariant> UniversalPosition<V> {
pub fn successors(&self, bit_vector: &CharacteristicVector, max_distance: u8)
-> Vec<UniversalPosition<V>>
{
// Hardcoded standard operations
// No generalized operation type system
}
}
Proposed Design (applies to both lazy and universal):
/// Generalized operation type from TCS 2011 Section 3
pub struct OperationType {
/// Characters consumed from first word (t^x)
x_consumed: u8,
/// Characters consumed from second word (t^y)
y_consumed: u8,
/// Operation weight/cost (t^w)
weight: f32,
/// Optional: Restricted character pairs (op^r)
restriction: Option<SubstitutionSet>,
}
/// Operation set defining custom edit distance semantics
pub struct OperationSet {
types: Vec<OperationType>,
}
impl OperationSet {
/// Standard Levenshtein operations
pub fn standard() -> Self {
Self {
types: vec![
OperationType { x_consumed: 1, y_consumed: 1, weight: 0.0, restriction: None }, // Match
OperationType { x_consumed: 1, y_consumed: 1, weight: 1.0, restriction: None }, // Subst
OperationType { x_consumed: 0, y_consumed: 1, weight: 1.0, restriction: None }, // Insert
OperationType { x_consumed: 1, y_consumed: 0, weight: 1.0, restriction: None }, // Delete
],
}
}
/// Weighted operations (e.g., OCR confidence scores)
pub fn weighted(weights: &[(u8, u8, f32)]) -> Self { /* ... */ }
/// Custom operations (e.g., Unicode normalization)
pub fn custom(types: Vec<OperationType>) -> Self { /* ... */ }
}
Reference: See docs/research/universal-levenshtein/TCS_2011_PAPER_ANALYSIS.md Section 3 for details.
Notation: the subsumption relation is written $<^\chi _s$.
Subsumption: Position p₁ subsumes position p₂ if p₁ is "at least as good" as p₂, meaning:
Anti-chain Property: No position in a state subsumes another.
File: src/transducer/position.rs:80-140
impl Position {
/// Check if this position subsumes another
///
/// Position p1 subsumes p2 if:
/// - p2 has more errors than p1
/// - The distance between positions satisfies: |p1.term_index - p2.term_index| ≤ (p2.num_errors - p1.num_errors)
pub fn subsumes(&self, other: &Position, algorithm: Algorithm, query_length: usize) -> bool {
// Check error dominance
if other.num_errors <= self.num_errors {
return false;
}
let error_diff = other.num_errors - self.num_errors;
let index_diff = (self.term_index as isize - other.term_index as isize).abs() as usize;
// Subsumption condition: index distance ≤ error difference
index_diff <= error_diff
}
}
Usage: src/transducer/state.rs:82-100
pub fn insert(&mut self, position: Position, algorithm: Algorithm, query_length: usize) {
// Check if this position is subsumed by an existing one
for existing in &self.positions {
if existing.subsumes(&position, algorithm, query_length) {
return; // Already covered, discard new position
}
}
// Remove any positions that this new position subsumes
self.positions.retain(|p| !position.subsumes(p, algorithm, query_length));
// Insert in sorted position
self.positions.insert(insert_pos, position);
}
Status: ✅ Fully implemented - Online subsumption during state construction
File: src/transducer/universal/subsumption.rs:1-100
/// Check if position p1 subsumes position p2
///
/// From thesis Definition 13 (page 37):
/// p1 <^χ_s p2 ⟺
/// (offset(p1) = offset(p2) ∧ errors(p1) < errors(p2)) ∨
/// (errors(p1) = errors(p2) ∧ offset(p1) < offset(p2))
pub fn subsumes<V: PositionVariant>(
p1: &UniversalPosition<V>,
p2: &UniversalPosition<V>,
max_distance: u8,
) -> bool {
// Type mismatch: I-type cannot subsume M-type (different domains)
if p1.is_i_type() != p2.is_i_type() {
return false;
}
// Same offset, fewer errors → p1 subsumes p2
if p1.offset() == p2.offset() && p1.errors() < p2.errors() {
return true;
}
// Same errors, earlier offset → p1 subsumes p2
if p1.errors() == p2.errors() && p1.offset() < p2.offset() {
return true;
}
false
}
Usage: src/transducer/universal/state.rs:158-176
pub fn add_position(&mut self, pos: UniversalPosition<V>) {
// Check if this position is subsumed by an existing one
for existing in &self.positions {
if subsumes(existing, &pos, self.max_distance) {
return; // Already covered, discard
}
}
// Remove any positions that this new position subsumes
self.positions.retain(|p| !subsumes(&pos, p, self.max_distance));
// Insert in sorted position
self.positions.insert(insert_pos, pos);
}
Status: ✅ Fully implemented - Online subsumption via $\sqcup$ operator
| Aspect | Lazy | Universal |
|---|---|---|
| Subsumption Logic | Distance-based ($\|\text{idx}_{1} - \text{idx}_{2}\| \le \text{err}_\text{diff}$) | Offset/error comparison |
| State Maintenance | Online anti-chain | Online anti-chain $(\sqcup$ operator) |
| Complexity | $\mathcal{O}(\text{kn})$ typical, k << n | $\mathcal{O}(\text{kn})$ typical, k << n |
| Performance | 3.3× faster than batch | Comparable |
Key Insight: Both implementations use online subsumption (check during insertion) rather than batch (insert all, then prune). This is a significant optimization validated by benchmarks.
Notation: the join operator is written $\sqcup$.
Anti-chain Property: For all positions p₁, p₂ in state Q:
p_{1} \nprec ^\chi _s p_{2} (p_{1}$ does not subsume p₂)p_{2} \nprec ^\chi _s p_{1} (p_{2}$ does not subsume p₁)Join Operator $(\sqcup )$: Subsumption closure when adding position to state:
Implicit via State::insert(): src/transducer/state.rs:82-100
/// Add a position to this state with online subsumption checking.
///
/// Maintains anti-chain property automatically.
pub fn insert(&mut self, position: Position, algorithm: Algorithm, query_length: usize) {
// Step 1: Check if new position is subsumed (reject if so)
for existing in &self.positions {
if existing.subsumes(&position, algorithm, query_length) {
return;
}
}
// Step 2: Remove positions subsumed by new position
self.positions.retain(|p| !position.subsumes(p, algorithm, query_length));
// Step 3: Insert new position (anti-chain maintained)
self.positions.insert(insert_pos, position);
}
Status: ✅ Implicit $\sqcup$ operator via insert logic
Explicit via UniversalState::add_position(): src/transducer/universal/state.rs:158-176
/// Add position, maintaining anti-chain property (⊔ operator)
///
/// Implements the subsumption closure from the thesis:
/// 1. Remove all positions that subsume the new position (worse positions)
/// 2. Add new position if it doesn't subsume any existing position
pub fn add_position(&mut self, pos: UniversalPosition<V>) {
// Step 1: Check if new position is subsumed
for existing in &self.positions {
if subsumes(existing, &pos, self.max_distance) {
return;
}
}
// Step 2: Remove subsumed positions
self.positions.retain(|p| !subsumes(&pos, p, self.max_distance));
// Step 3: Insert new position
self.positions.insert(insert_pos, pos);
}
Status: ✅ Explicit $\sqcup$ operator implementation
Both implementations are functionally identical — they maintain the anti-chain property via online subsumption. The universal version has explicit documentation referencing the paper's $\sqcup$ operator, while the lazy version achieves the same result with different naming.
Matrix-State: Internal representation using three components:
Construction Algorithm (simplified):
Status: ❌ Not applicable — Lazy automata don't use matrix-state representation
Why: Lazy automata are word-specific and use concrete indices:
pub struct Position {
term_index: usize, // Concrete index in query word
num_errors: usize, // Error count
is_special: bool, // Special flag for transposition/merge-split
}
There is no I/M abstraction because the automaton is built for a specific query word at runtime.
Status: ✅ Fully implemented via UniversalPosition enum
File: src/transducer/universal/position.rs:50-100
/// Universal position (I-type or M-type)
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum UniversalPosition<V: PositionVariant> {
/// Non-final position: I + offset#errors
INonFinal { offset: i8, errors: u8, _phantom: PhantomData<V> },
/// Final position: M + offset#errors
MFinal { offset: i8, errors: u8, _phantom: PhantomData<V> },
}
impl<V: PositionVariant> UniversalPosition<V> {
pub fn new_i(offset: i8, errors: u8, max_distance: u8) -> Result<Self, PositionError> {
// Validate invariants
Ok(Self::INonFinal { offset, errors, _phantom: PhantomData })
}
pub fn new_m(offset: i8, errors: u8, max_distance: u8) -> Result<Self, PositionError> {
// Validate invariants
Ok(Self::MFinal { offset, errors, _phantom: PhantomData })
}
}
State Construction: src/transducer/universal/state.rs:127-134
/// Create initial state {I + 0#0}
pub fn initial(max_distance: u8) -> Self {
let mut state = Self::new(max_distance);
let initial_pos = UniversalPosition::new_i(0, 0, max_distance)
.expect("I + 0#0 should always be valid");
state.positions.push(initial_pos);
state
}
Why It Works: Universal automata are word-agnostic, using abstract parameters I (start) and M (end) that can be instantiated for any word pair at query time.
Notation: the preprocessing (characteristic-vector) function is written $\chi[\text{Op},r]$.
Preprocessing Function: $\chi$[Op,r] computes characteristic information for operations:
\beta (a, w)$Purpose: Enables alphabet-independent automaton construction — precompute all character relationships once, then use for any word pair.
Status: ❌ Not applicable — Lazy automata don't need preprocessing
Why: Lazy automata perform direct character comparison at runtime:
// Direct comparison, no preprocessing needed
if query_char == dict_char {
// Match operation
successor.insert(Position::new(term_index + 1, num_errors), algorithm, query_length);
}
This is word-specific by design — the automaton is built for a specific query, so there's no need for alphabet-independent encoding.
Status: ✅ Fully implemented via CharacteristicVector
File: src/transducer/universal/bit_vector.rs:1-100
/// Characteristic vector β(a, w) encoding character matches
///
/// From thesis page 42: For character a and word w, β(a, w) is a bit vector
/// where bit i is 1 if w[i] = a, 0 otherwise.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CharacteristicVector {
/// Bit vector: bits[i] = 1 if word[i] matches query character
bits: SmallVec<[bool; 8]>,
}
impl CharacteristicVector {
/// Create characteristic vector for character a in word w
///
/// Example: β('b', "abc") = [false, true, false] = "010"
pub fn new(query_char: char, word: &str) -> Self {
let bits: SmallVec<[bool; 8]> = word
.chars()
.map(|c| c == query_char)
.collect();
Self { bits }
}
/// Get bit at position i
pub fn get(&self, index: usize) -> bool {
self.bits.get(index).copied().unwrap_or(false)
}
}
Usage in Transitions: src/transducer/universal/position.rs:200-300
impl<V: PositionVariant> UniversalPosition<V> {
pub fn successors(&self, bit_vector: &CharacteristicVector, max_distance: u8)
-> Vec<UniversalPosition<V>>
{
// Use bit vector to determine operation applicability
let match_bit = bit_vector.get(self.position_in_word());
if match_bit {
// Match operation applies
successors.push(/* match successor */);
}
// Always consider error operations (independent of character)
successors.push(/* substitution successor */);
// ... etc
}
}
Why It's Needed: Universal automata must work for any word pair without knowing them in advance. Characteristic vectors abstract the character comparison into a precomputable encoding.
Notation: a restricted substitution's replacement relation is written $\text{op}^r$.
Restricted Operation: op $= \langle\text{op}^x$, $\text{op}^y$, $\text{op}^r$, $\text{op}^w\rangle$
Where $\text{op}^r \subseteq \Sigma ^{\text{op}^x} \times \Sigma ^{\text{op}^y}$ is the allowed replacement relation.
Examples:
\text{op}^r$ = {(q,w), (q,a), (w,e), ...}\text{op}^r$ = {(O,0), (I,1), (l,I), ...}\text{op}^r$ = {(f,ph), (c,k), (c,s), ...}Status: 🚧 Work in progress — SubstitutionSet implemented, integration pending
File: src/transducer/substitution_set.rs:1-200
/// Set of allowed character substitutions (op^r)
///
/// Maps to the paper's restricted substitution relation: op^r ⊆ Σ × Σ
#[derive(Clone, Debug)]
pub struct SubstitutionSet {
/// Internal representation (optimized with SmallVec for small sets)
inner: SubstitutionSetInner,
}
impl SubstitutionSet {
/// Check if substitution (a, b) is allowed
pub fn allows(&self, from: char, to: char) -> bool {
match &self.inner {
SubstitutionSetInner::Small(vec) => {
// Linear scan for small sets (≤4 pairs)
vec.iter().any(|(a, b)| *a == from_byte && *b == to_byte)
}
SubstitutionSetInner::Large(set) => {
// Hash lookup for large sets (>4 pairs)
set.contains(&(from_byte, to_byte))
}
}
}
/// Preset: Phonetic substitutions
pub fn phonetic_basic() -> Self { /* ... */ }
/// Preset: Keyboard QWERTY proximity
pub fn keyboard_qwerty() -> Self { /* ... */ }
/// Preset: OCR confusion sets
pub fn ocr_friendly() -> Self { /* ... */ }
}
Integration Point (planned): src/transducer/lazy.rs:250-300
// Planned integration:
if policy.allows_substitution(query_char, dict_char) {
successor.insert(Position::new(term_index + 1, num_errors + 1), algorithm, query_length);
}
Status: Data structure complete, transition logic integration pending.
Status: 🚧 Work in progress — Same SubstitutionSet being used
File: src/transducer/universal/substitution_policy.rs:1-50
/// Policy for restricting substitution operations
pub trait SubstitutionPolicy: Clone + Debug {
fn allows_substitution(&self, from: char, to: char) -> bool;
}
/// Unrestricted policy: all substitutions allowed
#[derive(Clone, Debug, Default)]
pub struct Unrestricted;
impl SubstitutionPolicy for Unrestricted {
fn allows_substitution(&self, _from: char, _to: char) -> bool {
true // Always allow
}
}
/// Restricted policy: only specific substitutions allowed
#[derive(Clone, Debug)]
pub struct Restricted {
allowed: SubstitutionSet, // Uses same implementation as lazy
}
impl SubstitutionPolicy for Restricted {
fn allows_substitution(&self, from: char, to: char) -> bool {
self.allowed.allows(from, to)
}
}
Integration Point (planned): src/transducer/universal/position.rs:250-300
// Planned integration:
fn successors_with_policy<P: SubstitutionPolicy>(
&self,
bit_vector: &CharacteristicVector,
policy: &P,
max_distance: u8
) -> Vec<UniversalPosition<V>> {
// Check policy before adding substitution successors
if policy.allows_substitution(from_char, to_char) {
successors.push(/* substitution successor */);
}
}
Status: Policy trait defined, integration with successor generation pending.
Both implementations share the same underlying SubstitutionSet data structure, which directly corresponds to the paper's $\text{op}^r$ concept. The main difference is:
Diagonal Crossing Detection:
true if position p has crossed the diagonal at input length kPurpose: Determines when to transition from non-final (I) positions to final (M) positions during word processing.
Status: ❌ Not applicable — No I/M distinction in lazy automata
Why: Lazy automata use concrete indices and determine finality directly:
pub fn is_final(&self, query_length: usize) -> bool {
// Final if we've consumed the entire query
self.term_index >= query_length
}
pub fn infer_distance(&self, query_length: usize) -> Option<usize> {
let remaining = query_length.saturating_sub(self.term_index);
Some(self.num_errors + remaining)
}
There's no diagonal crossing check because finality is determined by comparing term_index with query_length directly.
Status: ✅ Implemented for the consumption-aware state API
Files:
src/transducer/universal/diagonal.rs - thesis-level rm, f_n, and m_n helperssrc/transducer/universal/state.rs - length_diff state and transition_with_consumption()pub struct UniversalState<V: PositionVariant> {
positions: SmallVec<[UniversalPosition<V>; 8]>,
max_distance: u8,
length_diff: i8,
}
impl<V: PositionVariant> UniversalState<V> {
pub fn transition_with_consumption(
&self,
bit_vector: &CharacteristicVector,
consumed_query: bool,
consumed_dict: bool,
) -> Option<Self> {
// Updates length_diff from consumption metadata, computes successors,
// and converts positions when |length_diff| > max_distance.
}
}
Compatibility Note: the older transition() API does not perform diagonal
crossing because it has no consumption metadata. Use
transition_with_consumption() for callers that need I/M conversion.
Verification: 36/36 universal state tests passed under a 4G RSS cap on 2026-06-19, including length-difference updates and I/M conversion boundary tests.
Historical Bug Description (from TCS_2011_PAPER_ANALYSIS.md Section 8):
length_diff (m) tracking in stateUniversalState now stores length_diff, and transition_with_consumption() updates it before applying diagonal conversion.Proposed Fix (from paper Section 9.2):
pub struct UniversalState<V: PositionVariant> {
positions: SmallVec<[UniversalPosition<V>; 8]>,
length_diff: i8, // NEW: m ∈ [-c, +c] for diagonal tracking
max_distance: u8,
}
With explicit length_diff, diagonal crossing can be correctly detected:
length_diff = |w| - |x| (word length difference)length_diff exceeds bounds [-c, +c]transition() intentionally skips diagonal crossing because it has no consumption metadata.| Aspect | Lazy | Universal |
|---|---|---|
| Diagonal Crossing | ❌ Not applicable | ✅ Via transition_with_consumption() |
| I/M Conversion | ❌ Not needed | ✅ Length-diff-aware conversion |
| Finality Detection | ✅ Direct index comparison | ✅ Requires consumption-aware transition path |
| Status | Working correctly | Core state support verified |
Verification: systemd-run --user --scope -p MemoryMax=4G -p MemorySwapMax=0 env CARGO_BUILD_JOBS=1 cargo test -j1 --lib transducer::universal::state::tests -- --test-threads=1 passed 36/36 universal state tests on 2026-06-19.
Notation: the characteristic vector is written $\beta$.
Characteristic Vector: $\beta (a, w)$ is a bit vector where:
\beta (a, w)[i] = 1$ if w[i] = a\beta (a, w)[i] = 0$ otherwiseExample: $\beta ('b',$ "abc") = [0, 1, 0] = "010"
Purpose: Abstracts character matching for alphabet-independent automaton construction. Universal automaton uses $\beta$ instead of direct character comparison.
Status: ❌ Not needed — Direct character comparison sufficient
Why: Lazy automata are word-specific:
// Direct comparison at transition time
if query_char == dict_char {
// Characters match
}
No need for bit vector abstraction because we have the actual characters available during transition computation.
Status: ✅ Fully implemented
File: src/transducer/universal/bit_vector.rs:1-100
/// Characteristic vector β(a, w) encoding character matches
///
/// From thesis page 42: For character a and word w, β(a, w) is a bit vector
/// where bit i is 1 if w[i] = a, 0 otherwise.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CharacteristicVector {
/// Bit vector: bits[i] = 1 if word[i] matches query character
bits: SmallVec<[bool; 8]>,
}
impl CharacteristicVector {
/// Create characteristic vector for character a in word w
///
/// Example: β('b', "abc") = [false, true, false] = "010"
pub fn new(query_char: char, word: &str) -> Self {
let bits: SmallVec<[bool; 8]> = word
.chars()
.map(|c| c == query_char)
.collect();
Self { bits }
}
/// Get bit at position i
pub fn get(&self, index: usize) -> bool {
self.bits.get(index).copied().unwrap_or(false)
}
/// Get length of bit vector (word length)
pub fn len(&self) -> usize {
self.bits.len()
}
}
Usage: Passed to UniversalPosition::successors() to determine operation applicability:
impl<V: PositionVariant> UniversalPosition<V> {
pub fn successors(&self, bit_vector: &CharacteristicVector, max_distance: u8)
-> Vec<UniversalPosition<V>>
{
let mut successors = Vec::new();
// Check if match operation applies
let match_bit = bit_vector.get(self.effective_position());
if match_bit {
// Match: ⟨1, 1, 0⟩
successors.push(self.apply_match());
}
// Error operations always apply (independent of bit vector)
if self.errors() < max_distance {
successors.push(self.apply_substitution());
successors.push(self.apply_insertion());
successors.push(self.apply_deletion());
}
successors
}
}
Why It's Critical: Universal automaton must work for any word pair without knowing them in advance. Characteristic vectors enable this by encoding character relationships in a word-agnostic way.
| Aspect | Lazy | Universal |
|---|---|---|
| Character Encoding | Direct comparison | Bit vector $(\beta )$ |
| Alphabet Dependence | Word-specific | Alphabet-independent |
| Preprocessing | None needed | Required for each character |
| Purpose | Runtime matching | Precomputed matching |
| Component | Lazy Status | Universal Status | Priority |
|---|---|---|---|
| Bounded Diagonal Property | ✅ Applied | ✅ Applied | Complete |
| Operation Types | ⚠️ Hardcoded | ⚠️ Hardcoded | Medium |
| Subsumption | ✅ Implemented | ✅ Implemented | Complete |
Anti-chain $(\sqcup )$ | ✅ Implemented | ✅ Implemented | Complete |
| Matrix-State | ❌ N/A | ✅ Implemented | Complete |
Preprocessing $\chi$ | ❌ N/A | ✅ Implemented | Complete |
| Restricted Substitutions | 🚧 In Progress | 🚧 In Progress | High |
| Diagonal Crossing | ❌ N/A | ✅ Consumption-aware | Complete |
| Characteristic Vector | ❌ N/A | ✅ Implemented | Complete |
| Concept | File(s) |
|---|---|
| State | src/transducer/state.rs |
| Position | src/transducer/position.rs |
| Transition Logic | src/transducer/lazy.rs |
| Algorithm Enum | src/transducer/algorithm.rs |
| SubstitutionSet | src/transducer/substitution_set.rs |
| Concept | File(s) |
|---|---|
| State | src/transducer/universal/state.rs |
| Position | src/transducer/universal/position.rs |
| Subsumption | src/transducer/universal/subsumption.rs |
| Diagonal Crossing | src/transducer/universal/diagonal.rs |
| Characteristic Vector | src/transducer/universal/bit_vector.rs |
| Substitution Policy | src/transducer/universal/substitution_policy.rs |
Based on the implementation mapping analysis:
File: src/transducer/universal/state.rs:310-360
length_diff tracking to UniversalStateFiles:
src/transducer/lazy.rs - Integrate SubstitutionSet into transition logicsrc/transducer/universal/position.rs - Integrate SubstitutionPolicy into successor generationNew File: docs/design/generalized-operations.md
OperationType struct matching paper's $\langle t^x, t^y, t^w\rangle$Algorithm enumNew Files: Test files validating paper concepts
\beta$ definitionPrimary Paper:
Related Documentation:
Implementation Files: See Section 10 tables above
Document Version: 1.0 Last Updated: 2025-11-12 Author: Claude Code (Anthropic AI Assistant) Purpose: Concrete mapping from TCS 2011 paper to liblevenshtein-rust implementation
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 |