gitql_parser/
name_similarity.rs

1const MIN_DISTANCE: usize = 2;
2
3pub(crate) fn find_closeest_string(target: &str, candidates: &[&&str]) -> Option<String> {
4    if candidates.is_empty() {
5        return None;
6    }
7
8    let mut closest_match: Option<String> = None;
9    let mut min_distance = usize::MAX;
10
11    for candidate in candidates {
12        let distance = levenshtein_distance(target, candidate);
13        if distance < min_distance {
14            min_distance = distance;
15            closest_match = Some(candidate.to_string());
16        }
17    }
18
19    if min_distance <= MIN_DISTANCE {
20        return closest_match;
21    }
22    None
23}
24
25fn levenshtein_distance(s1: &str, s2: &str) -> usize {
26    let s1_chars: Vec<char> = s1.chars().collect();
27    let s2_chars: Vec<char> = s2.chars().collect();
28
29    let s1_len = s1_chars.len();
30    let s2_len = s2_chars.len();
31
32    let vec1_len = s1_len + 1;
33    let vec12_len = s2_len + 1;
34
35    let mut matrix = vec![vec![0; vec12_len]; vec1_len];
36    for (i, vector) in matrix.iter_mut().enumerate().take(vec1_len) {
37        vector[0] = i;
38    }
39
40    for j in 0..vec12_len {
41        matrix[0][j] = j;
42    }
43
44    for i in 1..vec1_len {
45        for j in 1..vec12_len {
46            let cost = if s1_chars[i - 1] == s2_chars[j - 1] {
47                0
48            } else {
49                1
50            };
51
52            matrix[i][j] = (matrix[i - 1][j] + 1)
53                .min(matrix[i][j - 1] + 1)
54                .min(matrix[i - 1][j - 1] + cost);
55        }
56    }
57
58    matrix[s1_len][s2_len]
59}