use std::collections::HashSet;
#[derive(Debug, Clone)]
pub struct SimilarityResult {
pub exact: f64,
pub keyword: f64,
pub embedding: f64,
pub structure: f64,
pub weighted: f64,
pub should_merge: bool,
pub reason: String,
}
#[derive(Debug, Clone, PartialEq)]
pub enum QuestionType {
WhatIs,
HowTo,
Why,
When,
Where,
Who,
Which,
Does,
Can,
Other,
}
const STOPWORDS: &[&str] = &[
"what", "is", "the", "of", "in", "to", "for", "how", "why",
"are", "was", "were", "be", "been", "being", "have", "has", "had",
"do", "does", "did", "will", "would", "could", "should", "may",
"might", "shall", "can", "a", "an", "and", "or", "but", "if",
"it", "its", "this", "that", "these", "those", "on", "at", "by",
"with", "from", "about", "into", "through", "during", "before",
"after", "above", "below", "between", "under", "over",
];
pub struct SimilarityDetector {
merge_threshold: f64,
weights: SimilarityWeights,
}
#[derive(Debug, Clone)]
pub struct SimilarityWeights {
pub exact: f64,
pub keyword: f64,
pub embedding: f64,
pub structure: f64,
}
impl Default for SimilarityWeights {
fn default() -> Self {
Self {
exact: 0.1,
keyword: 0.3,
embedding: 0.5,
structure: 0.1,
}
}
}
impl SimilarityDetector {
pub fn new() -> Self {
Self {
merge_threshold: 0.85,
weights: SimilarityWeights::default(),
}
}
pub fn with_threshold(threshold: f64) -> Self {
Self {
merge_threshold: threshold,
weights: SimilarityWeights::default(),
}
}
pub fn with_weights(weights: SimilarityWeights) -> Self {
Self {
merge_threshold: 0.85,
weights,
}
}
pub fn detect(&self, q1: &str, q2: &str) -> SimilarityResult {
let exact = self.stage1_exact(q1, q2);
if exact == 1.0 {
return SimilarityResult {
exact: 1.0,
keyword: 1.0,
embedding: 1.0,
structure: 1.0,
weighted: 1.0,
should_merge: true,
reason: "exact_match".to_string(),
};
}
let keyword = self.stage2_keyword(q1, q2);
let embedding = self.stage3_embedding(q1, q2);
let structure = self.stage4_structure(q1, q2);
let weighted = self.weights.exact * exact
+ self.weights.keyword * keyword
+ self.weights.embedding * embedding
+ self.weights.structure * structure;
let (should_merge, reason) = if weighted >= self.merge_threshold {
let reason = if keyword > 0.8 {
"high_keyword_overlap"
} else if embedding > 0.85 {
"high_semantic_similarity"
} else if structure == 1.0 && keyword > 0.5 {
"same_type_keyword_overlap"
} else {
"weighted_above_threshold"
};
(true, reason.to_string())
} else {
(false, "below_threshold".to_string())
};
SimilarityResult {
exact,
keyword,
embedding,
structure,
weighted,
should_merge,
reason,
}
}
fn stage1_exact(&self, q1: &str, q2: &str) -> f64 {
let n1 = normalize(q1);
let n2 = normalize(q2);
if n1 == n2 { 1.0 } else { 0.0 }
}
fn stage2_keyword(&self, q1: &str, q2: &str) -> f64 {
let tokens1 = extract_keywords(q1);
let tokens2 = extract_keywords(q2);
if tokens1.is_empty() || tokens2.is_empty() {
return 0.0;
}
let intersection = tokens1.intersection(&tokens2).count();
let union = tokens1.union(&tokens2).count();
intersection as f64 / union as f64
}
fn stage3_embedding(&self, q1: &str, q2: &str) -> f64 {
let v1 = bag_of_words(q1);
let v2 = bag_of_words(q2);
cosine_similarity(&v1, &v2)
}
fn stage4_structure(&self, q1: &str, q2: &str) -> f64 {
let t1 = classify_question(q1);
let t2 = classify_question(q2);
if t1 == t2 { 1.0 } else { 0.5 }
}
pub fn find_candidates<'a>(&self, query: &str, candidates: &'a [&str]) -> Vec<(usize, SimilarityResult)> {
let mut results: Vec<(usize, SimilarityResult)> = candidates
.iter()
.enumerate()
.map(|(i, c)| (i, self.detect(query, c)))
.filter(|(_, r)| r.should_merge)
.collect();
results.sort_by(|a, b| b.1.weighted.partial_cmp(&a.1.weighted).unwrap());
results
}
}
fn normalize(s: &str) -> String {
let lowered: String = s.to_lowercase();
lowered.split_whitespace().collect::<Vec<_>>().join(" ")
}
fn extract_keywords(text: &str) -> HashSet<String> {
let stop_set: HashSet<String> = STOPWORDS.iter().map(|s| s.to_string()).collect();
text.to_lowercase()
.split(|c: char| !c.is_alphanumeric())
.filter(|w| w.len() >= 3 && !stop_set.contains(*w))
.map(String::from)
.collect()
}
fn bag_of_words(text: &str) -> Vec<f64> {
let n1 = text.to_lowercase();
let mut v = vec![0.0; 32];
let bytes = n1.as_bytes();
for w in bytes.windows(3) {
let idx = ((w[0] as usize) * 31 + (w[1] as usize) * 7 + (w[2] as usize)) % 32;
v[idx] += 1.0;
}
let mag: f64 = v.iter().map(|x| x * x).sum::<f64>().sqrt();
if mag > 0.0 {
for x in v.iter_mut() {
*x /= mag;
}
}
v
}
fn cosine_similarity(a: &[f64], b: &[f64]) -> f64 {
if a.len() != b.len() { return 0.0; }
let dot: f64 = a.iter().zip(b.iter()).map(|(x, y)| x * y).sum();
let mag_a: f64 = a.iter().map(|x| x * x).sum::<f64>().sqrt();
let mag_b: f64 = b.iter().map(|x| x * x).sum::<f64>().sqrt();
if mag_a == 0.0 || mag_b == 0.0 { return 0.0; }
dot / (mag_a * mag_b)
}
fn classify_question(q: &str) -> QuestionType {
let lower: String = q.to_lowercase();
let lower = lower.trim();
if lower.starts_with("what is") || lower.starts_with("what are") || lower.starts_with("what's") {
QuestionType::WhatIs
} else if lower.starts_with("how do") || lower.starts_with("how does") || lower.starts_with("how can") {
QuestionType::HowTo
} else if lower.starts_with("why") {
QuestionType::Why
} else if lower.starts_with("when") {
QuestionType::When
} else if lower.starts_with("where") {
QuestionType::Where
} else if lower.starts_with("who") {
QuestionType::Who
} else if lower.starts_with("which") {
QuestionType::Which
} else if lower.starts_with("does") || lower.starts_with("do") {
QuestionType::Does
} else if lower.starts_with("can") {
QuestionType::Can
} else {
QuestionType::Other
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_stage1_exact_match() {
let det = SimilarityDetector::new();
let r = det.detect("What is the capital of France?", "What is the capital of France?");
assert_eq!(r.exact, 1.0);
assert!(r.should_merge);
assert_eq!(r.reason, "exact_match");
}
#[test]
fn test_stage1_case_insensitive() {
let det = SimilarityDetector::new();
let r = det.detect("What is Rust?", "what is rust?");
assert_eq!(r.exact, 1.0);
}
#[test]
fn test_stage1_no_match() {
let det = SimilarityDetector::new();
let r = det.detect("What is Python?", "How to write Rust?");
assert_eq!(r.exact, 0.0);
}
#[test]
fn test_stage2_keyword_overlap() {
let det = SimilarityDetector::new();
let r = det.detect("What is the capital of France?", "Which city serves as France's capital?");
assert!(r.keyword >= 0.4, "keyword overlap should be >= 0.4, got {}", r.keyword);
}
#[test]
fn test_stage2_no_keywords() {
let det = SimilarityDetector::new();
let r = det.detect("is the", "are the");
assert_eq!(r.keyword, 0.0);
}
#[test]
fn test_stage3_embedding_similarity() {
let det = SimilarityDetector::new();
let r = det.detect("How to parse JSON in Rust?", "Parsing JSON data using Rust");
assert!(r.embedding > 0.3, "embedding should be > 0.3 for similar queries, got {}", r.embedding);
}
#[test]
fn test_stage4_same_type() {
let det = SimilarityDetector::new();
let r = det.detect("What is Rust?", "What is Python?");
assert_eq!(r.structure, 1.0);
}
#[test]
fn test_stage4_different_type() {
let det = SimilarityDetector::new();
let r = det.detect("What is Rust?", "How to learn Rust?");
assert_eq!(r.structure, 0.5);
}
#[test]
fn test_merge_decision_high_similarity() {
let det = SimilarityDetector::new();
let r = det.detect("What is the capital city of France?", "Which city serves as France's capital?");
assert!(r.weighted > 0.3);
}
#[test]
fn test_merge_decision_low_similarity() {
let det = SimilarityDetector::new();
let r = det.detect("How to bake bread?", "Rust ownership model explained");
assert!(!r.should_merge);
assert!(r.weighted < 0.5);
}
#[test]
fn test_custom_threshold() {
let det = SimilarityDetector::with_threshold(0.5);
let r = det.detect("What is Rust?", "What is Python?");
assert!(r.weighted > 0.0);
}
#[test]
fn test_custom_weights() {
let weights = SimilarityWeights {
exact: 0.0,
keyword: 0.7,
embedding: 0.3,
structure: 0.0,
};
let det = SimilarityDetector::with_weights(weights);
let r = det.detect("What is the capital of France?", "Which city serves as France's capital?");
assert!(r.keyword >= 0.3);
}
#[test]
fn test_find_candidates() {
let det = SimilarityDetector::with_threshold(0.3);
let candidates = [
"How to parse JSON in Rust?",
"Rust JSON parsing guide",
"Baking bread recipe",
"What is the weather?",
];
let results = det.find_candidates("How do I parse JSON in Rust?", &candidates);
assert!(results.len() >= 1);
assert!(results[0].1.weighted >= results.last().unwrap().1.weighted);
}
#[test]
fn test_find_candidates_no_matches() {
let det = SimilarityDetector::new();
let candidates = ["Baking bread recipe", "Weather forecast today"];
let results = det.find_candidates("Quantum physics explained", &candidates);
assert!(results.is_empty());
}
#[test]
fn test_question_classification() {
assert_eq!(classify_question("What is Rust?"), QuestionType::WhatIs);
assert_eq!(classify_question("How do I learn Python?"), QuestionType::HowTo);
assert_eq!(classify_question("Why does this fail?"), QuestionType::Why);
assert_eq!(classify_question("When was this written?"), QuestionType::When);
assert_eq!(classify_question("Where is the file?"), QuestionType::Where);
assert_eq!(classify_question("Who wrote this?"), QuestionType::Who);
assert_eq!(classify_question("Which option is best?"), QuestionType::Which);
assert_eq!(classify_question("Does this compile?"), QuestionType::Does);
assert_eq!(classify_question("Can I use this?"), QuestionType::Can);
assert_eq!(classify_question("Hello world"), QuestionType::Other);
}
#[test]
fn test_stopwords_filtered() {
let det = SimilarityDetector::new();
let r = det.detect("What is the thing?", "What is the other thing?");
assert!(r.keyword > 0.0);
}
#[test]
fn test_empty_queries() {
let det = SimilarityDetector::new();
let r = det.detect("", "");
assert_eq!(r.exact, 1.0);
}
#[test]
fn test_result_breakdown_fields() {
let det = SimilarityDetector::new();
let r = det.detect("What is Rust?", "How to write Rust?");
assert!(r.exact >= 0.0 && r.exact <= 1.0);
assert!(r.keyword >= 0.0 && r.keyword <= 1.0);
assert!(r.embedding >= 0.0 && r.embedding <= 1.0);
assert!(r.structure >= 0.0 && r.structure <= 1.0);
assert!(r.weighted >= 0.0 && r.weighted <= 1.0);
}
}