Liking cljdoc? Tell your friends :D

Levenshtein Distance Functions: Implementation Summary

Date: 2025-10-30 Author: Claude Code Status: ✅ Core Implementation Complete

Executive Summary

Successfully implemented three recursive memoized Levenshtein distance functions matching the C++ reference implementation, with comprehensive testing, benchmarking infrastructure, and optimization framework in place.

Key Achievements

✅ Three Complete Implementations:

standard_distance_recursive() - Standard Levenshtein (insertion, deletion, substitution)
transposition_distance_recursive() - optimal string alignment (restricted Damerau)
merge_and_split_distance() - Extended variant (adds merge/split operations) [NEW]

✅ 36 Property-Based Tests - All passing, covering mathematical distance metric properties

✅ Thread-Safe Memoization - Efficient caching with DashMap or RwLock<HashMap>

✅ Unicode Support - Correct character-based (not byte-based) operations

✅ Comprehensive Benchmarks - 10 benchmark groups with 100+ test cases

✅ Profiling Infrastructure - Scripts for flamegraph, perf, and cachegrind analysis

✅ Formal Verification Research - Evaluated Prusti, Kani, Creusot, and other tools

Implementation Details

1. Core Infrastructure (`src/distance/mod.rs`)

SymmetricPair

Ensures d(a,b) == d(b,a) share the same cache key through lexicographic ordering:

struct SymmetricPair {
    first: Arc<str>,   // Smaller string (lexicographically)
    second: Arc<str>,  // Larger string
}

Benefits:

50% reduction in cache entries
Guaranteed symmetry consistency
Efficient Arc<str> for string sharing

MemoCache

Thread-safe memoization with conditional compilation:

pub struct MemoCache {
    #[cfg(feature = "eviction-dashmap")]
    cache: DashMap<SymmetricPair, usize>,  // Lock-free

    #[cfg(not(feature = "eviction-dashmap"))]
    cache: RwLock<HashMap<SymmetricPair, usize>>,  // Standard
}

Features:

Lock-free with DashMap (feature flag)
Read-write locks for standard build
Zero-cost abstraction pattern

Helper Functions

substring_from(s: &str, char_offset: usize):

Character-aware substring extraction
Mirrors C++ f(u, t) function
Handles multi-byte UTF-8 correctly

strip_common_affixes(a: &str, b: &str):

Removes common prefix and suffix
Major optimization for similar strings
Prepared for future use

2. Algorithm Implementations

Standard Distance (`standard_distance_recursive`)

Operations: Insert, Delete, Substitute Complexity: O(m×n) worst-case, but with optimizations:

Optimizations:

Common prefix elimination: Skip matching prefixes before recursion
Early exit: Return immediately when distance becomes 0
Memoization: Cache all computed subproblems

Example:

let cache = create_memo_cache();
assert_eq!(standard_distance_recursive("kitten", "sitting", &cache), 3);

Transposition Distance (`transposition_distance_recursive`)

Operations: Insert, Delete, Substitute, Transpose (swap adjacent chars) Semantics: optimal string alignment, also called restricted Damerau distance. Unlike unrestricted Damerau–Levenshtein, a substring cannot be edited twice.

Key Logic (from C++):

// Check if characters at positions match in transposed order
if a == b1 && a1 == b {
    // Transpose operation: skip both characters
    let trans_dist = transposition_distance_recursive(ss, tt, cache);
    distance = distance.min(trans_dist);
}

Example:

let cache = create_memo_cache();
assert_eq!(transposition_distance_recursive("ab", "ba", &cache), 1);  // One swap
assert_eq!(transposition_distance_recursive("test", "tset", &cache), 1);

Merge and Split Distance (`merge_and_split_distance`) [NEW]

Operations: Insert, Delete, Substitute, Merge (2→1 chars), Split (1→2 chars)

Use Cases:

OCR error correction ("m" → "rn", "cl" → "d")
Phonetic matching
Specialized text correction

Split Operation:

if t_remaining.chars().count() > 1 {
    // Skip 2 chars in target: one source char → two target chars
    let tt = substring_from(&t_remaining, 2);
    let split_dist = merge_and_split_distance(s, tt, cache);
    distance = distance.min(split_dist);
}

Merge Operation:

