Restricted Substitutions Guide

Version: 0.9.1 Last Updated: 2025-11-12

---

Table of Contents

1. Introduction
2. Quick Start
3. Use Cases
4. Basic Examples
5. Advanced Examples
6. Performance Considerations
7. Best Practices
8. FAQ

---

Introduction

Restricted substitutions allow you to define custom character equivalences for fuzzy string matching. Instead of treating all character substitutions equally (as standard Levenshtein distance does), you can specify which substitutions should be treated as zero-cost (free).

What Are Restricted Substitutions?

In standard Levenshtein distance:

• "cat" vs "kat" has distance 1 (c→k substitution costs 1)
• "cat" vs "cut" has distance 1 (a→u substitution costs 1)

With restricted substitutions:

• You can define c↔k as zero-cost (phonetically equivalent)
• "cat" matches "kat" with distance 0 (c↔k is free)
• "cat" vs "cut" still has distance 1 (a→u costs 1)

Why Use Restricted Substitutions?

• Phonetic Matching: Treat phonetically similar characters as equivalent (f↔ph, c↔k, s↔z)
• Keyboard Typos: Allow common keyboard proximity errors (q↔w, a↔s)
• Diacritics: Match accented/unaccented variants (é↔e, ñ↔n)
• OCR Errors: Handle visually similar characters (0↔O, 1↔I↔l)
• Leetspeak: Match common substitutions (3↔e, @↔a, 0↔o)
• Script Variants: Allow hiragana↔katakana, simplified↔traditional

Zero-Cost Abstraction

The Unrestricted policy (default behavior) is a zero-sized type that adds zero overhead:

• Size: 0 bytes
• Runtime cost: 0 (compiler optimizes away all checks)
• Performance: Identical to pre-generic implementation

Only when you use Restricted policy do you pay for the feature (1–5% overhead).

---

Quick Start

Installation

Add to your Cargo.toml:

[dependencies]
liblevenshtein = "0.9.1"

Minimal Example

use liblevenshtein::prelude::*;
use liblevenshtein::transducer::{SubstitutionSet, Restricted, Algorithm};

// 1. Create a dictionary
let dict = DoubleArrayTrie::from_terms(vec!["cat", "phone"]);

// 2. Define substitutions
let mut substitutions = SubstitutionSet::new();
substitutions.allow('c', 'k');  // c → k
substitutions.allow('k', 'c');  // k → c (symmetric)

// 3. Create policy
let policy = Restricted::new(&substitutions);

// 4. Create transducer with policy
let transducer = Transducer::with_policy(dict, Algorithm::Standard, policy);

// 5. Query with substitutions
let results: Vec<String> = transducer.query("kat", 0).collect();
assert!(results.contains(&"cat".to_string()));  // "kat" matches "cat" with distance 0!

---

Use Cases

1. Phonetic Matching

Problem: Users search using phonetic spellings ("fone" for "phone", "senter" for "center").

Solution: Use phonetic equivalences.

use liblevenshtein::prelude::*;
use liblevenshtein::transducer::{SubstitutionSet, Algorithm};

// Use preset phonetic substitutions
let phonetic = SubstitutionSet::phonetic_basic();

let dict = DoubleArrayTrie::from_terms(vec!["phone", "center", "dogs"]);
let transducer = Transducer::with_substitutions(dict, Algorithm::Standard, phonetic);

// Phonetic queries match correctly
assert_eq!(transducer.query("fone", 1).count(), 1);   // matches "phone"
assert_eq!(transducer.query("senter", 1).count(), 1); // matches "center"
assert_eq!(transducer.query("dogz", 1).count(), 1);   // matches "dogs"

Included Equivalences:

• f ↔ ph (phone/fone)
• c ↔ k (cat/kat)
• c ↔ s (cent/sent)
• s ↔ z (dogs/dogz)

2. Keyboard Typo Tolerance

Problem: Users make typos by hitting adjacent keys ("qwerty" → "awerty").

Solution: Use keyboard proximity substitutions.

use liblevenshtein::prelude::*;
use liblevenshtein::transducer::{SubstitutionSet, Algorithm};

// Use QWERTY keyboard proximity
let keyboard = SubstitutionSet::keyboard_qwerty();

let dict = DoubleArrayTrie::from_terms(vec!["password", "hello"]);
let transducer = Transducer::with_substitutions(dict, Algorithm::Standard, keyboard);

