Function levenshtein

nodedb-fts/src/fuzzy.rs:20–56

Fuzzy string matching via Levenshtein edit distance. Used for typo-tolerant full-text search. When an exact term match isn't found in the inverted index, fuzzy matching finds terms within a configurable edit distance. Distance thresholds are adaptive based on token length: - 1-3 chars: exact only (no fuzzy — too many false positives) - 4-6 chars: max distance 1 - 7+ chars: max distance 2 Compute

(a: &str, b: &str)

///
/// Uses the two-row DP: O(min(a,b)) space, O(a*b) time.
pub fn levenshtein(a: &str, b: &str) -> usize {
    let a_chars: Vec<char> = a.chars().collect();
    let b_chars: Vec<char> = b.chars().collect();
    let a_len = a_chars.len();
    let b_len = b_chars.len();

    if a_len == 0 {
        return b_len;
    }
    if b_len == 0 {
        return a_len;
    }

    // Iterate the shorter string as the inner dimension.
    let (short, long) = if a_len <= b_len {
        (&a_chars[..], &b_chars[..])
    } else {
        (&b_chars[..], &a_chars[..])
    };
    let s_len = short.len();

    let mut prev_row: Vec<usize> = (0..=s_len).collect();
    let mut curr_row: Vec<usize> = vec![0; s_len + 1];

    for (j, l_ch) in long.iter().enumerate() {
        curr_row[0] = j + 1;
        for (i, s_ch) in short.iter().enumerate() {
            let cost = if s_ch == l_ch { 0 } else { 1 };
            curr_row[i + 1] = (prev_row[i + 1] + 1)
                .min(curr_row[i] + 1)
                .min(prev_row[i] + cost);
        }
        std::mem::swap(&mut prev_row, &mut curr_row);
    }

    prev_row[s_len]
}

/// Maximum allowed edit distance for a given token length.
///