if s_remaining.chars().count() > 1 {
    // Skip 2 chars in source: two source chars → one target char
    let ss = substring_from(&s_remaining, 2);
    let merge_dist = merge_and_split_distance(ss, t, cache);
    distance = distance.min(merge_dist);
}

Example:

let cache = create_memo_cache();
// Split: "m" → "rn" is one operation
assert_eq!(merge_and_split_distance("m", "rn", &cache), 1);
// Merge: "rn" → "m" is one operation
assert_eq!(merge_and_split_distance("rn", "m", &cache), 1);

3. Comparison with C++ Implementation

Aspect	C++ Implementation	Rust Implementation
Algorithm	Recursive + memoization	✅ Identical
Prefix optimization	Yes	✅ Yes
Early exit	Yes	✅ Yes
Thread safety	`std::shared_mutex`	✅ `DashMap` or `RwLock`
Cache key	`SymmetricPair`	✅ `SymmetricPair`
Hash function	MurmurHash2	✅ Default hasher
Helper function	`f(u, t)` = `u.substr(1+t)`	✅ `substring_from()`
Unicode	C++ chars (often ASCII)	✅ Better: true Unicode

Key Differences:

Rust has superior Unicode handling (character-based, not byte-based)
Rust uses Arc<str> for efficient string sharing
C++ uses raw pointers, Rust uses safe references

Testing & Verification

Unit Tests (`src/distance/mod.rs`)

20+ unit tests covering edge cases
Empty strings, identical strings, Unicode
Recursive vs iterative equivalence

Property-Based Tests (`tests/proptest_distance_metrics.rs`)

36 tests covering mathematical properties:

For All Algorithms:

✅ Non-negativity: d(x,y) ≥ 0
✅ Identity: d(x,x) = 0
✅ Indiscernibles: d(x,y) = 0 ⟹ x = y
✅ Symmetry: d(x,y) = d(y,x)
✅ Left invariance: d(zx, zy) = d(x,y)
✅ Right invariance: d(xz, yz) = d(x,y)

Standard Distance Only:

✅ Triangle inequality: d(x,z) ≤ d(x,y) + d(y,z)

Note: Transposition and merge/split distances do NOT satisfy triangle inequality (known limitation).

Cross-Validation:

✅ Recursive matches iterative for all test cases
✅ Unicode correctness across character sets

Test Configuration:

1000 test cases per property
ASCII and Unicode string generators
Comprehensive edge case coverage

Benchmarking Infrastructure

Benchmark Suite (`benches/distance_benchmarks.rs`)

10 Benchmark Groups:

standard_distance/iterative - Baseline iterative implementation
standard_distance/recursive - New recursive with cold cache
standard_distance/recursive_warm_cache - Cached performance
transposition_distance/iterative - Iterative transposition
transposition_distance/recursive - Recursive transposition
merge_split_distance - New merge/split algorithm
algorithm_comparison - Side-by-side comparison
scaling/string_length - Performance vs string length
cache/effectiveness - Cold vs warm cache performance
unicode - Unicode performance across character sets

Test Data:

Short strings (0-10 chars): "test", "best"
Medium strings (10-50 chars): "programming", "programing"
Long strings (50-200 chars): Full sentences
Unicode: ASCII, Latin (café), Japanese (日本語), Emoji (🌍)
Similarity patterns: Identical, 1-edit, prefix-match, completely different

Metrics Collected:

Time: Mean, median, std dev
Throughput: Bytes/second
Outliers: Statistical analysis
Sample size: 100 samples per benchmark

Performance Characteristics

Expected Performance Patterns

Iterative DP:

Time: O(m×n) predictable
Space: O(min(m,n)) two-row optimization
Best for: Single queries, different string pairs
Cache locality: Excellent (sequential access)

Recursive + Memoization:

Time: O(m×n) worst-case, much better with common prefixes
Space: O(cache_size) grows with unique subproblems
Best for: Similar strings, repeated queries
Cache locality: Depends on cache implementation

Optimization Opportunities

Already Implemented:

✅ Common prefix stripping ✅ Early exit on distance == 0 ✅ Symmetric caching (50% reduction) ✅ Thread-safe concurrent access

Future Optimizations:

⏭️ SIMD vectorization for DP matrix computation ⏭️ Common suffix stripping (prepared but not used) ⏭️ Cache eviction policies (LRU, size-based) ⏭️ Block processing for large strings ⏭️ GPU acceleration for batch processing

