Liking cljdoc? Tell your friends :D

Universal Levenshtein Automata - Progress Tracker

Date Started: 2025-11-06 Current Phase: Phase 0 (Planning & Documentation) Status: Documentation Complete, Ready to Begin Implementation

Overview

This document tracks the implementation progress of Universal Levenshtein Automata features for liblevenshtein-rust. Tasks are organized by phase, with checkboxes to mark completion.

Update this file as you complete tasks to maintain visibility into project status.

Phase 0: Planning & Documentation

Duration: 1 day Status: ✅ Complete

Tasks

[x] Research paper and analyze applicability
[x] Analyze current codebase architecture
[x] Create documentation directory structure
[x] Write README.md (overview and index)
[x] Write technical-analysis.md (codebase analysis)
[x] Write implementation-plan.md (phase breakdown)
[x] Write decision-matrix.md (approach comparison)
[x] Write architectural-sketches.md (code designs)
[x] Write use-cases.md (practical applications)
[x] Write progress-tracker.md (this file)

Completed: 2025-11-06

Phase 1: Core Restricted Substitutions

Duration: 1-2 weeks Status: ⏳ Not Started

Task 1.1: Create SubstitutionSet Structure (2 days)

File: /src/transducer/substitution.rs (NEW)

[ ] Create new file src/transducer/substitution.rs
[ ] Define SubstitutionSet struct with HashSet<(char, char)> backend
[ ] Implement new() constructor
[ ] Implement with_capacity() constructor
[ ] Implement add(source, target) method
[ ] Implement add_bidirectional(a, b) method
[ ] Implement is_allowed(source, target) method
[ ] Implement remove(), len(), is_empty(), clear() methods
[ ] Implement iter() method
[ ] Implement Default trait
[ ] Implement FromIterator trait
[ ] Add serde Serialize and Deserialize derives
[ ] Write unit tests for all operations
[ ] Write documentation with examples
[ ] Run cargo test - all tests pass
[ ] Run cargo clippy - no warnings

Acceptance Criteria:

SubstitutionSet compiles without errors
All unit tests pass
Documentation renders correctly
No clippy warnings

Task 1.2: Add SubstitutionSet to TransducerBuilder (1 day)

File: /src/transducer/builder.rs

[ ] Add use crate::transducer::substitution::SubstitutionSet;
[ ] Add substitution_set: Option<SubstitutionSet> field to TransducerBuilder struct
[ ] Initialize substitution_set: None in new() constructor
[ ] Implement with_substitution_set(set: SubstitutionSet) method
[ ] Add documentation to with_substitution_set() with examples
[ ] Pass substitution_set to Transducer in build_from_iter()
[ ] Run cargo check - compiles successfully
[ ] Run cargo test - no regressions
[ ] Run cargo doc - documentation builds

Acceptance Criteria:

Builder compiles with new field
Backward compatibility maintained (existing tests pass)
Documentation example compiles

Task 1.3: Add SubstitutionSet to Transducer (0.5 days)

File: /src/transducer/mod.rs

[ ] Add substitution_set: Option<SubstitutionSet> field to Transducer struct
[ ] Store substitution_set in Transducer constructor
[ ] Pass substitution_set.as_ref() to QueryIterator::new() in fuzzy_search()
[ ] Run cargo check - compiles successfully

Acceptance Criteria:

Transducer stores substitution_set
Compiles without errors

Task 1.4: Modify Standard Algorithm Transitions (1 day)

File: /src/transducer/transition.rs

[ ] Add substitution_set: Option<&SubstitutionSet> parameter to standard_transition()
[ ] Locate substitution check in transition logic (currently unconditional)

[ ] Add conditional check:

let substitution_allowed = match substitution_set {
    None => true,
    Some(set) => set.is_allowed(query_char, dict_char),
};

if substitution_allowed {
    next_state.insert(Position::new(i + 1, e + 1, false));
}

[ ] Verify insert/delete transitions remain unchanged (always allowed)
[ ] Run cargo test - all existing tests pass
[ ] Write new test: empty substitution set (no substitutions allowed)
[ ] Write new test: specific substitution set (only allowed pairs work)
[ ] Run cargo clippy - no warnings

