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    #[allow(clippy::needless_range_loop)]
41    for j in 0..vec12_len {
42        matrix[0][j] = j;
43    }
44
45    for i in 1..vec1_len {
46        for j in 1..vec12_len {
47            let cost = if s1_chars[i - 1] == s2_chars[j - 1] {
48                0
49            } else {
50                1
51            };
52
53            matrix[i][j] = (matrix[i - 1][j] + 1)
54                .min(matrix[i][j - 1] + 1)
55                .min(matrix[i - 1][j - 1] + cost);
56        }
57    }
58
59    matrix[s1_len][s2_len]
60}
gitql_parser/name_similarity.rs

gitql_parser/
name_similarity.rs
