2 use crate::symbol::Symbol;
7 /// Finds the Levenshtein distance between two strings
8 pub fn lev_distance(a: &str, b: &str) -> usize {
9 // cases which don't require further computation
11 return b.chars().count();
12 } else if b.is_empty() {
13 return a.chars().count();
16 let mut dcol: Vec<_> = (0..=b.len()).collect();
19 for (i, sc) in a.chars().enumerate() {
21 dcol[0] = current + 1;
23 for (j, tc) in b.chars().enumerate() {
24 let next = dcol[j + 1];
26 dcol[j + 1] = current;
28 dcol[j + 1] = cmp::min(current, next);
29 dcol[j + 1] = cmp::min(dcol[j + 1], dcol[j]) + 1;
38 /// Finds the best match for a given word in the given iterator
40 /// As a loose rule to avoid the obviously incorrect suggestions, it takes
41 /// an optional limit for the maximum allowable edit distance, which defaults
42 /// to one-third of the given word.
44 /// Besides Levenshtein, we use case insensitive comparison to improve accuracy on an edge case with
45 /// a lower(upper)case letters mismatch.
46 pub fn find_best_match_for_name<'a, T>(iter_names: T,
48 dist: Option<usize>) -> Option<Symbol>
49 where T: Iterator<Item = &'a Symbol> {
50 let max_dist = dist.map_or_else(|| cmp::max(lookup.len(), 3) / 3, |d| d);
52 let (case_insensitive_match, levenstein_match) = iter_names
54 let dist = lev_distance(lookup, &name.as_str());
61 // Here we are collecting the next structure:
62 // (case_insensitive_match, (levenstein_match, levenstein_distance))
63 .fold((None, None), |result, (candidate, dist)| {
65 if candidate.as_str().to_uppercase() == lookup.to_uppercase() {
71 None => Some((candidate, dist)),
72 Some((c, d)) => Some(if dist < d { (candidate, dist) } else { (c, d) })
77 if let Some(candidate) = case_insensitive_match {
78 Some(candidate) // exact case insensitive match has a higher priority
80 levenstein_match.map(|(candidate, _)| candidate)