Acceptance Criteria:

Standard algorithm respects substitution restrictions
No regression in existing tests
New tests pass

Task 1.5: Thread Substitution Set Through Query Pipeline (1 day)

File: /src/transducer/query.rs

[ ] Add substitution_set: Option<&'a SubstitutionSet> field to QueryIterator struct
[ ] Add substitution_set: Option<&'a SubstitutionSet> parameter to QueryIterator::new()
[ ] Store substitution_set in QueryIterator construction
[ ] Pass self.substitution_set to standard_transition() in next_state() method
[ ] Run cargo test - all tests pass
[ ] Run cargo check - compiles successfully

Acceptance Criteria:

QueryIterator passes substitution_set through pipeline
All existing tests pass (backward compatibility)
Compiles without errors

Task 1.6: End-to-End Integration Test (1 day)

File: /tests/integration/universal_la.rs (NEW)

[ ] Create new integration test file
[ ] Write test: keyboard proximity (QWERTY-like set)
- Query with allowed substitution → finds match
- Query with disallowed substitution → no match
[ ] Write test: empty substitution set
- Only exact matches allowed (distance=0)
- No substitutions possible
[ ] Write test: None substitution set
- All substitutions allowed (standard Levenshtein)
[ ] Run cargo test --test universal_la - all tests pass
[ ] Verify test coverage > 90% for new code

Acceptance Criteria:

Integration tests pass
Demonstrates end-to-end functionality
Coverage adequate

Task 1.7: Documentation and Examples (1 day)

File: /examples/basic_restricted_substitutions.rs (NEW)

[ ] Create example file showing basic usage
[ ] Example: Simple keyboard proximity (a↔s, s↔d)
[ ] Example: Query with allowed substitution
[ ] Example: Query with disallowed substitution
[ ] Add comments explaining behavior
[ ] Run cargo run --example basic_restricted_substitutions
[ ] Update main README.md with Universal LA section
[ ] Run cargo doc --open - verify documentation

Acceptance Criteria:

Example compiles and runs
Output demonstrates restricted substitutions
Documentation updated

Phase 1 Completion Checklist

[ ] All Phase 1 tasks completed
[ ] cargo test - all tests pass
[ ] cargo clippy - no warnings
[ ] cargo doc - documentation builds
[ ] No performance regression for None substitution_set case
[ ] Code review completed (if applicable)
[ ] Commit changes with descriptive message

Target Completion: Week 2

Phase 2: Practical Use Cases

Duration: 1 week Status: ⏳ Not Started

Task 2.1: QWERTY Keyboard Preset (1 day)

File: /src/transducer/substitution.rs

[ ] Implement SubstitutionSet::qwerty() constructor
[ ] Add all horizontal adjacencies (row 1, row 2, row 3)
[ ] Add all diagonal adjacencies (row 1↔2, row 2↔3)
[ ] Implement add_uppercase_variants() helper method
[ ] Write unit tests for QWERTY preset
[ ] Add to TransducerBuilder: with_qwerty_substitutions() method
[ ] Write documentation with examples
[ ] Run tests - all pass

Acceptance Criteria:

QWERTY preset includes all adjacencies
Tests verify correct pairs included
Builder convenience method works

Task 2.2: AZERTY Keyboard Preset (0.5 days)

File: /src/transducer/substitution.rs

[ ] Implement SubstitutionSet::azerty() constructor
[ ] Add AZERTY-specific adjacencies
[ ] Write unit tests
[ ] Add to TransducerBuilder: with_azerty_substitutions() method
[ ] Documentation

Acceptance Criteria:

AZERTY preset correct
Tests pass

Task 2.3: Dvorak Keyboard Preset (0.5 days)

File: /src/transducer/substitution.rs

[ ] Implement SubstitutionSet::dvorak() constructor
[ ] Add Dvorak-specific adjacencies
[ ] Write unit tests
[ ] Add to TransducerBuilder: with_dvorak_substitutions() method
[ ] Documentation

Acceptance Criteria:

Dvorak preset correct
Tests pass

Task 2.4: OCR Confusion Preset (1 day)