// Adjacent key typos are caught
assert!(transducer.query("passwird", 1).any(|s| s == "password")); // o→i adjacent
assert!(transducer.query("hwllo", 1).any(|s| s == "hello"));       // e→w adjacent

Included Adjacencies:

• Horizontal: q↔w, w↔e, e↔r, etc.
• Vertical: q↔a, w↔s, e↔d, etc.

3. Unicode Diacritics (Character-Level)

Problem: Users search without accents ("cafe" should match "café").

Solution: Use SubstitutionSetChar for Unicode support.

use liblevenshtein::prelude::*;
use liblevenshtein::transducer::{SubstitutionSetChar, RestrictedChar, Algorithm};

// Use preset diacritic equivalences
let diacritics = SubstitutionSetChar::diacritics_latin();

let dict = DoubleArrayTrieChar::from_terms(vec!["café", "niño", "über"]);
let policy = RestrictedChar::new(&diacritics);
let transducer = Transducer::with_policy(dict, Algorithm::Standard, policy);

// Diacritic variants match with distance 0
let results: Vec<String> = transducer.query("cafe", 0).collect();
assert!(results.contains(&"café".to_string()));

let results: Vec<String> = transducer.query("nino", 0).collect();
assert!(results.contains(&"niño".to_string()));

Included Diacritics:

• á, à, â, ä, ã, å ↔ a
• é, è, ê, ë ↔ e
• í, ì, î, ï ↔ i
• ó, ò, ô, ö, õ ↔ o
• ú, ù, û, ü ↔ u
• ñ ↔ n, ç ↔ c

4. OCR Error Correction

Problem: OCR systems confuse visually similar characters (0/O, 1/I/l).

Solution: Use OCR-friendly substitutions.

use liblevenshtein::prelude::*;
use liblevenshtein::transducer::{SubstitutionSet, Algorithm};

// Use OCR confusion pairs
let ocr = SubstitutionSet::ocr_friendly();

let dict = DoubleArrayTrie::from_terms(vec!["HELLO", "WORLD"]);
let transducer = Transducer::with_substitutions(dict, Algorithm::Standard, ocr);

// OCR confusions are tolerated
assert!(transducer.query("HELL0", 0).any(|s| s == "HELLO")); // O→0
assert!(transducer.query("W0RLD", 0).any(|s| s == "WORLD")); // O→0

Included Confusions:

• 0 ↔ O, o
• 1 ↔ I, l
• 5 ↔ S
• 8 ↔ B

5. Leetspeak Normalization

Problem: Normalize leetspeak variations ("l33t" → "leet").

Solution: Use leetspeak substitutions.

use liblevenshtein::prelude::*;
use liblevenshtein::transducer::{SubstitutionSet, Algorithm};

// Use leetspeak equivalences
let leet = SubstitutionSet::leet_speak();

let dict = DoubleArrayTrie::from_terms(vec!["leet", "hacker", "root"]);
let transducer = Transducer::with_substitutions(dict, Algorithm::Standard, leet);

// Leetspeak variants match
assert!(transducer.query("l33t", 0).any(|s| s == "leet"));     // 3→e
assert!(transducer.query("h4ck3r", 1).any(|s| s == "hacker")); // 4→a, 3→e
assert!(transducer.query("r00t", 0).any(|s| s == "root"));     // 0→o

Included Substitutions:

• 3 ↔ e
• @ ↔ a
• 0 ↔ o
• 1 ↔ i, l
• $ ↔ s
• 7 ↔ t

---

Basic Examples

Example 1: Custom Substitution Set

Build your own substitution set from scratch:

use liblevenshtein::prelude::*;
use liblevenshtein::transducer::{SubstitutionSet, Restricted, Algorithm};

// Build custom substitution set
let mut custom = SubstitutionSet::new();

// Add bidirectional equivalences
custom.allow('v', 'w'); custom.allow('w', 'v'); // v ↔ w
custom.allow('i', 'y'); custom.allow('y', 'i'); // i ↔ y
custom.allow('ph', 'f'); custom.allow('f', 'p'); // f ↔ ph (multi-char handled as 'p')

let dict = DoubleArrayTrie::from_terms(vec!["very", "happy"]);
let policy = Restricted::new(&custom);
let transducer = Transducer::with_policy(dict, Algorithm::Standard, policy);

// Custom equivalences work
assert!(transducer.query("wery", 0).any(|s| s == "very"));  // v↔w
assert!(transducer.query("happi", 0).any(|s| s == "happy")); // y↔i

