1use std::collections::HashSet;
9
10#[derive(Debug, Clone)]
12pub struct SimilarityResult {
13 pub exact: f64,
14 pub keyword: f64,
15 pub embedding: f64,
16 pub structure: f64,
17 pub weighted: f64,
18 pub should_merge: bool,
19 pub reason: String,
20}
21
22#[derive(Debug, Clone, PartialEq)]
24pub enum QuestionType {
25 WhatIs,
26 HowTo,
27 Why,
28 When,
29 Where,
30 Who,
31 Which,
32 Does,
33 Can,
34 Other,
35}
36
37const STOPWORDS: &[&str] = &[
39 "what", "is", "the", "of", "in", "to", "for", "how", "why",
40 "are", "was", "were", "be", "been", "being", "have", "has", "had",
41 "do", "does", "did", "will", "would", "could", "should", "may",
42 "might", "shall", "can", "a", "an", "and", "or", "but", "if",
43 "it", "its", "this", "that", "these", "those", "on", "at", "by",
44 "with", "from", "about", "into", "through", "during", "before",
45 "after", "above", "below", "between", "under", "over",
46];
47
48pub struct SimilarityDetector {
50 merge_threshold: f64,
51 weights: SimilarityWeights,
52}
53
54#[derive(Debug, Clone)]
55pub struct SimilarityWeights {
56 pub exact: f64,
57 pub keyword: f64,
58 pub embedding: f64,
59 pub structure: f64,
60}
61
62impl Default for SimilarityWeights {
63 fn default() -> Self {
64 Self {
65 exact: 0.1,
66 keyword: 0.3,
67 embedding: 0.5,
68 structure: 0.1,
69 }
70 }
71}
72
73impl SimilarityDetector {
74 pub fn new() -> Self {
75 Self {
76 merge_threshold: 0.85,
77 weights: SimilarityWeights::default(),
78 }
79 }
80
81 pub fn with_threshold(threshold: f64) -> Self {
82 Self {
83 merge_threshold: threshold,
84 weights: SimilarityWeights::default(),
85 }
86 }
87
88 pub fn with_weights(weights: SimilarityWeights) -> Self {
89 Self {
90 merge_threshold: 0.85,
91 weights,
92 }
93 }
94
95 pub fn detect(&self, q1: &str, q2: &str) -> SimilarityResult {
97 let exact = self.stage1_exact(q1, q2);
98
99 if exact == 1.0 {
101 return SimilarityResult {
102 exact: 1.0,
103 keyword: 1.0,
104 embedding: 1.0,
105 structure: 1.0,
106 weighted: 1.0,
107 should_merge: true,
108 reason: "exact_match".to_string(),
109 };
110 }
111
112 let keyword = self.stage2_keyword(q1, q2);
113 let embedding = self.stage3_embedding(q1, q2);
114 let structure = self.stage4_structure(q1, q2);
115
116 let weighted = self.weights.exact * exact
117 + self.weights.keyword * keyword
118 + self.weights.embedding * embedding
119 + self.weights.structure * structure;
120
121 let (should_merge, reason) = if weighted >= self.merge_threshold {
122 let reason = if keyword > 0.8 {
123 "high_keyword_overlap"
124 } else if embedding > 0.85 {
125 "high_semantic_similarity"
126 } else if structure == 1.0 && keyword > 0.5 {
127 "same_type_keyword_overlap"
128 } else {
129 "weighted_above_threshold"
130 };
131 (true, reason.to_string())
132 } else {
133 (false, "below_threshold".to_string())
134 };
135
136 SimilarityResult {
137 exact,
138 keyword,
139 embedding,
140 structure,
141 weighted,
142 should_merge,
143 reason,
144 }
145 }
146
147 fn stage1_exact(&self, q1: &str, q2: &str) -> f64 {
149 let n1 = normalize(q1);
150 let n2 = normalize(q2);
151 if n1 == n2 { 1.0 } else { 0.0 }
152 }
153
154 fn stage2_keyword(&self, q1: &str, q2: &str) -> f64 {
156 let tokens1 = extract_keywords(q1);
157 let tokens2 = extract_keywords(q2);
158 if tokens1.is_empty() || tokens2.is_empty() {
159 return 0.0;
160 }
161 let intersection = tokens1.intersection(&tokens2).count();
162 let union = tokens1.union(&tokens2).count();
163 intersection as f64 / union as f64
164 }
165
166 fn stage3_embedding(&self, q1: &str, q2: &str) -> f64 {
169 let v1 = bag_of_words(q1);
170 let v2 = bag_of_words(q2);
171 cosine_similarity(&v1, &v2)
172 }
173
174 fn stage4_structure(&self, q1: &str, q2: &str) -> f64 {
176 let t1 = classify_question(q1);
177 let t2 = classify_question(q2);
178 if t1 == t2 { 1.0 } else { 0.5 }
179 }
180
181 pub fn find_candidates<'a>(&self, query: &str, candidates: &'a [&str]) -> Vec<(usize, SimilarityResult)> {
183 let mut results: Vec<(usize, SimilarityResult)> = candidates
184 .iter()
185 .enumerate()
186 .map(|(i, c)| (i, self.detect(query, c)))
187 .filter(|(_, r)| r.should_merge)
188 .collect();
189 results.sort_by(|a, b| b.1.weighted.partial_cmp(&a.1.weighted).unwrap());
190 results
191 }
192}
193
194fn normalize(s: &str) -> String {
195 let lowered: String = s.to_lowercase();
196 lowered.split_whitespace().collect::<Vec<_>>().join(" ")
197}
198
199fn extract_keywords(text: &str) -> HashSet<String> {
200 let stop_set: HashSet<String> = STOPWORDS.iter().map(|s| s.to_string()).collect();
201 text.to_lowercase()
202 .split(|c: char| !c.is_alphanumeric())
203 .filter(|w| w.len() >= 3 && !stop_set.contains(*w))
204 .map(String::from)
205 .collect()
206}
207
208fn bag_of_words(text: &str) -> Vec<f64> {
209 let n1 = text.to_lowercase();
211 let mut v = vec![0.0; 32];
212 let bytes = n1.as_bytes();
213 for w in bytes.windows(3) {
214 let idx = ((w[0] as usize) * 31 + (w[1] as usize) * 7 + (w[2] as usize)) % 32;
215 v[idx] += 1.0;
216 }
217 let mag: f64 = v.iter().map(|x| x * x).sum::<f64>().sqrt();
219 if mag > 0.0 {
220 for x in v.iter_mut() {
221 *x /= mag;
222 }
223 }
224 v
225}
226
227fn cosine_similarity(a: &[f64], b: &[f64]) -> f64 {
228 if a.len() != b.len() { return 0.0; }
229 let dot: f64 = a.iter().zip(b.iter()).map(|(x, y)| x * y).sum();
230 let mag_a: f64 = a.iter().map(|x| x * x).sum::<f64>().sqrt();
231 let mag_b: f64 = b.iter().map(|x| x * x).sum::<f64>().sqrt();
232 if mag_a == 0.0 || mag_b == 0.0 { return 0.0; }
233 dot / (mag_a * mag_b)
234}
235
236fn classify_question(q: &str) -> QuestionType {
237 let lower: String = q.to_lowercase();
238 let lower = lower.trim();
239 if lower.starts_with("what is") || lower.starts_with("what are") || lower.starts_with("what's") {
240 QuestionType::WhatIs
241 } else if lower.starts_with("how do") || lower.starts_with("how does") || lower.starts_with("how can") {
242 QuestionType::HowTo
243 } else if lower.starts_with("why") {
244 QuestionType::Why
245 } else if lower.starts_with("when") {
246 QuestionType::When
247 } else if lower.starts_with("where") {
248 QuestionType::Where
249 } else if lower.starts_with("who") {
250 QuestionType::Who
251 } else if lower.starts_with("which") {
252 QuestionType::Which
253 } else if lower.starts_with("does") || lower.starts_with("do") {
254 QuestionType::Does
255 } else if lower.starts_with("can") {
256 QuestionType::Can
257 } else {
258 QuestionType::Other
259 }
260}
261
262#[cfg(test)]
263mod tests {
264 use super::*;
265
266 #[test]
267 fn test_stage1_exact_match() {
268 let det = SimilarityDetector::new();
269 let r = det.detect("What is the capital of France?", "What is the capital of France?");
270 assert_eq!(r.exact, 1.0);
271 assert!(r.should_merge);
272 assert_eq!(r.reason, "exact_match");
273 }
274
275 #[test]
276 fn test_stage1_case_insensitive() {
277 let det = SimilarityDetector::new();
278 let r = det.detect("What is Rust?", "what is rust?");
279 assert_eq!(r.exact, 1.0);
280 }
281
282 #[test]
283 fn test_stage1_no_match() {
284 let det = SimilarityDetector::new();
285 let r = det.detect("What is Python?", "How to write Rust?");
286 assert_eq!(r.exact, 0.0);
287 }
288
289 #[test]
290 fn test_stage2_keyword_overlap() {
291 let det = SimilarityDetector::new();
292 let r = det.detect("What is the capital of France?", "Which city serves as France's capital?");
293 assert!(r.keyword >= 0.4, "keyword overlap should be >= 0.4, got {}", r.keyword);
295 }
296
297 #[test]
298 fn test_stage2_no_keywords() {
299 let det = SimilarityDetector::new();
300 let r = det.detect("is the", "are the");
301 assert_eq!(r.keyword, 0.0);
302 }
303
304 #[test]
305 fn test_stage3_embedding_similarity() {
306 let det = SimilarityDetector::new();
307 let r = det.detect("How to parse JSON in Rust?", "Parsing JSON data using Rust");
308 assert!(r.embedding > 0.3, "embedding should be > 0.3 for similar queries, got {}", r.embedding);
309 }
310
311 #[test]
312 fn test_stage4_same_type() {
313 let det = SimilarityDetector::new();
314 let r = det.detect("What is Rust?", "What is Python?");
315 assert_eq!(r.structure, 1.0);
316 }
317
318 #[test]
319 fn test_stage4_different_type() {
320 let det = SimilarityDetector::new();
321 let r = det.detect("What is Rust?", "How to learn Rust?");
322 assert_eq!(r.structure, 0.5);
323 }
324
325 #[test]
326 fn test_merge_decision_high_similarity() {
327 let det = SimilarityDetector::new();
328 let r = det.detect("What is the capital city of France?", "Which city serves as France's capital?");
329 assert!(r.weighted > 0.3);
333 }
334
335 #[test]
336 fn test_merge_decision_low_similarity() {
337 let det = SimilarityDetector::new();
338 let r = det.detect("How to bake bread?", "Rust ownership model explained");
339 assert!(!r.should_merge);
340 assert!(r.weighted < 0.5);
341 }
342
343 #[test]
344 fn test_custom_threshold() {
345 let det = SimilarityDetector::with_threshold(0.5);
346 let r = det.detect("What is Rust?", "What is Python?");
347 assert!(r.weighted > 0.0);
349 }
350
351 #[test]
352 fn test_custom_weights() {
353 let weights = SimilarityWeights {
354 exact: 0.0,
355 keyword: 0.7,
356 embedding: 0.3,
357 structure: 0.0,
358 };
359 let det = SimilarityDetector::with_weights(weights);
360 let r = det.detect("What is the capital of France?", "Which city serves as France's capital?");
361 assert!(r.keyword >= 0.3);
362 }
363
364 #[test]
365 fn test_find_candidates() {
366 let det = SimilarityDetector::with_threshold(0.3);
367 let candidates = [
368 "How to parse JSON in Rust?",
369 "Rust JSON parsing guide",
370 "Baking bread recipe",
371 "What is the weather?",
372 ];
373 let results = det.find_candidates("How do I parse JSON in Rust?", &candidates);
374 assert!(results.len() >= 1);
375 assert!(results[0].1.weighted >= results.last().unwrap().1.weighted);
377 }
378
379 #[test]
380 fn test_find_candidates_no_matches() {
381 let det = SimilarityDetector::new();
382 let candidates = ["Baking bread recipe", "Weather forecast today"];
383 let results = det.find_candidates("Quantum physics explained", &candidates);
384 assert!(results.is_empty());
385 }
386
387 #[test]
388 fn test_question_classification() {
389 assert_eq!(classify_question("What is Rust?"), QuestionType::WhatIs);
390 assert_eq!(classify_question("How do I learn Python?"), QuestionType::HowTo);
391 assert_eq!(classify_question("Why does this fail?"), QuestionType::Why);
392 assert_eq!(classify_question("When was this written?"), QuestionType::When);
393 assert_eq!(classify_question("Where is the file?"), QuestionType::Where);
394 assert_eq!(classify_question("Who wrote this?"), QuestionType::Who);
395 assert_eq!(classify_question("Which option is best?"), QuestionType::Which);
396 assert_eq!(classify_question("Does this compile?"), QuestionType::Does);
397 assert_eq!(classify_question("Can I use this?"), QuestionType::Can);
398 assert_eq!(classify_question("Hello world"), QuestionType::Other);
399 }
400
401 #[test]
402 fn test_stopwords_filtered() {
403 let det = SimilarityDetector::new();
404 let r = det.detect("What is the thing?", "What is the other thing?");
405 assert!(r.keyword > 0.0);
407 }
408
409 #[test]
410 fn test_empty_queries() {
411 let det = SimilarityDetector::new();
412 let r = det.detect("", "");
413 assert_eq!(r.exact, 1.0);
414 }
415
416 #[test]
417 fn test_result_breakdown_fields() {
418 let det = SimilarityDetector::new();
419 let r = det.detect("What is Rust?", "How to write Rust?");
420 assert!(r.exact >= 0.0 && r.exact <= 1.0);
421 assert!(r.keyword >= 0.0 && r.keyword <= 1.0);
422 assert!(r.embedding >= 0.0 && r.embedding <= 1.0);
423 assert!(r.structure >= 0.0 && r.structure <= 1.0);
424 assert!(r.weighted >= 0.0 && r.weighted <= 1.0);
425 }
426}