liblevenshtein 0.9.1

Levenshtein/Universal Automata for approximate string matching using various dictionary backends
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

use liblevenshtein::prelude::*;
use liblevenshtein::transducer::Position;

#[test]
fn check_1_1_false_subsumes_0_1_true() {
    println!("\n=== Check if (1,1,false) subsumes (0,1,true) ===\n");

    let algorithm = Algorithm::Transposition;
    let query_length = 2;

    let p_1_1 = Position::new(1, 1); // (1,1,false)
    let p_0_1_special = Position::new_special(0, 1); // (0,1,true)

    println!(
        "p_1_1:          ({}, {}, false)",
        p_1_1.term_index, p_1_1.num_errors
    );
    println!(
        "p_0_1_special:  ({}, {}, true)",
        p_0_1_special.term_index, p_0_1_special.num_errors
    );
    println!();

    let subsumes = p_1_1.subsumes(&p_0_1_special, algorithm, query_length);
    println!("Does (1,1,false) subsume (0,1,true)? {}", subsumes);
    println!();

    if subsumes {
        println!("❌ BUG FOUND!");
        println!("  (1,1,false) incorrectly subsumes (0,1,true)");
        println!();
        println!("  Let's trace through the subsumption logic:");
        println!("  From position.rs line 82-145 (subsumes function):");
        println!();
        println!("  Input:");
        println!(
            "    self (lhs): i={}, e={}, s={}",
            p_1_1.term_index, p_1_1.num_errors, p_1_1.is_special
        );
        println!(
            "    other (rhs): j={}, f={}, t={}",
            p_0_1_special.term_index, p_0_1_special.num_errors, p_0_1_special.is_special
        );
        println!("    algorithm: Transposition");
        println!("    query_length: {}", query_length);
        println!();
        println!("  Step 1: Check e > f?");
        println!(
            "    {} > {} = {}",
            p_1_1.num_errors,
            p_0_1_special.num_errors,
            p_1_1.num_errors > p_0_1_special.num_errors
        );
        println!("    If true, return false (cannot subsume with more errors)");
        println!();
        println!("  Step 2: Transposition algorithm logic");
        println!("    if s (lhs is special): {}", p_1_1.is_special);

        println!("      → NO, lhs is NOT special");
        println!();
        println!("    if t (rhs is special): {}", p_0_1_special.is_special);
        println!("      → YES, rhs IS special");
        println!();
        println!("    Lines 116-125 handle this case:");
        println!("      if t {{");
        println!("        // rhs is special: adjusted formula");
        println!("        let adjusted_diff = if j < i {{");
        println!("          i.saturating_sub(j).saturating_sub(1)");
        println!("        }} else {{");
        println!("          j.saturating_sub(i) + 1");
        println!("        }};");
        println!("        return adjusted_diff <= (f - e);");
        println!("      }}");
        println!();
        println!(
            "    Applying with i={}, j={}, e={}, f={}:",
            p_1_1.term_index, p_0_1_special.term_index, p_1_1.num_errors, p_0_1_special.num_errors
        );
        println!(
            "      j < i? {} < {} = {}",
            p_0_1_special.term_index,
            p_1_1.term_index,
            p_0_1_special.term_index < p_1_1.term_index
        );
        println!("      → YES, so adjusted_diff = i.saturating_sub(j).saturating_sub(1)");
        println!(
            "      adjusted_diff = {}.saturating_sub({}).saturating_sub(1)",
            p_1_1.term_index, p_0_1_special.term_index
        );
        println!(
            "      adjusted_diff = {}.saturating_sub(1)",
            p_1_1.term_index - p_0_1_special.term_index
        );
        println!(
            "      adjusted_diff = {}",
            (p_1_1.term_index - p_0_1_special.term_index).saturating_sub(1)
        );
        println!();
        println!("      Check: adjusted_diff <= (f - e)?");
        println!(
            "      {} <= ({} - {})",
            (p_1_1.term_index - p_0_1_special.term_index).saturating_sub(1),
            p_0_1_special.num_errors,
            p_1_1.num_errors
        );
        println!(
            "      {} <= {}",
            (p_1_1.term_index - p_0_1_special.term_index).saturating_sub(1),
            p_0_1_special.num_errors - p_1_1.num_errors
        );
        println!("      0 <= 0");
        println!("      → TRUE!");
        println!();
        println!("  This is the BUG! The adjusted formula for transposition is incorrect.");
        println!("  A normal position at (1,1) should NOT subsume a special transposition");
        println!("  position at (0,1) - they represent different computational paths!");
        panic!("Bug confirmed: incorrect transposition subsumption formula");
    } else {
        println!("✓ Subsumption check is correct.");
    }
}