Example 2: Combining Substitution Sets

Combine multiple preset sets:

use liblevenshtein::prelude::*;
use liblevenshtein::transducer::{SubstitutionSet, Algorithm};

// Start with phonetic base
let mut combined = SubstitutionSet::phonetic_basic();

// Add keyboard typos
let keyboard = SubstitutionSet::keyboard_qwerty();
for &(a, b) in &[('q', 'w'), ('w', 'q'), ('a', 's'), ('s', 'a')] {
    combined.allow(a as char, b as char);
}

// Add leetspeak
combined.allow('3', 'e');
combined.allow('e', '3');
combined.allow('0', 'o');
combined.allow('o', '0');

let dict = DoubleArrayTrie::from_terms(vec!["hello", "phone"]);
let transducer = Transducer::with_substitutions(dict, Algorithm::Standard, combined);

// All substitution types work
assert!(transducer.query("h3llo", 1).any(|s| s == "hello")); // leetspeak
assert!(transducer.query("fone", 1).any(|s| s == "phone"));  // phonetic

Example 3: Capacity Pre-allocation

For large substitution sets, pre-allocate capacity:

use liblevenshtein::prelude::*;
use liblevenshtein::transducer::{SubstitutionSet, Algorithm};

// Pre-allocate for 200 substitution pairs
let mut large_set = SubstitutionSet::with_capacity(200);

// Add many pairs without reallocations
for i in 0..26 {
    let lower = (b'a' + i) as char;
    let upper = (b'A' + i) as char;
    large_set.allow(lower, upper);
    large_set.allow(upper, lower);
}

assert_eq!(large_set.len(), 52); // 26 pairs × 2 directions

---

Advanced Examples

Example 1: Case-Insensitive Greek Matching

Match Greek text case-insensitively:

use liblevenshtein::prelude::*;
use liblevenshtein::transducer::{SubstitutionSetChar, RestrictedChar, Algorithm};

// Greek case-insensitive matching
let greek = SubstitutionSetChar::greek_case_insensitive();

let dict = DoubleArrayTrieChar::from_terms(vec!["Αθήνα", "Ελλάδα"]); // Athens, Greece
let policy = RestrictedChar::new(&greek);
let transducer = Transducer::with_policy(dict, Algorithm::Standard, policy);

// Case variants match with distance 0
assert!(transducer.query("αθήνα", 0).any(|s| s == "Αθήνα")); // lowercase matches
assert!(transducer.query("ΕΛΛΆΔΑ", 0).any(|s| s == "Ελλάδα")); // uppercase matches

Example 2: Japanese Hiragana/Katakana

Allow hiragana↔katakana equivalence:

use liblevenshtein::prelude::*;
use liblevenshtein::transducer::{SubstitutionSetChar, RestrictedChar, Algorithm};

// Japanese script equivalences
let japanese = SubstitutionSetChar::japanese_hiragana_katakana();

let dict = DoubleArrayTrieChar::from_terms(vec!["カタカナ", "ひらがな"]);
let policy = RestrictedChar::new(&japanese);
let transducer = Transducer::with_policy(dict, Algorithm::Standard, policy);

// Hiragana queries match katakana terms
// (In real use, you'd have mixed-script dictionary entries)

Example 3: Multi-Language Support

Handle multiple languages with Unicode:

use liblevenshtein::prelude::*;
use liblevenshtein::transducer::{SubstitutionSetChar, RestrictedChar, Algorithm};

// Combine multiple language equivalences
let mut multilang = SubstitutionSetChar::new();

// Add Latin diacritics
let latin = SubstitutionSetChar::diacritics_latin();
for i in 0..latin.len() {
    // In real code, you'd iterate over pairs
}

// Add Greek case-insensitive
let greek = SubstitutionSetChar::greek_case_insensitive();
// (Similarly merge)

// Add Cyrillic case-insensitive
let cyrillic = SubstitutionSetChar::cyrillic_case_insensitive();
// (Similarly merge)

// Now supports French, Greek, and Russian simultaneously

Example 4: Custom Policy Implementation

Implement your own substitution policy:

use liblevenshtein::transducer::SubstitutionPolicy;

/// Custom policy: allow vowel substitutions only
#[derive(Copy, Clone, Debug)]
struct VowelPolicy;