File: /src/transducer/substitution.rs

[ ] Implement SubstitutionSet::ocr_confusions() constructor
[ ] Add digit-letter confusions (0↔O, 1↔I↔l, 5↔S, 8↔B)
[ ] Add letter-letter confusions (c↔e, n↔m, u↔v, r↔n)
[ ] Write unit tests with OCR examples
[ ] Add to TransducerBuilder: with_ocr_confusions() method
[ ] Documentation with OCR use case

Acceptance Criteria:

OCR preset includes common confusions
Tests demonstrate OCR correction
Documentation clear

Task 2.5: Phonetic English Preset (1 day)

File: /src/transducer/substitution.rs

[ ] Implement SubstitutionSet::phonetic_english() constructor
[ ] Add consonant confusions (c↔k, c↔s, f↔v, s↔z)
[ ] Add vowel confusions (a↔e, i↔y)
[ ] Write unit tests with phonetic examples
[ ] Add to TransducerBuilder: with_phonetic_english() method
[ ] Documentation

Acceptance Criteria:

Phonetic preset covers common sound-alikes
Tests demonstrate phonetic matching
Documentation with examples

Task 2.6: Examples and Documentation (1 day)

Files: /examples/keyboard_spell_checker.rs, /examples/ocr_correction.rs (NEW)

[ ] Create keyboard_spell_checker.rs example
- Load word list
- Build with QWERTY restrictions
- Demonstrate typo correction
[ ] Create ocr_correction.rs example
- Load scanned text
- Build with OCR confusions
- Demonstrate digit/letter correction
[ ] Update README.md with Universal LA section
- Overview of feature
- Links to examples
- Usage guide
[ ] Run cargo run --example keyboard_spell_checker
[ ] Run cargo run --example ocr_correction
[ ] Run cargo doc --open - verify all docs render

Acceptance Criteria:

Examples compile and run
Output demonstrates use cases
README updated with clear guide

Phase 2 Completion Checklist

[ ] All Phase 2 tasks completed
[ ] Five preset substitution sets available
[ ] Examples demonstrate real-world use cases
[ ] Documentation comprehensive
[ ] cargo test - all tests pass
[ ] Commit changes

Target Completion: Week 3

Phase 3: Integration with Existing Algorithms

Duration: 1 week Status: ⏳ Not Started

Task 3.1: Transposition Algorithm Integration (2 days)

File: /src/transducer/transition.rs

[ ] Add substitution_set: Option<&SubstitutionSet> parameter to transposition_transition()
[ ] Locate substitution checks in transposition logic
[ ] Add conditional substitution validation (similar to Standard)
[ ] Verify transposition operation itself remains unrestricted
[ ] Write unit tests:
- [ ] Transposition works (ab → ba)
- [ ] Substitution restrictions apply
- [ ] Combined transposition + restricted substitution
[ ] Run existing transposition tests - no regression
[ ] Documentation update

Acceptance Criteria:

Transposition + restricted substitutions works
No regression in existing tests
New tests pass

Task 3.2: MergeAndSplit Algorithm Integration (2 days)

File: /src/transducer/transition.rs

[ ] Add substitution_set: Option<&SubstitutionSet> parameter to merge_split_transition()
[ ] Locate substitution checks in merge/split logic
[ ] Add conditional substitution validation
[ ] Verify merge/split operations remain unrestricted
[ ] Write unit tests:
- [ ] Merge works (two chars → one)
- [ ] Split works (one char → two)
- [ ] Substitution restrictions apply
- [ ] Combined merge/split + restricted substitution
[ ] Run existing merge/split tests - no regression
[ ] Documentation update

Acceptance Criteria:

MergeAndSplit + restricted substitutions works
No regression
New tests pass

Task 3.3: Update Query Pipeline for All Algorithms (0.5 days)

File: /src/transducer/query.rs

[ ] Update next_state() to pass substitution_set to all algorithms:
- [ ] Algorithm::Transposition → transposition_transition()
- [ ] Algorithm::MergeAndSplit → merge_split_transition()
[ ] Run cargo check - compiles successfully
[ ] Run cargo test - all tests pass

