1const STOP_WORDS: &[&str] = &[
14 "a", "an", "the", "is", "are", "was", "were", "be", "been", "being", "what", "which", "who",
15 "whom", "this", "that", "these", "those", "am", "do", "does", "did", "will", "would", "shall",
16 "should", "can", "could", "may", "might", "must", "need", "dare", "i", "me", "my", "we", "our",
17 "you", "your", "he", "she", "it", "they", "them", "their", "its", "has", "have", "had",
18 "having", "in", "on", "at", "to", "for", "of", "with", "by", "from", "about", "into",
19 "through", "during", "before", "after", "how", "why", "when", "where",
20];
21
22const VS_OPERATORS: &[&str] = &[
24 "vs",
25 "vs.",
26 "versus",
27 "compared",
28 "comparison",
29 "comparing",
30 "against",
31 "differ",
32 "difference",
33 "differences",
34 "between",
35 "better",
36 "worse",
37 "or",
38];
39
40#[derive(Debug, Clone, PartialEq, Eq, Hash)]
42pub struct QueryFingerprint {
43 pub canonical: String,
45 pub simhash: u64,
47 pub is_comparison: bool,
49 pub entities: Vec<String>,
51}
52
53pub fn fingerprint(query: &str) -> QueryFingerprint {
64 let lower = query.to_lowercase();
65
66 let tokens: Vec<String> = lower
68 .split(|c: char| c.is_whitespace() || (c.is_ascii_punctuation() && c != '-'))
69 .filter(|t| !t.is_empty())
70 .map(|t| t.trim_matches('-').to_string())
71 .filter(|t| !t.is_empty())
72 .collect();
73
74 let has_vs = tokens.iter().any(|t| VS_OPERATORS.contains(&t.as_str()));
76 let (is_comparison, entities) = if has_vs {
77 extract_comparison_entities(&tokens)
78 } else {
79 (false, Vec::new())
80 };
81
82 let meaningful: Vec<String> = tokens
84 .iter()
85 .filter(|t| !STOP_WORDS.contains(&t.as_str()))
86 .filter(|t| !VS_OPERATORS.contains(&t.as_str()))
87 .map(|t| lightweight_stem(t))
88 .collect();
89
90 let canonical = if is_comparison && entities.len() >= 2 {
92 let mut sorted_entities = entities.clone();
94 sorted_entities.sort();
95 format!("{} vs", sorted_entities.join(" "))
96 } else {
97 let mut sorted: Vec<String> = meaningful.clone();
99 sorted.sort();
100 sorted.dedup();
101 sorted.join(" ")
102 };
103
104 let simhash = compute_simhash(&meaningful);
105
106 QueryFingerprint {
107 canonical,
108 simhash,
109 is_comparison,
110 entities,
111 }
112}
113
114pub fn is_near_duplicate(a: &QueryFingerprint, b: &QueryFingerprint, threshold: u32) -> bool {
119 if a.canonical == b.canonical {
120 return true;
121 }
122 hamming_distance(a.simhash, b.simhash) <= threshold
123}
124
125fn hamming_distance(a: u64, b: u64) -> u32 {
127 (a ^ b).count_ones()
128}
129
130fn extract_comparison_entities(tokens: &[String]) -> (bool, Vec<String>) {
137 let vs_pos = tokens
139 .iter()
140 .position(|t| VS_OPERATORS.contains(&t.as_str()));
141
142 match vs_pos {
143 Some(pos) => {
144 let left: Vec<String> = tokens[..pos]
145 .iter()
146 .filter(|t| !STOP_WORDS.contains(&t.as_str()))
147 .filter(|t| !VS_OPERATORS.contains(&t.as_str()))
148 .map(|t| lightweight_stem(t))
149 .collect();
150
151 let right: Vec<String> = tokens[pos + 1..]
152 .iter()
153 .filter(|t| !STOP_WORDS.contains(&t.as_str()))
154 .filter(|t| !VS_OPERATORS.contains(&t.as_str()))
155 .map(|t| lightweight_stem(t))
156 .collect();
157
158 if left.is_empty() {
161 let raw_right = &tokens[pos + 1..];
162 let and_pos = raw_right.iter().position(|t| t == "and" || t == "&");
163 if let Some(ap) = and_pos {
164 let entity_a: String = raw_right[..ap]
165 .iter()
166 .filter(|t| !STOP_WORDS.contains(&t.as_str()))
167 .map(|t| lightweight_stem(t))
168 .collect::<Vec<_>>()
169 .join(" ");
170 let entity_b: String = raw_right[ap + 1..]
171 .iter()
172 .filter(|t| !STOP_WORDS.contains(&t.as_str()))
173 .filter(|t| !VS_OPERATORS.contains(&t.as_str()))
174 .map(|t| lightweight_stem(t))
175 .collect::<Vec<_>>()
176 .join(" ");
177 if !entity_a.is_empty() && !entity_b.is_empty() {
178 let mut entities = vec![entity_a, entity_b];
179 entities.sort();
180 return (true, entities);
181 }
182 }
183 if right.len() >= 2 {
185 let mid = right.len() / 2;
186 let entity_a = right[..mid].join(" ");
187 let entity_b = right[mid..].join(" ");
188 let mut entities = vec![entity_a, entity_b];
189 entities.sort();
190 return (true, entities);
191 }
192 return (false, Vec::new());
193 }
194
195 if left.is_empty() || right.is_empty() {
196 return (false, Vec::new());
197 }
198
199 let left_entity = left.join(" ");
200 let right_entity = right.join(" ");
201
202 let mut entities = vec![left_entity, right_entity];
203 entities.sort();
204 (true, entities)
205 }
206 None => (false, Vec::new()),
207 }
208}
209
210fn lightweight_stem(word: &str) -> String {
215 let w = word.to_lowercase();
216
217 if w.len() <= 3 {
219 return w;
220 }
221
222 if w.ends_with("ing") && w.len() > 6 {
224 return w[..w.len() - 3].to_string();
225 }
226
227 if (w.ends_with("tion") || w.ends_with("sion")) && w.len() >= 7 {
229 return w[..w.len() - 4].to_string();
230 }
231
232 if w.ends_with("ed") && !w.ends_with("eed") && !w.ends_with("ied") && w.len() > 4 {
234 return w[..w.len() - 2].to_string();
235 }
236
237 if w.ends_with('s')
239 && !w.ends_with("ss")
240 && !w.ends_with("us")
241 && !w.ends_with("is")
242 && w.len() > 3
243 {
244 return w[..w.len() - 1].to_string();
245 }
246
247 w
248}
249
250fn compute_simhash(tokens: &[String]) -> u64 {
255 if tokens.is_empty() {
256 return 0;
257 }
258
259 let mut weights = [0i32; 64];
260
261 for token in tokens {
262 let hash = fnv1a_64(token);
263 for (i, weight) in weights.iter_mut().enumerate() {
264 if (hash >> i) & 1 == 1 {
265 *weight += 1;
266 } else {
267 *weight -= 1;
268 }
269 }
270 }
271
272 let mut fingerprint: u64 = 0;
273 for (i, &w) in weights.iter().enumerate() {
274 if w > 0 {
275 fingerprint |= 1u64 << i;
276 }
277 }
278 fingerprint
279}
280
281fn fnv1a_64(s: &str) -> u64 {
283 const FNV_OFFSET: u64 = 0xcbf29ce484222325;
284 const FNV_PRIME: u64 = 0x00000100000001B3;
285
286 let mut hash = FNV_OFFSET;
287 for byte in s.bytes() {
288 hash ^= byte as u64;
289 hash = hash.wrapping_mul(FNV_PRIME);
290 }
291 hash
292}
293
294pub fn cache_key(fp: &QueryFingerprint) -> String {
299 format!("qfp:{}", fp.canonical)
300}
301
302#[cfg(test)]
303mod tests {
304 use super::*;
305
306 #[test]
307 fn rust_vs_go_order_invariant() {
308 let a = fingerprint("rust vs go");
309 let b = fingerprint("go vs rust");
310 assert_eq!(a.canonical, b.canonical);
311 assert!(a.is_comparison);
312 assert!(b.is_comparison);
313 }
314
315 #[test]
316 fn comparing_detected_as_vs() {
317 let a = fingerprint("rust vs go");
318 let b = fingerprint("comparing rust and go");
319 assert!(a.is_comparison);
321 assert!(b.is_comparison);
322 assert_eq!(a.entities, b.entities);
324 }
325
326 #[test]
327 fn stop_words_removed() {
328 let a = fingerprint("what is machine learning");
329 let b = fingerprint("machine learning");
330 assert_eq!(a.canonical, b.canonical);
331 }
332
333 #[test]
334 fn case_insensitive() {
335 let a = fingerprint("JavaScript Frameworks");
336 let b = fingerprint("javascript frameworks");
337 assert_eq!(a.canonical, b.canonical);
338 }
339
340 #[test]
341 fn near_duplicate_detection() {
342 let a = fingerprint("best rust web frameworks 2024");
343 let b = fingerprint("top rust web framework 2024");
344 let distance = hamming_distance(a.simhash, b.simhash);
346 assert!(
347 is_near_duplicate(&a, &b, 16),
348 "Expected near-duplicate: a={}, b={}, distance={}",
349 a.canonical,
350 b.canonical,
351 distance,
352 );
353 }
354
355 #[test]
356 fn different_queries_not_duplicates() {
357 let a = fingerprint("rust programming language");
358 let b = fingerprint("cooking italian pasta recipes");
359 assert!(
360 !is_near_duplicate(&a, &b, 5),
361 "Unrelated queries should not be duplicates"
362 );
363 }
364
365 #[test]
366 fn lightweight_stem_strips_suffixes() {
367 assert_eq!(lightweight_stem("programming"), "programm");
368 assert_eq!(lightweight_stem("languages"), "language");
369 assert_eq!(lightweight_stem("compared"), "compar");
370 assert_eq!(lightweight_stem("education"), "educa"); assert_eq!(lightweight_stem("action"), "action"); }
373
374 #[test]
375 fn lightweight_stem_preserves_short_words() {
376 assert_eq!(lightweight_stem("go"), "go");
377 assert_eq!(lightweight_stem("is"), "is");
378 assert_eq!(lightweight_stem("the"), "the");
379 }
380
381 #[test]
382 fn cache_key_deterministic() {
383 let a = cache_key(&fingerprint("rust vs go"));
384 let b = cache_key(&fingerprint("go vs rust"));
385 assert_eq!(a, b, "Same query should produce same cache key");
386 }
387
388 #[test]
389 fn empty_query() {
390 let fp = fingerprint("");
391 assert_eq!(fp.canonical, "");
392 assert!(!fp.is_comparison);
393 }
394
395 #[test]
396 fn simhash_deterministic() {
397 let a = fingerprint("rust programming");
398 let b = fingerprint("rust programming");
399 assert_eq!(a.simhash, b.simhash);
400 }
401}