1pub fn levenshtein(a: &str, b: &str) -> usize {
12 let a_chars: Vec<char> = a.chars().collect();
13 let b_chars: Vec<char> = b.chars().collect();
14 let m = a_chars.len();
15 let n = b_chars.len();
16
17 if m == 0 {
18 return n;
19 }
20 if n == 0 {
21 return m;
22 }
23
24 let mut prev: Vec<usize> = (0..=n).collect();
25 let mut curr = vec![0; n + 1];
26
27 for i in 1..=m {
28 curr[0] = i;
29 for j in 1..=n {
30 let cost = if a_chars[i - 1] == b_chars[j - 1] {
31 0
32 } else {
33 1
34 };
35 curr[j] = (prev[j] + 1).min(curr[j - 1] + 1).min(prev[j - 1] + cost);
36 }
37 std::mem::swap(&mut prev, &mut curr);
38 }
39
40 prev[n]
41}
42
43pub fn find_similar<'a>(
44 word: &str,
45 candidates: &[&'a str],
46 max_distance: usize,
47) -> Option<&'a str> {
48 let word_lower = word.to_lowercase();
49 let mut best: Option<(&str, usize)> = None;
50
51 for &candidate in candidates {
52 let dist = levenshtein(&word_lower, &candidate.to_lowercase());
53 if dist <= max_distance {
54 match best {
55 None => best = Some((candidate, dist)),
56 Some((_, d)) if dist < d => best = Some((candidate, dist)),
57 _ => {}
58 }
59 }
60 }
61
62 best.map(|(s, _)| s)
63}
64
65pub fn did_you_mean<'c>(
73 word: &str,
74 candidates: impl IntoIterator<Item = &'c str>,
75) -> Option<&'c str> {
76 let lower = word.to_lowercase();
77 let budget = (lower.chars().count() / 3).max(1);
78 let mut best: Option<(usize, &'c str)> = None;
79 for candidate in candidates {
80 if candidate == word {
81 continue;
82 }
83 let distance = typo_distance(&lower, &candidate.to_lowercase());
84 if distance <= budget && best.map_or(true, |(d, _)| distance < d) {
85 best = Some((distance, candidate));
86 }
87 }
88 best.map(|(_, c)| c)
89}
90
91pub fn typo_distance(a: &str, b: &str) -> usize {
95 let a: Vec<char> = a.chars().collect();
96 let b: Vec<char> = b.chars().collect();
97 let (m, n) = (a.len(), b.len());
98 let mut d = vec![vec![0usize; n + 1]; m + 1];
99 for (i, row) in d.iter_mut().enumerate() {
100 row[0] = i;
101 }
102 for j in 0..=n {
103 d[0][j] = j;
104 }
105 for i in 1..=m {
106 for j in 1..=n {
107 let cost = if a[i - 1] == b[j - 1] { 0 } else { 1 };
108 d[i][j] = (d[i - 1][j] + 1)
109 .min(d[i][j - 1] + 1)
110 .min(d[i - 1][j - 1] + cost);
111 if i > 1 && j > 1 && a[i - 1] == b[j - 2] && a[i - 2] == b[j - 1] {
112 d[i][j] = d[i][j].min(d[i - 2][j - 2] + 1);
113 }
114 }
115 }
116 d[m][n]
117}
118
119pub const KNOWN_WORDS: &[&str] = &[
120 "all",
121 "some",
122 "no",
123 "most",
124 "few",
125 "every",
126 "the",
127 "a",
128 "an",
129 "this",
130 "that",
131 "is",
132 "are",
133 "was",
134 "were",
135 "be",
136 "and",
137 "or",
138 "if",
139 "then",
140 "not",
141 "must",
142 "can",
143 "may",
144 "should",
145 "would",
146 "could",
147 "who",
148 "what",
149 "where",
150 "when",
151 "why",
152 "how",
153 "man",
154 "men",
155 "woman",
156 "women",
157 "dog",
158 "cat",
159 "bird",
160 "mortal",
161 "happy",
162 "sad",
163 "tall",
164 "fast",
165 "slow",
166 "loves",
167 "runs",
168 "sees",
169 "knows",
170 "thinks",
171 "logic",
172 "reason",
173 "truth",
174 "false",
175 "John",
176 "Mary",
177 "Socrates",
178 "Aristotle",
179 "to",
180 "by",
181 "with",
182 "from",
183 "for",
184 "in",
185 "on",
186 "at",
187 "himself",
188 "herself",
189 "itself",
190 "themselves",
191 "he",
192 "she",
193 "it",
194 "they",
195 "him",
196 "her",
197 "them",
198];
199
200#[cfg(test)]
201#[path = "../../logicaffeine_tests/unit/logicaffeine_language/suggest/tests.rs"]
202mod tests;