Acceptance Criteria:

All algorithms receive substitution_set parameter
Compiles and tests pass

Task 3.4: Comprehensive Integration Tests (1 day)

File: /tests/integration/universal_la.rs

[ ] Write test: Standard + restricted substitutions
[ ] Write test: Transposition + restricted substitutions
[ ] Write test: MergeAndSplit + restricted substitutions
[ ] Write test: Edge cases
- Empty substitution set
- Single allowed pair
- Large substitution set
[ ] Run cargo test --test universal_la - all pass
[ ] Verify coverage

Acceptance Criteria:

Integration tests cover all algorithms
Edge cases tested
All tests pass

Task 3.5: Performance Benchmarks (2 days)

File: /benches/universal_la.rs (NEW)

[ ] Create benchmark file
[ ] Benchmark: Baseline (no restrictions, None)
- Standard algorithm
- Transposition algorithm
- MergeAndSplit algorithm
[ ] Benchmark: With restrictions (QWERTY preset)
- Standard algorithm
- Transposition algorithm
- MergeAndSplit algorithm
[ ] Benchmark: Different substitution set sizes
- Small set (10 pairs)
- Medium set (100 pairs)
- Large set (500 pairs)
[ ] Run cargo bench --bench universal_la
[ ] Document results in /docs/research/universal-levenshtein/benchmarks.md
[ ] Analyze overhead percentage
[ ] Identify optimization opportunities (for Phase 4)

Acceptance Criteria:

Benchmarks run successfully
Overhead < 20% (acceptable)
Results documented
Baseline for Phase 4 optimization

Phase 3 Completion Checklist

[ ] All Phase 3 tasks completed
[ ] All three algorithms support restricted substitutions
[ ] Integration tests comprehensive
[ ] Performance benchmarks complete
[ ] Overhead documented and acceptable
[ ] cargo test - all tests pass
[ ] cargo bench - benchmarks run
[ ] Commit changes

Target Completion: Week 4

Phase 4: Optimization (Optional)

Duration: 1 week Status: ⏳ Not Started Priority: Low (only if overhead > 15%)

Task 4.1: Perfect Hashing for Static Presets (2 days)

File: /src/transducer/substitution.rs

[ ] Add phf crate dependency to Cargo.toml
[ ] Create compile-time perfect hash maps for presets
- [ ] QWERTY
- [ ] AZERTY
- [ ] Dvorak
- [ ] OCR confusions
- [ ] Phonetic English
[ ] Implement qwerty_optimized(), etc. constructors
[ ] Benchmark: Compare HashSet vs phf::Map lookup
[ ] Document performance improvement
[ ] Update builder to use optimized presets

Acceptance Criteria:

phf-based lookups faster than HashSet
Overhead reduced by 5-10%
Tests still pass

Task 4.2: Bit Vector for ASCII (1 day)

File: /src/transducer/substitution.rs

[ ] Implement AsciiSubstitutionSet struct
[ ] Use 256×256 bit array (8 KB)
[ ] Implement add(), is_allowed() for bit vector
[ ] Benchmark: Compare with HashSet
[ ] Create SubstitutionSet::ascii_optimized() constructor
[ ] Document when to use ASCII optimization

Acceptance Criteria:

Bit vector faster for ASCII alphabets
Memory usage acceptable (8 KB)
Tests pass

Task 4.3: Subsumption Logic Review (2 days)

File: /src/transducer/position.rs

[ ] Review current subsumption predicates
[ ] Create test cases for triangle inequality violations
[ ] Investigate if subsumption breaks with restricted substitutions
[ ] Options:
- [ ] If OK: Document that current subsumption works
- [ ] If broken: Modify subsumption for Universal LA
- [ ] If complex: Disable subsumption for restricted substitutions
[ ] Run correctness tests
[ ] Benchmark performance impact

Acceptance Criteria:

Subsumption behavior documented
No correctness issues
Performance acceptable

Task 4.4: SIMD Acceleration (Optional, 1 day)

File: /src/transducer/substitution.rs

[ ] Investigate SIMD for batch substitution checks
[ ] Prototype SIMD implementation (if feasible)
[ ] Benchmark improvement
[ ] Document findings (may not be worth complexity)

