gitql_parser/
name_similarity.rs1const 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}