1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256
//! Edit distances.
//!
//! The [edit distance] is a metric for measuring the difference between two strings.
//!
//! [edit distance]: https://en.wikipedia.org/wiki/Edit_distance
// The current implementation is the restricted Damerau-Levenshtein algorithm. It is restricted
// because it does not permit modifying characters that have already been transposed. The specific
// algorithm should not matter to the caller of the methods, which is why it is not noted in the
// documentation.
use crate::symbol::Symbol;
use std::{cmp, mem};
#[cfg(test)]
mod tests;
/// Finds the [edit distance] between two strings.
///
/// Returns `None` if the distance exceeds the limit.
///
/// [edit distance]: https://en.wikipedia.org/wiki/Edit_distance
pub fn edit_distance(a: &str, b: &str, limit: usize) -> Option<usize> {
let mut a = &a.chars().collect::<Vec<_>>()[..];
let mut b = &b.chars().collect::<Vec<_>>()[..];
// Ensure that `b` is the shorter string, minimizing memory use.
if a.len() < b.len() {
mem::swap(&mut a, &mut b);
}
let min_dist = a.len() - b.len();
// If we know the limit will be exceeded, we can return early.
if min_dist > limit {
return None;
}
// Strip common prefix.
while let Some(((b_char, b_rest), (a_char, a_rest))) = b.split_first().zip(a.split_first())
&& a_char == b_char
{
a = a_rest;
b = b_rest;
}
// Strip common suffix.
while let Some(((b_char, b_rest), (a_char, a_rest))) = b.split_last().zip(a.split_last())
&& a_char == b_char
{
a = a_rest;
b = b_rest;
}
// If either string is empty, the distance is the length of the other.
// We know that `b` is the shorter string, so we don't need to check `a`.
if b.len() == 0 {
return Some(min_dist);
}
let mut prev_prev = vec![usize::MAX; b.len() + 1];
let mut prev = (0..=b.len()).collect::<Vec<_>>();
let mut current = vec![0; b.len() + 1];
// row by row
for i in 1..=a.len() {
current[0] = i;
let a_idx = i - 1;
// column by column
for j in 1..=b.len() {
let b_idx = j - 1;
// There is no cost to substitute a character with itself.
let substitution_cost = if a[a_idx] == b[b_idx] { 0 } else { 1 };
current[j] = cmp::min(
// deletion
prev[j] + 1,
cmp::min(
// insertion
current[j - 1] + 1,
// substitution
prev[j - 1] + substitution_cost,
),
);
if (i > 1) && (j > 1) && (a[a_idx] == b[b_idx - 1]) && (a[a_idx - 1] == b[b_idx]) {
// transposition
current[j] = cmp::min(current[j], prev_prev[j - 2] + 1);
}
}
// Rotate the buffers, reusing the memory.
[prev_prev, prev, current] = [prev, current, prev_prev];
}
// `prev` because we already rotated the buffers.
let distance = prev[b.len()];
(distance <= limit).then_some(distance)
}
/// Provides a word similarity score between two words that accounts for substrings being more
/// meaningful than a typical edit distance. The lower the score, the closer the match. 0 is an
/// identical match.
///
/// Uses the edit distance between the two strings and removes the cost of the length difference.
/// If this is 0 then it is either a substring match or a full word match, in the substring match
/// case we detect this and return `1`. To prevent finding meaningless substrings, eg. "in" in
/// "shrink", we only perform this subtraction of length difference if one of the words is not
/// greater than twice the length of the other. For cases where the words are close in size but not
/// an exact substring then the cost of the length difference is discounted by half.
///
/// Returns `None` if the distance exceeds the limit.
pub fn edit_distance_with_substrings(a: &str, b: &str, limit: usize) -> Option<usize> {
let n = a.chars().count();
let m = b.chars().count();
// Check one isn't less than half the length of the other. If this is true then there is a
// big difference in length.
let big_len_diff = (n * 2) < m || (m * 2) < n;
let len_diff = if n < m { m - n } else { n - m };
let distance = edit_distance(a, b, limit + len_diff)?;
// This is the crux, subtracting length difference means exact substring matches will now be 0
let score = distance - len_diff;
// If the score is 0 but the words have different lengths then it's a substring match not a full
// word match
let score = if score == 0 && len_diff > 0 && !big_len_diff {
1 // Exact substring match, but not a total word match so return non-zero
} else if !big_len_diff {
// Not a big difference in length, discount cost of length difference
score + (len_diff + 1) / 2
} else {
// A big difference in length, add back the difference in length to the score
score + len_diff
};
(score <= limit).then_some(score)
}
/// Finds the best match for given word in the given iterator where substrings are meaningful.
///
/// A version of [`find_best_match_for_name`] that uses [`edit_distance_with_substrings`] as the
/// score for word similarity. This takes an optional distance limit which defaults to one-third of
/// the given word.
///
/// We use case insensitive comparison to improve accuracy on an edge case with a lower(upper)case
/// letters mismatch.
pub fn find_best_match_for_name_with_substrings(
candidates: &[Symbol],
lookup: Symbol,
dist: Option<usize>,
) -> Option<Symbol> {
find_best_match_for_name_impl(true, candidates, lookup, dist)
}
/// Finds the best match for a given word in the given iterator.
///
/// As a loose rule to avoid the obviously incorrect suggestions, it takes
/// an optional limit for the maximum allowable edit distance, which defaults
/// to one-third of the given word.
///
/// We use case insensitive comparison to improve accuracy on an edge case with a lower(upper)case
/// letters mismatch.
pub fn find_best_match_for_name(
candidates: &[Symbol],
lookup: Symbol,
dist: Option<usize>,
) -> Option<Symbol> {
find_best_match_for_name_impl(false, candidates, lookup, dist)
}
#[cold]
fn find_best_match_for_name_impl(
use_substring_score: bool,
candidates: &[Symbol],
lookup_symbol: Symbol,
dist: Option<usize>,
) -> Option<Symbol> {
let lookup = lookup_symbol.as_str();
let lookup_uppercase = lookup.to_uppercase();
// Priority of matches:
// 1. Exact case insensitive match
// 2. Edit distance match
// 3. Sorted word match
if let Some(c) = candidates.iter().find(|c| c.as_str().to_uppercase() == lookup_uppercase) {
return Some(*c);
}
let mut dist = dist.unwrap_or_else(|| cmp::max(lookup.len(), 3) / 3);
let mut best = None;
// store the candidates with the same distance, only for `use_substring_score` current.
let mut next_candidates = vec![];
for c in candidates {
match if use_substring_score {
edit_distance_with_substrings(lookup, c.as_str(), dist)
} else {
edit_distance(lookup, c.as_str(), dist)
} {
Some(0) => return Some(*c),
Some(d) => {
if use_substring_score {
if d < dist {
dist = d;
next_candidates.clear();
} else {
// `d == dist` here, we need to store the candidates with the same distance
// so we won't decrease the distance in the next loop.
}
next_candidates.push(*c);
} else {
dist = d - 1;
}
best = Some(*c);
}
None => {}
}
}
// We have a tie among several candidates, try to select the best among them ignoring substrings.
// For example, the candidates list `force_capture`, `capture`, and user inputted `forced_capture`,
// we select `force_capture` with a extra round of edit distance calculation.
if next_candidates.len() > 1 {
debug_assert!(use_substring_score);
best = find_best_match_for_name_impl(
false,
&next_candidates,
lookup_symbol,
Some(lookup.len()),
);
}
if best.is_some() {
return best;
}
find_match_by_sorted_words(candidates, lookup)
}
fn find_match_by_sorted_words(iter_names: &[Symbol], lookup: &str) -> Option<Symbol> {
let lookup_sorted_by_words = sort_by_words(lookup);
iter_names.iter().fold(None, |result, candidate| {
if sort_by_words(candidate.as_str()) == lookup_sorted_by_words {
Some(*candidate)
} else {
result
}
})
}
fn sort_by_words(name: &str) -> Vec<&str> {
let mut split_words: Vec<&str> = name.split('_').collect();
// We are sorting primitive &strs and can use unstable sort here.
split_words.sort_unstable();
split_words
}