Function fuzzy_match

nodedb-fts/src/fuzzy.rs:75–114

Find terms in the index that fuzzy-match the query term. Returns `(matched_term, edit_distance)` pairs for all terms within the adaptive distance threshold. Results are sorted by distance (closest matches first).

(
    query_term: &str,
    index_terms: impl Iterator<Item = &'a str>,
)

/// the adaptive distance threshold. Results are sorted by distance
/// (closest matches first).
pub fn fuzzy_match<'a>(
    query_term: &str,
    index_terms: impl Iterator<Item = &'a str>,
) -> Vec<(&'a str, usize)> {
    let q_char_len = query_term.chars().count();
    let max_dist = max_distance_for_length(q_char_len);
    if max_dist == 0 {
        return Vec::new();
    }

    // Length-bucket prefilter: group candidates by character length, then
    // visit only buckets within the distance window. Edit distance is at
    // least |len(a) - len(b)|, so terms outside [q-d .. q+d] cannot match.
    // This bounds the number of expensive O(L²) levenshtein calls to the
    // candidates in the relevant buckets, avoiding whole-dictionary scans
    // on large term indexes.
    use std::collections::HashMap;
    let mut buckets: HashMap<usize, Vec<&'a str>> = HashMap::new();
    for term in index_terms {
        buckets.entry(term.chars().count()).or_default().push(term);
    }

    let low = q_char_len.saturating_sub(max_dist);
    let high = q_char_len.saturating_add(max_dist);
    let mut matches: Vec<(&'a str, usize)> = Vec::new();
    for len in low..=high {
        let Some(bucket) = buckets.get(&len) else {
            continue;
        };
        for term in bucket {
            let dist = levenshtein(query_term, term);
            if dist > 0 && dist <= max_dist {
                matches.push((*term, dist));
            }
        }
    }

    matches.sort_by_key(|&(_, d)| d);
    matches
}

/// Score discount for fuzzy matches based on edit distance.
///