impl SubstitutionPolicy for VowelPolicy {
    fn is_allowed(&self, dict_char: u8, query_char: u8) -> bool {
        const VOWELS: &[u8] = b"aeiouAEIOU";

        // Allow exact match or both are vowels
        dict_char == query_char ||
            (VOWELS.contains(&dict_char) && VOWELS.contains(&query_char))
    }
}

// Use custom policy
// let transducer = Transducer::with_policy(dict, Algorithm::Standard, VowelPolicy);

---

Performance Considerations

Overhead Comparison

Policy Type	Size	Runtime Overhead	Use Case
Unrestricted	0 bytes	0% (zero-cost)	Default, no substitutions
Restricted	8 bytes (ref)	1-5% (HashSet lookup)	Custom substitutions

Best Practices for Performance

1. Use Unrestricted when possible: If you don't need substitutions, use the default:

   let transducer = Transducer::new(dict, Algorithm::Standard); // Zero overhead
   

2. Pre-allocate substitution sets: Use with_capacity() for large sets:

   let mut set = SubstitutionSet::with_capacity(100); // Avoids reallocations
   

3. Reuse policies: Create policy once, use multiple times:

   let policy = Restricted::new(&substitutions);
   let trans1 = Transducer::with_policy(dict1, Algorithm::Standard, policy);
   let trans2 = Transducer::with_policy(dict2, Algorithm::Standard, policy);
   

4. Benchmark your use case: Overhead varies by:

   • Query length
   • Dictionary size
   • Substitution set size
   • Max edit distance

Memory Usage

use std::mem::size_of;
use liblevenshtein::transducer::{Unrestricted, Restricted, SubstitutionSet};

// Zero-sized type
assert_eq!(size_of::<Unrestricted>(), 0);

// Restricted is just a reference
assert_eq!(size_of::<Restricted>(), 8); // 64-bit pointer

// SubstitutionSet scales with number of pairs
let small = SubstitutionSet::new();
let large = SubstitutionSet::phonetic_basic();
println!("Small set: {} bytes (base)", size_of_val(&small));
println!("Large set: {} pairs = ~{} bytes", large.len(), 48 + large.len() * 24);

---

Best Practices

1. Always Add Symmetric Pairs

If you want bidirectional equivalence, add both directions:

let mut set = SubstitutionSet::new();

// ❌ WRONG: Only c→k works
set.allow('c', 'k');

// ✅ CORRECT: Both c→k and k→c work
set.allow('c', 'k');
set.allow('k', 'c');

2. Use Presets When Available

Don't reinvent the wheel:

// ❌ TEDIOUS: Manual construction
let mut phonetic = SubstitutionSet::new();
phonetic.allow('f', 'p'); phonetic.allow('p', 'f');
phonetic.allow('c', 'k'); phonetic.allow('k', 'c');
// ... many more

// ✅ BETTER: Use preset
let phonetic = SubstitutionSet::phonetic_basic();

3. Document Your Substitution Logic

Explain why you chose specific equivalences:

// Medical terminology: common abbreviations and variants
let mut medical = SubstitutionSet::new();
medical.allow('x', 'c'); medical.allow('c', 'x'); // "excision" ↔ "exsision"
medical.allow('ph', 'f'); medical.allow('f', 'p'); // "pharmacy" ↔ "farmacy"
// Document: Based on common medical spelling variants

4. Test Your Substitutions

Verify expected behavior:

#[test]
fn test_phonetic_matching() {
    let phonetic = SubstitutionSet::phonetic_basic();
    let dict = DoubleArrayTrie::from_terms(vec!["phone", "cat"]);
    let transducer = Transducer::with_substitutions(dict, Algorithm::Standard, phonetic);

    // Positive cases
    assert!(transducer.query("fone", 1).any(|s| s == "phone"));
    assert!(transducer.query("kat", 1).any(|s| s == "cat"));

    // Negative cases (ensure we don't over-match)
    assert!(!transducer.query("xyz", 1).any(|s| s == "phone"));
}

5. Choose Appropriate Max Distance

Substitutions reduce effective distance, so adjust max distance:

// With substitutions, distance 0 may match more
let results_d0 = transducer.query("kat", 0).collect::<Vec<_>>();

// Without substitutions, you'd need distance 1
let results_d1 = transducer_no_subs.query("kat", 1).collect::<Vec<_>>();

---

FAQ

Q1: What's the difference between SubstitutionSet and SubstitutionSetChar?

