rushdb_types/
names.rs

1//! Names of labels and properties compared the way people misspell them:
2//! tokens split on case and separators with plural endings dropped, then a
3//! spelling score. Shared by the catalog's name suggestions and SQL's
4//! "did you mean" errors.
5
6use std::collections::BTreeSet;
7
8/// Lowercase name tokens: camelCase and every non-alphanumeric character
9/// split words, and a plural ending is dropped (`ies` -> `y`; `es` after
10/// o, s, x, z, ch, sh; else a final `s`), as the Core platform's
11/// relationship analysis does (it drops `ies`/`s` only).
12#[must_use]
13pub fn name_tokens(name: &str) -> Vec<String> {
14    let mut words: Vec<String> = Vec::new();
15    let mut current = String::new();
16    let mut previous_lower = false;
17    for c in name.chars() {
18        if !c.is_alphanumeric() {
19            if !current.is_empty() {
20                words.push(std::mem::take(&mut current));
21            }
22            previous_lower = false;
23            continue;
24        }
25        if c.is_uppercase() && previous_lower && !current.is_empty() {
26            words.push(std::mem::take(&mut current));
27        }
28        previous_lower = c.is_lowercase() || c.is_ascii_digit();
29        current.extend(c.to_lowercase());
30    }
31    if !current.is_empty() {
32        words.push(current);
33    }
34    words
35        .into_iter()
36        .map(|word| {
37            if let Some(stem) = word.strip_suffix("ies") {
38                format!("{stem}y")
39            } else if ["oes", "ses", "xes", "zes", "ches", "shes"]
40                .iter()
41                .any(|ending| word.len() > ending.len() + 1 && word.ends_with(ending))
42            {
43                word[..word.len() - 2].to_string()
44            } else if word.len() > 1 && word.ends_with('s') {
45                word[..word.len() - 1].to_string()
46            } else {
47                word
48            }
49        })
50        .collect()
51}
52
53/// Edit distance between two strings, in characters.
54fn levenshtein(a: &str, b: &str) -> usize {
55    let a: Vec<char> = a.chars().collect();
56    let b: Vec<char> = b.chars().collect();
57    let mut row: Vec<usize> = (0..=b.len()).collect();
58    for (i, ca) in a.iter().enumerate() {
59        let mut diagonal = row[0];
60        row[0] = i + 1;
61        for (j, cb) in b.iter().enumerate() {
62            let above = row[j + 1];
63            row[j + 1] = (diagonal + usize::from(ca != cb))
64                .min(row[j] + 1)
65                .min(above + 1);
66            diagonal = above;
67        }
68    }
69    row[b.len()]
70}
71
72/// Spelling similarity of two names from 0 to 1: 1 when their tokens are
73/// equal (case, separators and plural endings ignored), else the larger of
74/// the edit-distance ratio and the token overlap of the joined forms.
75#[must_use]
76pub fn name_similarity(wanted: &str, candidate: &str) -> f64 {
77    let wanted_tokens = name_tokens(wanted);
78    let candidate_tokens = name_tokens(candidate);
79    let wanted_joined = wanted_tokens.concat();
80    let candidate_joined = candidate_tokens.concat();
81    if wanted_joined.is_empty() || candidate_joined.is_empty() {
82        return 0.0;
83    }
84    if wanted_joined == candidate_joined {
85        return 1.0;
86    }
87    let longest = wanted_joined
88        .chars()
89        .count()
90        .max(candidate_joined.chars().count());
91    #[expect(
92        clippy::cast_precision_loss,
93        reason = "name lengths are small; the ratio is a score"
94    )]
95    let edit = 1.0 - levenshtein(&wanted_joined, &candidate_joined) as f64 / longest as f64;
96    let wanted_set: BTreeSet<&String> = wanted_tokens.iter().collect();
97    let candidate_set: BTreeSet<&String> = candidate_tokens.iter().collect();
98    #[expect(
99        clippy::cast_precision_loss,
100        reason = "token counts are small; the ratio is a score"
101    )]
102    let overlap = wanted_set.intersection(&candidate_set).count() as f64
103        / wanted_set.union(&candidate_set).count() as f64;
104    edit.max(overlap)
105}
106
107/// The best-scoring candidates for `wanted` (score at least 0.5), best first.
108#[must_use]
109pub fn closest<'a>(
110    wanted: &str,
111    candidates: impl IntoIterator<Item = &'a str>,
112    limit: usize,
113) -> Vec<&'a str> {
114    let mut scored: Vec<(f64, &str)> = candidates
115        .into_iter()
116        .map(|candidate| (name_similarity(wanted, candidate), candidate))
117        .filter(|(score, _)| *score >= 0.5)
118        .collect();
119    scored.sort_by(|a, b| b.0.total_cmp(&a.0).then_with(|| a.1.cmp(b.1)));
120    scored.dedup_by(|a, b| a.1 == b.1);
121    scored
122        .into_iter()
123        .take(limit)
124        .map(|(_, name)| name)
125        .collect()
126}
127
128#[cfg(test)]
129mod tests {
130    use super::*;
131
132    #[test]
133    fn tokens_split_case_and_separators_and_drop_plurals() {
134        assert_eq!(
135            name_tokens("commander_character_ids"),
136            ["commander", "character", "id"]
137        );
138        assert_eq!(name_tokens("parentId"), ["parent", "id"]);
139        assert_eq!(name_tokens("Categories"), ["category"]);
140        assert_eq!(name_tokens("superheroes"), ["superhero"]);
141        assert_eq!(name_tokens("Examination Date"), ["examination", "date"]);
142    }
143
144    #[test]
145    fn names_score_by_spelling() {
146        assert!((name_similarity("patients", "Patient") - 1.0).abs() < f64::EPSILON);
147        assert!((name_similarity("superheroes", "superhero") - 1.0).abs() < f64::EPSILON);
148        assert!(name_similarity("eye_color_id", "eye_colour_id") > 0.8);
149        assert!(name_similarity("heroes", "publisher") < 0.5);
150        assert_eq!(
151            closest("patients", ["Patient", "Laboratory"], 3),
152            ["Patient"]
153        );
154    }
155}
rushdb_types/names.rs

rushdb_types/
names.rs
