1use std::collections::HashMap;
5
6const K1: f32 = 1.2;
7const B: f32 = 0.75;
8
9const STOP: &[&str] = &[
10 "a", "an", "and", "are", "as", "at", "be", "by", "can", "do", "does", "for", "from", "get", "how", "i", "if", "in", "is", "it", "me", "my", "of", "on",
11 "or", "should", "that", "the", "this", "to", "using", "what", "when", "where", "which", "with", "you", "your", "we", "our", "way", "want", "need", "there",
12 "their", "into", "vs", "versus", "about", "example", "show",
13];
14
15pub fn is_stop(w: &str) -> bool {
17 STOP.contains(&w)
18}
19
20pub fn stem(t: &str) -> String {
24 let mut s = stem0(t);
25 let n = s.len();
26 if s.is_ascii() && n > 8 && (s.ends_with("ability") || s.ends_with("ibility")) {
27 s.replace_range(n - 5.., "l");
28 } else if s.is_ascii() && n > 7 && s.ends_with("ation") {
29 s.truncate(n - 3);
30 }
31 if s.len() > 4 && s.ends_with('e') && s.is_ascii() {
32 s.pop();
33 }
34 s
35}
36
37fn stem0(t: &str) -> String {
38 let n = t.len();
39 if n <= 3 || !t.is_ascii() {
40 return t.to_string();
41 }
42 if n > 5 && t.ends_with("ies") {
43 return format!("{}y", &t[..n - 3]);
44 }
45 if n > 4 && (t.ends_with("sses") || t.ends_with("shes") || t.ends_with("ches") || t.ends_with("xes")) {
46 return t[..n - 2].to_string();
47 }
48 if t.ends_with('s') && !t.ends_with("ss") && !t.ends_with("us") && !t.ends_with("is") {
49 return t[..n - 1].to_string();
50 }
51 if n > 6 && t.ends_with("ing") {
52 return t[..n - 3].to_string();
53 }
54 if n > 5 && t.ends_with("ed") && !t.ends_with("eed") {
55 return t[..n - 2].to_string();
56 }
57 t.to_string()
58}
59
60pub fn terms(text: &str) -> Vec<String> {
62 crate::tokenize::tokenize(text).into_iter().map(|t| stem(&t)).collect()
63}
64
65pub fn query_terms(q: &str) -> Vec<String> {
67 let mut v: Vec<String> = crate::tokenize::tokenize(q)
68 .into_iter()
69 .filter(|t| !STOP.contains(&t.as_str()))
70 .map(|t| stem(&t))
71 .collect();
72 v.sort();
73 v.dedup();
74 v
75}
76
77const SYNONYMS: &[(&str, &[&str])] = &[
80 ("dict", &["dictionary", "dump", "mapping"]),
81 ("dictionary", &["dict"]),
82 ("convert", &["dump", "serializ", "transform", "cast"]),
83 ("serializ", &["dump", "json", "encod"]),
84 ("deserializ", &["pars", "load", "decod", "validat"]),
85 ("pars", &["validat", "decod", "load"]),
86 ("validat", &["pars", "check"]),
87 ("remov", &["delet", "drop"]),
88 ("delet", &["remov", "drop"]),
89 ("creat", &["new", "build", "mak", "init"]),
90 ("async", &["await", "promis", "futur"]),
91 ("error", &["except", "err", "fail"]),
92 ("except", &["error"]),
93 ("config", &["setting", "option", "configur"]),
94 ("setting", &["config"]),
95 ("option", &["config", "param"]),
96 ("fetch", &["request", "get"]),
97 ("request", &["fetch"]),
98 ("redirect", &["navigat"]),
99 ("navigat", &["redirect", "router"]),
100 ("spawn", &["task"]),
101 ("finish", &["complet", "done"]),
102 ("complet", &["finish", "done"]),
103 ("first", &["race", "select"]),
104 ("route", &["router", "path"]),
105 ("middleware", &["layer"]),
106 ("layer", &["middleware"]),
107 ("state", &["extension"]),
108 ("parameter", &["param", "arg", "argument"]),
109 ("param", &["parameter"]),
110 ("argument", &["arg", "param"]),
111 ("arg", &["argument"]),
112 ("javascript", &["js"]),
113 ("js", &["javascript"]),
114 ("typescript", &["ts"]),
115 ("ts", &["typescript"]),
116 ("databas", &["db"]),
117 ("db", &["databas"]),
118 ("unknown", &["extra", "strict"]),
119 ("extra", &["unknown"]),
120];
121
122pub fn expand(terms: &[String]) -> Vec<(String, f32)> {
124 let mut out: Vec<(String, f32)> = terms.iter().map(|t| (t.clone(), 1.0)).collect();
125 for t in terms {
126 if let Some((_, syns)) = SYNONYMS.iter().find(|(k, _)| k == t) {
127 for s in *syns {
128 if !out.iter().any(|(x, _)| x == s) {
129 out.push((s.to_string(), 0.35));
130 }
131 }
132 }
133 }
134 out
135}
136
137pub fn tf(parts: &[(&str, u16)]) -> (Vec<(String, u16)>, u32) {
139 let mut m: HashMap<String, u16> = HashMap::new();
140 let mut len = 0u32;
141 for (text, w) in parts {
142 let text = if text.len() > 16 * 1024 {
144 &text[..mcp_kit::search::floor_char(text, 16 * 1024)]
145 } else {
146 text
147 };
148 for t in terms(text) {
149 let e = m.entry(t).or_insert(0);
150 *e = e.saturating_add(*w);
151 len += *w as u32;
152 }
153 }
154 let mut v: Vec<(String, u16)> = m.into_iter().collect();
155 v.sort();
156 (v, len.max(1))
157}
158
159#[derive(Default)]
160pub struct Bm25 {
161 postings: HashMap<String, Vec<(u32, u16)>>,
162 lens: Vec<u32>,
163 avg: f32,
164}
165
166pub struct Hit {
167 pub doc: u32,
168 pub score: f32,
169 pub matched: usize,
171}
172
173impl Bm25 {
174 pub fn build<'a>(docs: impl Iterator<Item = (&'a [(String, u16)], u32)>) -> Bm25 {
175 let mut postings: HashMap<String, Vec<(u32, u16)>> = HashMap::new();
176 let mut lens = Vec::new();
177 let mut total = 0u64;
178 for (terms, len) in docs {
179 let id = lens.len() as u32;
180 lens.push(len);
181 total += len as u64;
182 for (t, f) in terms {
183 match postings.get_mut(t) {
184 Some(v) => v.push((id, *f)),
185 None => {
186 postings.insert(t.clone(), vec![(id, *f)]);
187 }
188 }
189 }
190 }
191 let avg = if lens.is_empty() { 1.0 } else { total as f32 / lens.len() as f32 };
192 Bm25 { postings, lens, avg }
193 }
194
195 pub fn len(&self) -> usize {
196 self.lens.len()
197 }
198
199 pub fn is_empty(&self) -> bool {
200 self.lens.is_empty()
201 }
202
203 pub fn df(&self, term: &str) -> usize {
205 self.postings.get(term).map_or(0, |p| p.len())
206 }
207
208 pub fn contains(&self, term: &str) -> bool {
209 self.postings.contains_key(term)
210 }
211
212 pub fn search(&self, qterms: &[String]) -> Vec<Hit> {
213 let weighted: Vec<(String, f32)> = qterms.iter().map(|t| (t.clone(), 1.0)).collect();
214 self.search_weighted(&weighted)
215 }
216
217 pub fn search_weighted(&self, qterms: &[(String, f32)]) -> Vec<Hit> {
219 let n = self.lens.len() as f32;
220 let mut scores: HashMap<u32, (f32, usize)> = HashMap::new();
221 for (t, w) in qterms {
222 let Some(list) = self.postings.get(t) else { continue };
223 let df = list.len() as f32;
224 let idf = ((n - df + 0.5) / (df + 0.5) + 1.0).ln();
225 for &(d, tf) in list {
226 let tf = tf as f32;
227 let norm = tf * (K1 + 1.0) / (tf + K1 * (1.0 - B + B * self.lens[d as usize] as f32 / self.avg));
228 let e = scores.entry(d).or_insert((0.0, 0));
229 e.0 += idf * norm * w;
230 if *w >= 1.0 {
231 e.1 += 1;
232 }
233 }
234 }
235 let q = qterms.iter().filter(|(_, w)| *w >= 1.0).count().max(1) as f32;
236 let mut hits: Vec<Hit> = scores
237 .into_iter()
238 .map(|(doc, (s, m))| Hit {
239 doc,
240 score: s * (0.4 + m as f32 / q),
241 matched: m,
242 })
243 .collect();
244 hits.sort_by(|a, b| b.score.partial_cmp(&a.score).unwrap_or(std::cmp::Ordering::Equal).then(a.doc.cmp(&b.doc)));
245 hits
246 }
247}
248
249#[cfg(test)]
250mod tests {
251 use super::*;
252 #[test]
253 fn stems_and_ranks() {
254 assert_eq!(stem("schemas"), "schema");
255 assert_eq!(stem("validating"), "validat");
256 assert_eq!(stem("validated"), "validat");
257 assert_eq!(stem("validate"), "validat");
258 assert_eq!(stem("parses"), stem("parse"));
259 assert_eq!(stem("class"), "class");
260 assert_eq!(stem("immutability"), stem("immutable"));
261 assert_eq!(stem("validation"), stem("validate"));
262 assert_eq!(stem("validations"), stem("validated"));
263 let a = tf(&[("object schema strict", 1)]);
264 let b = tf(&[("string schema", 1)]);
265 let idx = Bm25::build([(a.0.as_slice(), a.1), (b.0.as_slice(), b.1)].into_iter());
266 let hits = idx.search(&query_terms("how do I make strict object schemas"));
267 assert_eq!(hits[0].doc, 0);
268 }
269}