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
122
123
124
125
126
127
128
129
130
131
132
133
134
135

//! Detailed trace test for debugging insertion issues

use liblevenshtein::prelude::*;
use liblevenshtein::transducer::transition::{initial_state, transition_state};
use liblevenshtein::transducer::Unrestricted;

#[test]
fn trace_aple_to_apple() {
    let dict = DoubleArrayTrie::from_terms(vec!["apple"]);
    let root = dict.root();

    let query = b"aple";
    let max_distance = 1;

    println!(
        "\n=== Tracing 'aple' against 'apple' with distance {} ===",
        max_distance
    );
    println!(
        "Query: {:?} (length {})",
        std::str::from_utf8(query).unwrap(),
        query.len()
    );

    let mut state = initial_state(query.len(), max_distance, Algorithm::Standard);
    println!("\nInitial state: {:?}", state);

    // Traverse 'a'
    let a_node = root.transition(b'a').expect("Should have 'a'");
    state = transition_state(
        &state,
        Unrestricted,
        b'a',
        query,
        max_distance,
        Algorithm::Standard,
        false,
    )
    .expect("Should have state after 'a'");
    println!("\nAfter 'a': {:?}", state);
    println!("Node is_final: {}", a_node.is_final());

    // Traverse first 'p'
    let p1_node = a_node.transition(b'p').expect("Should have first 'p'");
    state = transition_state(
        &state,
        Unrestricted,
        b'p',
        query,
        max_distance,
        Algorithm::Standard,
        false,
    )
    .expect("Should have state after first 'p'");
    println!("\nAfter 'ap': {:?}", state);
    println!("Node is_final: {}", p1_node.is_final());

    // Traverse second 'p' - this is where insertion should happen
    if let Some(p2_node) = p1_node.transition(b'p') {
        println!("\nFound second 'p' in dictionary");
        if let Some(new_state) = transition_state(
            &state,
            Unrestricted,
            b'p',
            query,
            max_distance,
            Algorithm::Standard,
            false,
        ) {
            state = new_state;
            println!("After 'app': {:?}", state);
            println!("Node is_final: {}", p2_node.is_final());

            // Traverse 'l'
            if let Some(l_node) = p2_node.transition(b'l') {
                println!("\nFound 'l' in dictionary");
                if let Some(new_state) = transition_state(
                    &state,
                    Unrestricted,
                    b'l',
                    query,
                    max_distance,
                    Algorithm::Standard,
                    false,
                ) {
                    state = new_state;
                    println!("After 'appl': {:?}", state);
                    println!("Node is_final: {}", l_node.is_final());

                    // Traverse 'e'
                    if let Some(e_node) = l_node.transition(b'e') {
                        println!("\nFound 'e' in dictionary");
                        if let Some(new_state) = transition_state(
                            &state,
                            Unrestricted,
                            b'e',
                            query,
                            max_distance,
                            Algorithm::Standard,
                            false,
                        ) {
                            state = new_state;
                            println!("After 'apple': {:?}", state);
                            println!("Node is_final: {}", e_node.is_final());

                            // Check if we should match
                            println!("\n=== Final Check ===");
                            println!("Query length: {}", query.len());
                            if let Some(distance) = state.infer_distance(query.len()) {
                                println!("Inferred distance: {}", distance);
                                println!("Max distance: {}", max_distance);
                                println!("Should match: {}", distance <= max_distance);
                            } else {
                                println!("Could not infer distance!");
                            }
                        } else {
                            println!("No state after 'e' - traversal stopped!");
                        }
                    } else {
                        println!("No 'e' edge from 'appl'");
                    }
                } else {
                    println!("No state after 'l' - traversal stopped!");
                }
            } else {
                println!("No 'l' edge from 'app'");
            }
        } else {
            println!("No state after second 'p' - traversal stopped!");
            println!("This is the problem! The state should continue with insertion.");
        }
    } else {
        println!("\nNo second 'p' edge");
    }
}