Acceptance Criteria:

SIMD feasibility assessed
If beneficial: implemented and tested
If not: documented why

Phase 4 Completion Checklist

[ ] All Phase 4 tasks completed (or decided not needed)
[ ] Overhead < 10% (target achieved or documented)
[ ] Performance improvements measured
[ ] Documentation updated with optimization techniques
[ ] cargo test - all tests pass
[ ] cargo bench - improved performance
[ ] Commit changes

Target Completion: Week 5

Release Checklist

Before merging to main branch:

[ ] All phases completed (Phase 4 optional)
[ ] cargo test - all tests pass (100%)
[ ] cargo clippy - no warnings
[ ] cargo doc - documentation builds successfully
[ ] cargo bench - benchmarks run without errors
[ ] Code review completed (if applicable)
[ ] CHANGELOG.md updated with new features
[ ] API documentation complete
[ ] Examples tested and working
[ ] README.md updated
[ ] Performance overhead documented
[ ] Migration guide written (if needed - likely not)
[ ] CI/CD pipeline passes

Post-Release Tasks

[ ] Monitor GitHub issues for defect reports
[ ] Gather user feedback on API design
[ ] Consider additional preset substitution sets based on user requests
[ ] Track performance in real-world use cases
[ ] Update documentation based on user questions

Notes and Issues

Blockers

None currently

Open Questions

To be filled in during implementation

Decisions Made

2025-11-06: Chose Option B (Configuration-Based) over Option A (Algorithm Variant)
- Rationale: Better composability, aligns with paper, future-proof
- Decision documented in decision-matrix.md
2025-11-06: Use HashSet<(char, char)> for SubstitutionSet backend
- Rationale: Simple, O(1) lookup, sufficient for Phase 1
- Can optimize in Phase 4 if needed

Metrics

Code Changes

New files created: 0
Files modified: 0
Lines added: 0
Lines removed: 0

(Update as implementation progresses)

Test Coverage

Unit tests: 0 / not enumerated in this archived tracker
Integration tests: 0 / not enumerated in this archived tracker
Benchmark tests: 0 / not enumerated in this archived tracker
Coverage percentage: 0%

(Update after each phase)

Performance

Baseline (no restrictions): not measured in this archived tracker
With restrictions (QWERTY): not measured in this archived tracker
Overhead percentage: not measured in this archived tracker

(Update after Phase 3 benchmarks)

Timeline

Phase	Start Date	Target End	Actual End	Status
Phase 0 (Planning)	2025-11-06	2025-11-06	2025-11-06	✅ Complete
Phase 1 (Core)	not scheduled	Week 2	—	⏳ Not Started
Phase 2 (Use Cases)	not scheduled	Week 3	—	⏳ Not Started
Phase 3 (Integration)	not scheduled	Week 4	—	⏳ Not Started
Phase 4 (Optimization)	not scheduled	Week 5	—	⏳ Not Started

Resources

Documentation

README.md - Overview and quick start
technical-analysis.md - Codebase analysis
implementation-plan.md - Detailed phase plan
decision-matrix.md - Implementation approach comparison
architectural-sketches.md - Code designs
use-cases.md - Practical applications

Paper

"Universal Levenshtein Automata for a Generalization of the Levenshtein Distance"
Authors: Petar Mitankin, Stoyan Mihov, Klaus U. Schulz
Location: /home/dylon/Papers/Approximate String Matching/Universal Levenshtein Automata for a Generalization of the Levenshtein Distance.pdf

External Resources

Last Updated: 2025-11-06 Next Update: After Phase 1 completion Maintained By: Implementation team

❮Universal Levenshtein Automata - Implementation Plan Universal Levenshtein Automata - Technical Analysis❯

Can you improve this documentation?Edit on GitHub

cljdoc builds & hosts documentation for Clojure/Script libraries

Keyboard shortcuts

`Ctrl`+`k`	Jump to recent docs
`←`	Move to previous article
`→`	Move to next article
`Ctrl`+`/`	Jump to the search field

Raise an issue Browse cljdoc source Chat on Slack

× close