Profiling Infrastructure

Scripts Created

scripts/profile_distances.sh: Automated profiling with multiple tools:

Flamegraphs: Visual call stack analysis
- flamegraph_standard_iterative.svg
- flamegraph_standard_recursive.svg
perf stat: Hardware counter analysis
- Cache references/misses
- Branch prediction
- Instructions per cycle
perf record/report: Detailed profiling
- Hotspot identification
- Function-level statistics
perf annotate: Assembly-level analysis
- Instruction-level bottlenecks

Usage:

./scripts/profile_distances.sh
ls profiling_results/  # View generated reports

Formal Verification Research

Tool Evaluation

Evaluated 5 formal verification tools for Rust:

Tool	Score	Recommendation
Prusti	⭐⭐⭐⭐⭐	PRIMARY CHOICE
Kani	⭐⭐⭐⭐	Fallback for bounded verification
Creusot	⭐⭐⭐⭐	Alternative if Prusti fails
coq-of-rust	⭐⭐	Too manual, overkill
Verus	⭐⭐	Requires code rewrite

Recommended: Prusti

Why:

Low annotation overhead
Excellent VSCode integration
Can express distance metric properties naturally
Active development
Works with safe Rust (our code)

Example Specification:

use prusti_contracts::*;

#[pure]
#[ensures(result >= 0)]  // Non-negativity
#[ensures(source == target ==> result == 0)]  // Identity
#[ensures(result == standard_distance(target, source))]  // Symmetry
pub fn standard_distance(source: &str, target: &str) -> usize {
    // ... implementation
}

Next Steps:

Install: cargo install prusti-cli
Add specifications to iterative functions first
Verify with: cargo prusti
Extend to recursive functions if successful

See: docs/FORMAL_VERIFICATION_RESEARCH.md for full analysis

Documentation & Examples

Public API

Core Functions:

// Iterative implementations (existing)
pub fn standard_distance(source: &str, target: &str) -> usize
pub fn transposition_distance(source: &str, target: &str) -> usize

// Recursive implementations with memoization (NEW)
pub fn standard_distance_recursive(source: &str, target: &str, cache: &MemoCache) -> usize
pub fn transposition_distance_recursive(source: &str, target: &str, cache: &MemoCache) -> usize
pub fn merge_and_split_distance(source: &str, target: &str, cache: &MemoCache) -> usize  // NEW!

// Cache management (NEW)
pub fn create_memo_cache() -> MemoCache

Usage Examples

Simple Usage:

use liblevenshtein::distance::*;

// Iterative (no cache needed)
let dist = standard_distance("test", "best");
assert_eq!(dist, 1);

// Recursive with cache
let cache = create_memo_cache();
let dist = standard_distance_recursive("test", "best", &cache);
assert_eq!(dist, 1);

Repeated Queries (cache benefit):

let cache = create_memo_cache();

let words = vec!["test", "best", "rest", "fest"];
for w1 in &words {
    for w2 in &words {
        let dist = standard_distance_recursive(w1, w2, &cache);
        println!("d({}, {}) = {}", w1, w2, dist);
    }
}
// Cache reused across all 16 queries!

Merge/Split for OCR:

let cache = create_memo_cache();

// Common OCR errors
assert_eq!(merge_and_split_distance("m", "rn", &cache), 1);  // Split
assert_eq!(merge_and_split_distance("rn", "m", &cache), 1);  // Merge
assert_eq!(merge_and_split_distance("cl", "d", &cache), 1);  // Merge

Files Created/Modified

New Files:

✅ benches/distance_benchmarks.rs - Comprehensive benchmark suite
✅ tests/proptest_distance_metrics.rs - Property-based tests (36 tests)
✅ scripts/profile_distances.sh - Automated profiling script
✅ docs/FORMAL_VERIFICATION_RESEARCH.md - Tool evaluation
✅ docs/DISTANCE_FUNCTIONS_IMPLEMENTATION.md - This document

Modified Files:

✅ src/distance/mod.rs - Added 350+ lines:
- SymmetricPair struct
- MemoCache infrastructure
- Three recursive distance functions
- Helper functions
- 10+ new tests
✅ Cargo.toml - Added benchmark entry