Skip to main content

plato_tile_dedup/
lib.rs

1//! plato-tile-dedup v2 — 4-stage tile similarity detection
2//! From JC1's tile merge/split algorithms paper (1,470 lines)
3//! Stage 1: Exact match (fast reject) — 0.1 weight
4//! Stage 2: Keyword overlap (Jaccard) — 0.3 weight
5//! Stage 3: Embedding cosine (placeholder for real embeddings) — 0.5 weight
6//! Stage 4: Structural similarity (question type classification) — 0.1 weight
7
8use std::collections::HashSet;
9
10/// Similarity detection result with per-stage breakdown
11#[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/// Question type classification for structural similarity
23#[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
37/// Stop words excluded from keyword analysis (JC1's list + common additions)
38const 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
48/// 4-stage similarity detector
49pub 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    /// Run full 4-stage detection pipeline
96    pub fn detect(&self, q1: &str, q2: &str) -> SimilarityResult {
97        let exact = self.stage1_exact(q1, q2);
98
99        // Fast path: exact match
100        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    /// Stage 1: Exact question match (fastest)
148    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    /// Stage 2: Keyword overlap (Jaccard index)
155    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    /// Stage 3: Embedding cosine similarity (bag-of-words approximation)
167    /// In production, replace with real embeddings (all-MiniLM-L6-v2, 22MB)
168    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    /// Stage 4: Structural similarity (question type classification)
175    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    /// Batch detection against multiple candidates
182    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    // Simple character n-gram based embedding (32-dim)
210    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    // Normalize
218    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 // Keywords: {capital, france} ∩ {city, serves, france, capital} = {capital, france} / {capital, france, city, serves} = 0.5
294        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        // keyword ~0.67, embedding ~0.89, structure 1.0
330        // weighted = 0.1*0 + 0.3*0.67 + 0.5*0.89 + 0.1*1.0 = 0 + 0.201 + 0.445 + 0.1 = 0.746
331        // May not meet 0.85 threshold with bag-of-words embeddings
332        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        // Same type + shared keyword "is" → should exceed 0.5
348        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        // First result should be the most similar
376        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        // "thing" and "other" are the only keywords — "other" is >2 chars
406        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}