A: SubstitutionSet works with ASCII bytes (u8, 0–127) and is used with DoubleArrayTrie. SubstitutionSetChar works with full Unicode characters (char, U+0000–U+10FFFF) and is used with character-level dictionaries.

// Byte-level (ASCII only)
let mut ascii_set = SubstitutionSet::new();
ascii_set.allow('a', 'b'); // Works
ascii_set.allow('é', 'e'); // Silently ignored (non-ASCII)

// Character-level (full Unicode)
let mut unicode_set = SubstitutionSetChar::new();
unicode_set.allow('a', 'b');  // Works
unicode_set.allow('é', 'e');  // Works! ✅
unicode_set.allow('你', '好'); // Works! ✅

Q2: How do I make substitutions symmetric?

A: Add both directions explicitly:

let mut set = SubstitutionSet::new();
set.allow('c', 'k'); // dict 'c' matches query 'k'
set.allow('k', 'c'); // dict 'k' matches query 'c'

Q3: Can I use multiple substitution policies simultaneously?

A: No, a transducer has exactly one policy. Instead, merge substitution sets:

let mut combined = SubstitutionSet::phonetic_basic();
// Add more pairs from other sets
combined.allow('0', 'O');
combined.allow('O', '0');

Q4: What's the performance impact?

A:

• Unrestricted (default): 0% overhead (zero-cost abstraction)
• Restricted: 1–5% overhead (HashSet lookup on mismatches only)

The overhead is minimal because:

1. Exact matches short-circuit (no lookup)
2. FxHasher is very fast (~10-30ns per lookup)
3. Only called on character mismatches

Q5: Can I use substitutions with transposition/merge-split algorithms?

A: Yes! Policies work with all algorithm variants:

// Substitutions + Transposition
let transducer = Transducer::with_policy(
    dict,
    Algorithm::Transposition,
    policy
);

// Substitutions + MergeAndSplit
let transducer = Transducer::with_policy(
    dict,
    Algorithm::MergeAndSplit,
    policy
);

Q6: How do I handle multi-character substitutions like "ph" → "f"?

A: Currently, substitutions are single-character only. Multi-character support is planned for future releases. As a workaround:

// Workaround: Treat "ph" as 'p' in context
let mut set = SubstitutionSet::new();
set.allow('f', 'p'); // Partial match for "ph" → "f"
// Note: This doesn't fully solve the problem yet

Q7: Can I dynamically update substitutions?

A: SubstitutionSet is mutable, but Restricted policy holds a reference. To update:

let mut set = SubstitutionSet::new();
set.allow('a', 'b');

// Create transducer
let policy = Restricted::new(&set);
let transducer = Transducer::with_policy(dict, Algorithm::Standard, policy);

// ❌ Can't update set while policy/transducer exist (borrow checker)
// set.allow('c', 'd'); // Error: already borrowed

// ✅ Solution: Create new transducer with updated set
let mut new_set = set.clone();
new_set.allow('c', 'd');
let new_policy = Restricted::new(&new_set);
let new_transducer = Transducer::with_policy(dict, Algorithm::Standard, new_policy);

Q8: Why use Box::leak() in with_substitutions()?

A: To extend the lifetime to 'static, allowing the returned transducer to own its policy. This is a convenience tradeoff:

// Convenience method (leaks memory, but easy to use)
let transducer = Transducer::with_substitutions(dict, Algorithm::Standard, set);

// Explicit lifetime management (no leak, but requires reference)
let policy = Restricted::new(&set);
let transducer = Transducer::with_policy(dict, Algorithm::Standard, policy);
// Note: 'set' must outlive 'transducer'

For long-lived transducers, the leak is acceptable. For short-lived ones, use with_policy() directly.

---

Summary

Restricted substitutions provide powerful, flexible, and zero-cost (when unused) character equivalence matching:

✅ Use SubstitutionSet presets for common scenarios (phonetic, keyboard, leetspeak, OCR) ✅ Use SubstitutionSetChar for Unicode (diacritics, Greek, Cyrillic, Japanese) ✅ Zero overhead when disabled (default Unrestricted policy) ✅ 1–5% overhead when enabled (fast HashSet lookups) ✅ Fully backward compatible (existing code works unchanged)

Next Steps:

• Try the examples
• Read the API documentation
• Explore performance benchmarks

---

Author: liblevenshtein-rust contributors License: MIT OR Apache-2.0 Repository: https://github.com/dylon/liblevenshtein-rust

---

← Documentation Index